Lecture 12: Cache Memories
Computer Systems: A Programmer's Perspective (CS:APP)
Cache Memory Organization and Operation
Cache Memories
CPU 칩에 내장되어 있는 캐시 메모리(Cache memory)는 지역성의 원리에 기반하여 데이터를 빠르게 제공함으로써 시스템의 성능을 향상시킨다.
1
2
3
4
5
6
7
8
9
10
CPU
+—————————————————————————+
| ALU |
| ↕ |
| Register file |
| ↕ ↑ |
| Cache memory | | System bus Memory bus
| ↕ ↓ | / /
| Bus interface ←+—→ I/O bridge ←——→ Main memory
+—————————————————————————+
- 속도가 빠른 SRAM을 사용한다.
- CPU의 레지스터 파일 바로 옆에 위치하여, 레지스터와 캐시 간 데이터 이동이 빠르다.
General Cache Organization
캐시 메모리는 $S = 2^s$개의 세트(Set)로 구성되며, 각 세트는 $E = 2^e$개의 라인(Line)으로 구성된다.
각 라인은 다음과 같이 구성된다.
- 유효 비트(Valid bit): 데이터의 유효성을 나타낸다.
- 태그(Tag): 캐시 블록 검색에 사용된다.
- 캐시 블록(Cache block): $B = 2^b$ 바이트의 데이터를 저장한다.
캐시 메모리의 용량 $C$는 다음과 같이 계산된다.
\[C = S \times E \times B\]Cache Read
프로그램이 메모리 참조 명령을 실행하면, CPU는 참조할 주소를 캐시로 보내 데이터를 반환하도록 요청한다. 캐시는 받은 주소를 세 영역으로 나눈다.
| Tag | Set index | Block offset |
|---|---|---|
| $t \ \mathrm{bit}$ | $s \ \mathrm{bit}$ | $b \ \mathrm{bit}$ |
- 세트 인덱스를 확인한 뒤, 태그를 확인한다.
- 해당 세트의 모든 라인을 확인하여 일치하는 태그를 찾는다.
- 해당 라인의 유효 비트가 1이면 캐시 적중이 발생한다.
- 블록 오프셋을 통해 해당 캐시 블록 내에서 요청받은 데이터를 찾는다.
일치하는 태그가 없거나, 유효 비트가 0이면 캐시 미스가 발생한다.
Direct Mapped Cache
세트당 라인이 하나$(E = 1)$인 캐시를 Direct mapped cache라 한다.
다음과 같은 16바이트 메모리 시스템이 존재한다고 가정하자.
- 메모리는 2바이트 블록으로 분할된다. $(B = 2, \ b = 1)$
- 캐시 용량은 4바이트이다. $(C = 4)$
- 세트당 라인은 1개이다. $(E = 1)$
- 캐시는 4개의 세트로 구성된다. $(S = 4, \ s = 2)$
- 4비트 주소를 사용한다.
| Tag | Set index | Block offset |
|---|---|---|
| $1 \ \mathrm{bit}$ | $2 \ \mathrm{bit}$ | $1 \ \mathrm{bit}$ |
프로그램이 메모리 주소 0, 1, 7, 8, 0을 참조하는 명령을 실행한다.
| Address | Tag | Set index | Block offset |
|---|---|---|---|
| 0 | 0 | 00 | 0 |
| 1 | 0 | 00 | 1 |
| 7 | 0 | 11 | 1 |
| 8 | 1 | 00 | 0 |
처음엔 캐시가 비어 있으므로 유효 비트(v)는 모두 0이다.
| v | Tag | Cache Block | |
|---|---|---|---|
| Set 0 | 0 | ||
| ⋮ |
캐시가 주소 0에 있는 데이터 요청을 받는다.
- 주소 0의 세트 인덱스가 0이므로 세트 0을 확인한다.
- 유효 비트가 0이므로 캐시 미스가 발생하여, 메모리에서 데이터 블록을 가져온다.
| v | Tag | Cache Block | |
|---|---|---|---|
| Set 0 | 1 | 0 | Mem[0 ... 1] |
| ⋮ |
다음으로 주소 1이 들어온다.
- 주소 1의 세트 인덱스가 0이므로 세트 0을 확인한다.
- 태그가 0으로 일치하고 유효 비트가 1이므로, 캐시 적중이 발생한다.
- 블록 오프셋이 1이므로
Mem[1]을 반환한다.
다음으로 주소 7이 들어온다.
- 주소 7의 세트 인덱스가 3이므로 세트 3을 확인한다.
- 유효 비트가 0이므로 캐시 미스가 발생하여, 메모리에서 데이터 블록을 가져온다.
| v | Tag | Cache Block | |
|---|---|---|---|
| Set 0 | 1 | 0 | Mem[0 ... 1] |
| ⋮ | |||
| Set 3 | 1 | 0 | Mem[6 ... 7] |
다음으로 주소 8이 들어온다.
- 주소 8의 세트 인덱스가 0이므로 세트 0을 확인한다.
- 일치하는 태그가 없으므로 캐시 미스가 발생하여, 메모리에서 데이터 블록을 가져와 기존의 캐시 블록과 교체한다.
| v | Tag | Cache Block | |
|---|---|---|---|
| Set 0 | 1 | 1 | Mem[8 ... 9] |
| ⋮ | |||
| Set 3 | 1 | 0 | Mem[6 ... 7] |
다음으로 주소 0이 들어온다.
- 주소 0의 세트 인덱스가 0이므로 세트 0을 확인한다.
- 일치하는 태그가 없으므로 캐시 미스가 발생하여, 메모리에서 데이터 블록을 가져와 기존의 캐시 블록과 교체한다.
| v | Tag | Cache Block | |
|---|---|---|---|
| Set 0 | 1 | 0 | Mem[0 ... 1] |
| ⋮ | |||
| Set 3 | 1 | 0 | Mem[6 ... 7] |
이는 conflict miss1에 해당한다.
E-Way Set Associative Cache
세트당 라인이 E개인 캐시를 E-way set associative cache라 한다.
위와 유사한 16바이트 메모리 시스템이 존재한다고 가정하자. 단, 다음과 같은 차이점이 있다.
- 세트당 라인은 2개이다. $(E = 2)$
- 캐시는 2개의 세트로 구성된다. $(S = 2, \ s = 1)$
| Tag | Set index | Block offset |
|---|---|---|
| $2 \ \mathrm{bit}$ | $1 \ \mathrm{bit}$ | $1 \ \mathrm{bit}$ |
마찬가지로 메모리 주소 0, 1, 7, 8, 0을 참조하는 명령을 실행하고 나면, 최종적으로 캐시의 상태는 다음과 같다.
| v | Tag | Cache Block | |
|---|---|---|---|
| Set 0 | 1 | 00 | Mem[0 ... 1] |
| 1 | 10 | Mem[8 ... 9] | |
| Set 1 | 1 | 01 | Mem[6 ... 7] |
| 0 |
Write policies
데이터를 쓰려고 하는 블록이 캐시에 존재하는 경우를 Write hit라 하며, 이와 관련된 2가지 정책이 존재한다.
- Write-through: 캐시에 쓸 때마다 즉시 메모리에 쓴다. 데이터 일관성이 유지되지만, 메모리에 접근하는 비용이 많이 든다.
- Write-back: 일단 캐시에만 쓰고 해당 블록의 더티 비트(Dirty bit)를 활성화한 뒤, 나중에 블록이 캐시에서 제거될 때 메모리에 쓴다.
반대로 데이터를 쓰려고 하는 블록이 캐시에 없는 경우를 Write miss라 하며, 이와 관련된 2가지 정책이 존재한다.
- Write-allocate: 해당 블록을 메모리에서 캐시로 가져와서 쓴다.
- No-write-allocate: 해당 블록을 캐시로 가져오지 않고 메모리에 직접 쓴다.
일반적으로 다음과 같이 조합되어 사용된다.
- Write-back + Write-allocate
- Write-through + No-write-allocate
Cache Performance Metrics
- Miss rate: 캐시 미스가 발생하는 비율
- Hit time: 캐시 적중 여부를 판단하고, 적중 시 데이터를 읽어오는 데 소요되는 시간
- Miss penalty: 캐시 미스가 발생했을 때, 메모리에서 데이터를 가져오기 위해 추가로 소요되는 시간
평균 메모리 접근 시간(Average Memory Access Time, AMAT)은 다음과 같이 계산할 수 있다.
\[\mathrm{AMAT = Hit \ time + (Miss \ rate \times Miss \ penalty)}\]다음과 같은 경우를 가정해 보자.
| Parameter | Value |
|---|---|
| Hit time | 1 cycle |
| Miss penalty | 100 cycle |
이때 miss rate에 따른 AMAT는 다음과 같다.
| Miss rate | AMAT |
|---|---|
| 3% | 4 cycle |
| 1% | 2 cycle |
Miss rate가 2%p만 줄어도 평균 메모리 접근 시간이 2배나 빨라지는 것을 확인할 수 있다.
Writing Cache Friendly Code
- 자주 실행되는 코드, 특히 가장 많이 호출되는 함수와 그 내부 루프를 최적화하는 데 집중해야 한다.
- 중첩 루프에서는 안쪽 루프에 주목하여 캐시 미스를 최소화해야 한다.
- 반복적으로 참조되는 변수, 특히 지역 변수는 레지스터에 저장될 가능성이 높아 캐시 친화적이다.
- 배열을 순차적으로 참조(stride-1)하면 캐시 블록이 효율적으로 사용되어 miss rate가 낮아진다.
- 배열을 stride-2 패턴으로 참조하면 캐시 블록의 절반만 사용하게 되므로, stride-1에 비해 miss rate가 2배로 증가한다.
이처럼 캐시에 대한 이해를 바탕으로 코드의 지역성을 정량적으로 분석하여 최적화할 수 있다.
Performance Impact of Caches
The Memory Mountain
메모리 마운틴(Memory mountain)은 단위 시간당 메모리에서 읽은 바이트 수인 읽기 처리량(Read throughput)을 나타낸 그래프로, 프로그램의 지역성과 메모리 시스템의 성능을 표현한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
long data[MAXELEMS]; /* Global array to traverse */
/* test - Iterate over first "elems" elements of array "data" with
* stride of "stride", using 4 × 4 loop unrolling.
*/
int test(int elems, int stride) {
long sx2 = stride * 2, sx3 = stride * 3, sx4 = stride * 4;
long acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;
long length = elems;
long limit = length - sx4;
long i;
/* Combine 4 elements at a time */
for (i = 0; i < limit; i += sx4) {
acc0 += data[i];
acc1 += data[i + stride];
acc2 += data[i + sx2];
acc3 += data[i + sx3];
}
/* Finish any remaining elements */
for (; i < length; i++)
acc0 += data[i];
return acc0 + acc1 + acc2 + acc3;
}
먼저 test()를 한 번 호출하여 캐시를 채운 뒤, 다시 호출하여 읽기 처리량을 측정한다. 이러한 작업을 다양한 MAXELEMS 값과 stride 범위에 대해 수행하여, 결과를 그래프2로 나타낸다.
MAXELEMS값이 증가함에 따라 시간 지역성이 감소한다.data배열의 크기가 커질수록 낮은 계층의 메모리를 참조하게 되는데, stride-1의 경우 L3 구간도 L2 속도로 유지되는 것을 볼 수 있다. 이는 캐시가 stride-1 참조 패턴을 인식하여, 참조될 블록을 예측해서 가져오기 때문이다. (Aggressive prefetching)
stride가 증가함에 따라 공간 지역성이 감소한다.- stride-8이면 폭이 64바이트인 것인데, 이는 블록 크기와 같다. 즉 매번 다른 블록을 참조하게 되므로, 공간 지역성이 없는 셈이다. 이러한 이유로
stride가 8 이상일 때 그래프가 평평한 것을 볼 수 있다.
- stride-8이면 폭이 64바이트인 것인데, 이는 블록 크기와 같다. 즉 매번 다른 블록을 참조하게 되므로, 공간 지역성이 없는 셈이다. 이러한 이유로
그래프에서 보다시피 데이터를 메모리에서 읽는 것과 캐시에서 읽는 것의 차이는 엄청나다. 좋은 지역성을 가지면 캐시를 통해 읽기 처리량이 14 GB/s에 이르지만, 반대로 메모리만을 통하게 되면 100 MB/s까지도 내려간다.
Rearranging Loops to Improve Spatial Locality
중첩 루프를 재배열하여 공간 지역성을 향상시킬 수 있다. 다음은 행렬 곱셈을 수행하는 코드이다.
1
2
3
4
5
6
7
8
9
/* ijk */
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
double sum = 0.0;
for (int k = 0; k < n; k++)
sum += a[i][k] * b[k][j];
c[i][j] = sum;
}
}
캐시 블록의 크기가 32바이트라고 가정하고, 안쪽 루프에 주목해 보자.
a에 대한 행 방향 참조는 4번마다 1번씩 캐시 미스가 발생한다. (stride-1 참조 패턴)b에 대한 열 방향 참조는 매번 캐시 미스가 발생한다.
따라서 반복당 평균 캐시 미스 횟수는 1.25이다. jik 순으로 배치한 루프도 이와 동일하다.
1
2
3
4
5
6
7
8
/* kij */
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
r = a[i][k];
for (int j = 0; j < n; j++)
c[i][j] += r * b[k][j];
}
}
b와c에 대한 행 방향 참조는 각각 4번마다 1번씩 캐시 미스가 발생한다.
따라서 반복당 평균 캐시 미스 횟수는 0.5이다. ikj 순으로 배치한 루프도 이와 동일하다.
1
2
3
4
5
6
7
8
/* jki */
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
r = b[k][j];
for (int i = 0; i < n; i++)
c[i][j] += a[i][k] * r;
}
}
a와c에 대한 열 방향 참조는 각각 매번 캐시 미스가 발생할 것이다.
따라서 반복당 평균 캐시 미스 횟수는 2이다. kji 순으로 배치한 루프도 이와 동일하다.
| Load | Store | $\mathrm{miss/iter}$ | |
|---|---|---|---|
ijk (jik) | 2 | 0 | 1.25 |
kij (ikj) | 2 | 1 | 0.5 |
jki (kji) | 2 | 1 | 2 |
kij 순으로 배치한 루프의 성능이 가장 좋은 것을 확인할 수 있다.
Write-back 정책을 통해 쓰기 작업을 연기할 수 있기 때문에, store가 성능에 미치는 영향은 load에 비해 훨씬 작다.
Using Blocking to Improve Temproal Locality
블록화(Blocking)를 통해 시간 지역성을 향상시킬 수 있다.
1
2
3
4
5
6
7
8
9
10
11
c = (double *)calloc(sizeof(double), n * n);
/* Multiply n × n matrices a and b */
void mmm(double *a, double *b, double *c, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++)
c[i*n + j] += a[i*n + k] * b[k*n + j];
}
}
}
캐시 블록의 크기가 64바이트이고, 캐시 용량이 n보다 훨씬 작다고 가정하자. $(C \ll n)$
a에 대한 행 단위 참조는 $\frac{n}{8}$번의 캐시 미스가 발생한다.b에 대한 열 단위 참조는 $n$번의 캐시 미스가 발생한다.
따라서 c의 요소당 캐시 미스 횟수는 $\frac{9}{8} n$이고, $n^2$ 개의 요소가 있으므로 총 캐시 미스 횟수는 $\frac{9}{8} n^3$이다.
여기에 블록화를 적용해 보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
c = (double *)calloc(sizeof(double), n * n);
/* Multiply n × n matrices a and b */
void mmm(double *a, double *b, double *c, int n) {
for (int i = 0; i < n; i += B) {
for (int j = 0; j < n; j += B) {
for (int k = 0; k < n; k += B)
/* B × B mini matrix multiplications */
for (i1 = i; i1 < i + B; i++)
for (j1 = j; j1 < j + B; j++)
for (k1 = k; k1 < k + B; k++)
c[i1*n + j1] += a[i1*n + k1] * b[k1*n + j1];
}
}
}
한 번에 하나의 요소를 업데이트하는 대신, $B \times B$ 크기의 블록 단위로 업데이트한다.
a와b에 대한 블록 단위 참조는 각각 $\frac{B^2}{8}$번의 캐시 미스가 발생한다.a와b에 대한 블록으로 이루어진 행/열 단위 참조는 각각 $\frac{B^2}{8} \times \frac{n}{B} = \frac{Bn}{8}$번의 캐시 미스가 발생한다.
따라서 c의 블록당 캐시 미스 횟수는 $\frac{Bn}{4}$이고, 블록이 $(\frac{n}{B})^2$개 있으므로 총 캐시 미스 횟수는 $\frac{Bn}{4} \times (\frac{n}{B})^2 = \frac{1}{4B} n^3$이다. $B$ 값이 클수록 캐시 미스 횟수가 감소하고, a, b, c 3개의 블록이 캐시에 들어가야 하므로 $3B^2 < C$를 만족하는 가장 큰 $B$ 값을 선택하는 것이 최선일 것이다.
행렬 곱셈은 $3n^2$개의 데이터를 가지고 $2n^3$번의 계산을 수행하므로, 각 데이터 항목을 $O(n)$번씩 사용하게 된다. 이러한 경우에 블록화 기법을 이용하여 캐시 활용도를 높임으로써 성능을 향상시킬 수 있다.