An Unbalanced Partitioning Scheme for Graphs in Heterogeneous Computing
异构计算中一种图的非均衡划分算法

Most existing graph partitioning algorithms produce good equivalent partitions. It means that the partitioned subsets have equal number of vertexes, and meanwhile, the edge-cuts are minimal. However, in the heterogeneous computing environment, the computing power of different proeessors or workstations is variant, so that the size of the tasks scheduled on them should not be the same as well. In order to meet the need of the load balance for heterogeneous computing, this paper presents a novel algorithm that partitions the original task graph into unbalanced subsets according to the arbitrarily given conditions. In usual case, the number of the partitions is equal to that of the proeessors and the size of each partition is set according to the computing power. The algorithm is consisted of three phases. Coarsen the original graph, then partition the coarsest graph and last project it hack to the original graph and conduct refinement. We test the algorithm using Greenwich Graph Partitioning Archive and get good experiment results.