희소행렬이 무엇인지, 희소행렬 곱셈이 어떻게 이루어지는지는 사실 생각보다 간단하다.
하지만 실제 데이터에 대해 연산을 한다면 이런저런 문제가 발생한다.
GPU architecture
일단 GPU를 이용해 연산한다는 가정을 깔고 있기 때문에 간단하게 복기하자면 GPU의 가장 큰 특징은 코어가 여러개란 것이다.
따라서 병렬처리에 용이하지만 만약 자원을 효율적으로 사용하지 못한다면 CPU를 이용해 계산하는 것만 못할 수 있다.
CUDA terminology를 빌려 쓰자면 Thread들의 집합인 Thread block 이 GPU의 SM(Streaming Multiprocessor)에 스케줄링 되고, 블록내의 Thread들은 SP(Streaming Processor)에 의해 수행된다.
이때 32개의 Thread 단위로 같은 instruction을 수행하는데 이를 Warp이라고 부르며 GPU의 기본 수행단위이다.
GPU 메모리는 크게 Global memory, L2, L1 cache, shared memory, register file로 나뉘어지는데 최대한 Global memory access를 줄이는 것이 유리하다.
Load balancing problem
희소행렬 곱셈의 수행시간은 사실 인풋행렬의 형태에 의해 크게 좌우된다.
만약 행렬의 banded matrix를 띄거나 랜덤분포를 이루면 큰 문제가 없겠지만 어떤 행렬들은 power-law degree distribution이라는 특성을 갖는다.
간단하게 말하면 행렬의 특정 row나 column에 0이 아닌 원소들이 몰려있는 분포이다.
이럴 경우 어떤 문제가 발생할까?
Row-wise product-based spGEMM의 경우 각 행마다 원소의 개수가 크게 차이나게 되면 Thread 마다 workload가 차이나게 된다.
물론 이를 해결하기 위해 따로 Thread들의 작업량을 균등 분배하기 위해 전처리를 가할 수 있지만 "전처리 시간 + 추가 memory access cost"를 고려한다면 효과가 미미하거나 오히려 손해를 볼 가능성이 있다.
Outer product-based spGEMM의 경우엔 column의 각 element에 곱해지는 B의 벡터가 같기 때문에 Thread간 load imbalance 문제는 발생하지 않는다.
하지만 power-law 특성이 더 강해지면 Outer product에선 문제가 더 심화된다.
Power-law 특성이 강해지면 Row-wise나 Outer product 방식이나 두 방식 모두 load balancing 문제가 발생하게 되지만
Outer-product의 경우 column의 원소가 모두 동일한 벡터와 곱해진다. 따라서 column, row 모두 0이 아닌 원소가 많은 밀도 높은 벡터일 경우
workload amplification이 일어난다. 즉 Thread 간 workload는 동일하지만 Thread block 간 심각한 load imbalance가 발생하는 것이다.
보통의 경우 Thread block이 충분히 많다면 Round-Robin 스케줄링으로 격차가 메워지지만 Power-law가 심한 경우엔 심각한 성능저하가 발생한다.
이를 방지하기 위해 벡터를 쪼개는 방식을 이용한다.
Too Sparse Matrix
인풋 행렬이 Power-law 특성을 가진다는 것은 몇몇 노드들은 0이 아닌 원소가 굉장히 많다는 것을 의미하면서 동시에 대부분의 노드들은 0이 아닌 원소가 거의 없다는 것을 뜻한다.
GPU에서 가장 작은 수행단위가 32개의 Thread들의 집합인 warp이기 때문에 특별한 전처리를 하지 않는다면 각 연산마다 적어도 32개의 0이 아닌 원소가 필요하다.
하지만 데이터를 분석해보면 대부분의 노드의 차수(0이 아닌 원소의 개수)가 32도 안되는 경우가 많다.
이 경우 GPU의 자원이 낭비된다. Thread 가 instruction을 수행해야 하지만 issue 가능한 instruction이 없기 때문에
첫째로는 sp 코어가 놀게된다.
또 GPU는 많은 양의 register file로 각 Thread가 필요한 data들을 load 해놓고 stall이 필요할 때 context-switching을 이용하여 latency-hiding을 하지만
이 경우엔 latency-hiding을 할 수 없게된다.
이 문제를 해결하는 방법은 여러가지겠지만 Thread coarsening 이라는 직관적이고 간단한 방법으로 전처리 cost가 거의 없이 어느정도 완화할 수 있다.
Output management
희소행렬 곱셈을 수행할 때 생기는 문제들은 이것저것 있지만 사실 가장 큰 문제는 너무 큰 아웃풋 사이즈, 그리고 아웃풋을 관리하는 것이다.
첫째로 아웃풋의 원소가 몇개생길지 계산해보기 전까진 알 방법이 없다. 따라서 미리 아웃풋의 메모리를 할당받아야 하는 GPU의 경우 최대 얼만큼의 메모리가 필요한지 계산하는 과정이 필요하다.
이 과정을 거쳐야 2번째 포스팅 코드의 offset을 구할 수 있다.
두번째로 곱셈계산을 끝내면 위치가 중복된 원소들이 존재한다.
Row-wise 방식의 경우 Output Matrix C의 각 행마다 겹치는 원소가 존재하고
Outer-product 방식의 경우 판단위로 겹치는 원소가 존재하는데 결국 이 원소들을 전부 합쳐서 1개의 원소로 만들어야 곱셈연산이 완벽하게 끝난 것이다.
그럼 두가지 선택을 할 수 있는데 1) 모든 원소가 계산된 후 Merge Process를 수행한다. 와 2) 계산 중 겹치는 원소들을 Merge한다. 가 있다.
개인적으로 Row-wise product의 경우 2), Outer product의 경우 1)로 노선을 잡는게 맞는 것 같다.
Row-wise product의 경우는 행단위로 merge process가 이루어지기 때문에 겹치는 원소들이 이미 같은 SM에 존재하지만
Outer product의 경우 판단위 merge process가 필요하기 때문에 겹칠 원소들을 미리 모아놓지 않는다면 SM간 communication cost가 필요하고 굉장히 알고리즘적으로 복잡할 것이기 때문이다.
아웃풋을 어떻게 관리할지는 아직 연구가 필요한 부분이라고 생각되며 뚜렷한 해결책이 생각나지 않는다.
사실 merge process는 결국 memory transaction이 굉장히 많이 일어나기 때문에 최적화의 여지가 별로 없다.
merge 될 원소와 merge가 필요 없는 원소를 따로 분리하고 memory 접근을 줄이는 방향으로 생각해봤지만 사실 어떤 원소가 merge될지 안될지는 찍기나 다름없다.
이외에도 matrix내의 locality를 증가시킨다거나 하는 접근법이 있긴하지만 1) 전처리 시간이 오래걸린다는 점과 random 분포에선 사실상 NP problem이기 때문에 이는 고려하지 않겠다.
희소행렬 곱셈에 대해 연구하다보면 이런 문제들이 존재하고 이를 해결할 수 있는 접근법이 필요해진다.
댓글 없음:
댓글 쓰기