[컴퓨터구조#4-2] 캐시 최적화 (Cache Optimization) - miss penalty, miss rate 줄이기

참고: Computer Architecture: A Quantitative Approach (5th edition) - 2.1~2.3.

2024.04.12 - [Computer Architecture] - [컴퓨터구조#4-1] 캐시 최적화 (Cache Optimization) - hit time 줄이기, 캐시 대역폭 늘리기

지난 글에 이어, 이번 글에서는 miss penalty와 miss rate을 줄이는 캐시 최적화 기술에 대해서 알아볼 것이다.

목차

1. Small and simple first level caches
2. Way prediction
3. Pipelining cache
4. Nonblock cache
5. Multibanked cache
6. Critial word first, Early restart
7. Merging write buffer
8. Code and compiler optimizations
9. Hardware prefetching
10. Compiler prefetching

---

Recap

• hit time 줄이기: 1번, 2번 → 전력 소모도 줄인다.
• 캐시 대역폭 늘리기: 3번, 4번, 5번 → 전력 소모에는 서로 다른 영향을 준다.
• miss penalty 줄이기: 6번, 7번 → 전력에는 거의 영향이 없다.
• miss rate 줄이기: 8번 → 컴파일 시간에 대한 개선은 확실히 전력 소모를 개선한다.
• 병렬성 활용해 miss penalty나 miss rate 줄이기: 9번, 10번 → 사용되지 않는 프리페치된 데이터 때문에 전력 소모를 늘린다.

 

6. Critical Word First, Early Restart

보통 프로세서는 한 번에 하나의 워드만 필요로 한다는 관찰에 기반한 최적화 기술이다. 간단히 말하면, 요청된 워드를 전송하고 프로세서를 다시 시작하기 전에 전체 블록이 로드될 때까지 기다리지 말라는 전략이다.

• Critical word first: 먼저 메모리에서 missed 워드를 요청하고, 도착하는대로 바로 프로세서에 이를 보내는 것이다. 블록 내 나머지 워드를 채워넣는 동안 프로세서가 execution을 계속하도록 한다.
• Early restart: 워드를 일반적인 순서대로 요청하지만, 블록의 요청된 워드가 도착하면 바로 프로세서에 보낸다.

이 전략의 효과성은 블록 크기와(클수록 효과적), 블록의 아직 페치되지 않은 부분에 또다른 접근이 있을 가능성(공간적 지역성)에 달라진다.

 

7. Merging Write Buffer

이미 write buffer에 pending인 블록을 저장할 때, 업데이트를 중복해서 write buffer에 새로운 업데이트를 쓰는 것이 아닌 이미 존재하는 write buffer의 item을 업데이트하는 방법. 이는 메모리를 더 효율적으로 사용할 수 있도록 해주며, full write buffer로 인한 stall을 줄인다.

(위) write buffering 없는 경우 (아래) write buffering 있는 경우

하지만 이러한 쓰기 병합은 I/O 주소에는 적용되지 않는데, 메모리 내에서 각각의 I/O 레지스터가 워드 어레이처럼 행동하지 않기 때문이다. 예를 들어, I/O 주소는 단일 주소를 사용하는 multiword write을 사용하기보다는, I/O register당 하나의 주소와 데이터 워드를 필요로 할 수 있다. 이러한 부작용은 보통 페이지를 캐시에 의해 nonmerging write through를 요구하도록 마킹함으로써 구현할 수 있다.

 

8. Code and Compiler Optimizations

loop interchange와 blocking 두 가지가 있다.

Loop Interchange

nested loop를 순차 메모리 접근으로 바꾸는 것이다.

예를 들어, row-major로 메모리가 맵핑되어 있다고 가정하면 다음 코드는 spatial locality를 활용할 수 있게 된다.

/* Before */
for (k=0; k<100; k=k+1)
	for (j=0; j<100; j=j+1)
    	for (i=0; i<5000; i=i+1)
        	x[i][j] = 2*x[i][j];

/* After */
for (k = 0; k<00; k=k+1)
	for (i=0; i<5000; i=i+1)
    	for (j=0; j<100; j=j+1)
        	x[i][j] = 2*x[i][j];

Blocking

전체 행이나 열을 접근하는 대신, 행렬을 작은 블록으로 나눈다. 이는 메모리 접근을 더 많이 필요로 하지만 접근의 지역성을 개선시킨다. 

다음과 같이 행렬곱 연산을 예시로 생각해 보자. 각 행렬 요소는 double 타입이며 캐시 블록 크기는 8 double이라고 가정해보자. n x n 행렬 a와 b에 대하여, 캐시 크기 C << n이다.

c = (double *) calloc(sizeof (double), n*n);

/* Multiply n x n matrices a and b */
void mmm (double *a, double *b, double *c, int n) {
	int i, j, k;
    for (i=0; i<n; i++)
    	for (j=0; j<n; j++)
        	for (k=0; k<n; k++)
            	c[i*n+j] += a[i*n+k]*b[k*n+j];
}

 

 

캐시 미스를 생각해보면, 각 iteration마다, n/8 + n = 9n/8번의 미스가 발생한다. (n/8은 캐시의 row에서 블록 단위로 로드해올 때 발생하는 compulsory miss이고, n은 행렬의 column의 item들을 하나씩 가져올 때 발생한다.) 최종적으로 n x n 행렬인 c가 모두 완전히 계산되려면, 9n/8 * n^2 = 9/8 * n^3의 캐시미스가 발생한다.

N=6, i=1인 경우 예시

 

이때 blocking을 적용해보자. 처음보다 루프는 복잡해졌지만, 작은 블록 단위로 행렬을 나누었다.

c = (double *) calloc(sizeof (double), n*n);

/* Multiply n x n matrices a and b */
void mmm (double *a, double *b, double *c, int n) {
	int i, j, k;
    for (i=0; i<n; i+=B)
    	for (j=0; j<n; j+=B)
        	for (k=0; k<n; k+=B)
            /* B x B mini matrix multiplications */
            for (i1=i; i1<i+B; i1++)
            	for (j1=j; j1<j+B; j1++)
                	for (k1=k; k1<k+B; k1++)
            			c[i1*n+j1] += a[i1*n+k1]*b[k1*n+j1];
}

아까와 같이 C << n이고, 캐시 안에 3개의 블록이 들어간다고 가정하자(3B^2 < C)

각 iteration마다(즉 캐시의 각 블록을 한번 돌 때마다), 2n/B * B^2/8 = nB/4 번의 캐시미스가 발생한다. (A와 B 행렬에서 각각 n/B 번의 미스, 그리고 각 블록을 캐시로 가져올 때 B^2/8번의 미스)

총 캐시미스는 (nB/4)*(n/B)^2 = n^3/(4B)로, blocking을 적용하지 않은 경우보다 매우 캐시 미스가 줄어든 것을 알 수 있다. (B에 반비례하므로, 3B^2 << C를 만족하는 한 블록 크기가 클수록 캐시 미스가 줄어든다.)

blocking 적용 후

 

9. Hardware Prefetching

프리페치란, 데이터나 명령어를 접근되기 전에 fetch해오는 것이다. prefetch한 데이터는 캐시 혹은 별도의 버퍼에 저장할 수 있다. 캐시에 저장하는 경우 캐시 내 다른 데이터를 evict해야 할 수도 있고, 별도의 버퍼에 저장하는 경우 캐시 오염 문제는 없지만 추가적인 영역이 필요하다. 혹은 프리페칭하는 동안 필요한 접근들을 처리할 수 있도록 빈 캐시를 따로 lockup해야 한다.

프리페처의 효과를 알아보기 위한 메트릭은 다음과 같다.

• Timeliness: 데이터가 CPU에 의해 요구되기 전에 준비되어 있어야 함.
• Coverage: 얼마나 많은 미스가 줄어들었는지 → useful prefetches / total references
• Accuracy: 얼마나 많은 프리페치가 useful했는지 → useful prefetches / total prefetches

보통 coverage가 높으면 accuracy가 낮고, accuracy가 높으면 coverage가 낮다.

간단하게 프리페처의 종류에 대해 살펴보자.

• Simple sequential prefetcher: A라는 주소에 대해 A+B 만큼을 프리페치한다. (B는 블록 크기이다.)
• Stride prefetcher: simple sequential prefetcher의 확장 버전으로, stride S에 대하여 A+S*B만큼을 프리페치한다. S는 양수일 수도 있고 음수일 수도 있다. positive unit stride prefetcher는 simple sequential prefetcher와 동일하다.
  • stride S를 찾는 방법은 address-based와 PC-based 두 가지 방법이 있다. 주소 기반은 n개의 주소 stream을 바탕으로, PC-based는 PC의 부분적인 비트로 인덱싱된 하나의 entry를 확인하는 방법이다.
• Correlation-based prefetcher
  • 주소 correlation을 찾는다(e.g. A는 B 다음이다.) Markov prefetcher의 경우 여러 타겟을 지원할 수 있다.
  • 주소를 계속 트래킹하기 때문에 큰 테이블이 필요해서 practical하지는 않다. 이를 해결하기 위해 hashing을 사용할 수 있다.
• Dependence-based prefetcher
  • linked-list로 pointer chasing을 통해 데이터를 바탕으로 다음 주소를 찾는다. 일반적인 지역성은 활용하지 않는다.
• Region prefetcher
  • 미스 난 주소 주변의 여러 블록을 프리페치한다.
  • A에 미스가 나면, A-N, ... , A-1, A+1, ... A+N을 가져오는 식.
  • 대역폭을 너무 낭비할 수 있다.

 

10. Compiler Prefetching

프로세서가 필요로 하기 전에 명령어를 미리 프리페치하는 것이다. 레지스터와 캐시 프리페치 두 종류가 있다.

• Register prefetch: 값을 레지스터에 로드
• Cache prefetch: 데이터를 캐시에만 로드하고 레지스터에는 로드하지 않음.

컴파일러 프리페치는 faulting 혹은 nonfaulting이 될 수 있다. 주소가 가상 주소 fault와 protection 위반일 때 exception을 일으키거나 일으키지 않는 것이다. Nonfaulting의 경우 프리페치가 exception을 일으키는 상황에 처했을 때 no-op으로 바뀐다.

소프트웨어 프리페치의 경우, 프리페치 명령어는 다음과 같이 컴파일러나 프로그래머에 의해 추가될 수 있다. 프리페치 명령어는 데이터를 캐시(L1 혹은 L2)에 가져온다.

for (i=0; i<N; i+=1) {
	prefetch A[i+2]
    ...
    operations on A[i]
    ...
}

 

최종적으로, 10개의 최적화 방법을 다음과 같이 정리할 수 있다.