[컴퓨터구조] Cache Optimizations

이번 포스트에서는 캐시의 성능을 개선하는 방법들에 대해 알아보겠다.

캐시의 성능을 측정하는 지표로는 Average Memory Access Time (AMAT)이 있다.

AMAT = (Hit time) + (Miss rate) * (Miss penalty)로 계산된다.

CPU의 처리 성능이 높아질수록, 전체 시스템의 성능에 cache가 미치는 영향이 커지고, 캐시의 Miss rate와 Miss penalty를 줄이는 것이 중요해진다.

Associative Caches

Miss rate을 줄이는 대표적 기법으로 Associate cache가 있다. 이전 포스트에서 다뤘던 Direct mapped cache는 특정 메모리 주소가 하나의 Block 안에만 들어갈 수 있도록 정해져 있었다. Associative cache는 특정 메모리 주소가 여러 군데에 들어갈 수 있도록 한다. 한 메모리 주소가 들어갈 수 있는 캐시의 구역을 set이라 한다. n-way set associative cache는, set 하나에 n개의 block이 들어갈 수 있다. 이때 Block number가 set을 결정한다. 예를 들어 2-way set associative에서는 set 0에 block 0, 1이, set 1에 block 2, 3이 들어갈 수 있는 구조이다. 여기서 Block을 Line이라고 부르기도 한다.

(* n-way set associative cache는 set이 n개라는 게 아니라, set 당 line 개수가 n개라는 점에 주의하자.)

특히, set의 개수가 1개여서 어떤 block이든 캐시의 임의의 위치에 저장될 수 있는 경우를 fully associative라 한다.

n-way set associative 캐시의 장점은, 조금 더 유연하게 캐시 공간을 사용하여 miss rate을 줄일 수 있다는 점이다.

한편 n-way set associative 캐시에 저장된 데이터를 검색하기 위해서는, 데이터 주소로부터 block number, 또 그로부터 set number를 구한 뒤, 해당 set에 있는 n개의 block의 tag를 모두 비교해야 한다. 따라서 direct mapped 캐시보다 n배 많은 비교 회로가 필요하며, 그만큼 비싸다.

따라서 n을 늘리면 캐시의 miss rate가 감소하지만, 그렇게 얻는 이득은 n이 증가할수록 감소한다.

Replacement Policy

Direct mapped 캐시에서, 새로운 block을 캐시에 불러온다면 기존에 있던 데이터는 무조건 퇴출되었다.

반면 set associative 캐시에서는, 기존에 set에 있던 block을 무조건 지울 필요가 없다. 만약 invalid한 block (아직 메모리에서 값을 불러오지 않은 block)이 set에 남아 있다면, 그 block에 불러오면 된다. 하지만 invalid block이 없다면, 해당 set 중에서 퇴출시킬 block을 선택해야 한다.

Temporal locality에 기반해서, 해당 set 안에서 가장 먼 과거에 사용되었던 block을 사용하는 방법을 생각해볼 수 있다. 이러한 block을 least-recent used (LRU) block이라고 한다. (물론, LRU가 무엇인지 하드웨어적으로 알아내는 것은 associativity가 늘어날수록 어려워진다.) 혹은 이와 상관없이 그냥 set의 block들 중 랜덤하게 골라서 퇴출시킬 수도 있다.

associativity가 높은 캐시의 경우, 이 두 방법의 성능은 비슷한 것으로 알려져 있다.

Multilevel Cache

Cache와 메모리(DRAM)이라는 메모리 계층 구조를 더 세분화해, 여러 단계의 Cache를 만들어 성능을 향상시킬 수 있다. CPU 가장 아래에 있는 캐시를 L1 캐시라 하며, 그 다음부터 L2, L3과 같이 부른다. 상대적으로 용량이 작고 빠른 Primary cache, 즉 L1 캐시는 hit time을 최소화하는 데 집중하여 설계한다. L2 캐시는 L1에서 Miss가 났을 경우를 메모리에 접근하는 일이 일어나지 않도록 방지하는 역할을 한다. 따라 L2 캐시는 miss rate를 최소화하는 데 집중하여 설계한다. high-end 시스템에서는 L2 캐시보다 하위에 있는 L3 캐시까지 도입하기도 한다.

그 결과, L1에서 L3로 내려갈수록, 캐시의 miss rate가 낮아진다. 그리고 그만큼 Associativity는 증가하고, Hit time도 증가한다.

Writing Cache-friendly Code

프로세서가 캐시를 이용해 효과적으로 프로그램을 실행하기 위해서는, Locality를 고려해 프로그램을 작성하는 것이 좋다.

예를 들어, Matrix multiplication을 수행하는 다음 코드를 보자.

for (i=0; i<n; i++){
  for (j=0; j<n; j++){
    sum = 0.0;
    for(k=0; k<n; k++)
      sum += a[i][k] * b[k][j];
    c[i][j] = sum;
  }
}

이 코드는 b[k][j]의 주소가 inner loop의 iteration마다 크게 변하기 때문에, spatial locality를 충족시킨다고 보기 어렵다. 이러한 코드는 cache miss를 늘리게 된다. 대신, 아래와 같은 방식으로 작성하면 spatial locality를 향상시킬 수 있다.

for (i=0; i<n; i++){
  for (k=0; k<n; k++){
    r = a[i][k];
    for(j=0; j<n; j++)
      c[i][j] += r * b[k][j];
  }
}

일반적으로 spatial locality를 늘리기 위해서는 배열 등 데이터에 접근할 때 작은 stride로 접근해야 한다. 또한 temporal locality를 늘리기 위해서는 같은 데이터를 비슷한 시점에 자주 사용하는 것이 바람직하다.

Cache Summary

메모리 계층 구조와 캐시에 관한 내용들을 정리해 보자.

먼저 캐시의 block 배치는 associativity에 의해 결정된다. Direct mapped는 특정 메모리 주소가 block 1군데에만 들어갈 수 있는 반면 n-way associative cache는 block n군데 중 한 곳에 들어갈 수 있다. associativity가 높아질수록 miss rate는 감소하고, 하드웨어의 complexity, cost, access time은 증가한다.

캐시의 Block replacement는 주로 LRU 방식이나, random replacement를 사용한다.

캐시에 데이터를 쓸 때는 Write-through, write-back 방식이 있다. Write-through 방식은 간단하지만 효율적인 작동을 위해서는 write buffer가 필요하다. Write-back 방식에서는 우선 상위 계층 메모리만 업데이트하고, block이 replace될 때 하위 계층을 업데이트해도 된다. 그러나 dirty block을 기록하기 위해 하드웨어가 더 많은 state를 보관해야 한다.

Three Types of Cache Misses

Cache Miss의 구분

1. Compulsory misses: Block이 초기화되고 처음 접근했을 때 데이터가 없어 발생한다.
2. Capacity misses: 제한된 캐시 크기로 인해 replace된 block을 접근하려고 할 때 발생한다.
3. Conflict misses: Fully-associative가 아닌 경우, set 안에서 block 간의 competetion으로 인해 발생한다.

캐시 디자인을 변경할 때, 위 세 가지 Miss를 중심으로 trade-off를 비교하면 다음과 같다.

캐시 크기를 늘리는 경우: Capacity miss가 감소한다. 하지만 하드웨어가 커져 access time이 증가한

Associativity를 늘리는 경우: Conflict miss가 감소한다. 그러나 마찬가지로 access time이 증가한다.

Block size를 늘리는 경우: Compulsory miss가 감소한다. 그러나 miss penalty가 증가하고 pollution으로 인해 miss rate도 증가할 수 있다.

References

1. D. Patterson, J. Hennessy (2021). Computer Organization and Design: RISC-V edition (2nd ed). Morgan Kaufmann.
2. Lecture Notes from SNU CSE Computer Architecture (김지홍 교수님 강의노트)