비정렬 격자에 대한 광선 투사를 위한 셀 사이 연결정보 추출 병렬처리 알고리즘
Parallel Cell-Connectivity Information Extraction Algorithmfor Ray-casting on Unstructured Grid Data
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문은 비정렬 격자에 대한 광선투사 수행의 전처리 과정 중 하나인 셀 사이 연결정보 추출에 대한 멀티코어 CPU 기반 병렬처리 알고리즘을 제안한다. 본 연구는 기존의 직렬처리 알고리즘을 단순히 병렬화하였을 때 발생하는 동기화 문제를 확인하고, 이를 해결할 수 있는 3-단계 병렬처리 알고리즘을 제안한다. 제안하는 알고리즘은 각 단계 내에서의 스레드 간 동기화를 제거함으로서 병렬처리 효율을 높인다. 또한, 연결 정보 추출 알고리즘의 핵심 연산인, 삼각형 중복 검사 과정의 메모리 접근에 대한 공간적 지역성을 높이고 캐시 활용 효율을 향상시킨다. 본 연구는 나아가, 스레드 마다 자체 메모리 풀을 사용하게 함으로서 병렬처리 효율을 더욱 높인다. 본 연구의 효용성을 확인하기 위해, 제안하는 알고리즘을 두 개의 옥타코어 CPU를 가지는 시스템에 구현하고 세 개의 비정렬 격자 데이터에 적용하였다. 그 결과, 제안하는 병렬처리 알고리즘은 스레드 수 증가에 따라 지속적으로 성능 향상을 보여주었다. 또한, 32개 스레드(물리코어 16개)를 사용하여 기존 직렬처리 알고리즘 대비 최대 82.9배 높은 성능을 보여주었다. 이는 제안하는 알고리즘의 높은 병렬처리 확장성 및 캐시 활용 효율 개선 효과를 증명하며, 대용량 비정렬 격자 처리에 대한 적합성을 보여주는 결과다.
Abstract
We present a novel multi-core CPU based parallel algorithm for the cell-connectivity information extraction algorithm, which is one of the preprocessing steps for volume rendering of unstructured grid data. We first check the synchronization issues when parallelizing the prior serial algorithm naively. Then, we propose a 3-step parallel algorithm that achieves high parallelization efficiency by removing synchronization in each step. Also, our 3-step algorithm improves the cache utilization efficiency by increasing the spatial locality for the duplicated triangle test process, which is the core operation of building cell-connectivity information. We further improve the efficiency of our parallel algorithm by employing a memory pool for each thread. To check the benefit of our approach, we implemented our method on a system consisting of two octa-core CPUs and measured the performance. As a result, our method shows continuous performance improvement as we add threads. Also, it achieves up to 82.9 times higher performance compared with the prior serial algorithm when we use thirty-two threads (sixteen physical cores). These results demonstrate the high parallelization efficiency and high cache utilization efficiency of our method. Also, it validates the suitability of our algorithm for large-scale unstructured data.
참고문헌 (18)
- K. Brodlie, "Recent advances in volume visualization", Computer Graphics Forum, 20(2), pp.125~148 (2001)
- M. Garrity, "Raytracing irregular volume data", Computer Graphics, pp.35~40 (1990)
- P. Bunyk, "Simple, fast, and robust ray-casting of irregular grids", Scientific Visualization Conference (dagstuhl ‘97), pp.30~30 (1999)
- Ribeiro S., "Memory-Aware And Efficient Ray-Casting Algorithm", Proceedings Of The Xx Brazilian Symposium On Computer Graphics And Imge Processing, pp.147~154 (2007)
- André Maximo, "Memory efficient GPU-based ray casting for unstructured volume rendering", Volume Graphics, pp.155~162 (2008)
- 김덕수, "비정렬 격자 볼륨 렌더링을 위한 다중코어 CPU기반 메모리 효율적 광선 투사 병렬 알고리즘", 정보과학회논문지, 43(03), pp.304~313 (2016), 한국정보과학회
- Will Schroeder, "The visualization toolkit (4th ed.): An object-oriented approach to 3D graphics" (2006), Prentice-Hall, Inc.
- Wylie B., "Tetrahedral projection using vertex shaders", Proceedings of the IEEE Symposium on Volume visualization and graphics, pp.7~12 (2002)
- Marroquim R., "GPU-Based Cell Projection for Interactive Volume Rendering", Proceedings of the XIX Brazilian Symposium on Computer Graphics and Image Processing, pp.147~154 (2006)
- Weiler M., "Hardware-based view-independent cell projection", IEEE Transactions on Visualization and Computer Graphics, 9(2), pp.163~175 (2003)
- Callahan S. P., "Hardware-assisted visibility sorting for unstructured volume rendering", IEEE Transactions on Visualization and Computer Graphics, 11(3), pp.285~295 (2005)
- Farias, R, "ZSWEEP: An efficient and exact projection algorithm for unstructured volume rendering", Proceedings of the IEEE symposium on Volume visualization, pp.91~99 (2000)
- Espinha R., "High-quality hardware-based ray-casting volume rendering using partial pre-integration", Proceedings of the XVIII Brazilian Symposium on Computer Graphics and Image Processing, pp.273~ (2005)
- Bernardon F. F., "GPU-based Tiled ray-casting using Depth Peeling", Journal of Graphics Tools, 11(3), pp.23~29 (2006)
- NVIDIA, "CUDA programming guide 9.2", ~ (2018)
- Gu, Gibeom, "Accurate and Memory-Efficient GPU Ray-Casting Algorithm for Volume Rendering Unstructured Grid Data", EuroVis 2019 (2019)
- Walls, Keith G., "Method for improving the performance of dynamic memory allocation by removing small memory fragments from the memory pool", U.S. Patent No. 5,675,790, ~ (1997)
- L. Dagum, "OpenMP : an industry standard API for shared-memory programming", IEEE Computational Sci. and Engineering, 5, pp.46~55 (1998)