5장 캐시 친화적 코드 작성하기
2장에서 지역성에 대한 개념을 소개하고 어떤 경우에 좋은 지역성을 가질 수 있는지 알아봤어요.
그리고 캐시 메모리가 어떻게 동작하는지까지 이해했으니 우리는 좀 더 캐시 친화적으로 코드를 작성할 수 있어요.
이 5장의 핵심 내용은 다음과 같아요.
핵심 목표
- 좋은 지역성을 가진 캐시 친화적인 코드 작성하기
- 프로그램의 성능은 캐시 미스율
Miss Rate에 큰 영향을 받는다. - 좋은 지역성 -> 낮은 캐시 미스율 -> 빠른 실행 속도
핵심 개념 정리
1.Cache 관련 용어
- Block: 메모리 -> 캐시사이에 이동하는 데이터 단위예요.
- Line: 캐시에 있는 block 의 저장공간 + tag,valid bit 등 메타정보가 들어있어요.
- Set: 캐시에서 block 을 저장하는 그룹이예요. 직접매핑,집합결합성,완전결합성 캐시등이 있어요.
2.캐시 친화적 코딩 원칙
- 대부분의 시간은 몇 개의 핵심 함수와 핵심 루프를 실행하는데 소요돼요. 여기에 집중하기!
- 캐시 미스를 줄이자! 동일한 연산이더라도 미스가 적은 루프구조가 훨씬 빨라요.
6장 종합: 프로그램 성능에 대한 캐시의 영향
앞서 배운 내용을 실제 머신에서 돌아가는 프로그램의 성능에 대한 캐시의 영향을 학습하는 것으로 마무리할게요.
6.1 메모리 마운틴
프로그램이 시스템에서 데이터를 읽는 비율을
- 읽기 처리량
read throughput또는 - 읽기 대역폭
read bandwidth라고 불러요.
만약 프로그램이 s 초동안 N바이트를 읽는다면, 읽기 처리량은 N/s가 되고 보통은 초당 메가바이트 단위로 표시해요. MB/s
메모리 마운틴은 이러한 메모리 성능을 시각적으로 보여주는 2차원 그래프예요.
이번 장에서는 특정 배열을 다양한 Stride(간격)과 Size(배열 크기)로 읽는 프로그램을 통해 메모리 계층 구조의 특성을 분석하는 방법을 배웁니다.
주요 용어는 다음과 같아요.
| 개념 | 설명 |
|---|---|
| Read Throughput (MB/s) | 메모리에서 데이터를 읽는 속도. 초당 몇 메가바이트를 읽는지를 나타냄 |
| Stride | 배열을 순회할 때 건너뛰는 요소 수. spatial locality에 영향 |
| Size | 읽는 배열의 크기. working set 크기. temporal locality에 영향 |
| Loop Unrolling | 성능 최적화를 위해 루프 본문을 반복 작성하여 명령어-level 병렬성 증가 |
| Temporal Locality | 자주 사용하는 데이터를 반복해서 사용할 가능성 (시간적 국소성) |
| Spatial Locality | 근처에 있는 데이터를 함께 접근할 가능성 (공간적 국소성) |
| Cache 계층 구조 | L1 (32KB) → L2 (256KB) → L3 (8MB) → Main Memory |
그럼 메모리마운틴을 구현한 함수를 살펴볼게요.
1 long data[MAXELEMS]; /* The global array we’ll be traversing */
2
3 /* test - Iterate over first "elems" elements of array "data" with
4 * stride of "stride", using4x4 loop unrolling.
5 */
6 int test(int elems, int stride)
7 {
8 long i, sx2 = stride*2, sx3 = stride*3, sx4 = stride*4;
9 long acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;
10 long length = elems;
11 long limit = length - sx4;
12
13 /* Combine 4 elements at a time */
14 for (i = 0; i < limit; i += sx4) {
15 acc0 = acc0 + data[i];
16 acc1 = acc1 + data[i+stride];
17 acc2 = acc2 + data[i+sx2];
18 acc3 = acc3 + data[i+sx3];
19 }
20
21 /* Finish any remaining elements */
22 for (; i < length; i++) {
23 acc0 = acc0 + data[i];
24 }
25 return ((acc0 + acc1) + (acc2 + acc3));
26 }
27
28 /* run - Run test(elems, stride) and return read throughput (MB/s).
29 * "size" is in bytes, "stride" is in array elements, and Mhz is
30 * CPU clock frequency in Mhz.
31 */
32 double run(int size, int stride, double Mhz)
33 {
34 double cycles;
35 int elems = size / sizeof(double);
36
37 test(elems, stride); /* Warm up the cache */
38 cycles = fcyc2(test, elems, stride, 0); /* Call test(elems,stride) */
39 return (size / stride) / (cycles / Mhz); /* Convert cycles to MB/s */
40 }이 함수의 run 명령어로 다른 함수들을 호출하면
그 함수에 특정 Stride(간격), Size(크기) 등을 다양한 값으로 넣어주면서 값을 측정하는거예요.
이 메모리마운틴의 Stride와 Size가 커질수록 읽기성능이 그냥 바닥을 치는걸 알 수 있어요.
Stride 공간지역성
캐시는 라인단위로 메모리를 가져오므로 Stride 가 작아지면 같은 캐시메모리를 참조할 확률이 높아져서 공간 지역성이 좋아져요.
예를 들어 64바이트 짜리 캐시라인이면 a[0]을 읽을 때 캐시에 a[1] a[2]도 같이 올라와요. 그럼 배열을 순서대로 읽을 때, 캐시에 있는 값들이 재활용 될거예요.
Size 시간지역성
시간 지역성은 같은 데이터를 반복해서 접근하는 거죠?
예를 들어 크기가 4KB인 배열을 반복순회 한다고하면
한번 읽었던 데이터가 아직 캐시에 남아 있을 확률이 높아서 캐시 미스가 안나요.
그럼 시간지역성이 ok
반면 크기가 크면 캐시에 다 못들어가서 계속 교체될 거예요.
이런 특성들이 반영되어서 L1,L2,L3 의 경계지점에서 캐시성능이 급격히 하락하는걸 볼 수 있어요.
그래서 프로그램은 "작게, 자주, 연속적으로" 접근하라
6.2 공간 지역성을 높이기 위한 루프 재배치
행렬의 곱셈을 할 때 i,j,k 처럼 보통 3개의 루프를 사용해서 구현한다는걸 아실거예요.
이 장에서는 행렬 곱셈을 수행하는 루프의 여섯 가지 버전을 볼거예요.
모든 버전은 수학적으로 같은 결과를 계산하지만, 메모리 접근 순서가 달라지면서 성능 차이가 발생해요.
그 내용은...직접..보세요..
7장 요약.
메모리 저장장치는 빠를수록 용량이 작고 비싸다.
그래서 캐시 잘해야된다.
시간지역성 공간지역성 신경써서 프로그래밍 해라.
