[Computer Architecture] Cache Memory (캐시 메모리)

Principle of Locality

  큰 메모리에서 대부분의 메모리 접근을 빠르게 하는 것은 불가능하다. 프로그램이 어떤 특정 시간에 주소 공간 내의 비교적 작은 부분만을 접근한다는 것이 지역성의 원칙이다.

- Temporal Locality (시간적 지역성) : 한번 참조된 항목은 곧바로 다시 참조되는 경향이 있다.

- Spatial Locality (공간적 지역성) : 어떤 항목이 참조되면 그 근처에 있는 다른 항목들이 곧바로 참조될 가능성이 높다.

 

Memory Hierarchy

- 컴퓨터의 메모리를 메모리 계층구조로 구현함으로써 지역성의 원칙을 이용할 수 있다. 이는 서로 다른 속도와 크기를 갖는 여러 계층의 메모리로 구성되어 있다.

- 가장 빠른 메모리는 더 느린 메모리보다 비트당 가격이 비싸기 때문에 대개 그 크기가 작다.

- 두 계층 간 정보 전송의 최소 단위를 블록이라고 부른다.

- 프로세서가 요구한 데이터가 상위 계층의 어떤 블록에 있을 때 이를 적중(hit)이라고 부른다. 그리고 상위 계층에서 찾을 수 없다면 이를 실패(miss)라고 부른다. 이 때는 필요한 데이터를 포함하는 블록을 찾기 위해 하위 계층 메모리를 접근하게 된다.

- 적중률(hit rate)은 메모리 접근 중 상위 계층에서 찾을 수 있는 것의 비율로서 메모리 계층의 성능을 평가하는 척도로 이용된다. 실패율(miss rate, 1 - hit rate)는 메모리 접근 중 상위 계층에서 찾을 수 없는 것의 비율을 말한다.

- 실패 손실(miss penalty)은 하위 계층에서 해당 블록을 가져와서 상위 계층 블록과 교체하는 시간에다 그 블록을 프로세서에 보내는 데 걸리는 시간을 더한 값이다.

The Basics of Caches

Cache Memory

CPU와 가장 가까운 메모리 계층의 메모리

캐시에 없는 워드를 참조하기 직전과 직후의 캐시 상태이다. 이 참조는 Cache miss를 발생시켜 메모리에서 워드를 가져와 캐시에 넣도록 만든다.

 

Direct mapped(직접 사상)

워드의 메모리 주소를 캐시 블럭의 수로 나눈 나머지가 해당 메모리 워드가 캐시 내에 할당되는 위치이다.

 

- Tag : 캐시 공간에 어떤 블럭이 들어 있는지 식별하기 위한 필드이다. 이는 워드의 메모리 주스를 캐시블럭으로 나눈 몫이다.

- Valid : 캐시 블럭 안에 데이터의 유무를 나타내는 필드이다. 있으면 1, 없으면 0이다.

 

다음은 캐시 블럭의 수가 2^10개, 캐시 블럭의 사이즈가 2^2 byte인 캐시이다.

 

Block Size Considerations

캐시 사이즈 = 캐시 블럭 사이즈 * 블럭의 수

블럭 사이즈가 증가한다면? -> 블럭의 수가 감소한다. -> 블럭끼리의 경쟁이 심해진다. -> miss rate가 증가한다. pollution 또한 발생한다.

pollution : 실제로 자주 사용되는 중요한 데이터가 그렇지 않은 데이터에 의해 캐시에서 밀려나는 현상

 

Write-Through and Write-Back

- Write-Through : 캐시에 데이터를 write했을 때, 메인 메모리에 변경 사항을 즉시 반영하는 것. 하지만 이는 오래걸린다. 이를 개선하기 위해 write buffer에 데이터가 메모리에 써질 때 까지 기다리는 동안 데이터를 저장한다.

- Write-Back : 캐시에 데이터를 write했을 때, 메인 메모리에 변경 사항을 나중에 반영하는 것. 나중이라 함은 해당 캐시 블럭이 교체될 때 이다.

 

Associative Caches

- Fully Assocative

  비어있는 캐시 메모리가 있으면, 마음대로 주소를 저장하는 방식이다. 저장할 때는 매우 간단하지만, 찾을 때는 조건이나 규칙이 없어서 특정 캐시 Set안에 있는 모든 블럭을 한번에 찾아 원하는 데이터가 있는 검색해야 한다. 엔트리 마다 Tag comparator가 있어야 한다.

- n-way Set Associative
  특정 행을 지정하고, 그 행안에 어떤 열이든 비어있을 때 저장하는 방식이다. Direct Mapped에 비해 검색 속도는 느리지만, 저장이 빠르고 Fully associative에 비해 저장이 느린 대신 검색이 빠른 중간 형이다. n개의 Tag comparator를 필요로 한다. 블럭 주소를 n으로 나누었을 때의 나머지가 블럭이 들어갈 Set의 번호가 된다.

 

-> Associativity가 높을 수록 miss rate가 줄어들지만, 복잡성, 비용, 접근 시간은 증가한다.

 

  다음은 캐시 블럭의 수가 4이고, {0, 8, 0, 6, 8} 순서로 블럭에 접근 했을 때 Direct Mapped, 2-way set associative, Fully associative의 예시이다.

 

  n이 증가 할수록 miss rate가 감소한다. 하지만 n이 어느정도 커지면 set에 충분히 많은 데이터를 담기 때문에 n의 증가에 따른 miss rate의 감소율은 점차 줄어든다.

 

  다음은 캐시 블럭의 사이즈가 4byte이고, 2^8개의 캐시 블럭의 수를 가진 캐시 4개로 이루어진 4-way Set Associative Cache이다.

Block Replacement Policy

- Set Associative : non-valid한 엔트리, 없다면 Set에 있는 Entry중 하나

- LRU (Least-Recently Used) : 가장 긴 시간동안 접근되지 않은 엔트리

- Random : 아무거나

 

3C model (Sources of Misses)

- Compulsory Miss : 캐시에 한번도 들어오지 않았던 블록에 대한 첫 번째 접근에 의해 발생한다. 이를 Cold-Start Miss (최초 시작 실패)라고도 한다.

- Capacity Miss : 캐시가 프로그램 수행 중 필요한 모든 블록을 포함할 수 없을 때 발생한다. 용량 실패는 블록이 교체되고 나중에 다시 그 블록을 가져올 때 발생한다.

- Conflict Miss : Set Associative Cache 또는 Direct Mapped Cache 여러 블록들이 같은 집합에 대해 경쟁을 벌일 때 발생하는 Cache miss이다. 이 Miss는 같은 크기의 Fully Associative Cache 에서는 발생하지 않는다. 

 

Cache Design Trade-offs

Design change	Effect on miss rate	Negative performance effect
Increase cache size	Decrease capacity misses	May increase access time
Increase associativity	Decrease conflict misses	May increase access time
Increase block size	Decrease Compulsory Misses (due to spatial locality)	Increase miss penalty (Decrease # of Blocks -> pollution -> Increase miss rate)