시간 지역성을 높이는 전략: BLOCKING

1. 배경: 캐시는 작고, 데이터는 크다

• 큰 배열이나 행렬 연산(예: 행렬 곱셈)을 수행할 때, 데이터가 캐시에 다 안 들어가면
  같은 데이터를 계속 메모리에서 다시 불러와야 하죠. → 느림
• 하지만 캐시에 들어와 있는 동안 여러 번 다시 쓰면(=시간적 지역성), 성능이 크게 올라갑니다.

2. BLOCKING의 기본 아이디어

"큰 데이터를 한 번에 다루지 말고, 작은 덩어리(block)로 쪼개서 처리하자."

예시 (행렬 곱셈)

for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    for (k = 0; k < N; k++)
      C[i][j] += A[i][k] * B[k][j];

이 코드는 단순하지만, 실제로는 캐시가 자주 미스 납니다.
왜냐하면 A, B, C가 너무 커서 한 번 읽은 데이터가 캐시에서 금방 쫓겨나기 때문이죠.

그래서 Blocking을 씁니다:

for (ii = 0; ii < N; ii += B)
  for (jj = 0; jj < N; jj += B)
    for (kk = 0; kk < N; kk += B)
      // 작은 BxB 블록끼리만 곱함
      for (i = ii; i < ii + B; i++)
        for (j = jj; j < jj + B; j++)
          for (k = kk; k < kk + B; k++)
            C[i][j] += A[i][k] * B[k][j];

이제 프로그램은:

1. A, B, C의 작은 블록 하나씩을 캐시에 불러옴
2. 그 블록 안에서 필요한 모든 연산을 끝냄
3. 다 끝나면 버리고 다음 블록으로 넘어감

이렇게 하면 같은 데이터(예: A[i][k])를 캐시에 있을 때 여러 번 사용합니다 → 시간적 지역성 향상

3. 하지만 Core i7에서는 효과가 적은 이유

본문의 마지막 문장:

“Blocking does not improve the performance of matrix multiply on the Core i7, because of its sophisticated prefetching hardware.”

• 최신 CPU는 하드웨어 프리패처(prefetcher)가 자동으로 데이터를 미리 읽습니다.
• 그래서 Blocking이 수동으로 해주는 캐시 최적화 효과가 이미 구현되어 있음 → 효과가 덜함.

즉, Blocking은 이론적으로 강력하지만,
하드웨어가 단순한 시스템(임베디드, 구형 CPU 등)에서 더 유용합니다.