Abstract：Graph partitioning has been successfully applied in many areas. However, the graph partitioning is employed in parallel computing using the edge cuts as the communication volume; the main shortcoming is that edge cuts are not entirely the same as the communication volume. Moreover, the graph partitioning model does not consider the effects of communication latency and communication overhead distribution on the parallel performance. This paper thus proposes an improved graph partitioning model for parallel computing, which incorporates several factors (communication latency, maximum local communication overhead and total communication overhead) into a unified cost function. The model not only can overcome shortcomings of the edge cut metric,but also can advance a flexible treatment of different optimization objectives, and emphasize the effects of different factors on parallel performance effectively through the adjustable weighting parameters.
马永刚，谭国真，杨际祥，潘东. 一种改进的并行计算图划分模型[J]. , 2011, 32(3): 416-420.
MA Yong-gang,TAN Guo-zhen, YANG Ji-xiang, PAN Dong. Improved Graph Partitioning Model for Parallel Computing. , 2011, 32(3): 416-420.
