Parallel Performance Model for Vertex Repositioning Algorithms and Application to Mesh Partitioning

Many mesh optimization applications are based on vertex repositioning algorithms (VrPA). Since the time required for VrPA programs may be large and there is concurrency in processing mesh elements, parallelism has been used to improve performance. In this paper, we propose a performance model for parallel VrPA algorithms that are implemented on memory-distributed computers. This model is validated on two parallel computers and used in a quantitative analysis of performance scalability, load balancing and synchronization and communication overheads. We show that load imbalance and synchronization between boundary partitions are the major causes of the parallel bottlenecks. In order to diminish load imbalance, a new approach to mesh partitioning is proposed. This strategy reduces the imbalance in mesh element evaluations caused by multilevel k-way partitioning algorithms and consequently, improves the performance of parallel VrPA algorithms.