메모리 성능을 개선하기 위해 프로그래머가 적용할 수 있는 기법을, 캐시 우회부터 L1/L2 최적화, TLB와 프리페치까지 다룬다.
URL: https://lwn.net/Articles/255364/
Title: Memory part 5: What programmers can do
[편집자 주: Ulrich Drepper의 “What every programmer should know about memory” 5부에 오신 것을 환영한다. 이 글은 6장(프로그래머가 코드의 메모리 성능을 개선하기 위해 할 수 있는 일)을 다루는 첫 절반이다. 아직 읽지 않은 독자를 위해 1부, 2부, 3부, 4부도 온라인에 남아 있다.]
$ sudo 오늘 구독하세요 지금 구독하고 LWN 권한을 한 단계 올리세요. 게시되는 즉시 LWN의 모든 고품질 기사에 접근할 수 있고, 그 과정에서 LWN을 후원하는 데에도 도움이 됩니다. 지금 행동하면 무료 체험 구독으로 시작할 수 있습니다.
이전 절들의 설명을 통해, 프로그래머가 프로그램 성능에 긍정적으로든 부정적으로든 영향을 줄 수 있는 기회가 매우 많다는 점이 분명해졌다. 그리고 이는 메모리 관련 작업에 대해서만 한정한 이야기다. 여기서는 가장 아래 계층(물리 RAM 접근과 L1 캐시)부터 시작해, 메모리 처리에 영향을 미치는 OS 기능까지 포함하여 위로 올라가며 가능한 기회들을 살펴본다.
데이터가 생성되지만 (즉시) 다시 소비되지 않는 경우, 메모리 저장(store) 연산이 먼저 전체 캐시 라인을 읽은 뒤 캐시에 있는 데이터를 수정한다는 사실은 성능에 해롭다. 이 동작은 곧 다시 필요할 수도 있는 데이터를, 곧 사용되지 않을 데이터 때문에 캐시에서 밀어내게 만든다. 특히 행렬처럼 큰 데이터 구조를 채운 뒤 나중에 사용하는 경우에 그렇다. 행렬의 마지막 원소를 채우기 전에 크기 자체가 앞쪽 원소들을 축출(evict)해버리므로, 쓰기에 대한 캐싱은 효과가 없게 된다.
이런 상황(및 유사한 상황)을 위해 프로세서는 비시간적(non-temporal) 쓰기 연산을 지원한다. 여기서 non-temporal은 “데이터가 곧 재사용되지 않으므로 캐시할 이유가 없다”는 뜻이다. 비시간적 쓰기는 캐시 라인을 읽고 수정하는 대신, 새 내용을 직접 메모리에 쓴다.
비싸 보일 수 있지만 꼭 그렇지는 않다. 프로세서는 전체 캐시 라인을 채우기 위해 쓰기 결합(write-combining, 3.3.3절 참조)을 사용하려 시도한다. 이것이 성공하면 메모리 읽기 연산이 전혀 필요 없다. x86 및 x86-64 아키텍처에서는 gcc가 여러 intrinsic을 제공한다.
c#include <emmintrin.h> void _mm_stream_si32(int *p, int a); void _mm_stream_si128(int *p, __m128i a); void _mm_stream_pd(double *p, __m128d a); #include <xmmintrin.h> void _mm_stream_pi(__m64 *p, __m64 a); void _mm_stream_ps(float *p, __m128 a); #include <ammintrin.h> void _mm_stream_sd(double *p, __m128d a); void _mm_stream_ss(float *p, __m128 a);
이들 명령은 한 번에 큰 양의 데이터를 처리할 때 가장 효율적이다. 데이터는 메모리에서 로드되어 한두 단계 처리되고 다시 메모리에 기록된다. 데이터가 프로세서를 “흐르며(stream)” 지나가기에 intrinsic 이름이 그렇게 붙었다.
메모리 주소는 각각 8 또는 16바이트 정렬이어야 한다. 멀티미디어 확장을 사용하는 코드에서는 일반 mm_store* intrinsic을 이런 비시간적 버전으로 바꿀 수 있다. 9.1절의 행렬 곱 코드에서는 기록된 값을 곧바로 재사용하므로 이렇게 하지 않았다. 이는 stream 명령을 쓰는 것이 유용하지 않은 사례다. 이 코드에 대해서는 6.2.1절에서 더 다룬다.
프로세서의 쓰기 결합 버퍼는 하나의 캐시 라인에 대해 부분 쓰기 요청을 오래 유지하지 못한다. 일반적으로 하나의 캐시 라인을 수정하는 모든 명령은 연속해서 발행해야 쓰기 결합이 실제로 일어난다. 예시는 다음과 같다.
c#include <emmintrin.h> void setbytes(char *p, int c) { __m128i i = _mm_set_epi8(c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c); _mm_stream_si128((__m128i *)&p[0], i); _mm_stream_si128((__m128i *)&p[16], i); _mm_stream_si128((__m128i *)&p[32], i); _mm_stream_si128((__m128i *)&p[48], i); }
포인터 p가 적절히 정렬되어 있다고 가정하면, 이 함수 호출은 지정된 캐시 라인의 모든 바이트를 c로 설정한다. 쓰기 결합 로직은 네 개의 movntdq 명령이 생성된 것을 보고 마지막 명령이 실행될 때까지 메모리에 대한 쓰기 명령을 내리지 않는다. 요약하면 이 코드 시퀀스는 (1) 쓰기 전에 캐시 라인을 읽는 것을 피하고, (2) 곧 필요하지 않을 수 있는 데이터로 캐시를 오염시키는 것을 피한다. 특정 상황에서는 매우 큰 이점이 있을 수 있다. 일상적인 예로 C 런타임의 memset은 큰 블록에 대해 위와 같은 시퀀스를 사용해야 한다.
일부 아키텍처는 특화된 해법을 제공한다. PowerPC는 전체 캐시 라인을 0으로 지우는 dcbz 명령을 정의한다. 이 명령은 결과를 위한 캐시 라인을 할당하기 때문에 엄밀히 말해 캐시를 우회하는 것은 아니지만, 메모리에서 데이터를 읽지 않는다. 비시간적 store보다 제한적이다. 캐시 라인은 전부 0으로만 설정할 수 있고(비시간적 데이터라면) 캐시를 오염시키지만, 결과를 얻기 위해 쓰기 결합 로직이 필요하지는 않다.
비시간적 명령이 실제로 어떤 효과가 있는지 보기 위해, 2차원 배열로 구성된 행렬에 쓰는 성능을 재는 새 테스트를 보자. 컴파일러는 메모리에서 행렬을 배치할 때, 가장 왼쪽(첫 번째) 인덱스가 행(row)을 가리키며 그 행의 모든 원소가 메모리에 연속으로 놓이도록 한다. 오른쪽(두 번째) 인덱스는 행 내 원소를 가리킨다. 테스트 프로그램은 행렬을 두 방식으로 순회한다. 첫 번째는 내부 루프에서 열(column) 번호를 증가시키고, 두 번째는 내부 루프에서 행 인덱스를 증가시킨다. 즉, 그림 6.1과 같은 동작을 얻는다.
그림 6.1: 행렬 접근 패턴
3000×3000 행렬을 초기화하는 데 걸리는 시간을 측정한다. 메모리가 어떻게 동작하는지 보기 위해 캐시를 사용하지 않는 store 명령을 사용한다. IA-32에서는 “non-temporal hint”가 이에 사용된다. 비교를 위해 일반 store 연산도 측정한다. 결과는 표 6.1과 같다.
내부 루프 증가(increment) 행(Row) 일반(Normal) 0.048s 비시간적(Non-Temporal) 0.048s 표 6.1: 행렬 초기화 시간
캐시를 사용하는 일반 쓰기에서는 예상한 결과가 나온다. 메모리를 순차적으로 사용하면 전체 0.048초(약 750MB/s)로 훨씬 좋고, 더-혹은-덜 랜덤 접근은 0.127초(약 280MB/s)가 걸린다. 행렬이 충분히 커서 캐시는 사실상 무력하다.
여기서 주로 관심 있는 부분은 캐시를 우회하는 쓰기다. 순차 접근이 캐시를 사용하는 경우와 똑같이 빠르다는 점은 의외일 수 있다. 이유는 앞서 설명한 것처럼 프로세서가 쓰기 결합을 수행하기 때문이다. 더불어 비시간적 쓰기에 대한 메모리 순서 규칙은 완화되어 있다. 프로그램은 명시적으로 메모리 배리어(x86/x86-64에서는 sfence)를 삽입해야 한다. 이는 프로세서가 데이터를 언제 어떻게 되돌려 쓸지에 더 큰 자유를 갖게 하고, 이용 가능한 대역폭을 최대한 활용할 수 있게 한다.
내부 루프에서 열 방향 접근을 하는 경우는 다르다. 캐시 접근보다 훨씬 느리다(0.16초, 약 225MB/s). 여기서는 쓰기 결합이 불가능하고 각 메모리 셀을 개별적으로 주소 지정해야 한다. 이 과정은 RAM 칩의 새로운 행(row)을 계속 선택해야 하며 지연이 수반된다. 결과는 캐시 사용 실행보다 25% 나쁘다.
읽기 측면에서는(최근까지) 프로세서에 NTA 프리페치 명령 같은 약한 힌트 외에는 지원이 부족했다. 특히 메모리 매핑 I/O 같은 비캐시 가능 메모리에 대해, 읽기에는 쓰기 결합에 해당하는 기능이 없다는 점이 좋지 않다. Intel은 SSE4.1 확장에서 NTA 로드를 도입했다. 이는 소수의 스트리밍 로드 버퍼를 사용해 구현되며, 각 버퍼는 하나의 캐시 라인을 담는다. 특정 캐시 라인에 대한 첫 movntdqa 명령은 캐시 라인을 버퍼로 로드하며 다른 라인을 대체할 수 있다. 같은 캐시 라인에 대한 이후의 16바이트 정렬 접근은 적은 비용으로 로드 버퍼에서 제공된다. 다른 이유가 없다면 캐시 라인은 캐시에 로드되지 않으므로, 캐시를 오염시키지 않고 대량의 메모리를 읽을 수 있다. 컴파일러는 다음 intrinsic을 제공한다.
c#include <smmintrin.h> __m128i _mm_stream_load_si128 (__m128i *p);
이 intrinsic은 캐시 라인 내의 각 16바이트 블록 주소를 매개변수로 여러 번 호출하여, 캐시 라인 전체를 읽을 때까지 사용해야 한다. 그 다음에야 다음 캐시 라인으로 넘어가야 한다. 스트리밍 읽기 버퍼가 여러 개이므로, 두 개의 메모리 위치를 동시에 읽는 것도 가능할 수 있다.
이 실험에서 얻어야 할 점은 다음과 같다. 현대 CPU는 접근이 순차적이기만 하면 캐시되지 않은 쓰기(그리고 더 최근에는 읽기) 접근을 매우 잘 최적화한다. 이는 한 번만 사용되는 큰 데이터 구조를 다룰 때 유용하다. 둘째, 캐시는 랜덤 메모리 접근 비용의 일부(전부는 아님)를 가려준다. 이 예에서 랜덤 접근은 RAM 접근 구현 때문에 70% 더 느렸다. 구현이 바뀌기 전까지는 가능한 한 랜덤 접근을 피해야 한다.
프리페치에 대한 절에서 non-temporal 플래그를 다시 살펴볼 것이다.
캐시와 관련해 프로그래머가 할 수 있는 가장 중요한 개선은 1차 캐시(L1)에 영향을 주는 것들이다. 다른 계층을 포함하기 전에 먼저 L1을 논한다. 물론 L1을 위한 모든 최적화는 다른 캐시에도 영향을 준다. 모든 메모리 접근의 주제는 같다. 지역성(공간적/시간적)을 개선하고 코드와 데이터를 정렬하라.
6.2.1 L1 데이터 캐시 접근 최적화
3.3절에서 L1d 캐시를 효과적으로 쓰면 성능이 얼마나 개선되는지 이미 봤다. 이 절에서는 어떤 코드 변경이 성능 향상에 도움이 되는지 보인다. 앞 절의 흐름을 이어, 우선 메모리를 순차적으로 접근하도록 최적화하는 데 집중한다. 3.3절의 수치에서 봤듯, 메모리가 순차적으로 접근되면 프로세서는 자동으로 프리페치를 수행한다.
예제 코드는 행렬 곱이다. 1000×1000 double 원소의 정사각 행렬 두 개를 쓴다. 수학을 잊은 사람을 위해, 원소 a_ij와 b_ij를 가진 두 행렬 A, B(0≤i,j<N)의 곱은 다음과 같다.
이를 C로 직관적으로 구현하면 다음과 같다.
cfor (i = 0; i < N; ++i) for (j = 0; j < N; ++j) for (k = 0; k < N; ++k) res[i][j] += mul1[i][k] * mul2[k][j];
입력 행렬은 mul1과 mul2이고, 결과 res는 모두 0으로 초기화되어 있다고 가정한다. 간결한 구현이지만, 그림 6.1에서 설명한 문제와 정확히 같은 문제를 갖는다는 점이 분명해야 한다. mul1은 순차적으로 접근되지만, 내부 루프는 mul2의 행 번호를 진행시킨다. 즉 mul1은 그림 6.1의 왼쪽 행렬처럼, mul2는 오른쪽 행렬처럼 다뤄진다. 좋을 리 없다.
쉽게 시도할 수 있는 한 가지 처방이 있다. 각 원소가 여러 번 접근되므로, 사용 전에 두 번째 행렬 mul2를 재배열(수학 용어로 “전치(transpose)”)하는 것이 가치 있을 수 있다.
전치(전통적으로 위첨자 T로 표시) 후에는 두 행렬 모두를 순차적으로 순회하게 된다. C 코드 관점에서는 다음과 같다.
cdouble tmp[N][N]; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) tmp[i][j] = mul2[j][i]; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) for (k = 0; k < N; ++k) res[i][j] += mul1[i][k] * tmp[j][k];
전치 행렬을 담을 임시 변수 tmp를 만든다. 메모리를 더 만지게 되지만, 열마다 1000번의 비순차 접근이 (적어도 현대 하드웨어에서는) 더 비싸므로 이 비용을 회수하길 기대한다. 성능 테스트를 해보자. 2666MHz Intel Core 2에서 결과(클럭 사이클)는 다음과 같다.
원본 전치 사이클 16,765,297,870 3,922,373,010 상대 100% 23.4%
단순 변환만으로 76.6% 속도 향상을 얻는다. 복사 비용은 충분히 상쇄된다. 1000번의 비순차 접근이 정말로 치명적이다.
다음 질문은 이것이 최선인가이다. 또한 추가 복사 없이 대체 방법이 필요하다. 항상 복사를 할 여유가 있는 것은 아니다. 행렬이 너무 크거나 사용 가능한 메모리가 너무 작을 수 있다.
대체 구현을 찾으려면 관련 수학과 원본 구현이 수행하는 연산을 면밀히 봐야 한다. 기본적인 수학 지식만으로도, 결과 행렬 각 원소에 대해 더하는 순서는 각 항(addend)이 정확히 한 번씩만 등장하기만 하면 무관함을 알 수 있다. {여기서는 오버플로/언더플로/반올림 같은 산술 효과는 무시한다.} 이 이해를 통해 원본 코드 내부 루프에서 수행하던 덧셈의 순서를 재배열하는 해법을 찾을 수 있다.
이제 원본 코드 실행에서의 실제 문제를 보자. mul2의 접근 순서는 (0,0),(1,0),…,(N-1,0),(0,1),(1,1),…이다. 원소 (0,0)과 (0,1)은 같은 캐시 라인에 있지만, 내부 루프 한 바퀴가 끝날 때쯤이면 그 캐시 라인은 이미 오래전에 축출되었다. 이 예에서 내부 루프 한 라운드마다 세 행렬 각각에 대해 1000개의 캐시 라인(Core 2는 64바이트)이 필요하다. 이는 L1d 32kB를 훨씬 넘는다.
그렇다면 내부 루프를 실행하는 동안 중간 루프의 두 반복을 함께 처리하면 어떨까? 이 경우 L1d에 들어있음이 보장된 캐시 라인에서 double 값 두 개를 사용하게 된다. L1d 미스율을 절반으로 줄인다. 개선이긴 하지만, 캐시 라인 크기에 따라 아직 최선은 아닐 수 있다. Core 2의 L1d 캐시 라인은 64바이트다. 실제 값은 런타임에 다음으로 질의할 수 있다.
csysconf (_SC_LEVEL1_DCACHE_LINESIZE)
또는 명령행에서 getconf 유틸리티를 사용해 특정 캐시 라인 크기에 맞춰 프로그램을 컴파일할 수도 있다. sizeof(double)=8이므로 캐시 라인을 완전히 활용하려면 중간 루프를 8번 언롤해야 한다. 같은 논리로 res 행렬도 효율적으로 사용하려면(즉 동시에 8개의 결과를 쓰려면) 바깥 루프도 8번 언롤해야 한다. 여기서는 캐시 라인이 64바이트라고 가정하지만, 32바이트 캐시 라인 시스템에서도 두 캐시 라인이 100% 활용되므로 잘 동작한다. 일반적으로는 getconf를 써서 컴파일 타임에 캐시 라인 크기를 하드코딩하는 것이 좋다.
shgcc -DCLS=$(getconf LEVEL1_DCACHE_LINESIZE) ...
바이너리를 범용으로 만들려면 가장 큰 캐시 라인 크기를 사용해야 한다. L1d가 매우 작은 프로세서에서는 모든 데이터가 캐시에 들어가지 않을 수 있지만, 그런 프로세서는 고성능 프로그램에 적합하지 않다. 우리가 얻는 코드는 대략 다음과 같다.
c#define SM (CLS / sizeof (double)) for (i = 0; i < N; i += SM) for (j = 0; j < N; j += SM) for (k = 0; k < N; k += SM) for (i2 = 0, rres = &res[i][j], rmul1 = &mul1[i][k]; i2 < SM; ++i2, rres += N, rmul1 += N) for (k2 = 0, rmul2 = &mul2[k][j]; k2 < SM; ++k2, rmul2 += N) for (j2 = 0; j2 < SM; ++j2) rres[j2] += rmul1[k2] * rmul2[j2];
상당히 무서워 보인다. 어느 정도는 그렇지만, 몇 가지 트릭이 포함되어 있기 때문이다. 가장 눈에 띄는 변화는 이제 6중 루프라는 점이다. 바깥쪽 루프들은 SM(캐시 라인 크기 / sizeof(double)) 간격으로 증가한다. 이는 곱셈을 더 작은 문제로 나누어 캐시 지역성을 높인다. 안쪽 루프들은 바깥 루프가 생략한 인덱스를 순회한다. 여기에도 다시 세 개의 루프가 있다. 유일한 까다로운 부분은 k2와 j2 루프의 순서가 바뀌었다는 점인데, 실제 계산에서 k2에 의존하는 표현식은 하나뿐이지만 j2에 의존하는 것은 둘이기 때문이다.
나머지 복잡함은 gcc가 배열 인덱싱 최적화에 그다지 똑똑하지 않아서 생긴다. rres, rmul1, rmul2 같은 변수를 도입해 공통식을 내부 루프에서 가능한 한 밖으로(그리고 가능한 한 아래 단계로) 끌어내어 최적화한다. C/C++의 기본 aliasing 규칙(restrict를 쓰지 않으면 모든 포인터 접근은 aliasing 가능)이 컴파일러의 이런 결정을 돕지 못한다. 이것이 수치 계산에서는 Fortran이 여전히 선호되는 이유다. 빠른 코드를 쓰기 더 쉽다. {이론상 C99의 restrict 키워드가 이를 해결해야 하지만, 컴파일러가 아직 따라오지 못했다. 주된 이유는, 잘못된 코드가 너무 많아 컴파일러가 이를 믿고 최적화했다가는 잘못된 목적 코드를 생성할 수 있기 때문이다.}
이 모든 작업의 효과는 표 6.2에서 볼 수 있다.
원본 전치 부분 행렬(Sub-Matrix) 벡터화(Vectorized) 사이클 16,765,297,870 3,922,373,010 2,895,041,480 1,588,711,750 상대 100% 23.4% 17.3% 9.47% 표 6.2: 행렬 곱 시간
복사를 피함으로써 성능을 6.1% 더 얻는다. 게다가 추가 메모리가 필요 없다. 결과 행렬이 메모리에 들어가기만 하면 입력 행렬은 임의로 커도 된다. 이는 일반 해법에 필요한 조건이며, 우리는 이제 그 조건을 달성했다.
표 6.2에는 아직 설명하지 않은 열이 하나 더 있다. 현대 프로세서는 대개 벡터화에 대한 특수 지원을 포함한다. 종종 멀티미디어 확장으로 불리는 이 특수 명령은 2, 4, 8개 또는 그 이상의 값을 동시에 처리한다. 대개 SIMD(Single Instruction, Multiple Data) 연산이며, 데이터를 적절한 형태로 만들기 위한 다른 명령들이 보강된다. Intel의 SSE2는 한 번에 double 두 개를 처리한다. 명령 참조 매뉴얼에는 SSE2에 접근하는 intrinsic 함수들이 나열되어 있다. 이 intrinsic을 사용하면 프로그램은 원본 대비 추가로 7.3% 더 빨라진다. 결과적으로 원본 코드 실행 시간의 10% 만에 실행되는 프로그램을 얻는다. 사람들이 알아볼 만한 수치로는 318 MFLOPS에서 3.35 GFLOPS로 갔다. 여기서는 메모리 효과에만 관심이 있으므로 코드는 9.1절로 미뤄둔다.
마지막 버전에서도 mul2에 대한 캐시 문제는 여전히 있고, 프리페치도 여전히 잘 동작하지 않는다. 하지만 행렬을 전치하지 않는 한 해결할 수 없다. 언젠가 캐시 프리페치 유닛이 패턴을 더 똑똑하게 인식할 수 있게 된다면 추가 변경 없이도 해결될지도 모른다. 그럼에도 2.66GHz 프로세서에서 단일 스레드로 3.19 GFLOPS는 나쁘지 않다.
행렬 곱 예제에서 우리가 최적화한 것은 로드된 캐시 라인의 활용이다. 캐시 라인의 모든 바이트를 항상 사용한다. 단지 캐시 라인이 축출되기 전에 사용하도록 만들었을 뿐이다. 이는 분명 특수한 사례다.
더 흔한 경우는 하나 이상의 캐시 라인을 채우는 데이터 구조를 쓰면서도, 프로그램이 어떤 시점에 몇몇 멤버만 사용하는 상황이다. 그림 3.11에서 몇몇 멤버만 사용할 때 구조체 크기가 커지는 효과를 보았었다.
그림 6.2: 여러 캐시 라인에 걸친 배치
그림 6.2는 또 다른 벤치마크 결과다. 이번에는 동일한 리스트 원소의 두 값을 더한다. 한 경우에는 두 원소가 같은 캐시 라인에 있고, 다른 경우에는 하나는 리스트 원소의 첫 캐시 라인에, 다른 하나는 마지막 캐시 라인에 있다. 그래프는 그로 인해 경험하는 느려짐을 보여준다.
예상대로, 작업 집합(working set)이 L1d에 들어가면 부정적 효과는 없다. L1d가 더 이상 충분하지 않으면, 한 캐시 라인 대신 두 캐시 라인을 사용해야 하므로 페널티를 치른다. 빨간 선은 리스트가 메모리에 순차적으로 배치된 경우를 보여준다. 흔한 2단계 패턴이 보인다. L2 캐시가 충분할 때 약 17% 페널티, 메인 메모리를 써야 할 때 약 27% 페널티다.
랜덤 메모리 접근의 경우 상대 데이터는 조금 다르다. 작업 집합이 L2에 들어갈 때 느려짐은 25~35%다. 그 이상에서는 약 10%로 내려간다. 페널티가 줄어서가 아니라, 실제 메모리 접근 비용이 비례 이상으로 커지기 때문이다. 또한 어떤 경우에는 두 원소 사이 거리도 영향을 미친다. Random 4 CLs 곡선은 첫 번째와 네 번째 캐시 라인을 사용하기 때문에 더 큰 페널티를 보인다.
데이터 구조의 레이아웃이 캐시 라인과 어떻게 맞물리는지 쉽게 보려면 pahole 프로그램([dwarves] 참조)을 사용할 수 있다. 이 프로그램은 바이너리에 정의된 데이터 구조를 분석한다. 다음 정의를 포함하는 프로그램을 생각해 보자.
cstruct foo { int a; long fill[7]; int b; };
64비트 머신에서 컴파일했을 때 pahole 출력에는 그림 6.3과 같은 정보가 포함된다.
struct foo { int a; /* 0 4 */ /* XXX 4 bytes hole, try to pack */ long int fill[7]; /* 8 56 */ /* --- cacheline 1 boundary (64 bytes) --- */ int b; /* 64 4 */ }; /* size: 72, cachelines: 2 */ /* sum members: 64, holes: 1, sum holes: 4 */ /* padding: 4 */ /* last cacheline: 8 bytes */그림 6.3: pahole 실행 출력
이 출력은 많은 것을 알려준다. 첫째, 이 데이터 구조가 캐시 라인 하나를 넘어선다는 점이다. 도구는 현재 사용 중인 프로세서의 캐시 라인 크기를 가정하지만, 명령행 매개변수로 값을 덮어쓸 수 있다. 특히 구조체 크기가 캐시 라인 한계치를 아주 조금 넘는 경우이고, 이 타입의 객체가 많이 할당된다면 구조체를 압축할 방법을 찾는 것이 의미 있다. 일부 요소의 타입을 더 작게 만들 수 있거나, 몇 필드는 사실 플래그라서 비트 단위로 표현할 수 있을지도 모른다.
이 예에서는 압축이 쉽고 도구가 힌트도 준다. 출력은 첫 요소 뒤에 4바이트 구멍(hole)이 있음을 보여준다. 이는 구조체 및 fill 요소의 정렬 요구 때문에 생긴다. b 요소는 크기가 4바이트(줄 끝의 4로 표시)이므로 그 틈에 완벽히 들어간다. 그 결과 틈이 사라지고 구조체는 캐시 라인 하나에 들어간다. pahole은 이 최적화를 스스로 수행할 수 있다. --reorganize 매개변수를 쓰고 구조체 이름을 명령행 끝에 추가하면, 도구 출력은 최적화된 구조체와 캐시 라인 사용량을 보여준다. 요소를 옮겨 틈을 채우는 것 외에도, 비트필드를 최적화하고 패딩/홀을 결합할 수 있다. 자세한 내용은 [dwarves]를 보라.
뒤쪽 요소가 앞의 구멍에 딱 맞는 경우가 물론 이상적이다. 이 최적화가 유용하려면 객체 자체가 캐시 라인에 정렬되어야 한다. 이는 조금 뒤에 다룬다.
pahole 출력은 또한 요소를 재정렬해 함께 쓰는 요소들이 함께 저장되도록 해야 하는지 판단하는 데에도 도움이 된다. pahole을 사용하면 어떤 요소가 같은 캐시 라인에 있는지, 혹은 목적을 달성하려면 요소를 재배치해야 하는지 쉽게 알 수 있다. 자동 과정은 아니지만 도구가 상당히 도와준다.
개별 구조체 요소의 위치와 사용 방식도 중요하다. 3.5.2절에서 보았듯, 임계 워드(critical word)가 캐시 라인 뒤쪽에 있으면 성능이 나쁘다. 이는 프로그래머가 항상 다음 두 규칙을 따라야 함을 뜻한다.
작은 구조체의 경우, 프로그래머는 요소를 접근될 가능성이 높은 순서대로 배치해야 한다. 다만 hole을 채우는 등 다른 최적화도 적용할 수 있도록 유연하게 다뤄야 한다. 큰 데이터 구조에서는 캐시 라인 크기의 각 블록이 위 규칙을 따르도록 배치해야 한다.
그러나 객체 자체가 정렬되어 있지 않다면 요소 재정렬은 그만한 시간을 들일 가치가 없다. 객체 정렬은 데이터 타입의 정렬 요구에 의해 결정된다. 각 기본 타입은 자체 정렬 요구를 갖고, 구조체 타입은 그 요소들 중 가장 큰 정렬 요구가 구조체 정렬을 결정한다. 이는 거의 항상 캐시 라인 크기보다 작다. 즉 구조체 멤버를 같은 캐시 라인에 맞춰 배치해도, 할당된 객체가 캐시 라인 크기에 맞춰 정렬된다는 보장은 없다. 구조체 레이아웃 설계 시 사용한 정렬을 실제 객체에 보장하는 방법은 두 가지다.
c#include <stdlib.h> int posix_memalign(void **memptr, size_t align, size_t size);
이 함수는 새로 할당한 메모리의 포인터를 memptr가 가리키는 포인터 변수에 저장한다. 메모리 블록은 size 바이트이고, align 바이트 경계에 정렬된다.
컴파일러가 할당하는 객체(.data, .bss 등 및 스택)에는 변수 속성(attribute)을 사용할 수 있다.
cstruct strtype variable __attribute((aligned(64)));
이 경우 variable은 strtype 구조체의 정렬 요구와 무관하게 64바이트 경계에 정렬된다. 전역 변수와 자동 변수 모두에 동작한다.
하지만 이 방법은 배열에는 동작하지 않는다. 배열 요소 크기가 정렬 값의 배수가 아닌 한 배열의 첫 요소만 정렬되기 때문이다. 또한 모든 변수를 개별적으로 주석 처리해야 한다. posix_memalign도 정렬 요구 때문에 단편화 및/또는 더 큰 메모리 소비를 유발할 수 있어 완전히 공짜는 아니다.
cstruct strtype { ...members... } __attribute((aligned(64)));
이는 배열을 포함해 모든 객체를 적절히 정렬하도록 컴파일러에 지시한다. 다만 동적 할당 객체에 대해서는 프로그래머가 적절한 정렬을 요청해야 한다. 여기서도 posix_memalign을 사용해야 한다. gcc가 제공하는 alignof 연산자로 값을 얻어 posix_memalign의 두 번째 매개변수로 넘기면 쉽게 처리할 수 있다.
앞서 언급한 멀티미디어 확장은 거의 항상 메모리 접근이 정렬되어 있기를 요구한다. 즉 16바이트 메모리 접근이라면 주소가 16바이트 정렬이어야 한다. x86/x86-64에는 비정렬 접근을 처리할 수 있는 특수 변형이 있지만 느리다. 이런 강한 정렬 요구는 많은 RISC 아키텍처(모든 메모리 접근에 대해 완전 정렬을 요구)에서는 새삼스러운 것이 아니다. 아키텍처가 비정렬 접근을 지원하더라도, 특히 비정렬로 인해 로드/스토어가 한 캐시 라인 대신 두 캐시 라인을 건드리게 되면 정렬을 맞추는 것이 더 빠를 수 있다.
그림 6.4: 비정렬 접근 오버헤드
그림 6.4는 비정렬 메모리 접근의 효과를 보여준다. 익숙한 테스트(데이터 요소를 증가시키며 메모리를 순차/랜덤으로 방문)를 정렬된 리스트 요소와 의도적으로 비정렬된 요소에 대해 측정한다. 그래프는 비정렬 접근 때문에 발생하는 느려짐을 보여준다. 랜덤 접근보다 순차 접근에서 효과가 더 극적이다. 랜덤은 원래 메모리 접근 비용이 커서 비정렬 비용이 부분적으로 가려지기 때문이다. 순차의 경우 작업 집합이 L2에 들어갈 때 느려짐이 약 300%다. 이는 L1 캐시의 효과가 감소하기 때문이다. 일부 증가 연산이 이제 두 캐시 라인을 건드리고, 리스트 요소 작업을 시작할 때도 종종 두 캐시 라인을 읽어야 한다. L1과 L2 사이 연결은 너무 혼잡해진다.
작업 집합이 매우 큰 경우에도 비정렬 접근 효과는 20~30%에 달한다. 정렬된 접근 시간 자체가 이미 긴데도 큰 수치다. 이 그래프는 정렬을 진지하게 다뤄야 함을 보여준다. 아키텍처가 비정렬 접근을 지원하더라도 “정렬된 것과 같게 좋다”로 받아들여서는 안 된다.
하지만 이런 정렬 요구에는 부작용도 있다. 자동 변수가 정렬 요구를 가지면, 컴파일러는 모든 상황에서 그 정렬이 만족되도록 보장해야 한다. 호출 지점과 스택 처리 방식에 대해 컴파일러가 제어권이 없기 때문에 쉽지 않다. 이 문제는 두 방식으로 처리될 수 있다.
대부분의 ABI는 두 번째 방식을 따른다. 호출자가 규칙을 어기고 callee에서 정렬이 필요하면 프로그램은 실패할 가능성이 높다. 하지만 정렬 유지도 공짜는 아니다.
함수의 스택 프레임 크기가 반드시 정렬의 배수인 것은 아니다. 이 말은 그 스택 프레임에서 다른 함수를 호출하면 패딩이 필요하다는 뜻이다. 차이는, 스택 프레임 크기는 대부분 컴파일러가 알고 있으므로, 그 프레임에서 호출되는 어떤 함수에 대해서도 정렬을 보장하도록 스택 포인터를 어떻게 조정해야 할지 알고 있다는 점이다. 실제로 대부분의 컴파일러는 스택 프레임 크기를 올림(round up)해 처리한다.
가변 길이 배열(VLA)이나 alloca를 사용하면 이런 단순한 방식은 불가능하다. 이 경우 스택 프레임 총 크기는 런타임에야 알 수 있다. 생성된 코드가 (약간) 느려지는 적극적 정렬 제어가 필요할 수 있다.
일부 아키텍처에서는 멀티미디어 확장만 엄격한 정렬을 요구한다. 그런 시스템의 스택은 정상 데이터 타입을 위해 최소 정렬만 유지(대개 32비트는 4바이트, 64비트는 8바이트)한다. 이런 시스템에서 엄격한 정렬을 강제하면 불필요한 비용이 든다. 즉 멀티미디어 연산을 하지 않고 정렬에 의존하지 않는 것이 확실하다면 엄격한 정렬 요구를 없애고 싶을 수 있다. 다른 함수를 호출하지 않는 꼬리(tail) 함수이면서 멀티미디어 연산을 하지 않는 경우는 정렬이 필요 없다. 정렬이 필요 없는 함수만 호출하는 함수도 마찬가지다. 충분한 규모의 함수 집합을 식별할 수 있다면 프로그램은 정렬 요구를 완화할 수 있다. x86 바이너리에 대해 gcc는 완화된 스택 정렬을 지원한다.
-mpreferred-stack-boundary=2
이 옵션에 N 값을 주면 스택 정렬 요구는 2^N 바이트로 설정된다. 값 2를 쓰면 기본(16바이트)에서 4바이트로 줄어든다. 대부분의 경우 스택 push/pop이 어차피 4바이트 경계에서 동작하므로 추가 정렬 연산이 필요 없다. 이 머신 종속 옵션은 코드 크기를 줄이고 실행 속도를 높일 수 있다. 하지만 다른 많은 아키텍처에는 적용할 수 없다. x86-64에서도 대개 적용 불가인데, x86-64 ABI는 부동소수점 인자를 SSE 레지스터로 전달해야 하고 SSE 명령은 16바이트 정렬이 필요하기 때문이다. 그럼에도 사용 가능한 경우에는 눈에 띄는 차이를 만들 수 있다.
구조체 요소의 효율적 배치와 정렬만이 데이터 구조가 캐시 효율에 영향을 주는 유일한 요소는 아니다. 구조체 배열을 쓰면 구조체 정의 전체가 성능에 영향을 준다. 그림 3.11의 결과를 떠올려라. 배열 요소에 사용되지 않는 데이터가 늘어날수록 프리페치가 점점 덜 효과적이 되었고, 큰 데이터 세트에서는 프로그램이 덜 효율적이 되었다.
큰 작업 집합에서는 가능한 한 캐시를 잘 사용해야 한다. 그러려면 데이터 구조를 재배치해야 할 수도 있다. 개념적으로 함께 속하는 모든 데이터를 하나의 데이터 구조에 넣는 것이 프로그래머에게는 쉽지만, 최대 성능 관점에서는 최선이 아닐 수 있다. 다음 구조를 생각해 보자.
cstruct order { double price; bool paid; const char *buyer[5]; long buyer_id; };
이 레코드들이 큰 배열에 저장되고, 자주 실행되는 작업이 미결제(outstanding) 청구서들의 예상 결제액을 합산한다고 하자. 이 시나리오에서 buyer와 buyer_id 필드에 쓰인 메모리는 불필요하게 캐시에 로드된다. 그림 3.11의 데이터로 보아 프로그램은 잠재적으로 5배까지 느려질 수 있다.
order 구조를 둘로 나누어, 처음 두 필드는 한 구조에 두고 나머지 필드는 다른 곳에 저장하는 것이 훨씬 낫다. 이는 프로그램 복잡도를 올리지만, 성능 이득이 그 비용을 정당화할 수 있다.
마지막으로 또 다른 캐시 사용 최적화를 보자. 다른 캐시에도 적용되지만 주로 L1d에서 체감된다. 그림 3.8에서 보았듯, 캐시 연관도(associativity)가 증가하면 일반 동작에 이점이 있다. 캐시가 클수록 보통 연관도가 더 높다. L1d는 완전 연관(fully associative)이 되기에는 너무 크지만 L2만큼의 연관도를 갖기에는 충분히 크지 않다. 작업 집합의 많은 객체가 같은 캐시 set에 떨어지면 문제가 된다. set 과다 사용으로 축출이 일어나면, 캐시 대부분이 비어 있어도 지연을 겪을 수 있다. 이런 캐시 미스를 _충돌 미스(conflict miss)_라고 부르기도 한다. L1d 주소 지정은 가상 주소를 사용하므로, 이것은 사실 프로그래머가 어느 정도 제어할 수 있다. 함께 사용되는 변수를 함께 저장하면 같은 set에 떨어질 가능성을 줄일 수 있다. 그림 6.5는 이 문제가 얼마나 빨리 나타날 수 있는지 보여준다.
그림 6.5: 캐시 연관도 효과
이 그림에서는 익숙한 Follow 테스트를 NPAD=15로 한 특별 설정을 측정했다. {32비트 머신에서 수행했으므로 NPAD=15는 리스트 원소당 64바이트 캐시 라인 하나를 뜻한다.} x축은 두 리스트 원소 사이의 거리로, 비어 있는 리스트 원소 수로 측정한다. 다시 말해 거리 2는 다음 요소의 주소가 이전 요소보다 128바이트 뒤라는 뜻이다. 모든 요소는 같은 거리로 가상 주소 공간에 배치된다. y축은 리스트 총 길이이며, 116개 요소만 사용하므로 전체 작업 집합 크기는 641024바이트다. z축은 각 리스트 원소를 순회하는 데 필요한 평균 사이클 수를 보여준다.
그림의 결과는 놀랍지 않다. 적은 수의 요소를 사용하면 모든 데이터가 L1d에 들어가고 원소당 접근 시간은 3사이클뿐이다. 리스트 원소의 거의 모든 배치에서도 마찬가지다. 가상 주소는 충돌이 거의 없이 L1d 슬롯에 잘 매핑된다. 그런데 (이 그래프에서는) 두 개의 특별한 거리 값에서는 상황이 다르다. 거리가 4096바이트의 배수(즉 64개 요소 거리)이고 리스트 길이가 8보다 크면, 원소당 평균 사이클 수가 급격히 증가한다. 이런 상황에서는 모든 엔트리가 같은 set에 있고, 리스트 길이가 연관도보다 커지면 엔트리가 L1d에서 밀려나 다음 라운드에 L2에서 다시 읽어야 한다. 그 결과 원소당 약 10사이클의 비용이 든다.
이 그래프로 사용된 프로세서가 연관도 8, 총 32kB의 L1d를 가진다는 것을 알 수 있다. 필요하다면 이 테스트로 값을 결정할 수 있다. L2에서도 같은 효과를 측정할 수 있지만, L2는 물리 주소로 인덱싱되고 훨씬 크기 때문에 더 복잡하다.
프로그래머에게 이는 연관도가 주의할 가치가 있음을 의미한다. 2의 거듭제곱 경계에 맞춰 데이터를 배치하는 일은 현실에서 흔하지만, 바로 그런 상황이 위와 같은 효과와 성능 저하를 쉽게 유발한다. 비정렬 접근은 한 번의 접근이 추가 캐시 라인을 필요로 할 수 있어 충돌 미스 가능성을 높인다.
그림 6.6: AMD의 L1d 뱅크 주소
이 최적화를 수행하면 관련된 또 다른 최적화도 가능하다. 적어도 AMD 프로세서는 L1d를 여러 개의 개별 뱅크(bank)로 구현한다. L1d는 사이클당 두 데이터 워드를 받을 수 있지만, 두 워드가 서로 다른 뱅크에 있거나 같은 인덱스의 뱅크에 있을 때만 가능하다. 뱅크 주소는 그림 6.6처럼 가상 주소의 하위 비트에 인코딩되어 있다. 함께 쓰는 변수를 함께 저장하면 서로 다른 뱅크(또는 같은 인덱스의 뱅크)에 있을 가능성이 높다.
6.2.2 L1 명령 캐시 접근 최적화
좋은 L1i 사용을 위해 코드를 준비하는 데도 좋은 L1d 사용과 비슷한 기법이 필요하다. 다만 문제는, 프로그래머가 어셈블리로 코드를 쓰지 않는 한 L1i 사용 방식에 직접 영향력을 행사하기 어렵다는 점이다. 컴파일러를 쓴다면, 프로그래머는 컴파일러가 더 나은 코드 레이아웃을 만들도록 유도함으로써 간접적으로 L1i 사용에 영향을 줄 수 있다.
코드는 점프 사이에서는 선형이라는 장점이 있다. 이 구간에서는 프로세서가 메모리를 효율적으로 프리페치할 수 있다. 점프는 이 좋은 그림을 방해하는데, 이유는 다음과 같다.
이 문제들은 실행에 정지(stall)를 만들며 성능에 심각한 영향을 줄 수 있다. 그래서 오늘날 프로세서는 분기 예측(BP)에 큰 투자를 한다. 고도로 특화된 BP 유닛은 점프보다 가능한 한 훨씬 앞서 점프 대상을 결정해, 프로세서가 새 위치의 명령을 캐시에 로드하기 시작하도록 한다. 정적/동적 규칙을 사용하며 실행 패턴을 점점 더 잘 파악한다.
명령 캐시에서는 데이터를 가능한 한 빨리 캐시에 넣는 것이 더 중요하다. 3.1절에서 언급했듯, 명령은 실행 전에 디코딩해야 하며 이를 빠르게 하기 위해(x86/x86-64에서 중요), 명령은 메모리에서 읽어온 바이트/워드 형태가 아니라 디코딩된 형태로 캐시된다.
최상의 L1i 사용을 위해 프로그래머는 최소한 다음 측면들을 살펴야 한다.
이제 이러한 측면을 최적화하는 데 도움이 되는 컴파일러 기법을 살펴보자.
컴파일러는 최적화 레벨을 켜는 옵션을 제공하며, 특정 최적화를 개별적으로 켤 수도 있다. gcc의 높은 최적화 레벨(-O2, -O3)에서 켜지는 많은 최적화는 루프 최적화와 함수 인라이닝에 관한 것이다. 일반적으로 이는 좋은 최적화다. 이 방식으로 최적화되는 코드가 전체 실행 시간에서 큰 비중을 차지한다면, 전체 성능이 개선될 수 있다. 특히 함수 인라이닝은 컴파일러가 더 큰 코드 덩어리를 한 번에 최적화하도록 하며, 결과적으로 프로세서 파이프라인 구조를 더 잘 활용하는 기계어 코드를 생성할 수 있게 한다. 데드 코드 제거, 값 범위 전파(value range propagation) 같은 코드/데이터 처리도 프로그램의 더 큰 부분을 하나의 단위로 볼 수 있을 때 더 잘 작동한다.
코드 크기가 커지면 L1i(그리고 L2 및 더 높은 레벨) 캐시에 압력이 증가한다. 이는 성능을 떨어뜨릴 수도 있다. 더 작은 코드가 더 빠를 수 있다. 다행히 gcc에는 이를 지정하는 최적화 옵션이 있다. -Os를 쓰면 컴파일러는 코드 크기를 최적화한다. 코드 크기를 늘리는 것으로 알려진 최적화는 비활성화된다. 이 옵션은 종종 놀라운 결과를 만든다. 특히 컴파일러가 루프 언롤링이나 인라이닝을 잘 활용할 수 없는 경우 큰 이득이 된다.
인라이닝은 개별적으로도 제어할 수 있다. 컴파일러에는 인라이닝을 안내하는 휴리스틱과 제한이 있으며, 이 제한은 프로그래머가 조정할 수 있다. -finline-limit 옵션은 함수가 어느 정도 크면 인라이닝하기에 너무 크다고 간주할지를 지정한다. 함수가 여러 곳에서 호출된다면, 모든 곳에 인라인하면 코드 크기가 폭발할 수 있다. 하지만 그게 전부가 아니다. inlcand 함수가 f1과 f2에서 호출되고 f1과 f2가 순서대로 호출된다고 하자.
인라이닝함 인라이닝하지 않음 start f1 code f1 인라인된 inlcand more code f1 end f1 start f2 code f2 인라인된 inlcand more code f2 end f2 start inlcand code inlcand end inlcand start f1 code f1 end f1 start f2 code f2 end f2 표 6.3: 인라이닝 vs 비인라이닝
표 6.3은 인라이닝하지 않는 경우와 두 함수 모두에 인라이닝하는 경우 생성된 코드가 어떻게 보일 수 있는지 보여준다. inlcand가 f1과 f2에 인라인되면 생성 코드의 총 크기는 다음과 같다.
size f1 + size f2 + 2 × size inlcand
인라이닝이 없다면 총 크기는 size inlcand만큼 더 작다. f1과 f2가 서로 가까운 시점에 호출된다면, 인라이닝으로 인해 그만큼 더 많은 L1i/L2 캐시가 필요하다. 게다가 inlcand를 인라인하지 않으면 그 코드가 여전히 L1i에 남아 디코딩을 다시 하지 않아도 될 수도 있다. 게다가 분기 예측 유닛이 점프를 더 잘 예측할 수도 있는데, 이미 그 코드를 본 적이 있기 때문이다. 컴파일러 기본 인라인 상한이 프로그램에 최선이 아니라면 낮춰야 한다.
한편 인라이닝이 항상 의미 있는 경우도 있다. 함수가 한 번만 호출된다면 인라인하는 편이 낫다. 컴파일러가 값 범위 전파 같은 더 많은 최적화를 수행할 기회를 얻기 때문이다. 다만 선택 제한 때문에 인라이닝이 막힐 수 있다. gcc는 이런 경우를 위해 함수에 항상 인라인하도록 지정하는 옵션을 제공한다. always_inline 함수 속성을 추가하면 이름 그대로 컴파일러에 지시한다.
같은 맥락에서, 함수가 충분히 작더라도 절대 인라인되면 안 되는 경우 noinline 속성을 사용할 수 있다. 이 속성은 작은 함수라도 다양한 곳에서 자주 호출된다면 의미가 있다. L1i 내용을 재사용할 수 있고 전체 풋프린트를 줄일 수 있다면, 추가 함수 호출 비용을 상쇄하는 경우가 많다. 오늘날 분기 예측 유닛은 꽤 잘한다. 다만 인라이닝이 더 공격적인 최적화를 가능케 한다면 이야기가 달라진다. 이는 케이스 바이 케이스로 결정해야 한다.
always_inline 속성은 인라인된 코드가 항상 사용될 때 잘 동작한다. 하지만 그렇지 않다면? 인라인된 함수가 가끔만 호출된다면?
cvoid fct(void) { ... 코드 블록 A ... if (condition) inlfct() ... 코드 블록 C ... }
이런 코드 시퀀스에 대해 생성된 코드는 보통 소스 구조와 일치한다. 즉 코드 블록 A가 먼저, 그 다음 조건부 점프가 오며 조건이 false이면 앞으로 점프한다. 그 다음 인라인된 inlfct에서 나온 코드가 오고 마지막으로 코드 블록 C가 온다. 합리적으로 보이지만 문제가 있다.
조건이 자주 false라면 실행이 선형적이지 않다. 거의 실행되지 않는 큰 코드 덩어리가 중간에 있어, 프리페치 때문에 L1i를 오염시킬 뿐 아니라 분기 예측에도 문제를 일으킬 수 있다. 분기 예측이 틀리면 조건식은 매우 비효율적이 될 수 있다.
이는 인라이닝에만 국한된 문제가 아니다. 조건 실행이 치우쳐(lopsided) 있을 때(즉 어떤 결과가 압도적으로 자주 나올 때) 정적 분기 예측이 틀릴 가능성이 있고, 그 결과 파이프라인에 버블이 생길 수 있다. 이를 막기 위해, 덜 자주 실행되는 코드를 주 코드 경로 밖으로 옮기라고 컴파일러에 알려줄 수 있다. 그러면 if에 대해 생성되는 조건 분기는 다음 그림처럼 순서 밖에 있는 위치로 점프한다.
위쪽은 단순한 코드 레이아웃을 나타낸다. B 영역(예: 위 inlfct 인라인에서 생성된 코드)이 조건 I가 건너뛰기 때문에 자주 실행되지 않으면, 프로세서 프리페치는 드물게 쓰이는 B 블록이 포함된 캐시 라인까지 끌어오게 된다. 블록 재정렬을 사용하면 아래쪽처럼 바꿀 수 있다. 자주 실행되는 코드는 메모리에서 선형으로 배치되고, 드물게 실행되는 코드는 프리페치와 L1i 효율에 해가 되지 않는 곳으로 이동한다.
gcc는 이를 달성하는 두 방법을 제공한다. 첫째, 프로파일링 출력 결과를 반영하여 재컴파일할 때 코드 블록을 프로파일에 맞게 배치할 수 있다(7절에서 본다). 둘째, 명시적 분기 예측이다. gcc는 __builtin_expect를 인식한다.
clong __builtin_expect(long EXP, long C);
이 구문은 EXP가 C 값을 가질 가능성이 가장 높다고 컴파일러에 알려준다. 반환값은 EXP다. __builtin_expect는 조건식에서 사용하도록 의도되었다. 거의 모든 경우 불리언 표현식 맥락에서 쓰이므로, 다음과 같은 헬퍼 매크로를 정의하는 것이 편리하다.
c#define unlikely(expr) __builtin_expect(!!(expr), 0) #define likely(expr) __builtin_expect(!!(expr), 1)
그런 다음 다음과 같이 쓸 수 있다.
cif (likely(a > 1))
프로그래머가 이 매크로를 사용하고 -freorder-blocks 최적화 옵션을 사용하면 gcc는 위 그림처럼 블록을 재정렬한다. 이 옵션은 -O2에서는 활성화되지만 -Os에서는 비활성화된다. 블록을 재정렬하는 또 다른 옵션(-freorder-blocks-and-partition)도 있지만, 예외 처리와 함께 동작하지 않아 유용성이 제한된다.
특정 프로세서에서는 작은 루프에 또 다른 큰 장점이 있다. Intel Core 2 프런트엔드는 Loop Stream Detector(LSD)라는 특수 기능을 가진다. 루프가 18개 이하의 명령(서브루틴 호출이 없어야 함)으로 구성되고, 16바이트 단위 디코더 fetch가 최대 4번이면 되고, 분기 명령이 최대 4개이며, 64회 이상 실행되면, 루프가 때때로 명령 큐에 고정되어 다음에 루프를 사용할 때 더 빨리 사용할 수 있다. 이는 예컨대 바깥 루프를 통해 여러 번 들어가는 작은 내부 루프에 해당한다. 이런 특화 하드웨어가 없더라도, 컴팩트한 루프는 이점이 있다.
인라이닝만이 L1i 최적화의 전부는 아니다. 또 다른 측면은 데이터와 마찬가지로 정렬이다. 하지만 차이도 있다. 코드는 대부분 선형 덩어리이며 주소 공간에 임의로 배치할 수 없고, 컴파일러가 코드를 생성하므로 프로그래머가 데이터처럼 직접 조정할 수 없다. 그래도 프로그래머가 제어할 수 있는 측면이 있다.
각 개별 명령을 정렬하는 것은 의미가 없다. 목표는 명령 스트림이 순차적이 되는 것이다. 따라서 정렬은 전략적 위치에서만 의미가 있다. 어디에 정렬을 추가할지 결정하려면 어떤 이점이 있는지 이해해야 한다. 캐시 라인 시작에 명령이 있으면 {일부 프로세서는 명령에 대해 캐시 라인이 원자 단위가 아니다. Intel Core 2 프런트엔드는 16바이트 블록을 디코더에 발행하며, 적절히 정렬되어 발행된 블록이 캐시 라인 경계를 넘지 않는다. 캐시 라인 시작에 정렬하는 것은 프리페치의 긍정적 효과를 최적화하므로 여전히 이점이 있다.} 해당 캐시 라인 프리페치가 최대화된다. 명령의 경우 이는 디코더 효율도 의미한다. 캐시 라인 끝에 있는 명령이 실행되면, 프로세서는 새 캐시 라인을 읽고 명령을 디코딩할 준비를 해야 한다. 이 과정에서 캐시 미스 같은 문제가 발생할 수 있으므로, 캐시 라인 끝의 명령은 평균적으로 시작 부분의 명령만큼 효과적으로 실행되지 않는다.
여기에 더해, 제어가 막 그 명령으로 옮겨진 경우(즉 프리페치가 효과적이지 않은 경우) 문제가 가장 심하다는 점을 결합하면, 코드 정렬이 가장 유용한 위치에 대한 결론이 나온다.
처음 두 경우 정렬 비용은 작다. 실행이 새 위치에서 시작하므로, 이를 캐시 라인 시작으로 맞추면 프리페치와 디코딩을 최적화한다. {명령 디코딩에서 캐시 라인보다 작은 단위(예: x86/x86-64는 16바이트)를 쓰는 경우가 많다.} 컴파일러는 정렬로 인해 생긴 간격을 채우기 위해 NOP 명령을 삽입해 정렬을 수행한다. 이 “죽은 코드”는 공간을 조금 차지하지만 보통 성능을 해치지는 않는다.
세 번째 경우는 조금 다르다. 모든 루프 시작을 정렬하면 성능 문제가 생길 수 있다. 루프 시작은 종종 다른 코드 다음에 연속으로 오기 때문이다. 운이 나쁘면 이전 명령과 정렬된 루프 시작 사이에 간격이 생긴다. 앞의 두 경우와 달리 이 간격은 완전히 죽은 코드가 될 수 없다. 이전 명령 실행 후에는 루프의 첫 명령을 실행해야 하므로, 이전 명령 뒤에 gap을 채우는 NOP들을 두거나 루프 시작으로 무조건 점프해야 한다. 어느 쪽도 공짜가 아니다. 특히 루프가 자주 실행되지 않으면, NOP나 점프 비용이 정렬로 절약한 것보다 더 클 수 있다.
프로그래머가 코드 정렬에 영향을 줄 수 있는 방법은 세 가지다. 어셈블리로 코드를 쓰면 함수와 모든 명령을 명시적으로 정렬할 수 있다. 모든 아키텍처의 어셈블러는 이를 위해 .align 의사 명령을 제공한다. 고급 언어에서는 소스에서 직접 정렬 요구를 표현할 수 없고(데이터 타입/변수와 다름), 컴파일러 옵션을 사용한다.
-falign-functions=N
이 옵션은 모든 함수를 N보다 큰 가장 가까운 2의 거듭제곱 경계에 정렬한다. 즉 최대 N바이트의 간격이 만들어진다. 작은 함수에 큰 N을 쓰면 낭비다. 드물게 실행되는 코드도 마찬가지다. 이런 일은 인기/비인기 인터페이스가 섞인 라이브러리에서 흔하다. 옵션 값을 현명하게 고르면 속도를 높이거나 정렬을 피해서 메모리를 절약할 수 있다. N에 1을 주거나 -fno-align-functions를 쓰면 모든 정렬이 꺼진다.
두 번째 경우(순차적으로 도달하지 않는 기본 블록 시작)의 정렬은 다른 옵션으로 제어한다.
-falign-jumps=N
다른 세부 사항은 동일하며 메모리 낭비에 대한 경고도 같다.
세 번째 경우도 고유 옵션이 있다.
-falign-loops=N
역시 동일한 세부 사항과 경고가 적용된다. 다만 앞서 설명했듯, 정렬된 주소에 순차적으로 도달하면 NOP나 점프 명령을 실행해야 하므로 런타임 비용이 든다.
gcc에는 정렬 제어에 대한 또 다른 옵션이 있다. 완전성을 위해 언급만 한다. -falign-labels는 코드의 모든 레이블(기본적으로 모든 기본 블록 시작)을 정렬한다. 몇몇 예외적 경우를 제외하면 코드를 느리게 하므로 사용해서는 안 된다.
6.2.3 L2 및 상위 캐시 접근 최적화
L1 캐시 사용 최적화에 대해 말한 모든 것은 L2 및 상위 캐시 접근에도 적용된다. 마지막 레벨 캐시(LLC)에는 두 가지 추가 측면이 있다.
캐시 미스의 높은 비용을 피하려면 작업 집합 크기를 캐시 크기에 맞춰야 한다. 데이터가 한 번만 필요하다면 캐시는 어차피 효과가 없으므로 이런 최적화가 필요 없다는 것은 명백하다. 여기서는 데이터 세트가 한 번 이상 필요할 때의 워크로드를 말한다. 이 경우 작업 집합이 캐시에 들어가지 않게 되면, 프리페치가 성공적으로 수행되더라도 많은 캐시 미스로 인해 프로그램이 느려진다.
데이터 세트가 너무 큰 경우에도 프로그램은 일을 해야 한다. 작업을 캐시 미스를 최소화하는 방식으로 수행하는 것은 프로그래머의 몫이다. 마지막 레벨 캐시에서도 L1과 마찬가지로 더 작은 조각으로 일을 나눠 처리하면 가능하다. 이는 표 6.2의 최적화된 행렬 곱과 매우 유사하다. 다만 마지막 레벨 캐시에서는 작업할 데이터 블록이 더 클 수 있다. L1 최적화까지 동시에 필요하다면 코드는 더 복잡해진다. 예를 들어 입력 두 행렬과 출력 행렬이 함께 마지막 레벨 캐시에 들어가지 않는 행렬 곱을 생각해 보자. 이 경우 L1과 마지막 레벨 캐시 접근을 동시에 최적화하는 것이 적절할 수 있다.
L1 캐시 라인 크기는 보통 여러 프로세서 세대에 걸쳐 일정하다. 변하더라도 차이는 작다. 더 큰 크기를 가정하는 것은 큰 문제가 아니다. 캐시가 더 작은 프로세서에서는 캐시 라인 하나 대신 두 개 이상을 쓰게 된다. 어쨌든 캐시 라인 크기는 하드코딩하고 그에 맞춰 최적화하는 것이 합리적이다.
하지만 상위 캐시는 프로그램이 범용이어야 한다면 그렇지 않다. 상위 캐시 크기는 크게 달라질 수 있다. 8배 이상 차이도 드물지 않다. 가장 큰 캐시 크기를 기본으로 가정할 수는 없다. 그러면 가장 큰 캐시를 가진 머신을 제외하고는 모두에서 성능이 나빠진다. 반대 선택도 나쁘다. 가장 작은 캐시를 가정하면 캐시의 87% 이상을 버리는 셈이다. 이는 그림 3.14에서 보았듯 큰 캐시가 속도에 큰 영향을 줄 수 있으므로 좋지 않다.
이는 코드가 캐시 크기에 맞춰 동적으로 스스로를 조정해야 함을 뜻한다. 이는 프로그램에 특화된 최적화다. 여기서 말할 수 있는 것은, 프로그래머가 프로그램 요구량을 정확히 계산해야 한다는 점뿐이다. 데이터 세트 자체뿐 아니라 상위 캐시는 다른 용도로도 쓰인다. 예컨대 실행되는 명령도 캐시에서 로드된다. 라이브러리 함수를 사용하면 이 캐시 사용이 상당할 수 있다. 라이브러리 함수도 자체 데이터가 필요할 수 있어 사용 가능한 메모리를 더 줄인다.
메모리 요구량을 위한 공식이 있으면 캐시 크기와 비교할 수 있다. 앞서 말했듯 캐시는 여러 코어가 공유할 수 있다. 현재 {분명 곧 더 나은 방법이 생길 것이다!} 하드코딩 없이 올바른 정보를 얻는 유일한 방법은 /sys 파일시스템을 통한 것이다. 표 5.2에서 커널이 하드웨어에 대해 무엇을 공개하는지 보았다. 프로그램은 마지막 레벨 캐시에 대해 다음 디렉터리를 찾아야 한다.
/sys/devices/system/cpu/cpu*/cache
이는 그 디렉터리의 level 파일에서 가장 높은 숫자 값을 가진 것으로 인식할 수 있다. 디렉터리를 찾았으면 size 파일 내용을 읽고 shared_cpu_map 파일의 비트마스크에서 1로 설정된 비트 수로 그 숫자를 나눈다.
이렇게 계산한 값은 안전한 하한이다. 때로 프로그램은 다른 스레드/프로세스의 동작에 대해 더 알고 있을 수 있다. 그 스레드들이 같은 캐시를 공유하는 코어/하이퍼스레드에 스케줄되고, 캐시 사용이 총 캐시의 “할당 몫”을 소진하지 않는다고 안다면, 계산된 하한은 최적에 비해 너무 낮을 수 있다. 공정한 몫보다 더 쓸지는 상황에 달렸다. 프로그래머가 선택해야 하거나 사용자에게 결정하게 해야 한다.
6.2.4 TLB 사용 최적화
TLB 사용 최적화에는 두 가지가 있다. 첫째는 프로그램이 사용해야 하는 페이지 수를 줄이는 것이다. 이는 자동으로 TLB 미스 수를 줄인다. 둘째는 할당해야 하는 상위 디렉터리 테이블 수를 줄여 TLB 조회를 더 싸게 만드는 것이다. 테이블이 적을수록 메모리 사용이 줄어, 디렉터리 조회에 대한 캐시 히트율이 올라갈 수 있다.
첫 번째 최적화는 페이지 폴트 최소화와 밀접하다. 이는 7.5절에서 자세히 다룰 것이다. 페이지 폴트는 보통 일회성 비용이지만, TLB 미스는 TLB 캐시가 보통 작고 자주 플러시되므로 지속적인 페널티다. 페이지 폴트는 TLB 미스보다 자릿수가 다르게 비싸지만, 프로그램이 충분히 오래 실행되고 특정 부분이 충분히 자주 실행되면 TLB 미스가 페이지 폴트 비용을 상회할 수도 있다. 따라서 페이지 최적화는 페이지 폴트 관점뿐 아니라 TLB 미스 관점에서도 보아야 한다. 차이는 페이지 폴트 최적화는 코드와 데이터의 페이지 단위 그룹화만 필요하지만, TLB 최적화는 어떤 시점이든 가능한 한 적은 TLB 엔트리만 사용하도록 요구한다.
두 번째 TLB 최적화는 제어하기가 더 어렵다. 사용해야 하는 페이지 디렉터리 수는 프로세스 가상 주소 공간에서 사용된 주소 범위의 분포에 달려 있다. 주소 공간에서 넓게 흩어진 위치를 쓰면 더 많은 디렉터리가 필요하다. 또 하나의 복잡함은 ASLR(Address Space Layout Randomization)이 정확히 이런 상황을 만든다는 것이다. 공격자가 함수/변수 주소를 추측하지 못하게 하려는 목적에서, 스택/DSO/힙/실행 파일의 로드 주소가 런타임에 무작위화된다.
최대 성능을 위해서는 ASLR을 끄는 것이 분명 좋다. 하지만 추가 디렉터리로 인한 비용은 보통 충분히 낮아, 극단적인 경우가 아니면 이 단계는 불필요하다. 커널이 언제든 수행할 수 있는 한 가지 최적화는, 단일 매핑이 두 디렉터리 사이의 주소 공간 경계를 넘지 않도록 보장하는 것이다. 이는 ASLR을 최소한으로만 제한하며 보안을 크게 약화시키지는 않을 것이다.
프로그래머가 이에 직접 영향을 받는 유일한 경우는 주소 공간 영역을 명시적으로 요청할 때다. 이는 mmap에서 MAP_FIXED를 사용할 때 발생한다. 이렇게 새 주소 공간 영역을 할당하는 것은 매우 위험하며 거의 하지 않는다. 하지만 가능하며, 사용한다면 마지막 레벨 페이지 디렉터리 경계를 알고 요청 주소를 적절히 선택해야 한다.
프리페치의 목적은 메모리 접근의 지연(latency)을 숨기는 것이다. 오늘날 프로세서의 명령 파이프라인과 OOO(out-of-order) 실행 능력은 일부 지연을 숨길 수 있지만, 최대로 해봐야 캐시에 히트하는 접근에 대해서만 가능하다. 메인 메모리 접근 지연을 가리려면 명령 큐가 믿기 어려울 만큼 길어야 한다. OOO가 없는 일부 프로세서는 코어 수를 늘려 보완하려 하지만, 사용되는 코드가 모두 병렬화되어 있지 않다면 나쁜 트레이드오프다.
프리페치는 지연을 추가로 숨길 수 있다. 프로세서는 특정 사건에 의해 스스로 프리페치를 수행(하드웨어 프리페치)하거나, 프로그램이 명시적으로 요청(소프트웨어 프리페치)할 수 있다.
6.3.1 하드웨어 프리페치
하드웨어 프리페치의 트리거는 보통 특정 패턴의 두 번 이상의 캐시 미스 시퀀스다. 이 캐시 미스는 연속하는(또는 바로 앞의) 캐시 라인에 대해 발생할 수 있다. 오래된 구현은 인접 캐시 라인에 대한 미스만 인식했다. 현대 하드웨어는 stride도 인식한다. 즉 고정된 수의 캐시 라인을 건너뛰는 것도 패턴으로 인식해 처리한다.
모든 캐시 미스가 하드웨어 프리페치를 트리거한다면 성능에 나쁘다. 예컨대 전역 변수 같은 랜덤 메모리 접근은 흔하며, 그로 인한 프리페치는 대부분 FSB 대역폭을 낭비한다. 그래서 프리페치를 시작(kickstart)하려면 최소 두 번의 캐시 미스가 필요하다. 오늘날 프로세서는 메모리 접근 스트림이 하나 이상이라고 가정한다. 프로세서는 각 캐시 미스를 이런 스트림 중 하나에 자동으로 할당하려 하고, 임계값에 도달하면 하드웨어 프리페치를 시작한다. 요즘 CPU는 상위 캐시에 대해 8~16개의 별도 스트림을 추적할 수 있다.
패턴 인식을 담당하는 유닛은 해당 캐시에 연관된다. L1d와 L1i에 프리페치 유닛이 있을 수 있고, L2 및 상위에도 프리페치 유닛이 있을 가능성이 크다. L2 및 상위 프리페치 유닛은 같은 캐시를 사용하는 다른 코어와 하이퍼스레드와 공유된다. 따라서 8~16개라는 스트림 수는 금방 줄어든다.
프리페치의 큰 약점 하나는 페이지 경계를 넘을 수 없다는 점이다. 이유는 CPU가 수요 페이징(demand paging)을 지원한다는 점을 떠올리면 명백하다. 프리페처가 페이지 경계를 넘어가도록 허용하면 OS 이벤트를 트리거해 페이지를 사용 가능하게 해야 할 수 있다. 이는 그 자체로(특히 성능 측면에서) 나쁠 수 있다. 더 나쁜 것은 프리페처가 프로그램이나 OS의 의미론을 모른다는 점이다. 따라서 현실에서는 결코 요청되지 않을 페이지를 프리페치할 수도 있다. 즉 프로세서가 이전에 인식 가능한 패턴으로 접근했던 메모리 영역 끝을 넘어 계속 프리페치해 버릴 수 있다. 이는 가능할 뿐 아니라 매우 그럴듯하다. 프리페치의 부작용으로 그런 페이지 요청을 트리거한다면, 정상적으로는 일어나지 않을 요청 때문에 OS가 완전히 엉망이 될 수도 있다.
따라서 프리페처가 패턴을 얼마나 잘 예측하든, 프로그램은 페이지 경계에서 캐시 미스를 겪을 수밖에 없다는 점을 이해하는 것이 중요하다(명시적으로 프리페치하거나 새 페이지에서 읽기를 수행하지 않는 한). 이는 6.2절에서 설명한 대로 관련 없는 데이터를 배제해 캐시 오염을 최소화하도록 데이터 레이아웃을 최적화해야 하는 또 다른 이유다.
이런 페이지 제한 때문에 프로세서는 프리페치 패턴을 인식하는 데 지나치게 복잡한 로직을 두지 않는다. 여전히 4k 페이지 크기가 지배적인 상황에서는 의미가 있는 범위가 제한적이다. stride 인식 범위는 시간이 지나며 늘었지만, 오늘날 흔히 쓰는 512바이트 윈도우를 넘는 것은 크게 의미가 없을 것이다. 현재 프리페치 유닛은 비선형 접근 패턴을 인식하지 못한다. 그런 패턴은 진짜 랜덤이거나, 적어도 반복성이 낮아 인식할 의미가 없는 경우가 더 많기 때문이다.
하드웨어 프리페치가 우연히 트리거되어 성능을 망친다면 할 수 있는 일은 제한적이다. 한 가지 가능성은 문제를 감지하고 데이터/코드 레이아웃을 약간 바꿔보는 것이다. 하지만 어려울 가능성이 높다. x86/x86-64에서 ud2 명령 {또는 비-명령. 권장되는 미정의 opcode다.}을 간접 점프 뒤에 두는 것 같은 특수한 국소 해법이 있을 수 있다. 이는 명령 페처에 “이후 메모리를 디코딩하려고 노력하지 말라, 실행은 다른 위치로 계속된다”는 신호로 쓰인다. 하지만 매우 특수한 상황이다. 대부분은 이 문제를 감수해야 한다.
프로세서 전체에 대해 하드웨어 프리페치를 완전히 또는 부분적으로 비활성화할 수도 있다. Intel 프로세서에서는 이를 위해 MSR(Model Specific Register)이 사용된다(많은 프로세서에서 IA32_MISC_ENABLE의 비트 9; 비트 19는 인접 캐시 라인 프리페치만 비활성화). 이는 보통 특권 연산이므로 커널에서 수행해야 한다. 프로파일링 결과 중요한 애플리케이션이 하드웨어 프리페치 때문에 대역폭 고갈과 조기 캐시 축출을 겪는 것으로 나타난다면, 이 MSR 사용은 한 가지 선택지다.
6.3.2 소프트웨어 프리페치
하드웨어 프리페치의 장점은 프로그램을 조정할 필요가 없다는 점이다. 단점은 방금 설명했듯 접근 패턴이 단순해야 하고, 페이지 경계를 넘어 프리페치할 수 없다는 점이다. 이런 이유로 우리는 더 많은 가능성을 갖게 되는데, 그중 가장 중요한 것이 소프트웨어 프리페치다. 소프트웨어 프리페치는 특수 명령을 삽입하기 위해 소스 코드를 수정해야 한다. 일부 컴파일러는 프라그마로 어느 정도 자동으로 프리페치 명령을 삽입하는 기능을 지원한다. x86/x86-64에서는 Intel의 관례에 따른 컴파일러 intrinsic이 일반적으로 사용된다.
c#include <xmmintrin.h> enum _mm_hint { _MM_HINT_T0 = 3, _MM_HINT_T1 = 2, _MM_HINT_T2 = 1, _MM_HINT_NTA = 0 }; void _mm_prefetch(void *p, enum _mm_hint h);
프로그램은 어떤 포인터에도 _mm_prefetch intrinsic을 사용할 수 있다. 대부분의 프로세서(확실히 x86/x86-64)는 잘못된 포인터로 인한 오류를 무시하므로 프로그래머는 훨씬 편하다. 다만 전달된 포인터가 유효한 메모리를 가리킨다면 프리페치 유닛은 데이터를 캐시에 로드하고 필요하면 다른 데이터를 축출한다. 불필요한 프리페치는 반드시 피해야 한다. 캐시 효율을 떨어뜨리고 메모리 대역폭을 소비하기 때문이며(축출된 캐시 라인이 더티면, 두 캐시 라인에 대해 대역폭을 쓸 수도 있다).
_mm_prefetch와 함께 쓰는 다양한 힌트는 구현 정의(implementation defined)다. 즉 프로세서 버전마다 (약간씩) 다르게 구현할 수 있다. 일반적으로 _MM_HINT_T0는 inclusive 캐시에서는 모든 캐시 레벨로, exclusive 캐시에서는 가장 낮은 레벨 캐시로 데이터를 가져온다. 데이터 항목이 상위 레벨 캐시에 있으면 L1d로 로드된다. _MM_HINT_T1은 데이터를 L2로 끌어오되 L1d로는 넣지 않는다. L3가 있다면 _MM_HINT_T2도 비슷한 일을 할 수 있다. 다만 이런 세부 사항은 약하게만 규정되므로 실제 사용 프로세서에서 검증해야 한다. 일반적으로 데이터를 곧바로 사용할 것이라면 _MM_HINT_T0가 옳다. 물론 이는 L1d 캐시 크기가 프리페치된 데이터를 모두 담을 만큼 충분하다는 것을 전제로 한다. 즉시 사용하는 작업 집합이 너무 크다면, 모든 것을 L1d로 프리페치하는 것은 나쁜 생각이며 다른 두 힌트를 써야 한다.
네 번째 힌트 _MM_HINT_NTA는 특별하다. 이는 6.1절에서 설명한 비시간적(non-temporal aligned)과 관련된다. 데이터가 잠깐만 사용되므로 캐시 오염을 가능한 한 피하라는 뜻을 프로세서에 전달한다. 따라서 inclusive 캐시 구현에서는 로드시 낮은 레벨 캐시로 데이터를 읽어들이지 않도록 할 수 있다. 데이터가 L1d에서 축출될 때 L2 이상으로 밀어 넣지 않고 메모리로 바로 쓸 수도 있다. 이 힌트가 주어졌을 때 프로세서 설계자들이 사용할 수 있는 다른 트릭도 있을 수 있다. 하지만 이 힌트 사용 시 프로그래머는 주의해야 한다. 즉시 작업 집합이 너무 커서 NTA 힌트로 로드된 캐시 라인이 축출되면, 재로드는 메모리에서 일어나게 된다.
그림 6.7: 프리페치 적용 평균, NPAD=31
그림 6.7은 익숙한 포인터 추적(pointer chasing) 프레임워크를 사용한 테스트 결과다. 리스트는 랜덤화되어 있다. 이전 테스트와의 차이는 프로그램이 각 리스트 노드에서 실제로 시간을 좀 소비한다는 점(약 160사이클)이다. 그림 3.15의 데이터에서 배웠듯, 작업 집합 크기가 마지막 레벨 캐시보다 커지면 성능이 크게 나빠진다.
이제 계산보다 앞서 프리페치 요청을 발행해 상황을 개선할 수 있다. 즉 루프의 각 라운드에서 리스트의 새 원소를 프리페치한다. 프리페치된 노드와 현재 작업 중인 노드 사이 거리는 신중히 선택해야 한다. 각 노드를 160사이클 동안 처리하고 두 캐시 라인(NPAD=31)을 프리페치해야 하므로, 리스트 요소 5개 정도의 거면 충분하다.
그림 6.7은 프리페치가 실제로 도움이 됨을 보여준다. 작업 집합 크기가 마지막 레벨 캐시(머신은 512kB=2^19B의 L2)를 넘지 않는 동안 수치는 동일하다. 프리페치 명령은 측정 가능한 추가 부담을 주지 않는다. L2 크기를 넘는 순간 프리페치는 50~60사이클, 최대 8%를 절약한다. 프리페치로 모든 페널티를 숨길 수는 없지만 어느 정도는 도움이 된다.
AMD는 Opteron 라인 family 10h에서 prefetchw라는 또 다른 명령을 구현한다. 이는 현재 Intel 쪽에 대응이 없고 intrinsic으로도 제공되지 않는다. prefetchw는 다른 프리페치 명령처럼 캐시 라인을 L1로 프리페치하지만, 즉시 ‘M’ 상태로 둔다는 점이 다르다. 이후에 실제 쓰기가 없다면 단점이 된다. 하지만 하나 이상의 쓰기가 있다면, 캐시 상태를 바꿀 필요가 없어 쓰기가 빨라진다(프리페치 시 이미 바뀌었다).
프리페치는 여기서 얻은 8%라는 작은 이득보다 더 큰 이점을 제공할 수 있다. 하지만 제대로 하기는 악명 높게 어렵다. 특히 같은 바이너리가 다양한 머신에서 잘 성능을 내야 한다면 더 그렇다. CPU가 제공하는 성능 카운터는 프리페치 분석에 도움 된다. 하드웨어 프리페치, 소프트웨어 프리페치, 유효한 소프트웨어 프리페치, 각 레벨의 캐시 미스 등 다양한 이벤트를 카운트/샘플링할 수 있다. 7.1절에서 일부 이벤트를 소개한다. 이 카운터들은 머신 종속적이다.
프로그램을 분석할 때는 먼저 캐시 미스를 봐야 한다. 캐시 미스의 큰 원인을 찾았으면 문제의 메모리 접근에 프리페치 명령을 추가해 보라. 한 번에 한 곳씩 해야 한다. 각 수정의 결과는 유효한 프리페치 명령을 측정하는 성능 카운터를 관찰하며 확인해야 한다. 그 카운터가 늘지 않는다면 프리페치가 잘못되었거나, 메모리에서 로드할 시간이 충분하지 않거나, 프리페치가 아직 필요한 데이터를 캐시에서 축출하고 있을 수 있다.
오늘날 gcc는 한 가지 상황에서는 자동으로 프리페치 명령을 생성할 수 있다. 루프가 배열을 순회한다면 다음 옵션을 사용할 수 있다.
-fprefetch-loop-arrays
컴파일러는 프리페치가 의미가 있는지와 그렇다면 얼마나 앞서 볼지 결정한다. 작은 배열에는 불리할 수 있으며, 배열 크기를 컴파일 타임에 모르면 결과가 나빠질 수 있다. gcc 매뉴얼은 이득이 코드 형태에 크게 의존하고, 어떤 상황에서는 코드가 더 느려질 수도 있다고 경고한다. 프로그래머는 이 옵션을 신중하게 써야 한다.
6.3.3 프리페치의 특별한 형태: 추측(speculation)
프로세서의 OOO 실행 능력은 서로 충돌하지 않는다면 명령을 재배치할 수 있게 한다. 예를 들어(이번에는 IA-64로 예시):
st8 [r4] = 12 add r5 = r6, r7;; st8 [r18] = r5
이 코드는 레지스터 r4가 지정한 주소에 12를 저장하고, r6와 r7을 더해 r5에 저장한 다음, r18 주소에 그 합을 저장한다. 요점은 add 명령이 데이터 의존성이 없으므로 첫 st8보다 먼저(또는 동시에) 실행될 수 있다는 것이다. 하지만 피연산자 중 하나를 로드해야 한다면 어떻게 될까?
st8 [r4] = 12 ld8 r6 = [r8];; add r5 = r6, r7;; st8 [r18] = r5
추가된 ld8는 r8이 지정하는 주소에서 값을 로드한다. 이 로드와 다음 add 사이에는 명백한 데이터 의존성이 있다(그래서 ;;가 있다). 여기서 중요한 점은 새 ld8가 add와 달리 첫 st8 앞으로 옮겨질 수 없다는 것이다. 프로세서는 디코딩 중에 store와 load가 충돌하는지(즉 r4와 r8이 같은 값일 수 있는지)를 충분히 빨리 결정할 수 없다. 만약 동일하다면 st8이 r6로 로드될 값을 결정한다. 더 나쁜 것은 ld8가 캐시 미스 시 큰 지연을 가져올 수 있다는 점이다. IA-64는 이 경우를 위해 추측적 로드(speculative load)를 지원한다.
ld8.a r6 = [r8];; [... other instructions ...] st8 [r4] = 12 ld8.c.clr r6 = [r8];; add r5 = r6, r7;; st8 [r18] = r5
새 ld8.a와 ld8.c.clr 명령은 짝을 이루며, 이전 코드의 ld8를 대체한다. ld8.a는 추측적 로드다. 값은 즉시 사용할 수 없지만 프로세서는 작업을 시작할 수 있다. ld8.c.clr에 도달했을 때(사이에 충분한 명령이 있다면) 내용이 이미 로드되어 있을 수 있다. 이 명령의 인자는 ld8.a와 일치해야 한다. 앞의 st8가 값을 덮어쓰지 않았다면(r4와 r8이 같지 않다면) 아무 것도 할 필요가 없다. 추측적 로드가 제 역할을 했고 로드 지연은 숨겨진다. store와 load가 충돌한다면 ld8.c.clr이 메모리에서 값을 다시 로드해, 정상 ld8의 의미론을 얻게 된다.
추측적 로드는 (아직?) 널리 쓰이지 않는다. 하지만 이 예에서 보듯 지연을 숨기는 단순하면서도 효과적인 방법이다. 프리페치는 사실상 동등하며, 레지스터가 적은 프로세서에서는 추측적 로드가 큰 의미가 없을 수 있다. 추측적 로드는 값을 캐시 라인이 아니라 레지스터에 직접 로드한다는 (때로 큰) 장점이 있다. 예컨대 스레드가 디스케줄되면 캐시 라인이 다시 축출될 수 있기 때문이다. 추측이 가능하다면 사용해야 한다.
6.3.4 도우미 스레드
소프트웨어 프리페치를 쓰려 하면 코드 복잡도 문제에 자주 부딪힌다. 리스트 같은 데이터 구조를 순회해야 한다면, 동일한 루프 안에서 두 개의 독립적인 순회를 구현해야 한다. 하나는 일을 하는 정상 순회, 다른 하나는 앞을 내다보며 프리페치하는 순회다. 이는 쉽게 복잡해져 실수가 발생하기 쉽다.
또한 얼마나 앞을 볼지 결정해야 한다. 너무 가까우면 제때 메모리가 로드되지 않는다. 너무 멀면 방금 로드한 데이터가 이미 축출되었을 수 있다. 또 다른 문제는 프리페치 명령이 메모리 로드를 기다리며 블록되지는 않더라도 시간이 든다는 점이다. 명령은 디코딩되어야 하며, 예컨대 잘 작성/생성된 코드 때문에 디코더가 바쁘면 눈에 띌 수 있다. 마지막으로 루프의 코드 크기가 증가해 L1i 효율이 떨어진다. 이 비용 일부를 피하려고 여러 프리페치를 연속으로 발행하면(두 번째 로드가 첫 결과에 의존하지 않는다면) 미해결 프리페치 요청 수와 관련한 문제에 부딪힐 수 있다.
대안 접근은 정상 동작과 프리페치를 완전히 분리하는 것이다. 이는 두 개의 일반 스레드를 사용해 가능하다. 두 스레드는 프리페치 스레드가 두 스레드가 공유하는 캐시를 채우도록 스케줄되어야 한다. 언급할 만한 두 가지 특수 해법이 있다.
하이퍼스레드 사용은 특히 흥미롭다. 그림 3.22에서 보았듯, 하이퍼스레드가 독립 코드를 실행하면 캐시 공유는 문제가 된다. 하지만 한 스레드를 프리페치 도우미 스레드로 쓰면 문제가 아니다. 오히려 가장 낮은 레벨 캐시를 미리 채우는 것이 의도된 효과다. 또한 프리페치 스레드는 대부분 유휴이거나 메모리를 기다리므로, 다른 하이퍼스레드의 정상 동작은(스스로 메인 메모리에 접근할 필요가 없다면) 크게 방해받지 않는다. 그리고 그 “스스로 메인 메모리에 접근할 필요”를 줄여주는 것이 바로 프리페치 도우미 스레드다.
유일하게 까다로운 부분은 도우미 스레드가 너무 앞서 달리지 않게 하는 것이다. 캐시를 완전히 오염시켜 가장 오래된 프리페치 값이 다시 축출되면 안 된다. Linux에서는 futex 시스템 콜([futexes])이나, 조금 더 비용이 들지만 POSIX 스레드 동기화 프리미티브를 사용해 쉽게 동기화할 수 있다.
그림 6.8: 도우미 스레드 적용 평균, NPAD=31
이 접근의 이점은 그림 6.8에서 볼 수 있다. 이는 그림 6.7과 같은 테스트에 추가 결과를 더한 것이다. 새 테스트는 약 100개 리스트 엔트리 앞에서 달리는 도우미 스레드를 추가로 만들고, 각 리스트 원소의 모든 캐시 라인을 (프리페치뿐 아니라) 읽는다. 이 경우 리스트 원소당 두 캐시 라인이 있다(64바이트 캐시 라인 크기의 32비트 머신에서 NPAD=31).
두 스레드는 같은 코어의 두 하이퍼스레드에 스케줄된다. 테스트 머신은 코어가 하나뿐이지만, 코어가 더 있어도 결과는 비슷할 것이다. 6.4.3절에서 소개할 affinity 함수를 사용해 스레드를 해당 하이퍼스레드에 고정한다.
OS가 어떤 프로세서(둘 이상)를 하이퍼스레드로 알고 있는지 결정하려면 libNUMA의 NUMA_cpu_level_mask 인터페이스를 사용할 수 있다(12절 참조).
c#include <libNUMA.h> ssize_t NUMA_cpu_level_mask(size_t destsize, cpu_set_t *dest, size_t srcsize, const cpu_set_t*src, unsigned int level);
이 인터페이스는 캐시와 메모리를 통해 CPU들이 어떻게 연결되어 있는지에 대한 계층을 알아내는 데 쓰인다. 여기서 관심 있는 것은 레벨 1로, 하이퍼스레드에 해당한다. 두 스레드를 두 하이퍼스레드에 스케줄하려면 다음 libNUMA 함수를 쓸 수 있다(간결성을 위해 오류 처리는 생략).
ccpu_set_t self; NUMA_cpu_self_current_mask(sizeof(self), &self); cpu_set_t hts; NUMA_cpu_level_mask(sizeof(hts), &hts, sizeof(self), &self, 1); CPU_XOR(&hts, &hts, &self);
이 코드 실행 후 CPU 비트셋 두 개를 얻는다. self는 현재 스레드의 affinity 설정에 쓸 수 있고, hts 마스크는 도우미 스레드 affinity 설정에 쓸 수 있다. 이는 이상적으로 스레드를 생성하기 전에 일어나야 한다. 6.4.3절에서 affinity 설정 인터페이스를 소개한다. 하이퍼스레드가 없으면 NUMA_cpu_level_mask는 1을 반환한다. 이를 이 최적화를 피할 신호로 쓸 수 있다.
이 벤치마크 결과는 놀라울 수 있다(혹은 아닐 수도). 작업 집합이 L2에 들어가면 도우미 스레드 오버헤드 때문에 성능이 10~60% 떨어진다(작은 작업 집합 크기는 노이즈가 크니 무시). 데이터가 이미 L2에 있다면 프리페치 도우미 스레드는 기여 없이 시스템 자원만 쓰기 때문이니 예상할 수 있는 일이다.
하지만 L2 크기를 넘으면 그림이 바뀐다. 도우미 스레드는 실행 시간을 약 25% 줄여준다. 여전히 상승 곡선이 보이는 것은 프리페치가 충분히 빠르게 처리될 수 없기 때문이다. 그러나 메인 스레드의 산술 연산과 도우미 스레드의 메모리 로드는 서로 보완된다. 자원 충돌이 최소이므로 이런 시너지 효과가 생긴다.
이 테스트의 결과는 많은 다른 상황에도 적용될 수 있다. 하이퍼스레드는 캐시 오염 때문에 종종 유용하지 않지만, 이런 상황에서는 빛나며 활용해야 한다. sys 파일시스템을 통해 프로그램은 thread_siblings(표 5.3의 thread_siblings 열 참조)를 찾을 수 있다. 이 정보를 얻으면, 프로그램은 스레드 affinity를 정의한 뒤 루프를 두 모드로 실행하면 된다: 정상 동작과 프리페치. 프리페치할 메모리 양은 공유 캐시 크기에 따라야 한다. 이 예에서는 L2 크기가 중요하며, 프로그램은 다음을 사용해 크기를 질의할 수 있다.
csysconf(_SC_LEVEL2_CACHE_SIZE)
도우미 스레드의 진행을 제한해야 할지는 프로그램에 달렸다. 일반적으로 스케줄링 세부 사항이 큰 성능 저하를 유발할 수 있으므로 어느 정도 동기화를 두는 것이 최선이다.
6.3.5 직접 캐시 접근
현대 OS에서 캐시 미스의 한 원천은 들어오는 데이터 트래픽 처리다. 현대 하드웨어(네트워크 인터페이스 카드(NIC), 디스크 컨트롤러 등)는 CPU를 거치지 않고 수신/읽은 데이터를 메모리에 직접 쓸 수 있다. 이는 오늘날 장치의 성능에 필수지만 문제도 만든다. 네트워크에서 들어오는 패킷을 생각해 보자. OS는 패킷 헤더를 보고 어떻게 처리할지 결정해야 한다. NIC는 패킷을 메모리에 배치한 다음 도착을 프로세서에 알린다. 프로세서는 데이터가 언제 도착할지, 그리고 어디에 저장될지조차 모를 수 있으므로 프리페치할 기회가 없다. 그 결과 헤더를 읽을 때 캐시 미스가 난다.
Intel은 이를 완화하기 위한 기술을 칩셋과 CPU에 추가했다([directcacheaccess]). 아이디어는 패킷 데이터로, 패킷 도착 통지를 받게 될 CPU의 캐시를 미리 채우는 것이다. 여기서는 페이로드는 중요하지 않다. 이 데이터는 일반적으로 커널이나 사용자 레벨에서 상위 계층 함수들이 처리한다. 패킷 헤더는 처리 경로를 결정하는 데 쓰이므로 즉시 필요하다.
네트워크 I/O 하드웨어는 이미 DMA로 패킷을 쓴다. 즉 메모리 컨트롤러(노스브리지에 통합되어 있을 수 있음)와 직접 통신한다. 메모리 컨트롤러의 다른 한쪽은 FSB를 통해 프로세서와 연결된다(메모리 컨트롤러가 CPU 자체에 통합되어 있지 않다고 가정).
Direct Cache Access(DCA)의 아이디어는 NIC와 메모리 컨트롤러 사이 프로토콜을 확장하는 것이다. 그림 6.9의 첫 그림은 노스/사우스브리지를 갖는 일반 머신에서 DMA 전송이 시작되는 모습을 보여준다.
DMA 시작됨 / DMA 및 DCA 실행됨
그림 6.9: Direct Cache Access
NIC는 사우스브리지에 연결되어(또는 일부로서) 존재한다. DMA 접근을 시작하면서, 패킷 헤더에 대한 새 정보를 제공해 프로세서 캐시에 밀어 넣도록 한다.
전통적 동작에서는 2단계에서 메모리로의 연결을 통해 DMA 전송을 단순히 완료한다. DCA 플래그가 설정된 DMA 전송에서는 노스브리지가 추가로 특수한 새 DCA 플래그를 붙여 데이터를 FSB로 보낸다. 프로세서는 항상 FSB를 스누핑하며, DCA 플래그를 인식하면 해당 프로세서로 향하는 데이터를 가장 낮은 캐시로 로드하려 한다. DCA 플래그는 사실 힌트이므로, 프로세서는 이를 자유롭게 무시할 수 있다. DMA 전송이 끝나면 프로세서에 신호가 간다.
OS는 패킷을 처리할 때 먼저 어떤 종류의 패킷인지 결정해야 한다. DCA 힌트가 무시되지 않았다면, 패킷 식별을 위해 OS가 수행해야 하는 로드는 높은 확률로 캐시에 히트한다. 패킷당 수백 사이클 절약을, 초당 처리 가능한 수만 패킷에 곱하면, 특히 지연(latency) 측면에서 매우 의미 있는 절감이 된다.
이런 최적화는 I/O 하드웨어(NIC), 칩셋, CPU의 통합 없이는 불가능하다. 따라서 이 기술이 필요하다면 플랫폼을 현명하게 선택해야 한다.
| 이 글의 인덱스 엔트리 |
|---|
| GuestArticles |
![Image 2: [formula]](https://static.lwn.net/images/cpumemory/matrixmult.png)
![Image 3: [formula]](https://static.lwn.net/images/cpumemory/matrixmultT.png)
