一种改进的并行计算图划分模型

Improved Graph Partitioning Model for Parallel Computing

图划分成功地应用在许多领域,但应用于并行计算时,使用边割度量通信量,其主要缺点是不能准确代表通信量,而且图划分模型没有考虑通信延迟和通信额外开销的分布对并行性能的影响.提出了改进的图划分模型,该模型将影响并行性能的多个要素(通信延迟、最大的局部通信额外开销和整体通信额外开销)整合到一个统一的代价函数,不仅克服了图划分模型中边割度量的一些缺点,而且可以通过调整加权参数,处理不同的优化目标和强调不同因素对并行性能的影响.

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 commu- nication 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 ad- vance a flexible treatment of different optimization objectives, and emphasize the effects of different factors on parallel performance effectively through the adjustable weighting parameters.