Research Of Optimization Strategy For Parallel Graph Partitioning

In the large-scale scientific simulations, we often partition the computing tasks with the idea of divide and conquer. In order to achieve high parallel efficiency, we must ensure load balance, while minimizing communication cost between processors. So, how to effectively partition the tasks is very important. Based on graph theory, data dependency is abstracted to a graph. Thus load partitioning is turned to the problem of graph partitioning. Partitioning a graph into several subgraphs with load balancing of computation and communication is the main aim of parallel graph partitioning. Research of partitioning algorithms should synthesize connectivity, degree of parallelism, load balancing and communication cost.Current graph partitioning algorithms and softwares ignore the difference of the communication cost of processors between intra and inter node on multi-core parallel cluster. With the increase of the number of processor core on single node, the proportion of communication within a node is getting more and more large. It is necessary to take this difference in account to optimize overall performance of parallel computing. Therefore, in this paper, we present a new graph partitioning strategy for multi-core cluster. This strategy is to minimize the cost of communication between nodes with computing load balancing as possible. Performance analysis of the partitioning strategy and numerical experiment are given. Results show that this strategy of graph partition is effective to reduce the communication cost of multi-core cluster.For many numerical simulation applications, it is necessary to dynamically adjust task load. Repartition of graph(hypregraph) is used to deal with this. In this paper, the diffusion repartitioning and the remapping repartitioning strategies are analyzed. And we also present formulations of repartitioning model to measure the communication and migration overhead of repartition. Based on this work, we improve the repartition of the graph and modify the ParMetis with our strategy. Comparation is made between our improvement with two repartition strategies in ParMetis. Results show that the new repartition strategy is better than the diffusion and scratch remaping strategies in ParMetis with almost the same execute time .