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

YAML frontmatter와 전체 노트를 작성합니다. HN 댓글은 접근 불가로 인해 생략합니다.

---yaml title: "CPU를 정말 화나게 만드는 데이터 접근 패턴" date: 2026-06-29 source: pending-worker-injection type: analysis tags:

• memory-hierarchy
• cpu-optimization
• cache-coherence
• data-access-patterns
• performance-engineering
• education

---

한 줄 요약

캐시 라인, 페이지, 페이지 테이블 엔트리, DRAM bank 충돌을 순차적으로 악용해 무작위 접근보다 33% 더 느린 메모리 접근 패턴을 설계한 실험으로, CPU 메모리 계층 구조의 모든 병목을 실제로 체험할 수 있는 고급 성능 분석 글.

원문 핵심 내용

작동 방식: 순열만 바꿔 누산 속도를 극한으로 늦추기

저자는 data[] 배열의 정수를 합산하는 고정된 루프에서 positions[] 순열만 바꾸며 가장 느린 실행 시간을 찾는다. 조건은 다음과 같다.

• 데이터 크기: 2^26 개의 uint32_t → 65,536개 페이지 (각 4,096바이트, 정수 1,024개)
• Huge pages 비활성화, g++ -std=c++2a -O3 최적화, taskset -c 3으로 단일 코어 고정
• 시간 측정: rdtsc 사이클 카운트 (positions 생성 시간 제외)
• 머신: Intel Core Ultra 7 268V (L1d 48KB ×8, L2 2.5MB ×5, L3 12MB)

핵심 루프는 단순하다:

for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
    total += data[positions[i]];
}

단계별 악화 패턴과 구체 수치

① 선형 접근 (가장 빠름)

positions[i] = i → 데이터를 앞에서부터 순서대로 읽음 1.33억 사이클 (132,752,394) CPU의 하드웨어 프리페처가 순차 스트림을 완벽히 예측해 캐시 미스가 거의 없음.

② 무작위 접근 (첫 번째 직관)

Fisher-Yates shuffle로 positions를 완전히 섞음 15.7억 사이클 (1,572,108,618) → 선형보다 11.8배 느림 CPU가 다음 주소를 전혀 예측할 수 없어 거의 모든 접근이 캐시 미스.

③ 캐시 라인 단위 간격

64바이트 캐시 라인마다 정수 하나(4바이트)만 사용하고 다음 캐시 라인으로 이동. 같은 캐시 라인으로 돌아올 때 이미 캐시에서 축출됨. 7.19억 사이클 (718,804,156) 여전히 하드웨어 프리페처가 페이지 내에서는 스트리밍을 감지하지만, Intel은 4KiB 페이지 경계를 넘어 프리페치하지 않음.

④ 페이지 단위 간격

접근 간격을 페이지(4KB) 전체로 벌림. 65,536개 페이지를 순회하며 각 페이지의 같은 오프셋만 반복 접근. 14.1억 사이클 (1,411,153,154)

집합 연관 캐시 충돌 미스가 주 원인:

• L1d는 48KB, 12-way, 64 set 구조 → A와 A+4096은 같은 set에 매핑
• 페이지 stride는 같은 set만 반복 공격 → set당 12 way를 넘으면 캐시 라인 반복 축출/재로드
• 유효 L1d 용량이 768B (12 way × 64B)로 추락

⑤ 페이지 + 캐시 라인까지 분리

캐시 라인 재사용 거리를 65536 페이지 × 64 캐시라인/페이지 = 4M까지 늘림. 측정 결과 14.1억 사이클로 ④와 동일 → 코어 3의 private L1+L2(약 2.5MB)보다 4MB 데이터가 커서 어차피 L3에 의존해야 했기 때문. 재사용 거리가 4만(L1+L2 크기)을 넘으면 private 캐시 재사용 기대 불가.

⑥ 페이지 stride 8 (가장 느린 구간)

연속 페이지 대신 N페이지 간격으로 접근. stride=8일 때 최악 기록 20.6억 사이클 (2,058,425,640) → 무작위보다 31% 느림.

주된 이유: 페이지 테이블 엔트리(PTE) 캐시 지역성 파괴

• PTE는 8바이트 → 캐시 라인 하나에 8개 PTE
• stride 8에서는 데이터 접근마다 다른 PTE 캐시 라인 필요 → 매 접근마다 PTE 캐시 미스 + 데이터 캐시 미스가 동시 발생
• MMU가 페이지 워크를 거의 모든 접근에서 수행하게 됨

⑦ DRAM bank/row 충돌 시도 (최종)

물리 주소를 DRAM bank/row 매핑(비문서화)에 따라 재배치. bank 내에서 row를 계속 바꾸면 precharge+activation 지연 유발. 20.8억 사이클 (2,082,308,014) → stride 8보다 조금 더 느리나, 매핑 추정이 정확하지 않아 큰 차이는 없음.

전체 결과 비교표

트레이드오프: 느리게 만드는 것이 왜 유용한가?

이 실험은 CPU 메모리 계층의 모든 병목을 독립적으로 격리해 보여준다. 실제 개발에서는 이런 패턴을 피해야 하지만, 반대로 성능 최적화를 위해 어떤 요소를 신경 써야 하는지 역으로 가르쳐준다.

• 순차 접근 vs 무작위 접근의 차이는 10배 이상 → 데이터 구조를 배열/벡터로 설계하고 캐시 친화적인 순회를 해야 함
• 집합 연관 캐시의 충돌 미스는 용량보다 접근 패턴이 더 중요함을 보여줌 (768B만 유효)
• 페이지 경계와 PTE 캐시는 stride가 8의 배수일 때 특히 취약 → 실제 DB 인덱스나 해시 테이블 설계에서 고려할 점
• DRAM row buffer 활용은 물리 주소 매핑에 의존적이며, 일반 애플리케이션에서는 통제 어려움

새로운 시각

하나의 루프가 CPU의 모든 계층을 '검사'하는 방법

이 글은 단순히 '느린 패턴 만들기'라는 퍼즐을 통해 컴퓨터 구조 교과서의 각 장(chapter)을 실제로 실험실에서 검증한 사례다. 보통 CS 학부에서는 캐시, TLB, DRAM을 따로 배우지만, 이 실험은 동일한 루프 안에서 이들이 어떻게 상호작용하는지 보여준다. 특히 stride 8이 무작위보다 더 느리다는 점은 '무작위가 최악'이라는 직관을 깨며, 하드웨어 프리페처와 PTE 캐시의 공진(resonance) 현상을 암시한다. 이는 소프트웨어에서 의도치 않게 발생할 수 있는 최악의 접근 패턴으로, 실제 대규모 해시 테이블이나 인덱스 스캔에서 유사한 현상이 발생할 가능성이 있다.

캐시 '용량'보다 '연관도(associativity)'가 더 결정적인 경우

일반적으로 L1d 크기가 48KB이므로 4MB 데이터는 당연히 캐시에 맞지 않는다고 생각하기 쉽다. 하지만 페이지 간격 접근에서는 단일 set에 12 way만 있기 때문에 유효 용량이 768B로 줄어든다. 즉, 캐시 전체 용량이 충분해도 접근 패턴이 특정 set을 집중 공격하면 캐시가 거의 무용지물이 된다. 이는 cache coloring이나 배열 차원 순서 같은 최적화 기법이 왜 중요한지 근본적으로 설명해준다.

DRAM bank 충돌은 실용적 통제가 어렵다

저자가 DRAM 매핑을 추정했지만 실제로 큰 효과를 보지 못한 점은 현대 CPU의 주소 해싱(address hashing)이 의도적으로 bank-level parallelism을 증가시키도록 설계되었음을 시사한다. 즉, 일반 개발자가 DRAM bank 충돌을 의도적으로 피하거나 유발하는 것은 거의 불가능에 가깝다. 오히려 캐시와 TLB 최적화에 집중하는 것이 생산적이다.

자녀와 미래에 대한 시사점

컴퓨터는 '마법'이 아니라 '예측 가능한 규칙'의 집합

이 글은 어린 학습자에게 컴퓨터가 어떻게 '생각'하는지를 구체적인 숫자와 패턴으로 보여준다. 단순히 "코딩을 배워라"는 추상적인 조언보다, "같은 일을 하는 코드라도 메모리 접근 순서에 따라 15배 차이가 난다"는 경험은 알고리즘과 하드웨어의 연결을 직관적으로 이해하게 한다. 미래 세대는 단순히 프로그래밍 언어 문법을 아는 것을 넘어, CPU의 물리적 한계를 고려한 효율적인 설계 마인드를 갖추는 것이 중요하다.

교육에의 함의: 실험으로 배우는 컴퓨터 구조

전통적인 컴퓨터 공학 교육은 이론과 추상화에 치우쳐 있다. 이런 실험을 통해 학생들은 직접 코드를 수정하고, 캐시 미스 카운터를 측정하며, 그래프를 그려보는 경험을 해야 한다. 저자가 제공한 GitHub 저장소(slowest.cc)를 실제로 실행해보면 L1, L2, TLB, DRAM의 영향을 손으로 만질 수 있다. 의료 분야 종사자인 사용자가 자녀에게 추천할 만한 '컴퓨터 속 세상'을 체험하는 과외 프로젝트로 활용할 수 있다.

의료 분야와의 연결: 데이터 접근 패턴이 의료 소프트웨어에도 영향을 준다

사용자는 소화기·내시경·종양학 분야 종사자다. 의료 영상 처리(PACS, 내시경 비디오 분석)나 유전체 데이터 분석에서는 방대한 양의 데이터를 실시간으로 처리해야 한다. 예를 들어, CT 스캔 이미지를 순차적으로 읽으면 빠르지만, 무작위로 타일 단위로 접근하면 성능이 급락한다. 이런 최적화 지식은 의료 기기 소프트웨어나 연구용 파이프라인의 효율을 높이는 데 직접 적용된다. 또한, 어린 환자 교육용 시뮬레이션을 개발할 때도 '느린 접근'이 사용자 경험에 미치는 영향을 고려할 수 있다.

---