A Divide-and-Conquer Algorithm of Delaunay Triangulation with GPGPU

Author

Min-Bin Chen

Author_Institution

China Univ. of Technol., Taipei, Taiwan

fYear

2012

fDate

17-20 Dec. 2012

Firstpage

175

Lastpage

177

Abstract

In this study, we will parallelize the D&C algorithm with CUDA. In stead of recursive programming in D&C, the recursive stack is implemented on the host side (CPU) and the merge operation is executes on GPU in parallel. Since the recursive stack is a fully binary tree in this algorithm, the merge operations on the nodes in each layer of the binary tree can be performed synchronously. In this data-parallel computation, with the careful management of data structure, the data of each node can be arranged in the same block and no need to share data between threads, so the parallelism is not broken.

Keywords

divide and conquer methods; graphics processing units; mesh generation; parallel architectures; tree data structures; CUDA; D&C algorithm parallelization; Delaunay triangulation; GPGPU; data structure management; data-parallel computation; divide-and-conquer algorithm; fully binary tree; recursive programming; recursive stack; Algorithm design and analysis; Binary trees; Computers; Graphics processing units; Merging; Programming;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Architectures, Algorithms and Programming (PAAP), 2012 Fifth International Symposium on

Conference_Location

Taipei

ISSN

2168-3034

Print_ISBN

978-1-4673-4566-8

Type

conf

DOI

10.1109/PAAP.2012.50

Filename

6424754