SUMMARY

We present the results of an evaluation study on the re-structuring of a latency-bound mesh generation algorithm into a latency-tolerant parallel kernel. We use concurrency at a ne-grain level to tolerate long, variable, and unpredictable latencies of remote data gather operations required for parallel guaranteed quality Delaunay triangulations. Our performance data from a 16 node SP2 and 32 node Cluster of Sparc Workstations suggest that more than 90 % of the latency from remote data gather operations can be masked eectively at the cost of increasing communication overhead between 2 and 20 % of the total run time. Despite the increase in the communication overhead the latency-tolerant mesh generation kernel we present in this paper can generate tetrahedral meshes for parallel eld solvers eight to nine times faster than the traditional approach. Copyright? 2003 John Wiley & Sons, Ltd. KEY WORDS: mesh generation; parallel computing; Delaunay triangulation; guaranteed quality; latency tolerant algorithm