이 실습 과제는 거짓 공유를 제거하여 성능을 향상시키는 데 중점을 둡니다. 이 실습에는 메모리상에서 서로 가까이 위치한 데이터를 병렬로 수정하는 여러 스레드가 있습니다. 이로 인해 큰 오버헤드가 발생합니다. 캐시 일관성을 유지하기 위해 각 코어가 수정된 데이터를 포함하는 캐시 라인을 서로 주고받아야 하기 때문입니다.
여기서 여러분의 과제는 각 스레드가 별도의 캐시 라인에 접근하도록 하여 거짓 공유를 제거하는 것입니다.
기대 속도 향상: 최소 60%.
작성자: Jakub Beránek (@Kobzol)
힌트
힌트 1:
여러분의 시스템에서 하나의 캐시 라인에 Accumulator
객체가 몇 개 들어갑니까? CPU 캐시에 대해 알고 있는 내용을 바탕으로
생각해 볼 때, 여러 스레드가 같은 캐시 라인에 쓰기를 하면 어떤 문제가
생길 수 있습니까?
힌트 2:
Accumulator의 크기는 4이므로 x86에서는 하나의 캐시
라인에 16개가 들어갑니다. 적어도 하나의 스레드가 다른 스레드가 접근하는
캐시 라인에 속한 Accumulator를 갱신하려 할 가능성이 상당히
높습니다. 프로세서는 Accumulator로 감싼 원자적 변수(그리고
그 변수가 위치한 캐시 라인)에 접근하는 모든 코어가 가장 최근의 갱신을 볼
수 있도록 보장해야 합니다. 캐시 라인 안의 Accumulator가
갱신되기 전에 이전 캐시 라인을 읽어 두었던 스레드들에게 이것은 성능상
어떤 영향을 미칩니까?
힌트 3:
거짓 공유를 피하려면 각 Accumulator 객체가 각자의 캐시
라인에 위치하도록 해야 합니다.
풀이:
배경:
이 실습은 멀티스레드 환경에서 실행되며, 여러 스레드가
Accumulator 구조체로 감싼 원자적 정수들의 컨테이너를
증가시키는 작업을 맡습니다.
코드는 여러 번 실행되며, 실행할 때마다 서로 다른 개수의
스레드(thread_count)를 생성합니다. 컨테이너
std::vector<Accumulator>에는
thread_count개의 Accumulator 객체가 들어
있습니다. 예를 들어 세 개의 스레드가 실행되면 벡터에는 세 개의
Accumulators가 있습니다.
이 원본 코드의 성능 벤치마크는 다음과 같습니다.
-------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------
bench1/iterations:20/real_time 209 ms 209 ms 20
Performance counter stats for './lab':
27,735,792,018 task-clock # 6.619 CPUs utilized
1,357 context-switches # 48.926 /sec
27 cpu-migrations # 0.973 /sec
1,566 page-faults # 56.461 /sec
5,618,330,777 instructions # 0.05 insn per cycle
107,505,349,386 cycles # 3.876 GHz
526,104,194 branches # 18.968 M/sec
1,232,123 branch-misses # 0.23% of all branches
4.190116386 seconds time elapsedperf report ./lab을 사용해 분석하면, 핫스팟이 원자적
덧셈 단계인 target.value += item % 13이라고 보고됩니다.
│ // Write result to accumulator ▒
│ target.value += item % 13; ▒
47 │ mov eax,edx ▒
│ imul rax,rax,0x4ec4ec4f ▒
│ shr rax,0x22 ▒
199 │ lea r8d,[rax+rax*2] ▒
60 │ lea eax,[rax+r8*4] ▒
│ sub edx,eax ▒
│ operator--() volatile noexcept ▒
│ { return __atomic_sub_fetch(&_M_i, 1, int(memory_order_seq_cst)); } ▒
│ ▒
│ __int_type ▒
│ operator+=(__int_type __i) noexcept ▒
│ { return __atomic_add_fetch(&_M_i, __i, int(memory_order_seq_cst)); } ▒
91892 │ lock add DWORD PTR [rdi],edx ▒
621 │ add rcx,0x4 ▒
│ cmp rcx,rsi ▒
189 │ ↑ jne 70 멀티스레드 환경에서 작업하고 있으므로 캐시 간(Cache-To-Cache, C2C)
분석을 살펴보는 것도 합리적입니다(perf c2c record ./lab으로
데이터를 수집하고 perf c2c report로 검토합니다). 공유된
캐시 라인이 상당히 많이 보이며, 캐시 라인 분포를 보면 이 공유가
std::vector<Accumulator>에 넣어 둔 원자적 변수에 대한
쓰기 때문에 발생하고 있음을 알 수 있습니다.
=================================================
Global Shared Cache Line Event Information
=================================================
Total Shared Cache Lines : 32
Load HITs on shared lines : 87678
Fill Buffer Hits on shared lines : 81
L1D hits on shared lines : 4225
L2D hits on shared lines : 53
LLC hits on shared lines : 83318
Load hits on peer cache or nodes : 0
Locked Access on shared lines : 87498
Blocked Access on shared lines : 0
Store HITs on shared lines : 64939
Store L1D hits on shared lines : 64934
Store No available memory level : 0
Total Merged records : 147818=================================================
Shared Cache Line Distribution Pareto
=================================================
#
# ----- HITM ----- ------- Store Refs ------ --------- Data address --------- ---------- cycles ---------- Total cpu Shared >
# Num RmtHitm LclHitm L1 Hit L1 Miss N/A Offset Node PA cnt Code address rmt hitm lcl hitm load records cnt Symbol Object Source:Line No>
# ..... ....... ....... ....... ....... ....... .................. .... ...... .................. ........ ........ ........ ....... ........ .............................. ... ................. ....
#
----------------------------------------------------------------------
0 0 37147 27050 0 0 0x5555555da540
----------------------------------------------------------------------
0.00% 12.80% 5.06% 0.00% 0.00% 0x10 0 1 0x555555561004 0 3102 609 6474 1 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 0.01% 0.00% 0.00% 0.00% 0x10 0 1 0x555555561007 0 38184 0 6 1 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 10.26% 11.61% 0.00% 0.00% 0x14 0 1 0x555555561004 0 3005 294 6963 2 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 10.26% 11.40% 0.00% 0.00% 0x18 0 1 0x555555561004 0 2798 640 6903 7 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 0.00% 0.00% 0.00% 0.00% 0x18 0 1 0x555555561007 0 60801 0 1 1 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 11.22% 12.18% 0.00% 0.00% 0x1c 0 1 0x555555561004 0 3066 570 7485 8 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 0.00% 0.00% 0.00% 0.00% 0x1c 0 1 0x555555561007 0 34044 0 1 1 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 11.76% 12.52% 0.00% 0.00% 0x20 0 1 0x555555561004 0 3125 831 7878 6 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 0.01% 0.00% 0.00% 0.00% 0x20 0 1 0x555555561007 0 45967 0 2 1 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 12.80% 13.80% 0.00% 0.00% 0x24 0 1 0x555555561004 0 3126 825 8659 7 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 0.00% 0.00% 0.00% 0.00% 0x24 0 1 0x555555561007 0 47485 0 2 2 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 11.96% 13.32% 0.00% 0.00% 0x28 0 1 0x555555561004 0 2971 239 8266 2 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 0.01% 0.01% 0.00% 0.00% 0x28 0 1 0x555555561007 0 39104 0 4 1 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 9.41% 9.99% 0.00% 0.00% 0x2c 0 1 0x555555561004 0 2903 862 6382 6 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 0.01% 0.00% 0.00% 0.00% 0x2c 0 1 0x555555561007 0 46987 0 4 3 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 6.33% 6.62% 0.00% 0.00% 0x30 0 1 0x555555561004 0 3011 712 4236 6 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 0.00% 0.00% 0.00% 0.00% 0x30 0 1 0x555555561007 0 0 0 1 1 [.] solution(std::vector<unsig lab atomic_base.h:418 0
0.00% 3.15% 3.46% 0.00% 0.00% 0x34 0 1 0x555555561004 0 2850 1402 2119 8 [.] solution(std::vector<unsig lab atomic_base.h:418 0해결책:
Accumulator 구조체를 살펴봅시다.
struct Accumulator {
std::atomic<uint32_t> value = 0;
};sizeof(Accumulator) == 4임을 알 수 있습니다. x86
플랫폼에서 캐시 라인의 폭은 64바이트입니다. 즉, 이러한 Accumulator
객체가 최대 16개까지 같은 캐시 라인에 위치할 수 있습니다.
x86에서는 메모리에서 어떤 주소를 가져올 때 그 주소를 포함하는 캐시 라인 전체를 가져옵니다(64바이트를 초과하는 객체의 경우에는 해당 객체를 포함하는 캐시 라인 집합 전체를 가져옵니다).
여러 원자적 변수가 같은 캐시 라인에 있을 때, 스레드 A가 Atomic A에 쓰는 동안 다른 스레드들이 별개의 원자적 변수(Atomic B, Atomic C 등)에 동시에 쓰려고 하면, 시스템의 캐싱 프로토콜은 최신 버전을 얻도록 다른 스레드들이 캐시 라인을 다시 불러오게 강제합니다. 이 과정은 비용이 커서 성능을 크게 떨어뜨립니다. 이 원자적 객체들은 서로 관련이 없는데도, 이제 쓰기 연산 때문에 스레드 사이에 의존성이 생깁니다. 이것이 바로 거짓 공유입니다.
해결책은 각 원자적 변수가 자기만의 캐시 라인에 놓이도록 하는
것입니다. 이는 구조체나 원자적 변수 자체에 alignas를
사용하여 할 수 있습니다.
constexpr int CACHE_LINE_SIZE = 64;
struct alignas(CACHE_LINE_SIZE) Accumulator {
std::atomic<uint32_t> value = 0;
};
/// OR:
struct Accumulator {
alignas(CACHE_LINE_SIZE) std::atomic<uint32_t> value = 0;
};이렇게 변경한 뒤 성능 분석을 다시 실행하면 80% 이상 성능이 향상되었음을 확인할 수 있습니다(36.3 ms 대 209ms).
-------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------
bench1/iterations:20/real_time 36.3 ms 35.2 ms 20
Performance counter stats for './lab':
5,429,911,802 task-clock # 7.367 CPUs utilized
1,313 context-switches # 241.809 /sec
51 cpu-migrations # 9.392 /sec
1,574 page-faults # 289.876 /sec
5,087,982,332 instructions # 0.26 insn per cycle
19,279,139,853 cycles # 3.551 GHz
397,647,449 branches # 73.233 M/sec
669,664 branch-misses # 0.17% of all branches
0.737028094 seconds time elapsedCache-To-Cache 보고서를 분석하면 캐시 라인 공유가 완전히 사라졌음을 확인할 수 있습니다.
=================================================
Global Shared Cache Line Event Information
=================================================
Total Shared Cache Lines : 0
Load HITs on shared lines : 0
Fill Buffer Hits on shared lines : 0
L1D hits on shared lines : 0
L2D hits on shared lines : 0
LLC hits on shared lines : 0
Load hits on peer cache or nodes : 0
Locked Access on shared lines : 0
Blocked Access on shared lines : 0
Store HITs on shared lines : 0
Store L1D hits on shared lines : 0
Store No available memory level : 0
Total Merged records : 0참고: 보고서에는 여전히 일부 캐시 라인 공유가 나타날 수 있지만, 이는 실습 코드 자체가 아니라 다른 프로세스와 관련된 것입니다. 보고서에서 공유된 캐시 라인의 출처를 살펴보면 이 점을 분명히 알 수 있습니다.