Parallel Matrix Transpose : Coalesced Memory Access & Bank Conflicts (SYCL 구현)

문제 소개

Matrix transpose는 행렬의 행과 열을 교환하여 새로운 행렬을 얻는 operation[2]이다. 주대각축을 중심으로 반사 대칭을 하는 연산으로 Eq 1.과 같은 특징을 만족한다.

Eq 1. Transpose of Matrix

Matrix transpose는 더하기, 곱하기와 같은 수 계산이 필요없는 operation으로, 단순히 원하는 위치의 데이터를 읽어와 원하는 위치에 쓰기만 하면 된다. 즉 memory operation이 대부분을 차지한다.

 

Matrix transpose를 병렬화할 경우, matrix의 각 element는 다른 element와 관계 없이 독립적으로 읽고 쓰기가 되기에 쉽게 병렬화할 수 있다. 하나의 work-item은 [i,j]-번째 input 행렬의 element를 읽어와 [j,i]-번째 output 행렬의 element에 그 값을 쓰도록 병렬화 하면 된다. (이와 별개로 inplace matrix transpose의 경우는 구현하기 매우 복합하다.)

 

다만 computation이 전혀없고 memory opearation만 있기에 GPU를 통한 병렬화에서 성능 향상을 기대하기 어렵다. 작은 크기의 matrix일 경우 GPU보다 CPU로 병렬화 하는 것이 훨씬 빠르며, GPU의 메모리 성능이 좋지 못할 경우 GPU 병렬화 코드의 계산 성능은 더욱 떨어진다. 즉 matrix transpose는 GPU의 강점인 많은 ALU를 전혀 활용하지 못하는 문제이다.

 

이번 포스터에서는 GPU를 통한 parallel matrix transpose에 관한 좋은 자료[1]가 있기에 이에 대하여 정리해보고자 한다. 자료 [1]은 matrix transpose 문제의 핵심 병목인 GPU memory operation 최적화 방향에 대하여 중점적으로 제안하다.

 

 

병렬화 코드 - 1 : 기본 구현

Fig 1. 기본 구현의 memory access 문제 예시

가장 간단한 구현은 GPU의 (x,y)-번째 work-item이 Input[x][y] 데이터를 Output[y][x]에 저장하도록 GPU kernel을 작성하면 된다. Fig 1.은 기본 구현의 memory access pattern에서 발생할 수 있는 비효율성을 잘 보여준다. 주황색 박스는 한 sub-group(CUDA에서는 warp, lock-step으로 동시에 실행되는 thread들의 집합)이 한번에 처리하는 데이터 영역을 그림으로 나타낸 것이다. 총 32개의 work-item이 sub-group을 구성한다고 하자. Input 데이터를 읽을 때 32개의 work-item들은 row방향으로 연속하게 데이터 32개를 읽게 되는데, 이 경우 GPU는 coalesced memory access를 통해 단 한번의 memory read를 통해 global memory에서 32개의 데이터를 읽어올 수 있다.

 

Coalesced memory access는 연속적인 memory access operation들을 하나의 transaction으로 처리하는 기술[3]이다. 한번의 global memory access로 128bytes(32개의 float)를 읽어올 수 있기에, 4byte(float, int 등)씩 32번 데이터를 읽는 것에 비해 32배 더 빠르게 메모리 접근이 가능하다.

 

Input 데이터를 읽어올 경우 물리적으로 연속적인 32개의 데이터를 읽어오기에 coalesced memory access가 가능하였는데, Output 데이터에 32개의 데이터를 쓸때는 문제가 발생한다. Fig 1.에서 32개의 work-item들은 Output에서 연속하지 않는 데이터 영역에 데이터 쓰기를 진행한다. 따라서 이 경우 32번의 데이터 쓰기는 coalesced memory access가 되지 않고, 실제로 32번 메모리 접근이 발생한다.

 

 

 

병렬화 코드 - 2 : Coalesced Memory Write via Shared Memory

Fig 2. Optimized global memory access 예시. [2]를 참고하여 그림

이러한 inefficient global access pattern을 방지하기 위해 [2]은 Output에 쓸때도 coalesced memory write가 가능한 쓰기 패턴을 제안한다. Fig 2.은 해당 방식을 잘 나타낸 그림이다.

 

핵심은 output에 결과를 쓸때, 그림속 파란색 박스와 같이 sub-group이 shared memory에서 column 방향으로 이웃한 데이터를 읽어와 row 방향으로 이웃한 output의 영역에 데이터를 쓰는 것이다. 이렇게 하면 output에 쓸때 32개의 물리적으로(row 방향으로) 이웃한 데이터 쓰기가 되기에 coalesced memory access가 가능해진다.

 

Shared memory를 쓰는 것은 work-group내 work-item들끼리 데이터를 공유할 수 있도록 하기 위해서이다. 기본구현에서는 하나의 work-item은 자기가 input[x][y]에서 읽어온 데이터를 output[y][x]에 쓰기만 하면 됐었다. 따라서 다른 work-item들끼리의 데이터 공유가 필요없었다. 병렬화 코드 2번 방식에서는 하나의 work-item이 읽어온 데이터와 쓰는 데이터는 서로 다르다. 즉 내가 읽어온 데이터를 shared memory에 저장해놓고, 나는 다른 work-item이 읽어온 데이터를 shared memory에서 읽어와 output에 쓰는 방식으로 진행된다.

 

 

 

병렬화 코드 - 3 : Avoid Shared Memory Bank Conflicts

Shared memory access는 32개의 bank로 구성되며, 각 bank에 나눠진 데이터에 대한 접근은 병렬적으로 처리가 가능하다. 물리적으로 이웃한 shared memory 주소는 다른 bank를 가지도록 구성되는데, 따라서 column 방향으로 이웃한 shared memory 주소는 같은 bank에 속한다. Fig 3.은 shared memory bank conflict 문제를 잘 보여준다. Fig 3. (a)에서 4개의 Cores는 4개의 데이터에 각각 접근하는데, 이 경우 4개의 데이터는 각기 다른 bank에 속하므로 병렬적으로 읽어올 수 있다. 그러나 (b)에서 1번, 2번 core가 1번 bank에 동시에 접근한다. 이 경우 1번 bank는 순차적으로 1번 core의 데이터 처리, 2번 core의 데이터 처리를 한다. 따라서 계산 성능 하락이 불가피하다.

 

Fig 3. Shared memory bank conflict 예시 [4]

 

Fig 2.에서 한 sub-group이 shared memory의 파란색 데이터 영역을 읽을 때, 32개의 work-item은 모두 같은 bank에 접근하게 된다. 이에 따라 32번의 shared memory read는 순차적으로 실행되게 된다. 이를 각기 다른 bank들을 이용해 접근하게 할 수 있다면 32번의 read가 동시에 처리될 수 있어 성능 향상이 가능하다.

 

간단한 트릭으로 이것이 가능한데, 이는 shared memory이 column의 개수를 32가 아닌 33으로 늘려주면 된다. 이렇게하면 column으로 이웃한 주소가 같은 bank에 속하지 않는다.

 

Fig 4. No shared memory bank conflict [5]

Fig 4.은 해당 트릭을 시각적으로 잘 보여준다. 이 예시에서는 bank의 개수를 16개라고 가정하자. 왼쪽의 경우와 같이 column의 개수가 bank의 개수와 같을 경우, 하나의 column에 속한 데이터주소는 모두 같은 bank에 속한다. 오른쪽의 경우와 같이 column의 개수가 bank의 개수보다 1 클 경우, 하나의 column에 속한 데이터주소는 모두 다른 bank에 속한다. 이를 통해 column 방향으로 이웃한 shared memory 데이터를 읽어올 때도 병렬적으로 처리가 가능해진다.

 

 

 

구현

GitHub - jhson989/SYCL-primitives: Basic parallel executed primitives implemented using SYCL

위 프로젝트는 sycl을 통한 parallel matrix transpose를 구현한 것이다.

 

 

 

Reference

[1] https://developer.nvidia.com/blog/efficient-matrix-transpose-cuda-cc/

[2] https://en.wikipedia.org/wiki/Transpose

[3] https://cvw.cac.cornell.edu/gpu/coalesced

[4] Koike, Atsushi & Sadakane, Kunihiko. (2015). A Novel Computational Model for GPUs with Applications to Efficient Algorithms. International Journal of Networking and Computing. 5. 26-60. 10.15803/ijnc.5.1_26. 

[5] http://cuda-programming.blogspot.com/2013/02/bank-conflicts-in-shared-memory-in-cuda.html