(1) 기본 원리
 
 

 

■ 지역성의 원리(principle of the locality)
 
 
 - 명령어 또는 데이터를 수행하기 위하여 CPU가 주기억장치를 접근할 때는 프로그램 루프, 서브루틴, 테이블 또는 배열 구   조의 데이터등으로 인하여 인접한 위치에 있는 명령어나 데이터들에 집중되는 경향이 있는데, 이와 같은 특성을 지역성   의 원리라고 한다.
- CPU보다 느린 주기억장치 접근 속도를 높이기 위하여 지역성의 원리를 고려하여 중앙 처리 장치와 주 기억 장치 사이에   작고 빠른 기억 장치를 설치하고 이곳으로 반복적으로 참조될 프로그램 및 데이터의 불록을 옮겨 놓은 후 이곳에서 호출   하여 실행시킴으로써 기억 장치 접근 시간을 단축할 수 있도록 만든 것이 캐시 기억 장치이다. 
            
  
 [그림]  캐시와 주 기억 장치
 
 
           (2) 기본 동작
 
 
            - 동작 순서
 
 
           ① 중앙 처리 장치가 주 기억 장치로부터 한 워드를 읽으려고 할 때는 먼저 그 워드가 캐시에 있는 지를 검사한다.
 
 
           ② 만약에 있으면 그 워드가 중앙 처리 장치로 전달되고 그렇지 않으면 그 워드가 포함된 한 불록이
 
 
           주 기억 장치로부터 캐시로 읽혀지고 동시에 중앙 처리 장치로 전달된다.
 
 
            - 적중(Hit)
 
 
           중앙 처리 장치가 주 기억 장치를 참조할 때 캐시에서 참조하고자 하는 워드를 찾을 경우
 
 
            - 실패(Miss)
 
 
           원하는 워드를 캐시에서 못 찾을 경우
 
 
            - 적중률(hit ratio)
 
 
           적중률   = (적중의 수) / (주 기억 장치 접근의 총수) = (적중의 수) / (적중의 수 + 실패의 수)
 
 
           보통 0.9 이상의 값을 가지고 있다.
 
 
 
 
     5-5-2  캐시 설계상의 주요 요소들 
 
 

캐시의 크기   불록의 크기   사상 함수   교체 알고리즘   기록 동작

1 k ∼ 128 k 워드 4 ∼ 8 워드 직접 사상(direct mapping) 연관 사상(associative mapping) 집합 연관 사상(set associative mapping) 최소 최근 사용(LRU) 선입 선출(FIFO) 최소 사용 빈도(LFU) 랜덤(random) 동시 기록(write through) 후 기록(write back) 단일 기록(write once)

               

 

 

 

 

 

 

 

 

 

 

 

  [표]  캐시 설계상의 주요 요소들
 
 
           (1) 캐시의 크기
 
 
            연구 결과에 의하면 1 k ∼ 128 k 워드가 최적
 
 
           (2) 사상 함수(mapping function)
 
 
            주 기억 장치의 주소를 캐시 기억 장치 내의 적당한 워드로 사상(mapping)하는 방법
 
 
            ① 직접 사상(direct mapping)
 
 
            - 구현하기 가장 간단한 방법
 
 
            - 주 기억 장치의 각 불록은 그 불록에 대해서 정해진 캐시 인덱스에만 저장          
 
 
            - 캐시 기억 장치에 2k개의 워드가 있고 주 기억 장치에 2n개의 워드가 있다면 기억 장치 주소는 n 비트로서
             (n-k) 비트의 태그 필드와 k 비트의 인덱스 필드로 구성            
 
 
            - k 비트의 인덱스 필드가 캐시의 주소로 되고, 캐시의 각 워드도 태그와 데이터로 구성된다.

 
  
 [그림]  RAM을 사용한 캐시 기억 장치 구성도

             
 
 
 - 주소 버스에 실린 주소 중 태그 필드와 캐시에서 읽은 워드의 태그 필드를 비교하여 같으면 적중(Hit),그렇지 않으면  실패  (Miss)이다.실패일 때는 원하는 워드가 주 기억 장치에서 읽혀져서 새로운 태그를 가지고 캐시에 저장된다.
- 만약 같은 인덱스를 가지고 있지만 태그가 다른 두개 이상의 워드가 반복하여 접근되면 적중률이 상당히 떨어지는 단점
 
 
 
            ② 연관 사상(associative mapping)
 
 
 - 주 기억 장치의 불록이 캐시의 어느 인덱스에도 저장될 수 있는 사상방법
- 주 기억 장치의 주소와 데이터가 캐시에 저장되므로 캐시 워드의 크기는 주기억 장치의 주소 비트 수와 워드당 데이터 비트 수    의  합이 된다.
   연관 사상은 가장 빠르고 가장 융통성 있는 캐시 구조
- 캐시 기억 장치가 연관 기억 장치로 구성되어 있으며, 기억장치의 특정 번지 내용을 참조하고자 한다면 인자 레지스터에   는 주소를 저장하고 키 레지스터는 주소 부분만 비교하도록 하면 된다.

  
 [그림] 연관 사상

 
 
            ③ 집합 연관 사상(set-associative mapping)
 
 
 - 직접 사상과 연관 사상을 조합
- 인덱스는 같고 태그가 다른 두 개 이상의 워드들을 집합으로 하여 연관 기억 장치에 넣어 놓고 직접 사상과 유사하게 각   워드를 주 기억 장치의 인덱스에 의해서 참조
- 캐시를 구성하는 연관 기억 장치의 각 워드는 태그와 데이터를 가지고 있으며, 캐시의 각 주소는 주 기억 장치 주소의   인덱스에 의해서 선택되고, 캐시 내의 어느 주소가 선택되면 그 주소에 있는 많은 태그들이 한꺼번에 검색된다.

  
 [그림] 집합 연관 사상 캐시 구성

                     
 
 
           (3) 교체 알고리즘
 
 
 - 캐시 실패(Miss)가 발생하여 원하는 워드를 포함하는 불록을 캐시로 불러 올 때 비어 있는 블록이 없을 경우 교체 대상의 캐시   블록을 선택하는 알고리즘
- 연관 사상 또는 집합 연관 사상 방법에서 적용
 
                   
 
 
 ① 최소 최근 사용(least recently used ; LRU)
  - 캐시 내에서 사용되지 않은 채로 가장 오래 있었던 불록을 교체
② 선입 선출(first-in first-out ; FIFO)
  - 캐시 내에서 가장 오래된 불록을 교체
  - 구현이 용이하지만 특정 상황에서는 불록이 너무 자주 교체되는 단점
③ 최소 사용 빈도(least frequently used ; LFU)
  - 가장 적게 사용된 불록을 교체
④ 랜덤 알고리즘
  - 임의(random)로 선택된 불록을 교체
 
 
 
                  
 
 
           (4) 기록 동작(write policy)
 
 
             - 변경된 캐시의 내용을 주기억장치의 같은 불록에 언제 갱신할 것인가?
 
 
 ① 동시 기록(write through)
- 프로세서가 캐시 불록의 내용을 변경할 때 주 기억 장치에 있는 대응 불록의 내용도 같이 변경
- 데이터의 일관성을 쉽게 보장할 수 있는 장점
- 기억 장치 접근 횟수가 많아짐
② 후 기록(write back)
- 갱신은 캐시에서만 하고, 1 비트의 태그를 이용하여 갱신된 불록을 표시하고, 표시된 불록은 새 불록으로 교체되기   전에 주 기억 장치로 복사
- 주 기억 장치에 대한 기록 동작을 최소화
- 주 기억 장치의 일부분이 무효(invalid)상태에 있으므로 입출력 모듈에 의한 접근은 반드시 캐시를 통해야 한다.

 

 http://nengjung.kit.ac.kr/~yskim/lecture/com_5_5.html

에서 더 보세요
 
 
 

 

출처 : http://k.daum.net/qna/view.html?qid=45BzC