CPU 아키텍처 기초

SIMD를 제대로 이해하려면 데이터가 어떻게 흘러 다니는지 알아야 합니다. 레지스터, 캐시, 메모리 — 이 세 계층이 프로그램의 실제 속도를 결정합니다.

1. 데이터 흐름 전체 그림

  DRAM (수 GB)
    ↓ 메모리 버스 (수십 ns)
  L3 캐시 (수 MB, 칩 공유)
    ↓ ~10 사이클
  L2 캐시 (수백 KB, 코어 공유)
    ↓ ~5 사이클
  L1 캐시 (32–64 KB, 코어 전용)
    ↓ ~4 사이클
  레지스터 (수십 개, 수 KB)
    ↓ 0 사이클 (이미 CPU 안)
  ALU / FPU / SIMD 유닛
    → 연산 결과 → 다시 레지스터

코드가 arr[i] + arr[j]를 계산할 때, 덧셈 자체는 1 사이클이지만 데이터가 DRAM에 있으면 300 사이클을 기다려야 합니다. 병목은 연산이 아니라 데이터 이동입니다.

2. 레이턴시 표

위치용량 (Pi 5)레이턴시대역폭
레지스터~수 KB0 사이클무제한
L1 캐시32 KB / 코어~4 사이클~200 GB/s
L2 캐시512 KB / 코어~12 사이클~100 GB/s
L3 캐시2 MB 공유~30 사이클~50 GB/s
DRAM수 GB~200 사이클~17 GB/s
L1에 있으면 4 사이클, DRAM에 있으면 200 사이클. 50배 차이입니다. 알고리즘보다 캐시 히트율이 더 중요할 때가 많습니다.

3. 캐시 라인 — 데이터는 항상 64바이트 단위로 이동

캐시는 바이트 단위가 아니라 캐시 라인 단위로 움직입니다. ARM64(Pi 5)에서 캐시 라인은 64바이트입니다.

메모리:  [  0  ][  1  ][  2  ][ ... ][  63 ] [  64 ] ...
                                        ↑
                              arr[0]에 접근

캐시 라인:  ├─────────────────── 64 바이트 ───────────────────┤
             arr[0]부터 arr[63]까지 한꺼번에 L1로 올라옴
let arr: [u8; 128] = [0; 128];

// arr[0] 접근 → 캐시 미스 → arr[0..64] 전부 L1로 로드
let _ = arr[0];

// arr[1]~arr[63] 접근 → 이미 L1에 있음 → 캐시 히트 (4 사이클)
let _ = arr[32];

// arr[64] 접근 → 새 캐시 라인 → 또 미스
let _ = arr[64];

SIMD와의 관계: u8x16은 16바이트, u8x32는 32바이트 — 둘 다 64바이트 캐시 라인 안에 딱 맞게 들어갑니다. SIMD 연산이 빠른 이유 중 하나는 이미 캐시에 올라온 데이터를 레지스터 하나로 퍼 올리기 때문입니다.

4. 레지스터의 종류 (ARM64)

ARM64에는 두 종류의 레지스터가 있습니다.

종류이름크기용도
범용 레지스터 (GPR)x0–x30, sp64비트정수, 주소, 분기
SIMD/FP 레지스터v0–v31128비트벡터 연산, 부동소수점
범용 레지스터 (64비트):
  x0: [████████████████████████████████████████████████████████████████]
       ← 64비트 →

SIMD 레지스터 (128비트):
  v0: [████████|████████|████████|████████|████████|████████|████████|████████]
       ← 16개의 u8 → 또는 ← 4개의 f32 → 또는 ← 2개의 f64 →
같은 v0 레지스터를 다른 시각으로 해석:

  v0.16b  →  u8  × 16  (16개 바이트)
  v0.8h   →  u16 × 8   (8개 반정수)
  v0.4s   →  f32 × 4   (4개 단정밀도)
  v0.2d   →  f64 × 2   (2개 배정밀도)

실제 비트는 똑같고, 명령어가 어떻게 해석하느냐의 차이

5. 로드 / 스토어 — 메모리 ↔ 레지스터

CPU는 메모리를 직접 연산하지 않습니다. 반드시 레지스터로 로드 → 연산 → 메모리에 스토어 순서를 따릅니다.

LOAD:   메모리[주소] ──────────────→ 레지스터
STORE:  레지스터 ──────────────────→ 메모리[주소]
COMPUTE: 레지스터 + 레지스터 ─────→ 레지스터
ARM64 어셈블리로 보면:

; x0 = &arr[0] 주소라고 가정

; 스칼라 로드 (1바이트)
LDRB w1, [x0]        ; arr[0] → w1 (8비트)

; SIMD 로드 (16바이트 한 번에)
LDR q0, [x0]         ; arr[0..16] → v0 (128비트)

; 이게 from_slice(&arr[0..16])의 실제 기계어
// Rust 코드
let v = u8x16::from_slice(&arr[0..16]);

// → 컴파일하면 (release):
//   LDR q0, [x0]   ← 딱 한 줄
//   (루프도, 복사도 없음)

6. 정렬 (Alignment)

SIMD 로드는 데이터가 특정 바이트 경계에 맞춰 있을 때 가장 빠릅니다. u8x16은 16바이트 정렬, u8x32는 32바이트 정렬이 이상적입니다.

정렬된 경우 (16바이트 경계에서 시작):
메모리:  0x10 [v0|v1|v2|...|v15]  ← LDR q0 한 번
                ↑ 주소가 16의 배수

미정렬 경우 (경계 걸침):
메모리:  0x0e  ..  [v0|v1|...|v13] | [v14|v15| ...
         두 캐시 라인에 걸침 → 추가 비용 또는 fault
use std::alloc::{Layout, alloc};

// 16바이트 정렬 보장 할당
let layout = Layout::from_size_align(64, 16).unwrap();
let ptr = unsafe { alloc(layout) };

// Vec은 정렬 보장 없음 → 실제론 보통 align 8
// 정렬이 중요한 경우 aligned_vec 등 crate 사용

// std::simd의 from_slice는 미정렬도 처리하지만
// 정렬된 경우 컴파일러가 더 빠른 명령어 선택 가능

7. 파이프라인과 처리량 vs 레이턴시

현대 CPU는 여러 명령어를 동시에 실행합니다(파이프라인/슈퍼스칼라).

구분의미예 (ARM64 NEON)
레이턴시명령어 하나가 완료되기까지 걸리는 사이클FADD: 4 사이클
처리량사이클당 실행 가능한 명령어 수FADD: 2개/사이클
// 의존성이 있는 루프 — 파이프라인 활용 불가
let mut sum = 0u32;
for x in data {
    sum += x as u32;  // 이전 sum에 의존 → 순차 실행
}

// SIMD 병렬 누산 — 4개 독립 누산기
let mut acc = [u32x4::splat(0); 4];  // 독립 레인 4세트
for chunk in data.chunks_exact(16) {
    let v = u8x16::from_slice(chunk);
    // ... 각 acc에 분산하여 누산
    // → 파이프라인이 4개 동시 실행
}
let total = acc[0] + acc[1] + acc[2] + acc[3];

8. 프리패치 — 캐시 미스를 미리 막기

CPU에게 "곧 이 주소가 필요할 거야"라고 미리 알려주면 연산하는 동안 백그라운드에서 데이터를 L1으로 올려놓습니다.

use std::arch::aarch64::__prefetch;

fn process_large(data: &[u8]) {
    let chunks = data.chunks_exact(64);
    for (i, chunk) in chunks.enumerate() {
        // 8 청크(512바이트) 앞의 데이터 미리 로드 요청
        if i + 8 < data.len() / 64 {
            unsafe {
                __prefetch::<0, 0>(data.as_ptr().add((i + 8) * 64));
                //          ↑ locality=0 (곧 한 번만 쓸 것)
            }
        }
        // 현재 청크 처리...
    }
}
현대 CPU는 순차 접근 패턴을 자동으로 프리패치합니다. 배열을 앞에서 뒤로 순서대로 읽는 것이 빠른 이유가 이것입니다. 랜덤 접근(해시맵 체이닝, 포인터 따라가기)은 프리패처가 예측 불가능해 느립니다.

9. 이 모든 것이 Swiss Table 설계에 반영된 이유

Swiss Table이 이 아키텍처 지식을 직접 활용합니다:

설계 결정이유
제어 바이트 16개 = 한 그룹u8x16 = 128비트 SIMD 레지스터 하나
제어 배열과 버킷 배열 분리제어 배열만 캐시에 올려 스캔 → 버킷(크고 무거움)은 확정 후에만 접근
16바이트 정렬SIMD 로드 최적화
순차 프로빙캐시 프리패처 활용, 랜덤 접근 최소화
로드 팩터 87.5%빈 슬롯을 항상 남겨 프로빙 조기 종료

10. Rust에서 확인하기

// 타입의 크기와 정렬 확인
println!("{}", std::mem::size_of::());   // 16
println!("{}", std::mem::align_of::());  // 16

// 캐시 라인 크기 (상수로 정의해 쓰기)
const CACHE_LINE: usize = 64;

// 캐시 라인 정렬 구조체
#[repr(align(64))]
struct CacheAligned(T);

// 메모리 주소가 정렬됐는지 확인
fn is_aligned(ptr: *const u8, align: usize) -> bool {
    ptr as usize % align == 0
}

다음 단계