GPU 기반 병렬 Shifted Sort 알고리즘을 이용한 Signed Distance Fields 구현 :Implementation of Signed Distance Fields Using GPU-based Parallel Shifted Sort Algorithm

김희수

추천

검색

자료유형: 학위논문

저자정보: 김희수 (덕성여자대학교, 徳成女子大學校大學院)

지도교수: 박태정

발행연도: 2018

저작권: 덕성여자대학교 논문은 저작권에 의해 보호받습니다.

이용수1

이 논문의 연구 히스토리 (2)

2018

GPU 기반 병렬 Shifted Sort 알고리즘을 이용한 Signed Distance Fields 구현

김희수 디지털미디어학과 2018.01 학위논문

2017

일반적인 GPU 트리 탐색과의 비교실험을 통한 GPU 기반 병렬 Shifted Sort 알고리즘 분석

김희수 , 박태정 디지털콘텐츠학회논문지 2017.10 학술저널

이 논문의 후속연구가 궁금하신가요?
연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
이 논문의 연구 히스토리 확인하기

초록· 키워드

오류제보하기

Signed Distance Fields (SDF)는 다양한 분야에서 사용되어 왔고 이제는 그 범위가 더 넓어지고 있다. 이러한 SDF를 계산하는 방법에 있어서 일반적인 GPU 기반 트리 탐색을 수행할 경우 병렬 처리 속도가 생각보다 크게 향상되지 않는 경우가 대부분이다.
본 논문에서는 Shifted sort 알고리즘을 대안으로 제시하고 트리 탐색에서의 병렬 탐색 효율 저하는 GPU 병렬 처리 하드웨어 아키텍처 내 최소 물리적 스레드 실행 단위인 warp에서의 분기문(if, else 문)으로 인한 warp divergence가 일어나기 때문임을 제시한다. Shifted sort 알고리즘은 warp divergence가 상대적으로 적어 일반적인 트리 탐색에 비해 빠른 계산 속도를 보이지만 shifted sort 알고리즘은 아직 공간 탐색에 대한 연구가 진행되지 않아 kd-tree와 같은 일반적인 트리 탐색처럼 공간을 탐색하는 데 어려움이 있다. 따라서 주어진 메시의 최소단위 face인 삼각형의 중점을 shifted sort 알고리즘의 입력데이터로 사용하여 삼각형에 대한 고속 탐색 실험을 수행함으로써 shifted sort 알고리즘 방식의 SDF 계산 가능성 여부를 테스트하고자 한다. 이후 삼각형에 대한 입력 데이터를 중점, 꼭짓점, 삼각형 세 변의 중점까지 테스트 범위를 확장하고자 한다.
Shifted sort 알고리즘을 이용한 SDF 구현은 정확성과 빠른 처리 속도 이 두 가지 특성을 가지고 그 성능을 증명한다. 정확성의 경우 3차원 샘플모델을 reduction SDF 방식과 shifted sort 알고리즘으로 구현한 SDF 방식 이 두 가지 알고리즘을 이용한 SDF의 결과를 비교하여 L2 norm 계산을 통해 두 결과의 오차의 크기에 대해 분석한다.
Reduction SDF 방식은 하나의 쿼리와 모든 삼각형과의 거리를 계산한 후, 가장 최소의 거리를 가지고 있는 값을 가지고 거리장을 만든다. 이는 100%에 가까운 정확성을 가지고 있기 때문에 shifted sort 알고리즘으로 구현한 SDF의 결과와의 비교를 통해 제안하는 알고리즘으로 구현한 SDF의 값이 얼마만큼의 정확한 값을 가지는지 알 수 있다. [0, 0.75]3의 범위 내에서 최대로 나올 수 있는 결과와 제안하는 알고리즘으로 구현한 두 값의 비교 결과 모델에 따라 최소 0.0002%부터 최대 0.9%의 오차율을 가지며, 이는 최소 99.1%의 정확성을 가진다.
처리 시간의 경우, 100%의 정확성을 가지고 있는 reduction SDF를 크기가 같은 삼각형으로 이루어져 있는 geosphere 모델을 가지고 SDF를 구현하는데 15467ms가 소요되고, SDF 구현에 주로 사용되는 일반적인 트리 탐색 알고리즘인 kd-tree 탐색에서 SDF를 구현했을 경우 최대 처리시간이 707ms 걸린다. 반면, shifted sort 알고리즘을 이용하여 SDF를 구현한 경우 330ms로 kd-tree 탐색 알고리즘과는 약 2.3배의 시간 차이를 보인다. 이는 100%의 정확성을 가지고 있는 reduction SDF 방식의 최대 처리 시간인 15467ms보다는 약 46배 빠르다. 이후, visual profiler 분석을 통해 일반적인 트리 탐색 알고리즘인 kd-tree와 shifted sort 알고리즘과의 정확한 성능 비교를 제시한다.

Computer graphics fields that use Signed Distance Fields (SDF) are increasing. Parallel processing speed is not significantly improved when performing a general GPU-based tree search method to calculate SDF.
In this paper, we propose an alternative shifted sort algorithm to show that parallel search efficiency degradation in tree search is caused by warp divergence due to branch statement (if statement) in warp, the minimum physical thread execution unit in GPU parallel processing hardware architecture. The shifted sort algorithm has a low warp divergence that is faster than a general tree search algorithm. However, it difficult to search a space like a normal tree search in a kd-tree because the shifted sort algorithm is not applicable to a spatial search. Therefore, we want to test calculating a SDF with a shifted sort method that performs a fast search experiment on the triangle using the center point of the triangle as the minimum unit face of the given mesh representing the input data of the shifted sort. We then extend the test range from the point of the triangle input data to the triangle midpoint and the vertices of the triangles.
The shifted sort algorithm demonstrates its performance with accuracy and fast processing speed. In case of accuracy, the SDF method that implements the 3D sample model with the reduction SDF method and the shifted sort algorithm compares the results of the SDF using the two algorithms and analyzes the error magnitudes of the two results through L2 norm calculation.
Reduction SDF method calculates the distance between one query and all triangles, and then produces a distance field with the smallest distance. Since this is close to 100% accuracy, we can see how accurate the value of SDF implemented by the proposed algorithm is by comparing with the result of SDF implemented with shifted sort algorithm. According to the comparison result of the two values implemented by the proposed algorithm, the error rate is at least 0.0002% up to 0.9%, which is at least 99.1% accurate.
In the case of the processing time, SDF is implemented with a geosphere model consisting of a triangle of the same size. The reduction SDF takes 15467ms. When SDF is implemented in kd-tree search algorithm is 707ms. On the other hand, if the SDF is implemented using the shifted sort algorithm, it takes 330ms. This is about 46 times faster than the maximum processing time of the reduction SDF method of 15467ms and 2.3 times faster than the kd-tree SDF method. Then, we show the accurate performance comparison between the general tree search algorithm kd-tree and the shifted sort algorithm through visual profiler analysis.

Ⅰ. 서론 ······················································································································ 1
1. 연구 목적 ········································································································· 1
2. 연구 방법 ········································································································· 2
Ⅱ. 연구의 이론적 배경 ··························································································· 3
1. 공간 분할 구조 ······························································································· 3
1) Approximate Nearest Neighbor (ANN) 탐색 ···································· 3
2) Octree 탐색 ································································································ 5
3) kd-tree 탐색 ······························································································ 7
2. CUDA의 기본 구조 ························································································ 8
1) Warp ············································································································ 9
2) Warp Divergence ··················································································· 11
Ⅲ. Shifted sort 알고리즘을 이용한 Signed Distance Fields ···················· 12
1. Signed Distance Fields (SDF) ································································· 12
2. Shifted sort 알고리즘 ················································································· 14
1) 동작 원리 ··································································································· 16
2) 구현 ············································································································ 17
3. 실험 개요 ········································································································ 18
Ⅳ. 실험 결과 및 분석 ····························································································· 19
1. Shifted sort 알고리즘을 이용한 SDF의 정확성 ····································· 19
1) 커널 분석 ··································································································· 22
2) Visualization ···························································································· 31
3) 개선 방향 ··································································································· 33
2. Shifted sort 알고리즘의 처리 속도 ·························································· 36
1) kd-tree와 Shifted sort 알고리즘의 커널 분석 ································· 39
2) 개선 방향 ··································································································· 42
Ⅴ. 결론 및 향후 연구 ··························································································· 43
참 고 문 헌 ············································································································· 45
ABSTRACT ············································································································· 47
감사의 글 ················································································································· 49

최근 본 자료

전체보기

구분	그룹	데이터 항목
AI 학습용 데이터	원문	원문 PDF 파일
AI 학습용 데이터	원문 + 메타 (기본/상세)	원문 PDF 파일 및 서지정보 CSV
대량 구매용 데이터	B2B 구독 방식	특정 자료 한정으로 원문 접근 권한 부여
대량 구매용 데이터	URL 전달 방식	바로 PDF 뷰어를 열람할 수 있는 URL 제공

구분	그룹	데이터 항목
AI 학습용 데이터	기본 메타	발행기관명, 간행물명, 권호명, 권(vol), 호(issue), 통권, 발행연도, 발행월, 논문명, 저자명, 시작페이지, 종료페이지, 전체페이지, 상세페이지URL
상세 메타 데이터	발행기관 메타	발행기관 이명, 영문명, 창립연도, 홈페이지URL, 발행기관 소개
	간행물 메타	부제목, 간행물 유형, ISSN, ISBN, 최초발행연도, 폐간연도, 간행빈도, 발행주기, 등재사항, 이용수, 피인용수, 권호수, 논문수, 표지이미지
	논문 메타	작성 언어, 부제목, 대등제목, 목차, 키워드, 초록, 이미지, 참고문헌, 이용수, 피인용수, 논문활용도, DBpia통합주제분류, KDC분류, DDC분류, 한국연구재단분류, UCI, DOI
	저자 메타	소속기관, 소속부서, 직급, 연구분야, 연구키워드, 이용수, 피인용수, 저자 논문활용도

구분	그룹	데이터 항목
※ 결합형/맞춤형 메타 데이터는 신청 내용에 따라 다양하게 제공 가능
이용순위 정보	주제분야별 많이 이용된 논문	“인문학”에서 많이 이용된 논문 TOP100
	이용기관별 많이 이용된 논문	“중고등학교”에서 많이 이용된 논문 TOP100
	세부기관별 많이 이용된 논문	“서울대학교”에서 많이 이용된 논문 TOP100
	키워드별 많이 이용된 논문	“Chat GPT”에서 많이 이용된 논문 TOP100
키워드 정보	많이 이용된 키워드	특정기간/분야/저널 내 많이 이용된 키워드
	많이 발행된 키워드	특정기간/분야/저널 내 많이 발행된 키워드
	많이 검색된 키워드	특정기간/분야/저널 내 많이 검색된 키워드
	연구 트렌드 키워드	특정 키워드 연관 연구동향 분석 데이터 키워드

논문 기본 정보

이 논문의 연구 히스토리 (2)

초록· 키워드

목차

최근 본 자료

댓글(0)