GPU에서 효율적인 병렬처리를 위한 R-tree 질의 처리 기법 (Range Query Method of R-tree for Efficient Parallel Processing on GPU)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 18권 / 5호 / 409 ~ 413페이지
· 저자명 : 김민철, 최원익

초록

Guttman이 처음 R-tree를 제안한 이후에 R-tree의 질의 성능 향상을 위한 연구가 많이 이루어졌다. 기존의 연구들은 R-tree의 공간 활용도를 증가시키고 MBR의 중복 영역을 줄이는데 중점을 두었다. 이러한 연구는 크게 R-tree의 분할 및 병합 알고리즘을 향상시키는 기법, 벌크 로딩을 이용해서 공간 활용도를 증가시키는 방법 그리고 R-tree의 노드를 메모리 또는 저장 데이터의 특성에 맞추어 노드 구조를 변경시키는 기법 등이 있다. 비록 이러한 기법들이 R-tree의 질의 처리 성능을 향상시켰지만 CPU의 순차적 처리 특성 때문에 CPU기반의 R-tree의 성능 향상에는 한계가 있다. 본 논문에서는 CPU의 순차처리 한계를 극복하기 위해서 GPU에 적합한 R-tree인 G-tree를 제안한다. G-tree는 GPU 메모리 특성에 맞도록 노드의 구조를 변경하였다. 또한 CPU 기반의 R-tree의 검색 순서인 깊이 우선 검색 방식을 GPU에 적합하도록 너비 우선 검색 방식으로 변경하여 최대의 병렬화 효과를 이끌어 냈다. 실험에서는 실제 환경을 적용하기 위해서 캘리포니아 도로 데이터를 사용하였다. 실험 결과에서 G-tree는 CPU 기반의 R-tree에 비해 질의 영역의 넓이에 따라서 최대 2000배 가량의 성능향상을 보여주었다.

영어초록

Since Guttman's paper in 1984, there have been a number of researches and attempts for increasing R-tree's range query performances. Those researches include the advancements of split & merge algorithms and the bulk loading approaches. Also, researches on modifying the node structure to be optimized for different levels of the memory hierarchy have been well studied. Although these works have improved R-tree's range query performances, there are limitations to achieve more range query performance gain from CPU-based R-trees. It is due to CPU's sequential processing. In this paper, we propose a GPU sensitive R-tree called G-tree. It overcomes the limitations of such CPU-based R-trees. It is a variant of R-trees that consists of modified node structures in order to adapt to the GPU memory access pattern. Furthermore, it consists of modified query sequence to be suitable for GPU processing architecture. In experiments, we use a real dataset. Experimental results show that G-tree is up to 2000 times faster than CPU-based R-trees as size of query region increases.

참고자료

· 없음