ParaPART: parallel mesh partitioning tool for distributed systems
Jian Chen, Valerie Taylor · Concurrency Practice and Experience · 2000
In this paper, we present ParaPART, a parallel version of a mesh partitioning tool called PART for distributed systems. PART takes into consideration the heterogeneities in processor performance, network performance and application computational complexities to achieve a balanced estimate of execution time across the processors in the distributed system. Simulated annealing is used in PART to perform the backtracking search for desired partitions. ParaPART significantly improves the performance of PART by using the asynchronous multiple Markov chain approach of parallel simulated annealing. ParaPART is used to partition six irregular meshes into 8, 16 and 100 subdomains using up to 64 client processors on an IBM SP machine. The results show superlinear speedup in most cases and nearly perfect speedup for the remaining cases. Using the partitions from ParaPART, we ran an explicit, two-dimensional finite element code on two geographically distributed IBM SP machines. Results indicate that ParaPART produces results within 3% of PART. The execution time of the finite element code was reduced by 12% for eight processors as compared with partitions that consider only processor performance; this is significant given the theoretical upper bound of 15% reduction. Up to 35% reduction was achieved when up to 40 processors were used for the same problems. Copyright © 2000 John Wiley & Sons, Ltd.