A compact parallel algorithm for spherical Delaunay triangulations. (5th October 2016)

• Record Type: Journal Article
• Authors: Prill, Florian; Zängl, Günther
• Other Names: Melab Nouredine guestEditor.; Mezmaz Mohand guestEditor.; Wyrzykowski Roman guestEditor.; Szymanski Boleslaw K. guestEditor.
• Is Part Of: Concurrency and computation. Volume 29:Number 9(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2016-10-05
• Subjects: spherical Delaunay triangulation -- parallel computing -- computational geometry -- stencil computation -- space‐filling curves; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3971
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: We present a data‐parallel algorithm for the construction of Delaunay triangulations on the sphere. Our method combines a variant of the classical Bowyer–Watson point insertion algorithm with the recently published parallelization technique by Jacobsen et al . It resolves a breakdown situation of the latter approach and is suitable for practical implementation because of its compact formulation. Some complementary aspects are discussed such as the parallel workload and floating‐point arithmetics. In a second step, the generated triangulations are reordered by a stripification algorithm. This improves cache performance and significantly reduces data‐read operations and indirect addressing in multi‐threaded stencil loops. This paper is an extended version of our Parallel Processing and Applied Mathematics conference contribution. Copyright © 2016 John Wiley & Sons, Ltd.