메모리 정렬

네, 또 행렬 곱셈입니다...

일부 사람들이 믿거나 어디선가 들었을 수도 있는 것과 달리, 최적의 성능을 얻으려면 여전히 메모리 정렬이 필요한 경우가 있습니다. 이 실습 과제가 바로 그러한 경우입니다. 먼저 간단히 소개하겠습니다.

데이터 정렬이 중요한 대표적인 경우는 SIMD 코드로, 이 코드에서는 로드와 스토어가 단일 연산으로 큰 데이터 덩어리에 접근합니다. 대부분의 프로세서에서 L1 캐시는 어떤 정렬 상태의 데이터든 읽고 쓸 수 있도록 설계되어 있습니다. 일반적으로 로드/스토어가 정렬되지 않았더라도 캐시 라인 경계를 넘지 않는다면 성능 저하는 전혀 없습니다. 그러나 로드나 스토어가 캐시 라인 경계를 넘으면, 그러한 접근에는 캐시 라인 읽기가 두 번 필요합니다(분할 로드/스토어). 이때 분할 레지스터를 사용해야 하는데, 이 레지스터는 두 부분을 보관하다가 두 부분을 모두 가져오면 이를 하나의 레지스터로 합칩니다. 분할 레지스터의 수는 제한되어 있습니다. 분할 접근이 산발적으로 실행될 때는 일반적으로 전체 실행에 눈에 띄는 성능 영향 없이 완료됩니다. 그러나 이러한 일이 자주 발생하면, 정렬되지 않은 메모리 접근은 지연을 겪게 됩니다.

우리의 간단한 행렬 곱셈은 SIMD 명령어를 생성합니다. 작은 크기의 행렬에는 캐시 친화적인 접근과 벡터화된 코드를 얻기 위해 루프 교환을 적용한 일반 버전을 사용합니다. 더 큰 크기에 대해서는 루프 블로킹(Loop Blocking)을 사용하는 버전을 직접 만들었습니다. 상용구 코드를 모두 제공하므로 몇 줄만 변경하면 됩니다.

행렬이 정렬되지 않으면 분할 로드가 매우 빈번하게 발생하여 성능 문제를 일으킵니다. 이 실습에서는 이 문제를 해결해야 합니다. 중요: 행렬의 오프셋만 정렬하는 것으로는 충분하지 않으며, 행렬의 각 행도 정렬해야 합니다. 이를 위해 더미 열을 삽입할 수 있습니다.

AVX2 코드에서는 각 행이 32바이트 경계에 정렬되면 충분하고, SSE와 ARM Neon에서는 16바이트 정렬만 필요합니다. 그러나 AVX-512는 64바이트 정렬이 필요합니다. 안전하게 하려면 캐시 라인 경계에 정렬할 수 있습니다. Apple 프로세서(M1, M2 및 이후 모델 등)에서는 L2 캐시가 128바이트 캐시 라인 단위로 동작한다는 점을 유의하십시오.

Intel의 하향식 방법론(TMA)을 적극적으로 사용하고 있다면, 이는 Memory_Bound -> L1_Bound -> Split Loads 범주 아래에 반영됩니다. 정렬을 개선하면 다음 이벤트의 변화를 관찰하십시오: mem_inst_retired.split_loads, mem_inst_retired.split_stores.

성능 저하는 로드와 스토어 모두에 적용되므로, 모든 행렬을 정렬해야 한다는 점을 유의하십시오.

힌트

힌트 1:

해당 행렬의 각 행의 시작과 끝이 캐시 라인 경계와 일치하도록 해야 합니다.


힌트 2:

행렬의 시작 부분에는 alignas 키워드를 사용할 수 있습니다. 행의 끝이 캐시 라인 경계에서 끝나도록 하려면 그 밖에 무엇을 해야 하겠습니까?


힌트 3:

행의 길이를 다음 정렬 경계에 맞도록 올림하십시오. 이를 위해 행렬에 비어 있는 패딩 열을 추가해야 할 수도 있습니다.


풀이:

배경:

이 실습은 메모리 정렬과, 잘못 정렬된 데이터를 로드하고 저장할 때 발생할 수 있는 페널티에 관한 것입니다. 실습에서 제시하는 예제는 행렬이 메모리에 올바르게 정렬되지 않은 상태에서 수행하는 행렬 곱셈입니다.

정렬되지 않은 데이터를 사용할 때의 문제는 행렬의 한 행에 있는 데이터가 두 캐시 라인에 걸쳐 있을 수 있다는 점입니다. 이 때문에 이 데이터에 대한 모든 연산이 둘로 나뉘게 되며(즉, 분할 로드와 분할 저장), 필요한 값을 얻으려면 서로 독립적인 두 로드/저장을 다시 합쳐야 하므로 비효율이 발생합니다.

해결책:

실습 바이너리를 실행한 출력을 보면 정렬 불량이 성능에 어떤 영향을 미치는지 알 수 있습니다:

----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
bench1/_63/iterations:30000       27.0 us         26.9 us        30000
bench1/_64/iterations:30000       18.8 us         18.8 us        30000
bench1/_65/iterations:30000       23.5 us         23.5 us        30000
bench1/_128                        180 us          180 us        15422
bench1/_256                       1869 us         1869 us         1504
bench1/_511/iterations:50        15535 us        15530 us           50
bench1/_512/iterations:50        16894 us        16892 us           50
bench1/_513/iterations:50        15924 us        15921 us           50
bench1/_1024                    200084 us       200038 us           10

먼저 열이 63, 64, 65인 경우를 비교해 봅시다. x86에서 실행하면 캐시 라인의 길이는 64바이트이므로, 너비가 63과 65인 행렬은 아주 약간만 정렬이 어긋나 있습니다. 정렬된 버전이 63보다 30.3%, 65보다 20% 빠르다는 것을 알 수 있습니다. 흥미롭게도 위의 512 경우는 양옆의 정렬되지 않은 버전보다 약간 느리게 실행되는 것으로 보이므로, 다른 요인도 작용하고 있습니다.

지금까지는 행렬의 첫 번째 요소가 캐시 라인의 시작에서 시작한다고 가정했지만, 실제로는 그렇지 않을 수도 있습니다. 이는 결과에 영향을 줄 수 있으므로, 행렬의 시작 부분을 정렬하고 분석을 다시 실행해 봅시다.

solution.h에서 using Matrix 정의를 헤더 파일에 정의된 AlignedVector 타입을 사용하도록 변경해야 합니다:

using Matrix = AlignedVector<float>;

각 행렬의 첫 번째 요소를 캐시 라인의 시작에 올바르게 정렬한 상태로 벤치마크를 다시 실행한 결과입니다:

----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
bench1/_63/iterations:30000       28.1 us         28.1 us        30000
bench1/_64/iterations:30000       19.5 us         19.5 us        30000
bench1/_65/iterations:30000       26.2 us         26.2 us        30000
bench1/_128                        151 us          151 us        16706
bench1/_256                       1398 us         1398 us         2004
bench1/_511/iterations:50        14134 us        14132 us           50
bench1/_512/iterations:50        12161 us        12161 us           50
bench1/_513/iterations:50        14286 us        14284 us           50
bench1/_1024                    124944 us       124938 us           22

여기서는 64와 512 경우에서 양옆의 분할 버전에 비해 예상했던 성능 향상을 확인할 수 있습니다. 이는 데이터 시작 부분의 정렬이 중요하다는 것을 보여 줍니다.

그렇다면 끝 부분은 어떻겠습니까? 정렬되지 않은 열 경우는 열 수가 x86의 캐시 라인 크기(64바이트)의 배수인 경우에 비해 여전히 눈에 띄는 성능 저하를 보입니다. 이를 해결하려면 행렬에 빈 열을 채워 넣어 그 길이가 캐시 라인 크기의 배수, 더 정확히 말하면 캐시 라인 하나에 들어가는 float 요소 개수의 배수가 되도록 해야 합니다.

이를 위해 solution.cpp에 함수를 하나 만듭니다:

int get_next_multiple(int N) {
  const auto y = ELEMS_PER_CACHE_LINE - 1;
  return N + y & ~y;
}

여기서 ELEMS_PER_CACHE_LINE은 solution.h에 다음과 같이 정의됩니다:

inline constexpr int ELEMS_PER_CACHE_LINE = CACHELINE_SIZE / sizeof(float);

CACHELINE_SIZE는 기존 코드에서 제공하는 상수입니다.

get_next_multiple은 N 이상인 ELEMS_PER_CACHE_LINE의 첫 번째 배수를 반환하며, 여기서 N은 행렬의 열 수입니다.

마지막으로 n_columns 함수를 변경합니다:

int n_columns(int N) {
  return get_next_multiple(ELEMS_PER_CACHE_LINE, N);
}

벤치마크를 다시 실행하면 다음과 같은 결과를 얻습니다:

----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
bench1/_63/iterations:30000       26.4 us         26.4 us        30000
bench1/_64/iterations:30000       18.8 us         18.8 us        30000
bench1/_65/iterations:30000       21.7 us         21.7 us        30000
bench1/_128                        155 us          155 us        18185
bench1/_256                       1463 us         1462 us         1910
bench1/_511/iterations:50        12625 us        12623 us           50
bench1/_512/iterations:50        12294 us        12290 us           50
bench1/_513/iterations:50        10436 us        10433 us           50
bench1/_1024                    127967 us       127944 us           22

작은 크기의 행렬에서는 큰 영향이 눈에 띄지 않지만, 이제 511의 성능이 512와 거의 같아진 것을 볼 수 있습니다. 이제 511이 512바이트 너비로 실행되므로 이는 당연한 결과입니다. 흥미롭게도 513(이제 너비 528바이트)은 512의 경우보다도 더 빠르게 실행되는 것으로 보입니다!


해결책 코드(링크):

해결책 링크