zbMATH — the first resource for mathematics

Parallel static and dynamic multi-constraint graph partitioning. (English) Zbl 1012.68146
Summary: Sequential multi-constraint graph partitioners have been developed to address the static load balancing requirements of multi-phase simulations. These work well when (i) the graph that models the computation fits into the memory of a single processor, and (ii) the simulation does not require dynamic load balancing. The efficient execution of very large or dynamically adapting multi-phase simulations on high-performance parallel computers requires that the multi-constraint partitionings are computed in parallel. This paper presents a parallel formulation of a multi-constraint graph-partitioning algorithm, as well as a new partitioning algorithm for dynamic multi-phase simulations. We describe these algorithms and give experimental results conducted on a 128-processor Cray T3E. These results show that our parallel algorithms are able to efficiently compute partitionings of similar edge-cuts as serial multi-constraint algorithms, and can scale to very large graphs. Our dynamic multi-constraint algorithm is also able to minimize the data redistribution required to balance the load better than a naive scratch-remap approach. We have shown that both of our parallel multi-constraint graph partitioners are as scalable as the widely-used parallel graph partitioner implemented in PARMETIS. Both of our parallel multi-constraint graph partitioners are very fast, as they are able to compute three-constraint 128-way partitionings of a 7.5 million vertex graph in under 7 s on 128 processors of a Cray T3E.

68R10 Graph theory (including graph drawing) in computer science
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI
[1] A load balancing technique for multi-phase computations. Proceedings of High Performance Computing ?97, 1997; 15-20.
[2] Dynamic load-balancing for parallel structural mechanics simulations with DRAMA. Proceedings of ECT2000, 2000.
[3] Multilevel algorithms for multi-constraint graph partitioning. Proceedings of Supercomputing ?98, 1998.
[4] Graph partitioning for high performance scientific simulations. CRPC Parallel Computing Handbook. Morgan Kaufmann, 2001.
[5] Walshaw, Applied Mathematical Modelling 25 pp 123– (2000) · Zbl 1076.65538 · doi:10.1016/S0307-904X(00)00041-X
[6] Gupta, IBM Journal of Research and Development 41 pp 171– (1996) · doi:10.1147/rd.411.0171
[7] A multilevel algorithm for partitioning graphs. Proceedings of Supercomputing ’95, 1995.
[8] Karypis, Journal of Parallel and Distributed Computing 48 (1998)
[9] Quality matching and local improvement for multilevel graph-partitioning. Technical Report, University of Paderborn, 1999.
[10] Walshaw, Parallel Computing 26 pp 1635– (2000) · Zbl 0948.68223 · doi:10.1016/S0167-8191(00)00046-6
[11] Karypis, SIAM Journal on Scientific Computing 20 pp 359– (1998) · Zbl 0915.68129 · doi:10.1137/S1064827595287997
[12] Data structures for weighted matching and nearest common ancestors with linking. Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990; 434-443. · Zbl 0800.68617
[13] A linear time heuristic for improving network partitions. Proceedings 19th IEEE Design Automation Conference, 1982; 175-181.
[14] Kernighan, The Bell System Technical Journal 49 pp 291– (1970) · Zbl 0333.05001 · doi:10.1002/j.1538-7305.1970.tb01770.x
[15] Karypis, SIAM Review 41 pp 278– (1999) · Zbl 0918.68073 · doi:10.1137/S0036144598334138
[16] A coarse-grain parallel multilevel k-way partitioning algorithm. Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing, 1997.
[17] Graph partitioning for emerging scientific simulations. PhD Thesis, University of Minnesota, 1999.
[18] Oliker, Journal of Parallel and Distributed Computing 52 pp 150– (1998) · Zbl 0920.68016 · doi:10.1006/jpdc.1998.1469
[19] JOVE: A dynamic load balancing framework for adaptive computations on an SP-2 distributed-memory multiprocessor. Technical Report 94-60, Department of Computer and Information Science, NJIT, 1994.
[20] Schloegel, IEEE Transactions on Parallel and Distributed Systems (2000)
[21] PARMETIS: Parallel graph partitioning and sparse matrix ordering library. Technical Report, University of Minnesota, Department of Computer Science and Engineering, 1997.
[22] METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, version 4.0. Technical Report, University of Minnesota, Department of Computer Science and Engineering, 1999.
[23] Multilevel circuit partitioning. Proceedings 34th ACM/IEEE Design Automation Conference, 1997.
[24] Dynamic multi-partitioning for parallel finite element applications. ParCo ’99. Submitted.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.