I/O-Efficient Multilevel Graph Partitioning Algorithm for Massive Graph Data(Scientific and Engineering Computing with Applications)(<Special Section>Hardware/Software Support for High Performance Scientific and Engineering Computing)

概要

論文の詳細を見る
Graph data in large scientific/engineering applications are often too massive to fit inside the computer's main memory. The resulting input/output (I/O) costs could be a major performance bottleneck. This paper proposes an extension to extant multilevel graph partitioning algorithms with improved I/O-efficiency. The input graph is envisioned as the union of disjoint blocks (subgraphs) of almost the same size. Each block is coarsened in turn. Recursive matching and contraction are the operations in this phase. All the coarsened blocks are then merged in an iterative manner in order to ensure that the resulting graph fits in the main memory. This graph is then treated with an in-core multilevel graph partitioning algorithm in the usual way. Our experimental results show that the larger graph size is, the more dependent on the I/O-efficiency the performance is. And our modification can easily partition very large graphs. It also exhibits considerable improvement in I/O-complexity.
社団法人電子情報通信学会の論文
2004-07-01