Journal of Digital Contents Society (디지털콘텐츠학회 논문지)

Digital Contents Society (한국디지털콘텐츠학회)
권호 표지
DOI QR코드

DOI QR Code

Analysis of Morton Code Conversion for 32 Bit IEEE 754 Floating Point Variables

IEEE 754 부동 소수점 32비트 float 변수의 Morton Code 변환 분석

  • Park, Taejung (Dept. of Digital Media, Duksung Women's University)
  • Received : 2016.05.09
  • Accepted : 2016.06.29
  • Published : 2016.06.30
Download PDF
⟨ Previous Next ⟩

Abstract

Morton codes play important roles in many parallel GPU applications for the nearest neighbor (NN) search in huge data and queries with its applications growing. This paper discusses and analyzes the meaning of Tero Karras's 32-bit 'unsigned int' Morton code algorithm for three-dimensional spatial information in $[0,1]^3$ and its geometric implications. Based on this, this paper proposes 64-bit 'unsigned long long' version of Morton code and compares the results in both CPU vs. GPU and 32-bit vs. 64-bit versions. The proposed GPU algorithm runs around 1000 times faster than the CPU version.

GPU 기반 병렬처리에서 대규모 데이터의 인접 정보 검색(nearest neighbor search)에서 Morton code의 역할이 점점 더 중요하게 부각되고 있으며 그 응용 사례도 점차 증가하고 있다. 본 논문에서는 Tero Karras가 제안한 float 형 변수에 기반한 $[0,1]^3$ 공간 내의 3차원 기하 정보를 32비트 unsigned int형 Morton code로 변경하는 기존의 방법을 논의하고 그 기하학적인 의미를 분석함으로써, 보다 높은 해상도를 구현할 수 있는 64비트 unsigned long long형의 Morton code 변환 알고리듬을 제안한다. 제안하는 알고리듬은 GPU에서 구현되었을 때 CPU에서 실행하는 것보다 약 1000배 수준의 성능 향상을 달성한다.

Keywords

References

  1. NVIDIA OptiX, https://developer.nvidia.com/optix
  2. https://en.wikipedia.org/wiki/Z-order_curve
  3. https://en.wikipedia.org/wiki/Hilbert_curve
  4. John Cheng, Max Grossman, and Ty McKercher, "Professional CUDA C Programming", p. 84, 1st Edition, Wrox, 2014.
  5. Shengren Li, Lance Simons, Jagadeesh Bhaskar Pakaravoor, Fatemeh Abbasinejad, John D. Owens and Nina Amenta, "kANN on the GPU with Shifted Sorting", In Proceedings of Eurographics/ACM SIGGRAPH Symposium on High Performance Graphics, pp. 039-047, 2012.
  6. https://devblogs.nvidia.com/parallelforall/thinking-parallel-part-iii-tree-construction-gpu/
  7. https://en.wikipedia.org/wiki/IEEE_floating_point
  8. Tero Karras and Timo Aila, "Fast Parallel Construction of High-quality Bounding Volume Hierarchies", In Proceedings of the 5th High-Performance Graphics Conference, pp.89-99, 2013.
  9. https://en.wikipedia.org/wiki/Octree
  10. https://ko.wikipedia.org/wiki/IEEE_754

Cited by

  1. GPU 하드웨어 아키텍처 기반 sub-warp 단위 병렬 프리픽스(prefix) 연산의 정확한 구현 vol.18, pp.3, 2016, https://doi.org/10.9728/dcs.2017.18.3.613
  2. 병렬 Shifted Sort 알고리즘의 Warp 단위 CUDA 구현 최적화 vol.18, pp.4, 2016, https://doi.org/10.9728/dcs.2017.18.4.739
  3. 일반적인 GPU 트리 탐색과의 비교실험을 통한 GPU 기반 병렬 Shifted Sort 알고리즘 분석 vol.18, pp.6, 2016, https://doi.org/10.9728/dcs.2017.18.6.1151
  4. Implementation of Parallel k-Approximate Nearest Neighbor Search using Six Dimensional Shifted Sort with CUDA vol.20, pp.3, 2016, https://doi.org/10.9728/dcs.2019.20.3.605
  5. Shifted Sorting-based k-Approximate Nearest Neighbor Searching Algorithm with Extra Loops Based on Permutation for Better Accuracy vol.22, pp.2, 2016, https://doi.org/10.9728/dcs.2021.22.2.325