루프 타일링(블로킹)은 다차원 배열을 다루는 코드의 속도를 높이는 데 사용할 수 있는 중요한 기법입니다. 배열에 대한 메모리 접근 패턴 중 하나가 열 방향이거나, 코드에서 루프 안에서 같은 데이터에 여러 번 접근하는 경우, 이 기법은 성능에 매우 큰 도움이 될 수 있습니다. 이 기법은 행렬 곱셈과 행렬 회전 연산의 속도를 높이기 위해 자주 사용됩니다.

CPU는 행렬의 새 원소를 불러올 때마다 같은 행에 속한 인접 원소 몇 개(캐시 라인)도 함께 가져옵니다. 행렬이 크고 행렬에 열 방향으로 접근하는 경우, 캐시 활용도가 낮아 코드의 성능이 떨어질 수 있습니다. 첫 번째 행의 두 번째 원소에 접근할 즈음에는 그 원소가 행렬의 다른 행 원소들을 담은 캐시 라인으로 교체되어 더 이상 캐시에 남아 있지 않기 때문입니다.

따라서 행렬 전체를 한 번에 순회하는 대신, CPU 캐시에 완전히 들어가는 작은 조각으로 나눌 수 있습니다. 행렬을 블록(타일) 단위로 처리하면 CPU 캐시에 있는 행렬 원소를 재사용하게 되며, 이를 통해 코드의 속도가 향상됩니다. TILE_SIZE에 알맞은 값을 고르는 일은 실험적이며, 하드웨어 아키텍처와 알고리즘 자체에 모두 좌우됩니다. 힌트: Roofline 성능 분석(Intel Advisor 또는 다른 도구에서 제공)을 사용하여 루프의 성능을 제한하는 요인이 무엇인지 파악할 수 있습니다.

Authored-by: @ibogosavljevic

힌트

힌트 1:

행렬을 전치할 때 원본 행렬의 원소에 행 우선 순서로 접근하면, 전치된 객체에는 열 우선 순서로 접근해야 하는데, 이는 일반적으로 캐시 친화적이지 않습니다. 이 영향을 줄이기 위해 할 수 있는 일이 있겠습니까?


힌트 2:

in의 원소 [j, i]를 읽을 때, 해당 원소가 위치한 캐시 라인 전체를 캐시로 가져옵니다. 그러나 in을 열 우선 순서로 순회하기 때문에(주어진 열에 대해 2000개 행 전체를 반복합니다) 함께 위치한 이 원소들은 활용되지 못합니다. 즉, [0,0]에서 시작하면 [0, 1]에 도달하기 전에 [2000, 0]까지 반복합니다. in[0][0]에 접근하면서 in[0][1]의 메모리 주소도 캐시에 들어왔겠지만, 그때쯤이면 이 메모리는 캐시에서 밀려났을 가능성이 높습니다. 유용한 데이터가 캐시에서 너무 자주 밀려날 위험을 줄이도록 루프를 리팩터링할 수 있겠습니까?


힌트 3:

핵심은 in과 out의 처리를 더 작은 크기의 타일로 나누어, 둘에 관련된 전체 메모리가 L1(또는 L2) 캐시에 완전히 들어가도록 하는 것입니다. 이렇게 하면 데이터를 전치하는 동안 발생하는 비용이 큰 캐시 미스의 횟수를 최소화할 수 있습니다.


풀이:

배경:

이 실습에서는 2000x2000 크기의 큰 행렬을 전치합니다. 원래 루프를 살펴보면 몇 가지 사실을 알 수 있습니다.

for (int i = 0; i < size; i++) {
  for (int j = 0; j < size; j++) {
    out[i][j] = in[j][i];
  }
}

행렬 in은 열 우선 순서로 접근됩니다(즉, (0,0) -> (1,0) -> ... -> (2000,0) -> (0,1) -> ...). 이러한 접근 패턴과 배열의 크기 때문에, 코드는 메모리가 캐시로 로드되는 방식의 이점을 얻지 못합니다.

코드가 (0,0)의 요소를 로드하면, 0번째 행의 다음 몇 개 요소(예: (0,1), (0,2) 등)도 메모리에서 이들이 모두 위치한 캐시 라인의 일부로 함께 로드됩니다. 그러나 열 우선 순서로 순회하기 때문에, 이 다음 요소들은 전혀 참조되지 않습니다. (2000번의 반복 후) 0번째 행으로 돌아와 (0,1)에 접근하려 할 때쯤이면, 그 사이의 조회들로 인해 원래 데이터가 캐시에서 축출되었기 때문에 거의 확실하게 캐시 미스가 발생합니다.

원래 코드로 500번 반복했을 때의 조회 시간 예시는 다음과 같습니다:

----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
bench1/iterations:500       16.8 ms         16.8 ms          500

해결책

이 캐시 축출 문제를 해결하는 한 가지 방법은 큰 행렬을 타일, 즉 블록으로 나누어 두 블록의 전체 크기가 L1 캐시(그리고 가능하다면 L2 캐시까지)에 들어갈 만큼 작아지도록 하는 것입니다. 이 접근 방식은 플랫폼에 크게 의존하며, 결국 특정 머신과 캐시 크기에 맞게 조정해야 합니다.

제 머신에서는 64x64, 32x32, 16x16 타일을 테스트했습니다. 행렬을 16x16 크기의 조각으로 나누고 다음과 같이 전치를 수행했을 때 가장 좋은 결과를 얻었습니다:

static constexpr int TILE_SIZE = 16;
for (int i = 0; i < size; i+= TILE_SIZE) {
  for (int j = 0; j < size; j+= TILE_SIZE) {
    for (int k = i; k < std::min(i + TILE_SIZE, size); k++) {
      for (int l = j; l < std::min(j + TILE_SIZE, size); l++) {
        out[k][l] = in[l][k];
      }
    }
  }
}

새 벤치마크는 원래 코드보다 거의 세 배 빠른 시간을 보여 줍니다:

----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
bench1/iterations:500       5.72 ms         5.72 ms          500

해결책 코드(링크):

해결 방법 링크