블로킹(Blocking) & 타일링(Tiling) — 초간단 요약

한 줄 요약
큰 문제를 작은 타일로 쪼개 캐시에 머무는 동안 최대한 계산·재사용해서 캐시 미스↓ 성능↑.
(타일링이 더 넓은 개념, 캐시 문맥에선 둘을 거의 동일하게 사용)

언제 쓰나

• 데이터가 커서 DRAM 왕복이 잦을 때
• 재사용(행렬곱, 컨볼루션/스텐실, DP)이 많은 커널

핵심 원칙 (필수 5개)

1. Stride-1이 되도록 루프 교환
2. 타일(블록) 크기를 캐시에 맞춤 → 작업 집합 ≤ 캐시 일부(약 1/2~2/3)
3. 필요 시 다단계 블로킹(L3→L2→L1), 레지스터 블로킹(작은 패널 누적)
4. 읽기는 묶어서, 쓰기는 한 번에(store 최소화)
5. 측정으로 결정: 타일 크기 스윕(B=16,24,32,…) 후 최적 선택

블록 크기 잡는 법 (감 잡기)

• 공식: 작업 집합 바이트 ≈ (타일에 쓰는 원소 수) × elem_size
  이를 (목표 캐시 용량) × 여유계수 이하로
• 행렬곱(double): 작업 집합 ≈ 3·B²·8
  L1 32KB → 예산 24KB로 잡으면 3·B²·8 ≤ 24KB ⇒ B ≈ 32 전후

미니 예시 (행렬곱 스케치)

• 타일 반복: for ii+=B, jj+=B, kk+=B 안에서 (i,j,k) 계산
• 효과: A(i,k), B(k,j), C(i,j)가 타일 내부에서 반복 재사용

주의할 점 (3가지)

• false sharing: 스레드 간 같은 캐시라인 쓰기 피하기(패딩/경계 조정)
• 충돌 미스: 파워오브투 정렬 몰림 시 타일/패딩 조정
• 너무 크거나 너무 작은 타일 금지(캐시 초과 vs 오버헤드/불균형)

치트시트

• 우선순위: Stride-1 → 블로킹 → 다단계/레지스터 → 벡터화 → 병렬화
• 경험치 값: L1 32KB & double → B ≈ 32부터 시험
• 항상: 이론은 가이드, 결정은 측정(미스율/대역폭/IPC)