Berkeley UPC - Unified Parallel C

Mesh generation using Delaunay triangulation in UPC

This movie demonstrates a visualization of a 2D run of the LBNL Delaunay triangulation mesh generation code, written in UPC by Parry Husbands. It is an implementation of a parallel projection-based algorithm (Blelloch, Miller, Talmor), and uses a divide-and-conquer strategy where vertices and processors are recursively divided using a parallel convex hull algorithm. The recursive partitioning to assigns vertices into well-balanced subsets (ideally an equal number of vertices per thread) while being sensitive to spatial locality of the vertices. At the base of the recursion, each processor solves its partition of the mesh using the sequential Triangle package (Shewchuk).

The object is to create a triangular mesh partioning that minimizes edge length and maximizes vertex angles, while remaining valid with respect to several other graph-theoretic constraints (such as no edge crossings). In the visualization, the blue lines represent the operation of the parallel convex hull algorithm which performs the recursive subdivision. Other colors represent the assignment of vertices to processors, and the edges represent the partitioning selected by the application. A caching scheme is used to conserve communication of vertices, and the cache occupancy across UPC threads is also shown.

The program was built using the Berkeley UPC v2.2 compiler and run on 'Ram' (an SGI Altix at Oak Ridge National Laboratory) using the "shmem" GASNet conduit.

This page last modified on Tuesday, 19-Mar-2019 15:03:05 PDT