Graph partitioning models for parallel computing

Authors
Hendrickson, B Kolda, TG
Citation
B. Hendrickson et Tg. Kolda, Graph partitioning models for parallel computing, PARALLEL C, 26(12), 2000, pp. 1519-1534
Citations number
33
Categorie Soggetti
Computer Science & Engineering
Journal title
PARALLEL COMPUTING
ISSN journal
01678191 → ACNP
Volume
26
Issue
12
Year of publication
2000
Pages
1519 - 1534
Database
ISI
SICI code
0167-8191(200011)26:12<1519:GPMFPC>2.0.ZU;2-C
Abstract
Calculations can naturally be described as graphs in which vertices represe nt computation and edges reflect data dependencies. By partitioning the ver tices of a graph, the calculation can be divided among processors of a para llel computer. However, the standard methodology for graph partitioning min imizes the wrong metric and lacks expressibility. We survey several recentl y proposed alternatives and discuss their relative merits. (C) 2000 Elsevie r Science B.V. All rights reserved.