Graph partitioning models for parallel computing

被引：244

作者：

Hendrickson, B

Kolda, TG

机构：

[1] Sandia Natl Labs, Parallel Comp Sci Dept, Albuquerque, NM 87185 USA

[2] Sandia Natl Labs, Computat Sci & Math Res Dept, Livermore, CA 94551 USA

来源：

PARALLEL COMPUTING | 2000年 / 26卷 / 12期

关键词：

graph partitioning; hypergraph partitioning; parallel computing;

D O I：

10.1016/S0167-8191(00)00048-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Calculations can naturally be described as graphs in which vertices represent computation and edges reflect data dependencies. By partitioning the vertices of a graph, the calculation can be divided among processors of a parallel computer. However, the standard methodology for graph partitioning minimizes the wrong metric and lacks expressibility. We survey several recently proposed alternatives and discuss their relative merits. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：1519 / 1534

页数：16

共 33 条

[1]

AKYANAT C, 1998, COMMUNICTION

[2]

[Anonymous], 1995, CHACO USERS GUIDE VE

[3]

[Anonymous], 1970, BELL SYST TECH J, DOI [10.1002/j.1538-7305.1970.tb01770.x, DOI 10.1002/J.1538-7305.1970.TB01770.X]

[4]

AYKANAT C., 1996, LECT NOTES COMPUTER, V1117, P75