yuchi's development

KD-Tree를 순회할땐 stack이 필요하다. stack을 구현한다는게 CPU코드에선 아무 문제도 아니지만 CUDA에선 고민이 좀 필요하다.
CUDA에서 자유롭게 쓸 수 있는 메모리는 Global Memory이다. 그런데 겁나 느리다. 시스템 메모리보단 엄청 빠르지만 GPU보단 한참 느리다.
stack을 global memory에 올려놓으면 아무래도 억세스할때마나 stall이 걸린다.
CUDA에서 사용할 수 있는 고속 메모리는 shared memory가 있다. 여기다 stack을 올려놓으면 물론 빠르다. 그런데 shared memory는 용량이 제한되어있다. 안그래도 적은데 이걸 block내의 thread가 나눠 쓰려니 정말 택도 없이 부족하다.
그래서 다음의 두가지 방법을 추가하여 총 세가지 방법으로 구현하고 테스트해봤다.

1. stack on Global Memory
커널함수 안에서 잡은 배열(global memory)에 stack을 올린다. 코드는 심플하다. CPU코드와 완전히 같다.

2. stack on Shared Memory + short stack
shared memory에 stack을 올려놓되 occupancy를 떨어뜨리지 않을 정도로 작은 사이즈만 할당한다. stack사이즈가 모자라면 가장 앞쪽 leaf까지 순회한 후 stack을 비우고 이때까지의 min_t, max_t값으로 root 노드부터 다시 탐색한다.

3. stack on Shared Memory + stack on Global Memory
shared memory에 stack을 올려놓되 occupancy를 떨어뜨리지 않을 정도로 작은 사이즈만 할당한다. stack 사이즈가 모자라면 stack의 메모리를 global memory로 치환한다. 기존에 들어있던 데이터는 global memory로 카피한다.

이렇게 구현한후 결과를 보면…
CPU : Xeon e5-2620@ 2.4GHz,
GPU : GTX 1060
테스트 환경 : 복셀 오브젝트 54000여개, 복셀개수 1500만여개

1. stack on Global Memory
필요 레지스터 수(SM5.2기준) : 45개
라이트맵 베이킹에 걸린 시간 : 4603.69ms

2. stack on Shared Memory + short stack
필요 레지스터 수(SM5.2기준) : 47개
라이트맵 베이킹에 걸린 시간 : 4874.14ms

3. stack on Shared Memory + stack on Global Memory
필요 레지스터 수(SM5.2기준) : 53개
라이트맵 베이킹에 걸린 시간 : 4664.40ms

그냥 쌩으로 Global Memory에 올린게 제일 빠르다.
3번이 제일 빠를줄 알았는데 근소한 차이로 2위를 기록하고 있다. 3번의 경우 레지스터 개수를 많이 소모하는게 문제인걸로 추측한다. Occupancy를 이론상 100%로 맞추기 위해서 3가지 방식 모두 컴파일시 레지스터 개수를 32개로 제한했다. 레지스터 개수를 제한했기 때문에 부족한 레지스터 수만큼 global memory억세스를 더 하게 된다. 이 점에서 레지스터를 가장 많이 사용하는 3번이 가장 불리하다. shared memory를 사용하고 추가적인 node탐색을 하지 않는만큼의 성능이득을 레지스터 부족으로 까먹었다고 예상할 수 있겠다.

2번은 역시나 추가적인 node 탐색이 문제가 된다. 사용하는 레지스터 개수도 적은 편이고 global memory 억세스도 적은건 이득이지만 추가적인 node탐색시 워프내의 다른 스레드들이 몽땅 놀게 되기 때문에 성능 하락이 크다.

다른 하드웨어 조합으로도 테스트 해보고 1번으로 갈지 3번으로 갈지 결정해야겠다. 아마 다른 조합에서도 1번이 제일 빠를거 같다만…