소프트웨어 메모리 프리페칭
CPU 데이터 프리페처가 메모리 접근 패턴을 파악하지 못할 때 소프트웨어 프리페칭이 유용합니다. 핵심은 CPU에 다음과 같이 알려 주는 특수 명령어를 사용하는 것입니다. "이 메모리 위치를 조금 뒤에 사용할 예정입니다. 제가 다른 작업을 하는 동안 미리 가져와 주시겠습니까? 그러면 제가 돌아왔을 때 바로 쓸 수 있도록 준비되어 있을 것입니다."
GCC와 Clang에서는 __builtin_prefetch를 사용하여 CPU에
데이터 프리페치를 요청할 수 있습니다. 예를 들어, index가
임의의 수일 때 배열 원소 my_array[index]에 접근하려 한다고
가정합시다. 이를 프리페치하려면
__builtin_prefetch(&my_array[index]); 또는
__builtin_prefetch(&my_array + index);를
사용합니다.
프리페칭은 성능을 높일 수도 있지만 오히려 떨어뜨릴 수도 있습니다. 접근하려는 데이터가 데이터 캐시에 없으면 성능에 도움이 됩니다. 데이터가 캐시에 있으면 성능을 떨어뜨립니다. 따라서 대부분의 경우 트리나 해시 맵처럼 큰 자료 구조에 무작위 메모리 접근이 있을 때 효과를 봅니다.
프리페칭으로 속도 향상을 얻기 위한 또 하나의 전제 조건은 프리페칭을 요청한 시점과 실제로 데이터에 접근하는 시점 사이에 어느 정도 시간이 지나야 한다는 것입니다(이를 "프리페칭 윈도"라고 합니다). 프리페치하려는 데이터에 곧바로 접근하면 기대한 결과를 얻을 수 없습니다.
작성자: @ibogosavljevic
힌트
힌트 1:
입력이 무작위이기 때문에 하드웨어 프리페처는 이후 루프 반복에서 필요할 데이터를 미리 적재해 주지 못합니다. 따라서 컴파일러 내장 함수를 통한 소프트웨어 프리페칭으로 이를 직접 처리해야 합니다.
힌트 2:
데이터를 프리페치하도록 루프를 수정할 때 고려해야 할 몇 가지 단계가 있습니다.
- 프리페칭하는 데이터를 충분히 일찍 적재하십시오. 데이터의 적재와 사용 사이에는 반드시 확보해야 하는 프리페칭 윈도가 있습니다. 이 윈도는 메모리 주소가 알려지는 순간부터 그 주소의 데이터가 필요해지는 시점까지의 시간입니다. 이 간격이 너무 짧으면 비순차(Out-Of-Order) CPU 엔진이 프리페칭을 수행할 수 없습니다.
- 데이터는 가능한 한 가장 늦은 시점에 프리페칭해야 합니다. 이러한 프리페칭 때문에 중간 루프 반복에 필요한 데이터가 캐시에서 축출될 수 있고, 이는 다시 이후의 캐시 미스로 인한 오버헤드를 더할 수 있기 때문입니다.
- 이미 캐시에 있을 가능성이 높은 데이터는 적재하지 마십시오.
힌트 3:
각 반복에서 적절한 "스텝" 크기를 실험해 보면서, 지금으로부터 N번째 반복 뒤에 사용될 값에 대해 프리페칭 요청을 보내 보십시오. 위에서 제시한 기준에 맞도록 N을 조정해 보십시오.
풀이:
배경:
이 실습에는 크기가 약 32MB인 큰 해시 맵이 있습니다. 이 크기로는 전체가 캐시에 들어가지 않습니다. 따라서 DRAM 조회가 필요한 캐시 미스가 불가피하게 여러 번 발생합니다.
먼저 pmu-tools의 toplev.py를 사용하여 이
실습을 살펴보면(예를 들어 컴퓨터에 pmu-tools가 설치되어
있다면 이 실습의 build 디렉터리에서
YOUR/PATH/TO/toplev.py --core S0-C0 --run-sample -l2 -v --no-desc taskset -c 0 ./lab를
실행하십시오):
-----------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------
bench1 96.2 ms 96.1 ms 7
...
C0 FE Frontend_Bound % Slots 21.1 [ 8.0%]
C0 BAD Bad_Speculation % Slots 8.5 < [ 8.0%]
C0 BE Backend_Bound % Slots 52.9 [ 8.0%]
C0 RET Retiring % Slots 17.4 < [ 8.0%]
C0 FE Frontend_Bound.Fetch_Latency % Slots 17.8 [ 8.0%]
C0 FE Frontend_Bound.Fetch_Bandwidth % Slots 3.8 < [ 8.0%]
C0 BAD Bad_Speculation.Branch_Mispredicts % Slots 8.4 < [ 8.0%]
C0 BAD Bad_Speculation.Machine_Clears % Slots 0.2 < [ 8.0%]
C0 BE/Mem Backend_Bound.Memory_Bound % Slots 37.7 [ 8.0%]<==
C0 BE/Core Backend_Bound.Core_Bound % Slots 15.2 [ 8.0%]
C0 RET Retiring.Light_Operations % Slots 9.2 < [ 8.0%]
C0 RET Retiring.Heavy_Operations % Slots 8.2 < [ 8.0%]
C0-T0 MUX % 8.00
C0-T1 MUX % 8.00 Memory Bound 상태임이 분명해집니다. 대부분의 시간이 메모리에서 데이터를 가져오는 데 소비됩니다. 이는 코드를 살펴보면 쉽게 알 수 있습니다.
solution.cpp의 루프를 살펴보면:
for (int val : lookups) {
if (hash_map->find(val))
result += getSumOfDigits(val);
}lookups는 무작위로 생성된 정수를 백만 개 넘게 담고 있는
벡터입니다. hash_map 클래스의 find 함수 구현을
살펴보면:
bool find(int val) const {
int bucket = val % N_Buckets;
return m_vector[bucket] != UNUSED;
}본질적으로 약 32MB에 달하는 거대한 벡터에서 메모리 주소를 무작위로 조회하고 있음을 알 수 있습니다. 이는 비용이 큰 캐시 미스와 막대한 성능 저하를 부르는 전형적인 원인입니다.
해결책
입력이 무작위이므로 하드웨어 프리페처는 이후 루프 반복에서 필요할 데이터를 미리 불러오는 방식으로 도움을 줄 수 없습니다. 따라서 소프트웨어 프리페칭을 사용하여 이를 직접 수행해야 합니다.
데이터를 프리페치하도록 루프를 수정할 때 고려해야 할 몇 가지 단계가 있습니다:
- 프리페치하는 데이터가 충분히 일찍 로드되도록 하십시오. 데이터의 로드와 사용 사이에는 반드시 충족되어야 하는 프리페칭 윈도가 있습니다. 이 윈도는 메모리 주소가 알려지는 시점부터 해당 주소의 데이터가 필요해지는 시점까지의 시간입니다. 이 간격이 너무 짧으면 비순차(Out-Of-Order) CPU 엔진이 프리페칭을 수행할 수 없습니다.
- 데이터는 가능한 한 가장 늦은 시점에 프리페치해야 합니다. 이러한 프리페칭으로 인해 중간 루프 반복에 필요한 데이터가 캐시에서 축출될 수 있고, 그 결과 뒤이은 캐시 미스로 오버헤드가 추가될 수 있기 때문입니다.
- 이미 캐시에 있을 가능성이 높은 데이터는 로드하지 마십시오.
변경 사항은 항상 벤치마크해야 합니다. 소프트웨어 프리페칭은 올바르게 적용하기 어려운 경우가 많으며, 잘못 적용하면 코드 성능에 눈에 띄는 악영향을 미칠 수 있습니다.
루프에 "스텝"을 도입할 수 있습니다. 이를 통해 i번째
반복에서 i + step번째 반복에 필요할 값을 프리페치하도록
CPU에 신호를 보냅니다. 최적의 스텝을 찾기 위해 여기서 많은 실험을 해 볼
수 있지만, 캐시 라인의 너비가 합리적인 출발점이 될 것입니다. 이렇게 하면
프리페치가 이미 캐시에 있는 데이터와 불필요하게 겹칠 위험을 최소화할 수
있습니다.
벡터에는 4바이트로 가정하는 int가 들어 있으므로 스텝을
16으로 설정할 수 있습니다.
소프트웨어 프리페칭을 구현하려면 컴파일러 내장 함수
__builtin_prefetch를 사용해야 합니다. 맵에
prefetch_find 함수를 추가해 봅시다:
void prefetch_find(int val) const {
int bucket = val % N_Buckets;
__builtin_prefetch(&m_vector[bucket]);
}그런 다음 solution.cpp의 루프를 다시 작성해 봅시다:
static constexpr auto prefetch_step = 16;
int solution(const hash_map_t *hash_map, const std::vector<int> &lookups) {
int result = 0;
const auto size = lookups.size();
if (size <= prefetch_step) {
for (std::size_t i = 0; i < size; i++) {
if (const int val = lookups[i]; hash_map->find(val)) {
result += getSumOfDigits(val);
}
}
return result;
}
for (auto i = 0; i + prefetch_step < size; i++) {
if (const int val = lookups[i]; hash_map->find(val)) {
result += getSumOfDigits(val);
}
hash_map->prefetch_find(lookups[i + prefetch_step]);
}
for (auto i = size - prefetch_step; i < size; i++) {
if (const int val = lookups[i]; hash_map->find(val)) {
result += getSumOfDigits(val);
}
}
return result;
}먼저 prefetch_step을 정의하고 그 값을 16으로
설정했습니다(더 나은 성능을 얻을 수 있는지 다른 값으로도 자유롭게 실험해
보십시오!). 그런 다음 lookups[i + prefetch_step]의
프리페치를 트리거하도록 루프를 수정합니다. 그런 다음
i = lookups.size() - prefetch_step부터 마지막 <16개의
요소를 순회합니다.
이 코드를 실행하고 pmu-tools로 분석하면 다음과 같은
결과가 나옵니다.
-----------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------
bench1 43.5 ms 43.5 ms 24
...
C0 FE Frontend_Bound % Slots 25.9 [ 8.0%]
C0 BAD Bad_Speculation % Slots 11.6 < [ 8.0%]
C0 BE Backend_Bound % Slots 41.0 [ 8.0%]
C0 RET Retiring % Slots 21.6 [ 8.0%]
C0 FE Frontend_Bound.Fetch_Latency % Slots 21.4 [ 8.0%]
C0 FE Frontend_Bound.Fetch_Bandwidth % Slots 4.4 < [ 8.0%]
C0 BAD Bad_Speculation.Branch_Mispredicts % Slots 11.5 < [ 8.0%]
C0 BAD Bad_Speculation.Machine_Clears % Slots 0.1 < [ 8.0%]
C0 BE/Mem Backend_Bound.Memory_Bound % Slots 24.0 [ 8.0%]<==
C0 BE/Core Backend_Bound.Core_Bound % Slots 17.0 [ 8.0%]
C0 RET Retiring.Light_Operations % Slots 10.1 < [ 8.0%]
C0 RET Retiring.Heavy_Operations % Slots 11.5 [ 8.0%]
C0-T0 MUX % 8.00
C0-T1 MUX % 8.00 당연히 여전히 Memory Bound 상태이지만, 그 비율은 리소스의 37.7%에서 24.0%로 감소했습니다. 둘째로, 벤치마크가 훨씬 빠르게 실행되는 것을 확인할 수 있습니다. 24회 반복에 43.5ms가 걸린 반면, 이전에는 7회 반복에 96.1ms가 걸렸습니다. 이는 반복당 1.81ms 대 반복당 13.7ms에 해당하며, 거의 87%에 달하는 속도 향상입니다! 캐시/TLB 미스로 인한 페널티는 매우 크며, 이를 최소화하기 위해 할 수 있는 모든 일은 코드를 눈에 띄게 빠르게 만듭니다.