반복 공간을 바꿔 GPU 복사 속도 높이기, 또는 항등 함수 최적화하기
2026년 10월 31일 게시
정수 나눗셈과 덧셈에 관한 최근 글에 이어, 이번에는 바이트 복사를 살펴본다. 대부분의 컴파일러는 데이터를 복사하는 코드를 생성하며, 대개 아주 작은 복사를 매우 많이 수행한다. 이런 경우 실행 중에 복잡한 최적화를 시도하면 오히려 손해일 수 있다. 반면 배열 언어는 연산 수가 비교적 적고 각 연산의 규모는 큰 편이라 다른 최적화를 적용할 여지가 있다. Futhark는 이제 실행 중에만 알 수 있는 배열 배치 정보를 이용해 일부 복사를 조금 더 빠르게 한다. 일부 프로그램에서 효과가 있지만, 이 기법은 실용성보다 흥미가 더 클 수도 있다.
배열 배치와 LMAD
Futhark가 배열 배치를 표현하는 방식은 이전 글에서 자세히 다뤘다. 여기서는 핵심만 다시 설명한다.
n차원 배열의 인덱스 공간을 컴퓨터 메모리의 1차원 인덱스 공간에 대응시키려면, n개의 인덱스를 메모리 블록 안의 상대 오프셋을 나타내는 정수 하나로 바꾸는 인덱스 함수가 필요하다. 이 함수는 원칙적으로 매우 복잡할 수 있지만, Futhark는 정적으로 분석하면서 실행 중에도 표현할 수 있도록 선형 메모리 접근 기술자(linear memory access descriptor, LMAD)라는 구조화된 표현을 사용한다.
간단히 말하면 n차원 공간의 LMAD는 차원마다 정수 쌍 하나씩을 갖는다. 각 쌍은 크기와 스트라이드를 나타낸다. d차원 공간의 LMAD L은 다음과 같이 쓴다.
L = [(n_1, s_1), ..., (n_d, s_d)]
d차원 LMAD에 d개의 정수를 적용하면 다음과 같이 계산한다.
L(i_1, ..., i_d) = i_1*s_1 + ... + i_d*s_d
각 인덱스에 대응하는 스트라이드를 곱한 뒤 모두 더한다. LMAD L로 표현한 2차원 배열 A에서 A[i,j]를 읽으려면 L(i,j)로 오프셋을 구하고, 원소 크기를 곱해 A가 저장된 메모리의 주소를 계산한다.
행 우선 순서(row-major)로 저장한 크기 [4][5] 배열의 LMAD는 다음과 같다.
[(4, 5), (5, 1)]
열 우선 순서(column-major)로 저장했다면 다음과 같다.
[(4,1), (5, 4)]
행 우선 순서에서는 인덱스 [i][j]를 [i+1][j]로 바꿀 때 주소가 5만큼 늘고, 열 우선 순서에서는 1만큼 늘어난다. LMAD를 쓰면 배열의 논리적 모양과 실제 메모리에 저장된 원소 순서를 분리할 수 있다. LMAD를 조정하는 것만으로 슬라이싱, 모양 바꾸기, 전치를 복사 없이 처리할 수도 있다. 슬라이싱에는 차원 정보에 더해 오프셋 하나가 필요하지만, 이 글에서는 중요하지 않다.
인덱스 계산에는 LMAD의 크기가 필요하지 않지만, 여러 원소를 다룰 때는 유용하다. 크기 정보로 배열의 크기를 알 수 있기 때문이다. 같은 모양의 배열 A와 B가 메모리 블록 AM과 BM에 있고, 각각 LMAD AL과 BL로 표현된다면 다음 반복문으로 A를 B에 복사할 수 있다.
for i_1 < n_1:
...
for i_d < n_d:
BM[BL(i_1, ..., i_d)] = AM[AL(i_1, ..., i_d)]
LMAD가 단사(injective)라고 가정하면, 즉 각 인덱스가 서로 다른 오프셋에 대응하고 특히 스트라이드가 0인 경우가 없으면, 반복 간 의존성이 없다. 따라서 모든 반복을 병렬로 실행할 수 있다. Futhark 컴파일러는 이런 LMAD만 생성하므로 이후에도 이 가정을 사용한다.
LMAD가 모든 배치를 표현할 수 있는 것은 아니지만, 중요한 경우인 차원 순열은 표현할 수 있다. 컴파일러 내부에서는 LMAD 구성 요소가 대개 기호식이고, 실행 중에도 LMAD를 사용해 배열 복사를 동적으로 최적화한다. 따라서 언제나 단순 반복문을 쓰는 것과 다르다.
LMAD 복사 최적화와 GPU 접근 순서
LMAD AL과 BL로 표현한 배열 A와 B를 각각 메모리 블록 AM과 BM에 저장했다고 하자. 앞서 본 반복문으로 복사할 수 있지만, 하드웨어 벡터화 같은 기능을 활용하도록 작성된 플랫폼의 memcpy()나 GPU에 대응하는 함수가 더 빠를 가능성이 있다. 두 배열의 배치가 같고 메모리 사이에 빈 곳이 없는 연속 배열이라면 memcpy(B, A, m)처럼 처리할 수 있다. 여기서 m은 전체 바이트 수다.
연속 배열인지는 실행 중 분석으로 판별할 수 있다. LMAD의 이웃한 두 차원 (n_1,s_1), (n_2,s_2)는 s_1=s_2*n_2일 때 하나의 차원 (n_1*n_2,s_2)으로 합칠 수 있다. LMAD 차원의 순열 중 하나라도 이런 방식으로 모든 차원을 하나로 합칠 수 있으면 연속 배열이다. 크기가 1인 차원은 무시해도 된다. 최악의 경우 이 판별에는 지수 시간이 걸린다. 매 복사 때마다 수행하면 대부분의 언어에서는 부담이 될 수 있지만, 탐색 시간은 배열 크기가 아니라 배열의 차원 수에 대해 지수적으로 늘어난다. Futhark 프로그램의 배열은 보통 차원이 많지 않고, 차원 수는 배열 크기와 관계없이 상수다. 따라서 수천 개, 혹은 수십억 개 원소를 복사하기 전에 명령어 수천 개를 쓰는 것은 큰 부담이 아니다.
또 다른 중요한 특수 사례는 행렬 전치에 해당하는 복사다. 단순한 전치는 모든 하드웨어에서 지역성이 나쁘다. 읽기나 쓰기 가운데 한쪽이 스트라이드 접근을 하기 때문이다. 하지만 메모리 계층을 세심하게 활용하면 전체 메모리 복사 속도에 거의 근접한 전치를 구현할 수 있다. 구체적인 방법은 이 글의 범위를 벗어난다.
전치는 각 LMAD의 연속 차원을 합쳐 두 차원만 남긴 뒤 서로 전치된 형태인지 확인해 판별할 수 있다. Futhark는 여기에 더해, 바깥 차원 하나가 변하지 않고 ‘행렬’끼리 연속해서 저장되지 않아도 되는 배치 전치, 즉 map transpose도 지원한다.
전치는 중요하다. Futhark는 프로그램이 실제로 배열을 어떻게 사용하는지에 따라 순회 지역성을 개선하려고 프로그램에 전치를 넣기 때문이다. 전치를 효율적으로 처리하지 못한다면 이런 최적화는 제대로 작동하지 않는다. 고수준 프로그래밍 언어를 쓰면 데이터 표현도 최적화할 수 있다는 점은 이 방식의 장점 가운데 하나다.
관심 있는 독자는 Futhark의 호스트 메모리 복사 함수 구현을 볼 수 있다. 이 함수는 원소 자료형에 맞게 매크로로 확장되며, 앞서 설명한 사례를 처리한다.
앞으로 더 흥미로운 구조를 찾아낼 수도 있지만, LMAD가 너무 복잡해 분석하기 어려운 경우에는 원소별 반복문으로 돌아가야 한다. 그래도 이 반복문은 병렬로 실행할 수 있다. 다만 휴리스틱을 써서 조금 더 나은 방법을 적용할 수 있다. LMAD로 표현한 배열 간 복사의 일반 반복문은 다음과 같다.
for i_1 < n_1:
...
for i_d < n_d:
BM[BL(i_1, ..., i_d)] = AM[AL(i_1, ..., i_d)]
이를 GPU에서 실행한다고 하자. GPU는 중첩 병렬성을 지원하지 않으므로 위 반복문을 하나의 반복문으로 변환한다.
for i < n_1 * ... n_d:
(i_1, ..., i_d) = unpack_flat_index(i)
BM[BL(i_1, ..., i_d)] = AM[AL(i_1, ..., i_d)]
unpack_flat_index 함수는 나눗셈을 여러 번 수행하는 복잡한 형태가 되지만, 여기서는 다루지 않는다. 이 1차원 반복문이 원래의 중첩 반복문을 단순히 평탄화한 것이고, 같은 사전식 순서를 유지한다고 하자. 반복마다 GPU 스레드 하나를 배정하더라도 의존성이 새로 생기지는 않는다. 따라서 지역성을 개선하기 위해 반복 순서를 바꿀 수 있다. 이는 목적지 LMAD가 단사이기 때문에 가능하며, 임의의 LMAD에 대해서는 성립하지 않는다.
GPU는 스레드를 워프나 웨이브프런트라는 그룹으로 묶어 실행한다. 그룹 크기는 보통 32개 또는 64개 스레드이며, 그룹 안의 스레드는 같은 명령을 동시에 실행한다. 하드웨어는 이들의 메모리 접근을 각각 연속된 메모리 블록을 다루는 하나 이상의 트랜잭션으로 처리한다. 스레드들이 가까운 메모리 위치에 접근하면 필요한 트랜잭션 수가 줄어든다. 이를 메모리 접근 병합(coalescing)이라고 한다. 병합되지 않으면 모든 스레드의 접근을 처리하기 위해 여러 트랜잭션이 필요하다. GPU 프로그래밍에서 병합 접근을 보장하는 것은 가장 기본적인 성능 요건 가운데 하나다. 일반적으로 이웃한 스레드가 배열의 이웃한 원소에 접근하도록 해야 한다.
Futhark의 일반 LMAD 복사용 GPU 커널은 인덱스 공간을 일종의 ‘열 우선’ 방식으로 평탄화한다. 이 방식에서는 이웃한 스레드가 가장 바깥 차원의 이웃한 인덱스를 처리한다. 2차원 배열을 복사할 때 두 스레드가 [i,j]와 [i+1,j]에 해당하는 원소를 복사하는 식이다. 이는 논리적 반복 순서이며, 논리적 인덱스가 실제 반복 공간에 어떻게 대응하는지는 원본과 목적지 배열의 LMAD가 정한다.
여기서 복사 전에 LMAD 차원의 순서를 바꾸는 최적화가 나온다. 원본 LMAD의 스트라이드가 작은 차원부터 정렬하고, 스트라이드가 같으면 목적지 LMAD를 기준으로 정렬한다. 이 방식은 이웃한 스레드가 접근하는 위치 사이의 스트라이드를 줄이는 것이 목표다. 이상적으로는 완전히 병합된 접근을 기대하지만, 스트라이드가 1보다 커도 이득이 있을 수 있다. 테스트한 GPU에서는 병합되지 않은 읽기가 쓰기보다 비용이 큰 듯해 원본 배열의 지역성을 우선한다. 스트라이드 정렬에는 기본 선택 정렬을 사용한다. 시간 복잡도는 이차지만, 지역성을 개선할 수 있다면 감수할 만한 비용이다.
핵심은 다음과 같다.
- 일반 복사 커널은 이웃한 GPU 스레드에 가장 바깥 차원의 이웃한 인덱스를 배정한다.
- 가장 바깥 차원이 메모리에서 스트라이드가 가장 작은 차원이라는 보장은 없다.
- 반복 차원의 순서를 바꾸면 이웃한 스레드가 메모리의 이웃한 위치에 접근하도록 할 수 있다.
- 원본과 목적지 LMAD의 스트라이드를 기준으로 정렬해 실행 중에 순열을 선택한다.
예를 들어 모양이 [n][m]인 2차원 배열 xss에서 각 행의 첫 원소를 제거하는 슬라이스 xss[:, 1:]를 보자. Futhark는 기본적으로 배열을 행 우선 순서로 저장하므로 xss의 LMAD는 [(n,m),(m,1)]이고, 슬라이스의 LMAD는 [(n,m),(m-1,1)]이다. 슬라이스 자체는 복사 없이 처리되므로 문제가 없다. 하지만 엔트리 포인트가 외부로 반환하는 값처럼 Futhark가 ‘정규화’된 배열 표현을 요구하는 경우가 있다. 정규화된 표현은 빈 공간이 없는 행 우선 순서다.
이 슬라이스를 정규화된 행 우선 표현으로 바꾸려면 [(n,m-1),(m-1,1)]로 복사해야 한다. 원본 배열이 연속적이지 않으므로 일반 LMAD 복사 커널을 써야 한다. 가장 바깥 차원의 스트라이드가 m으로, 대개 큰 값이므로 읽기와 쓰기가 병합되지 않는다. 두 LMAD에 같은 순열을 적용해 차원을 스트라이드 순으로 정렬하면, n>1,m>1일 때 다음과 같이 된다.
- 슬라이스 LMAD:
[(m-1,1),(n,m)] - 목적지 LMAD:
[(m-1,1),(n,m-1)]
이제 가장 바깥 차원의 스트라이드가 1이므로 접근을 완전히 병합할 수 있다.
성능 영향
Futhark 벤치마크 모음 전체에서 이 변경의 영향은 크지 않았다. 대부분의 프로그램은 지역성이 나쁜 복사를 하지 않았기 때문이다. 예외 사례의 속도 향상도 기억하기로 최대 10%였다. 그러나 기존 프로그램에서 효과가 작다고 해서 최적화할 사례를 만들지 말라는 법은 없다. 다음 Futhark 함수들은 인식된 LMAD 패턴인 memcpy()나 전치에 해당하지 않도록 작성됐다. 따라서 일반 복사 경로를 사용한다.
entry slice_2d [n] [m] (xss: [n][m]i32) = copy xss[:, 1:] entry slice_3d [n] [m] [k] (xsss: [n][m][k]i32) = copy xsss[:, :, 1:] entry reversed_rows [n] [m] (xss: [n][m]i32) = copy (map reverse xss)
정렬 기반 최적화를 적용하지 않았을 때, AMD RX 7900 XT GPU에서 hip 백엔드로 측정한 결과는 다음과 같다.
copy.fut:slice_2d (no tuning file):
[8192][8193]i32: 17561μs (95% CI: [ 17500.2, 17606.0])
[65536][1025]i32: 36062μs (95% CI: [ 36026.8, 36096.0])
[1048576][65]i32: 27241μs (95% CI: [ 27091.3, 27366.1])
[16777216][5]i32: 3466μs (95% CI: [ 3464.8, 3467.5])
copy.fut:slice_3d (no tuning file):
[256][256][1025]i32: 48624μs (95% CI: [ 48537.3, 48735.5])
[65536][32][33]i32: 57708μs (95% CI: [ 57610.5, 57816.4])
copy.fut:reversed_rows (no tuning file):
[8192][8192]i32: 12468μs (95% CI: [ 12438.8, 12537.8])
[16777216][4]i32: 3071μs (95% CI: [ 3069.5, 3071.6])
정렬을 적용한 결과는 다음과 같다.
copy.fut:slice_2d (no tuning file):
[8192][8193]i32: 971μs (95% CI: [ 964.5, 979.8])
[65536][1025]i32: 992μs (95% CI: [ 990.8, 993.8])
[1048576][65]i32: 990μs (95% CI: [ 988.5, 991.9])
[16777216][5]i32: 1010μs (95% CI: [ 1008.6, 1011.6])
copy.fut:slice_3d (no tuning file):
[256][256][1025]i32: 1366μs (95% CI: [ 1363.9, 1368.1])
[65536][32][33]i32: 1364μs (95% CI: [ 1361.7, 1366.9])
copy.fut:reversed_rows (no tuning file):
[8192][8192]i32: 996μs (95% CI: [ 994.0, 998.3])
[16777216][4]i32: 999μs (95% CI: [ 997.3, 1000.7])
일부 사례에서는 속도가 크게 향상됐다. slice_2d는 약 36배 빨라졌다. 이런 프로그램이 특별히 인위적인 사례라고 보기도 어렵다. 절대 성능은 약 514 GiB/s로 높지 않지만, 컴파일러에서 복사를 더 빠르게 할 방법을 살펴보고 싶어졌다. 항등 함수를 최적화하는 셈이라 어리석게 느껴질 수도 있지만, 데이터를 옮기는 일도 제대로 처리해야 하는 중요한 작업이다.
다음 주제는 아직 정하지 않았다. 이 글은 주로 GPU를 다뤘지만 CPU 백엔드에서도 비슷한 효과를 기대할 수 있다. 현재 DIKU 학생 한 명이 CPU 병렬 전치의 속도를 높이는 작업을 하고 있어, 앞으로 그 내용을 다룰 수도 있다.
댓글 (0)
로그인하면 이 기사에 내 생각을 남길 수 있어요