매니코어 환경에서의 향상된 기수정렬

Abstract

3차원 메쉬 복셀화는 입력으로 들어온 메쉬 데이터를 복셀 데이터로 변환하는 과정으로 프로세스에는 정렬 알고리즘이 포함된다. 일반적인 정렬 알고리즘은 GPU 구조에서 성능이 좋지 않은 알고리즘이기 때문에 3차원 메쉬 복셀화의 수행시간의 대부분을 차지하는 문제점이 있다. 이 논문에서는 GPU 환경에서의 병렬화가 힘들어 3차원 메쉬 복셀화 수행시간 중 대부분을 차지하고 있는 정렬 부분을 매니코어 환경을 이용하여 최적화한다. 이를 위해 두 단계로 이루어진 개선된 기수 정렬 방법을 사용한다. 이 논문에서 제안한 방법으로 기존의 방법과 비교한 결과, 기존 방법으로 해결할 수 없는 데이터 범위를 정렬할 수 있으며 정렬 가능한 데이터의 경우 데이터 크기에 따라 최대 2.25배의 속도 향상을 얻을 수 있었다.

3D mesh voxelization is the process of converting inputted mesh data into voxel data, which includes sorting algorithm. Since a general sorting algorithm does not have a good performance in the GPU structure, its problem is that it takes up most of the time for 3D mesh voxelization. Using a many-core environment, this paper seeks to optimize the performing time of sorting time which takes up the most time for 3D mesh voxelization because sorting is difficult in a GPU environment. For this, it uses the improved radix sorting method consisting of two-step. According to the result of comparing the existing method to a new method proposed in this paper, the data range that cant be solved by the previous method can now be sorted, with up to 2.25 times of speed improvement gained depending on the data size for the sortable data.