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

 (blog.weineng.me)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 같은 정수 합산 루프라도 접근 순서만 바꾸면 실행 시간이 크게 달라지며, 실험은 무작위 접근보다 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% 느린 합산 패턴을 만들 수 있음
  • 전원 절약 모드 전환처럼 누산을 더 느리게 만드는 방법도 있지만, 이는 접근 패턴만 바꾸는 실험과는 별개임

함께 보면 좋은 글 β

GN⁺   [-]
Lobste.rs 의견들

  • 내부 Windows 11 개발 연구가 이런 모습이구나 싶어서 재미있게 읽었음 /s

  • https://github.com/ob/cache 를 만들면서 이 내용을 배웠음

    • README의 두 문장을 어떻게 이해해야 할지 궁금함
      하나는 Computer Architecture: A Quantitative Approach 476쪽 연습문제 5.2에서 지연 시간 수치를 생성하는 기법을 처음 봤다고 하고, 다른 하나는 Rafael Héctor Saavedra‑Barrera의 박사 논문에서 아이디어가 왔다고 함
      서로 다른 내용을 말하는 건지, 모순인지, 아니면 같은 내용이고 Saavedra-Barrera가 CA:AQA에서 인용되는 건지 확인하고 싶음
      Claude 프로그램이 README 작성에서 배제됐는지도 불명확하고, 저장소 기여자로도 표시되어 있어서 참조가 실제인지 먼저 확인하고 싶음

  • 커스텀 캐시 계층 접근을 실험해보고 싶다면 내가 만든 시뮬레이터도 추천함
    https://github.com/TheCloudlet/Stratum

  • 인덱스를 계산하는 오버헤드와 실제 접근 비용을 어떻게 분리했는지 궁금함

    • positions를 만드는 시간까지 같이 세지 않고 accumulator 사이클만 재는 방법을 묻는 거라면, reset과 arrange_positions를 먼저 실행한 뒤 rdtsc_start()와 rdtsc_end() 사이에 accumulator(data, positions)만 넣는 매크로를 썼음
      이후 결과를 출력하고 sum == linear_scan_sum을 검증하며, do_not_optimize(sum)으로 최적화 제거를 막았음

  • 교수들이 가르쳐준 데이터 접근 패턴으로도 해보자면, SafeNumber.java 클래스부터 만들고 add(SafeNumber b) 멤버가 필요해짐
    다음 학기에는 이걸 Redis 뒤에 배치해서 웹스케일 성능을 내는 아키텍처를 배울 것 같음
    Claude 덕분에 벤치마크를 Java로 옮겨봤는데, Java SafeNumber[]가 선형 접근에서 C++ uint32_t[]보다 약 3.6배 느리고, Fisher-Yates 셔플에서는 C++ 선형 대비 52.2배 느렸음
    절대 시간으로는 6,700만 원소 기준 C++ 선형 10,258,584ns, Java 선형 36,740,667ns, C++ 셔플 264,856,042ns, Java 셔플 535,724,208ns였고, 생각보다 “겨우 4배” 수준이라 인상적임

    • Java 배수가 썩 좋지는 않은데, Project Valhalla가 나오면 더 가까워질 수도 있겠음
답변달기