Proximity computation is one of the most fundamental geometric operations for various applications including physically-based simulations, computer graphics, robotics, Etc. Also proximity computation is one of the most time consuming parts in various applications. There have been numerous attempts to accelerate the queries like adopting an acceleration hierarchy to cull redundant computations. Even though these methods are general and improve the performance of various proximity queries by several orders of magnitude, there are ever growing demands for further improving the performance of proximity queries, since the model complexities are also ever growing. Recently, the number of cores on a single chip has continued to increase in order to achieve a higher computing power. Also, various heterogeneous computing architectures consisting of dierent types of parallel computing resources have been introduced. However, prior acceleration techniques such as using acceleration hierarchies gave less consideration for utilizing such parallel architectures and heterogeneous computing environments. Since we are increasingly seeing more heterogeneous computing environments, it is getting more important to utilize them for proximity queries, in an ecient and robust manner.
In this thesis, we employ heterogeneous parallel computing architectures to accelerate the performance of proximity computation for various applications. To eciently utilize heterogeneous computing resources, we propose parallel computing systems and algorithms for proximity computation. We start with a specic proximity query and design a novel ecient parallel algorithm based on knowledge of the query and computing resources. Then we extend our method to various proximity queries and propose a general proximity computing framework. Also we improve the utilization eciency of computing resources by designing optimization-based scheduling algorithm. With the proposed methods, an order of magnitude improvement is achieved on various quires by using up to two hexa-core CPUs and four dierent GPUs over using a single CPU core. In addition we propose an out-of-core proximity computation algorithm to handle a massive data that requires a larger memory space than the memory size of a computing resource in a heterogeneous computing system, especially for the particle-based fluid simulation. The proximity computing system using the out-of-core algorithm robustly works for a large-scale scene and achieves up to two order of magnitude performance improvement over a previous out-of-core approach. These results demonstrate the eciency and robustness of approaches.
근접질의(proximity query)는 물체들 사이의 거리와 관련된 연산들로서, 컴퓨터 그래픽스, 물리기반 시뮬레이션, 로봇 공학 등 다양한 분야에서 사용되는 기반 연산 중 하나다. 근접질의는 또한 각종 응용 분야에서 가장 많은 연산 시간을 요구하는 연산이기도 하다. 이와 같은 근접질의 연산의 넓은 활용 분야와 그 연산 속도의 중요성에 따라 계층적 공간 분할 자료구조 등과 같은 다양한 가속 기술이 개발되어왔다. 이러한 가속 기술에 힘입어 연산의 속도가 수 십에서 수 백배 향상되었지만, 대용량 데이터에 대해 실시간의 성능을 제공하기에는 여전히 충분한 성능을 보여주지 못하고 있다. 최근 연산장치의 발전 경향을 살펴보면, 단일 연산 코어의 성능을 향상시키는 것 보다 하나의 칩(chip)에 여러 개의 연산 코어를 집적하는 방향으로 발전하고 있다. 이와 더불어 Intel의 Sandy Bridge나 Sony의 Cell 구조 같은 이종 병렬처리(heterogeneous parallel computing) 연산장치도 활발히 개발되고 있다. 하지만 기존 근접질의 가속 기술들은 병렬처리에 대한 고려가 미미한 편이다. 최근 다양한 병렬처리 근접질의 기술들이 개발되고 있지만, 다중 코어 CPU 또는 GPU 등 한 종류의 연산 장치 만 활용한다는 한계점을 가지고 있다. 또한, 여전히 대용량 데이터에 대해 실시간 성능을 보여주지 못하고 있다.
본 논문에서는 이종 병렬처리 연산장치를 활용하여 근접질의 연산을 가속한다. 그리고 효율적인 이종 연산 장치의 활용을 위한 시스템 및 알고리즘들을 제안한다. 본 논문은 우선 근접질의의 하나인 연속 충돌탐지 연산을 다중 코어 CPU와 GPU를 동시에 사용하여 가속하는 병렬처리 알고리즘을 제안한다. 다음으로 알고리즘을 다양한 근접질의로 확장하고 범용적 이종 병렬처리 연산 시스템을 제안한다. 또한, 최적화 기반의 일 분배 알고리즘을 제안하여 연산 시스템의 활용 효율을 극대화 한다. 제안하는 기술들은 다양한 근접질의에 적용되었으며, 두 개의 다중 코어 CPU와 네 개의 서로 다른 GPU를 사용하여 다중 코어 CPU 하나 사용 대비 10배 이상의 성능 향상을 얻을 수 있었다. 이는 본 연구의 범용성과 효용성을 증명하는 결과이다. 또한 본 논문은 연산 장치의 주기억 장치의 용량을 초과하는 대용량 데이터를 다루기 위한 아웃 오브 코어(out-of-core) 근접 질의 기술로 연구의 영역을 확장한다. 본 논문은 대규모 입자기반 유체 시뮬레이션처리를 위한 아웃 오브 코어 근접 질의 기술을 제안한다. 이를 통해 대규모의 입자를 안정적으로 처리 가능하며, 기존 아웃 오브 코어 기술 대비 최대 수십 배의 성능 향상을 얻을 수 있다. 이러한 연구 결과는 본 논문이 제안하는 기술들의 안정성과 효용성을 증명한다.
