21. Parallel Collision Detection Method based on kd-tree Implemented in GPU

Title(KR)

• GPU 기반 kd-tree를 이용한 병렬 충돌 처리 기법

Title(ENG)

• Parallel Collision Detection Method based on kd-tree Implemented in GPU

Keywords(KR)

• 충돌 처리, GPU, 병렬 처리, Fermi 아키텍처

Keywords(ENG)

• collison dectection, GPU, parallel processing, Fermi architecture

Author

• Taejung Park

Abstract(KR)

GPU는 메모리 대역폭이 연산 속도를 결정하는 병목 지점이 된다. 즉, GPU 프로그래밍 시에는 불규칙적인 메모리 액세스나 다중 스레드들 사이에서의 서로 다른 명령 실행 분기가 발생하면 속도가 크게 저하되는 문제가 발생한다. 따라서 게임 엔진 충돌 처리용으로 사용되는 kd-tree와 같은 적응형 탐색(adaptive traverse) 기법은, 불규칙적인 메모리 액세스 및 서로 다른 명령 분기로 인해 지금까지 GPU 구조에 적합하지 않은 것으로 인식되어 왔다. 그러나 최근 NVIDIA의 Fermi 아키텍처의 등장과 함께 CPU에서처럼 GPU 다중 프로세서에도 캐시 메모리가 적용되고 있다. 본 논문에서는 이러한 새로운 GPU 아키텍처의 장점을 활용해서 충돌 처리 시간을 크게 줄일 수 있는 GPU 기반 kd-tree를 제안한다. 제안하는 GPU 기반 병렬 kd-tree는 체크 지점 65536 개에서 최근접 삼각형까지의 거리를 찾는 작업이 Fermi 아키텍처(캐시 적용) 기반에서 단일 코어 CPU 기반 kd-tree에 비해 평균 백 만 배 이상(1.0x106) 빨라졌으며, 이전 세대 Tesla 아키텍처(캐시 미적용) 기반 병렬 kd-tree에 비해서도 약 50 배 가까이 빠른 속도를 보였다.

Abstract(ENG)

GPU has a performance bottleneck in memory bandwidth; GPU performance becomes degenerated when irregular memory access patterns and different branching occur. In this regard, it had been known that adaptive traverse methods including kd-tree, which inevitably cause irregular memory access and branching patterns were not suitable for GPU programming. However, with recent advance in GPU hardware architecture, NVIDIA’s Fermi architecture in particular, it is possible to embed cache memories for multi-cores in GPU. In this paper, we present a parallel kd-tree based on GPU for fast collision detection. Our method reduces time in detecting collisions for around one million fold for test meshes than kd-tree implemented in a single CPU core. Besides, the kd-tree implemented in newer Fermi architecture is around 50 times faster than the previous generation Tesla architecture thanks to multiprocessor memory caches.

Page 195-203