CPU를 정말 화나게 만드는 데이터 접근 패턴

같은 정수 합산 루프라도 접근 순서만 바꾸면 실행 시간이 크게 달라지며, 실험은 무작위 접근보다 30% 이상 느린 순열을 만들 수 있음을 보임
선형 접근은 1.33억 사이클 로 빠른 반면, 무작위 접근은 CPU가 다음 위치를 예측하기 어려워 15.7억 사이클 까지 느려짐
캐시 라인과 페이지 경계를 이용해 접근을 벌리면 프리페처와 캐시 재사용이 약해지고, 집합 연관 캐시 특성 때문에 L1d의 실질 활용 용량이 768B 수준으로 줄어듦
페이지 stride를 8로 두면 PTE 캐시 라인 지역성까지 깨져 20.6억 사이클 을 기록하며, 단순 무작위 셔플보다 더 나쁜 패턴이 됨
DRAM bank/row 충돌을 노린 근사 패턴은 20.8억 사이클 로 조금 더 느렸지만, 물리 주소의 DRAM 매핑이 플랫폼 의존적이라 완전히 통제하기는 어려움
실험 조건과 기준
목표는 data

배열의 정수를 합산하는 고정된 accumulator

함수에서 positions

순열만 바꿔 가장 느린 실행 시간 을 만드는 것임
positions

생성 시간은 제외하고, 누산 함수 실행 시간만 rdtsc

사이클 카운트로 측정함
데이터 크기는 2^26

개의 uint32_t

정수임
65,536개 페이지 사용
각 페이지는 4,096바이트
각 페이지에는 1,024개의 정수가 들어감
huge pages는 비활성화됨
측정 머신은 Intel Core Ultra 7 268V 기반 x86_64 시스템임
CPU 8개
L1d 합계 320KiB, L1i 합계 512KiB
L2 합계 14MiB
L3 12MiB
전체 코드는 GitHub 저장소 에 있으며, 예시는 g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out

로 실행함
핵심 루프는 positions[i]

가 가리키는 data[pos]

를 순서대로 더하는 단순한 형태임
선형 접근과 무작위 접근의 차이
가장 단순한 linear

패턴은 positions[i] = i

로 배열을 앞에서부터 차례대로 접근함
선형 접근은 132,752,394 사이클 이 걸렸고, CPU가 순차 접근에 강하게 최적화되어 있어 가장 빠른 축에 속함
fisher_yates_shuffle

로 positions

를 무작위 순열로 만들면 CPU가 다음에 접근할 데이터를 예측하기 어려워짐
무작위 접근은 1,572,108,618 사이클 이 걸려 선형 접근보다 10배 이상 느림
실험은 여기서 더 나아가, 무작위보다 나쁜 순열을 의도적으로 만들 수 있는지 확인함
캐시 라인과 페이지 단위로 접근 벌리기
첫 번째 악화 패턴은 연속 접근이 항상 캐시 라인 하나씩 떨어지도록 positions

를 배치함
이 패턴은 64바이트 캐시 라인에서 4바이트 정수 하나만 사용한 뒤 다음 캐시 라인으로 이동함
같은 캐시 라인으로 돌아올 때쯤 재사용 가능한 데이터가 캐시에서 밀려났을 가능성이 큼
캐시 라인 간격 접근은 718,804,156 사이클 이 걸려 선형 스캔보다 4배 이상 느림
그래도 이 경우 하드웨어 프리페처는 data

에 대한 단순 스트리밍 패턴을 감지해 미래 캐시 라인을 미리 가져올 수 있음
많은 Intel 하드웨어 데이터 프리페처는 4KiB 페이지 경계를 넘는 프리페치 를 하지 않음
다음 패턴은 접근 간격을 캐시 라인이 아니라 페이지 전체 로 벌림
각 페이지는 4,096바이트
page_index * elements_per_page + element_index

형태로 페이지별 같은 오프셋을 먼저 접근함
페이지 간격 접근은 1,411,153,154 사이클 로 크게 느려짐
집합 연관 캐시와 재사용 거리
실험 머신의 코어별 L1d 캐시는 48KB, 12-way, 64 set 구조임
L1d에 64개 set이 있으므로 주소 A

와 A + 4096

바이트는 같은 L1d set에 매핑됨
4,096바이트는 64 sets * 64-byte cache line

임
페이지 단위 stride는 각 내부 루프가 전체 64개 set에 고르게 퍼지지 않고 같은 set 을 계속 치게 만듦
한 set에는 12개 way만 있으므로 12개를 넘는 활성 캐시 라인이 경쟁하면 CPU가 라인을 반복적으로 축출하고 다시 로드해야 함
L1d 전체 용량은 48KB지만, 이 접근 패턴에서 유용하게 쓰이는 L1d 용량은 12 ways * 64B

인 768B 수준임
separated_by_a_page

패턴은 65,536개 캐시 라인을 접근한 뒤 같은 캐시 라인으로 돌아오므로 캐시 라인 재사용 거리가 65,536임
페이지 안의 캐시 라인까지 분리한 separated_by_a_page_and_cacheline

패턴은 재사용 거리를 65536 pages * 4096 page size / 64 cacheline size

까지 늘림
그러나 결과는 1,408,519,172 사이클 로 페이지 단위 접근과 거의 같았음
실험은 core 3에서 실행됐고, 해당 코어는 2.5MB L2와 48KB L1을 가짐
65,536개 페이지를 한 번 순회하면 4MB 데이터를 접근함
이는 해당 코어의 private L1/L2 용량보다 큼
다음에 필요한 캐시 라인이 private cache에 남아 있을 가능성이 낮음
private cache 재사용은 캐시 라인 재사용 거리가 대략 ((2560+48)*1024/64)

인 약 4만보다 작을 때만 기대할 수 있음
페이지 stride, PTE, DRAM까지 괴롭히기
다음 변형은 연속 페이지가 아니라 N개 페이지 간격 으로 접근하는 separated_by_stride_pages_and_cacheline

패턴임
여러 stride를 측정한 결과, 페이지 stride가 8일 때 가장 나쁜 결과가 나왔고 무작위 접근보다 느렸음
-DSTRIDE=8

로 단독 실행하면 2,058,425,640 사이클 이 걸림
stride 8에서 피크가 생긴 가능한 이유 중 하나는 주소 변환 임
가상 주소 접근은 MMU가 물리 주소로 변환함
변환에는 page table entry(PTE)가 사용됨
PTE는 8바이트이고, 캐시 라인 하나에는 PTE 8개가 들어감
8페이지 stride에서는 데이터 캐시 라인뿐 아니라 페이지 매핑을 위한 별도 캐시 라인도 매번 가져오게 된다고 판단함
마지막 단계는 DRAM controller 동작까지 방해하려는 시도임
DRAM은 channel, rank, chip, bank, row, column으로 구성됨
bank 안에는 여러 row가 있음
특정 row를 접근하려면 해당 row를 활성화해 row buffer로 복사함
같은 bank에서 다른 row를 접근하려면 기존 row를 precharge로 닫고 새 row를 활성화해야 함
같은 bank 안에서 row를 번갈아 접근하면 row-buffer conflict 가 발생해 DRAM controller 응답이 느려짐
반대로 이미 열린 row를 접근하면 row-buffer hit가 되고, 여러 bank를 동시에 쓰면 memory controller가 작업을 겹쳐 처리할 수 있음
느린 패턴을 만들기 위한 전략은 다음과 같음
가상 page number를 page table로 물리 frame number(PFN)로 변환함
page offset을 보존해 물리 주소를 구성함
물리 주소를 DRAM channel, rank, bank group, bank, row, column으로 해석함
같은 bank 안의 서로 다른 row를 반복 접근해 거의 매 요청마다 precharge와 activation을 강제함
하지만 물리 주소에서 DRAM channel, rank, bank, row로 가는 매핑은 문서화되지 않았고 플랫폼 의존적임
CPU, 메모리 타입, BIOS/firmware 설정, channel/rank 구성, address hashing에 따라 달라질 수 있음
DRAMA 나 Sudoku 같은 도구를 쓸 수 있지만, 이 실험 머신에서는 동작시키지 못함
DRAMA 논문과 로컬 실험을 바탕으로 bank group 4개, group당 bank 4개, DRAM_ROW_SHIFT = 18

을 사용해 근사함
DRAM bank/row 충돌까지 고려한 패턴은 2,082,308,014 사이클 로 stride 8보다 일관되게 조금 느렸지만 차이는 크지 않음
완전한 row conflict를 만들지 못한 데에는 몇 가지 제약이 있음
bank group hash, bank hash, row shift 추정이 정확하지 않을 수 있음
8페이지 stride는 약 32KB 간격 접근이므로 같은 DRAM row에 있기 어려움
Intel의 bank hashing 때문에 실제로는 여러 bank를 동시에 쓰게 됨
전체 실행 예시는 다음 결과를 보임
linear

: 132,752,394
fisher_yates_shuffle

: 1,572,108,618
separated_by_a_cacheline

: 718,804,156
separated_by_a_page

: 1,411,153,154
separated_by_a_page_and_cacheline

: 1,408,519,172
stride=8 separated_by_stride_pages_and_cacheline

: 2,058,425,640
separated_by_stride_bank_conflicts_and_cacheline

: 2,082,308,014
캐시, 프리페처, 캐시 라인 재사용, PTE 접근, DRAM bank/row 특성을 차례로 악화시키면 무작위 접근보다 33% 느린 합산 패턴을 만들 수 있음
전원 절약 모드 전환처럼 누산을 더 느리게 만드는 방법도 있지만, 이는 접근 패턴만 바꾸는 실험과는 별개임
댓글과 토론