C 함수를 CUDA로 포팅하기

CPU에서 구현했던 각종 C 함수를 GPU에서 돌리기 위해 며칠째 똑같은 삽질을 계속하는 중.

GPU는 서로 다른 자료를 가지고 동일한 연산을 수행하는 데에 매우 탁월하므로 상당한 가속이 이루어질 것으로 생각하고 포팅하고 있지만 여러가지 난제에 부딪히고 있다.

1) 알고리즘 복잡도
물론 상당히 복잡한 알고리즘도 포팅할 수는 있겠지만, 과연 효율적인가에 대해서는 의문이 남는다. 주지한 바대로 GPU상에서 가속되는 요인 중 하나는 동시에 여러 쓰레드가 돌기 때문이다. 동시에 구동 가능한 쓰레드의 수는 세 가지의 요인에 의해 결정된다. 첫번째는 사용된 레지스터의 수이고, 두 번째는 shared memory의 크기, 마지막 하나는 사용한 GPU의 사양이다. 이 세 가지는 런타임에 결정되는 것이 아니라 컴파일 시점에 결정되는데, 사용한 컴파일러 (정확히 얘기하면 CUDA nvcc의 버전)에 따라 다르게 결정되므로 CUDA 라이브러리의 버전을 잘 결정할 필요가 있다.

예를 들어, hypothesis-test의 형태를 갖는 알고리즘을 만든다고 하면, test단계는 보통 비교적 간단한 사칙연산으로 해결되는 경우가 많다. 이러한 사칙연산에는 GPU가 매우 강력한데 이는 비교적 레지스터를 적게 쓰면서 해결할 수 있고, 구현상 branch가 적은 단일 flow process가 되는 경우가 많기 때문이다. 이러한 구조의 계산에서 병렬계산은 매우 강력하며 상당히 많은 수의 쓰레드를 동시에 수행할 수 있다. 반면, hypothesis 단계는 단순 random process나 markov random walk의 경우처럼 간단하게 구현되는 경우가 아닌 model fitting이 필요한 경우라면 비교적 복잡해진다. 특히 수치해석기법이 활용된 경우에는 수많은 반복 연산과 divergent branch가 존재하므로 그만큼 많은 레지스터를 소모하게 된다.

간단한 예로 numerical recipe등에 있는 singular value decomposition 알고리즘을 보면, householder matrix로 바꾸어 reduction하는 과정을 거치는데, 이 과정에서 loop와 branch가 많아서 레지스터 소모량이 크다. svd를 한 번 사용하면 cuda 2.0 beta의 경우 레지스터를 거의 30개 정도 사용하게 되며 이 경우 쓰레드는 최대 16개 구동할 수 있다. 물론 그것만 할 수는 없으므로 더 사용하게 되면 동시 구동되는 쓰레드의 수는 더 줄어든다.

가속성능이 얼마나 나올지는 구현한 알고리즘에 따라 달라질 수 있다. 관건은 사용된 레지스터의 수를 줄이는 것이며 이는 컴파일러 성능에 비례한다.

2) pointer argument의 사용
CUDA로 포팅하면서 조금 난감한 문제 가운데 하나는 __device__함수에서 메모리 할당이 안된다는 점이다. GPU에서는 계산만 수행하므로 메모리관리는 외부에서 직접 해주어야 한다. 그런데 보통의 C 함수 구현에서는 보통 가변메모리를 할당해서 다른 함수의 인자로 넘겨주어 결과를 받아오는 경우가 많고 특히 벡터나 행렬연산을 하는 경우에 이런 패턴으로 구현하는 경우가 많다. 이러한 패턴은 CUDA를 사용해도 허용되지 않으므로 내부에서 사용될 메모리를 밖에서 미리 잡아 넘겨주어야 한다.

그러나 모든 부속함수의 모든 지역변수를 일일히 cudaMemAlloc으로 잡는 것은 너무 번거로운 일이고 device global 메모리를 사용하면 coalescing을 신경써야 하므로 일이 너무 커진다. 특히나 알고리즘이 복잡해질수록 더욱 그렇다. 이때는 shared memory를 사용해서 빠르게 access해야 하는데, 서로 다른 쓰레드가 서로 간섭하지 않도록 shared memory space를 디자인하는 것이 중요하다. 예를 들어 쓰레드의 갯수가 n이고 m 벡터를 인자로 넘기는 상황이라면, nm 크기의 shared memory를 잡아서 함수내에서 써 주는 식이다.

여기서도 볼 수 있는 것은 함수 내의 메모리할당이 많은 알고리즘일수록, 그리고 벡터의 크기가 클 수록 shared memory의 사용량이 비례해서 증가한다는 점이다. 쓰레드 블록내에서 shared memory의 크기가 한정되어 있으므로 global memory를 사용하지 않는다면 쓰레드 갯수를 늘리는 것이 한정되며 이는 가속성능을 저하시킨다.

shared memory를 얼마나 쓸지는 코딩 단계에서 결정되므로 신중히 결정해야 한다. 너무 크면 동시에 구동되는 쓰레드가 적어질 수 있고, global memory에 많이 할당하면 그만큼 쓰레드 수행 속도가 느려진다.
(shared memory 변수는 함수 내에서도 정의할 수 있는 것으로 보이나 가급적이면 전역변수로 선언하자. 컴파일러나 런타임라이브러리에 따라 다른 결과를 보이는 것 같다.)

3) Precision의 문제
GPU는 아직까지 single precision 계산만을 지원한다. CUDA 2.0과 GT200 GPU가 나오면서 double precision계산이 지원되기 시작한 것으로 보이지만, Compute Capa. 1.3이상인 GPU를 사용해야만 가능한 것 같다. 결국, 시도라도 해보려면 GT200을 사용하는 GTX280, GTX260이나 Tesla S1070, C1060중에 하나를 사용해야 한다는 의미. (2008년 7월 15일 현재)

결국 알고리즘이 double precision을 필요로 하는 경우에는 CUDA 활용이 제한될 수 밖에 없다. 이런 경우는 수치해석기법이 필요한 경우 많이 발생할 것 같은데, condition number가 작은 문제인 경우, 또 반복적인 계산을 통해 최적화를 수행하는 과정이 들어간 경우 등이 이에 해당할 것이다. 특히나 중간 계산값에 따라 결과 정확도가 많이 달라지는 경우에는 precision을 반드시 체크해봐야 할 것 같다.