research-article

Wavefront Diffusion and LMSR: Algorithms for Dynamic Repartitioning of Adaptive Meshes

Authors:

Kirk Schloegel,

George Karypis,

Vipin KumarAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 12, Issue 5

Pages 451 - 466

https://doi.org/10.1109/71.926167

Published: 01 May 2001 Publication History

Abstract

Current multilevel repartitioning schemes tend to perform well on certain types of problems while obtaining worse results for other types of problems. We present two new multilevel algorithms for repartitioning adaptive meshes that improve the performance of multilevel schemes for the types of problems that current schemes perform poorly while maintaining similar or better results for those problems that current schemes perform well. Specifically, we present a new scratch-remap scheme called Locally-matched Multilevel Scratch-remap (or simply LMSR) for repartitioning of adaptive meshes. LMSR tries to compute a high-quality partitioning that has a large amount of overlap with the original partitioning. We show that LMSR generally decreases the data redistribution costs required to balance the load compared to current scratch-remap schemes. We present a new diffusion-based scheme that we refer to as Wavefront Diffusion. In Wavefront Diffusion, the flow of vertices moves in a wavefront from overweight to underweight subdomains. We show that Wavefront Diffusion obtains significantly lower data redistribution costs while maintaining similar or better edge-cut results compared to existing diffusion algorithms. We also compare Wavefront Diffusion with LMSR and show that these provide a trade-off between edge-cut and data redistribution costs for a wide range of problems. Our experimental results on a Cray T3E, an IBM SP2, and a cluster of Pentium Pro workstations show that both schemes are fast and scalable. For example, both are capable of repartitioning a seven million vertex graph in under three seconds on 128 processors of a Cray T3E. Our schemes obtained relative speedups of between nine and 12 when the number of processors was increased by a factor of 16 on a Cray T3E.

References

[1]

R. Biswas and R. Strawn, “A New Procedure for Dynamic Adaption of Three-Dimensional Unstructured Grids,” Applied Numerical Math. vol. 13, pp. 437-452, 1994.

Digital Library

[2]

J. Boillat, “Load Balancing and Poisson Equation in a Graph,” Concurrency: Practice and Experience, vol. 2, pp. 289-313, 1990.

Digital Library

[3]

T. Bui and C. Jones, “A Heuristic for Reducing Fill in Sparse Matrix Factorization,” Proc. Sixth SIAM Conf. Parallel Processing for Scientific Computing, pp. 445-452, 1993.

[4]

J. Castanos and J. Savage, “Repartitioning Unstructured Adaptive Meshes,” Proc. Int'l. Parallel and Distributed Processing Symp., 2000.

Digital Library

[5]

J. Cong and M. Smith, “A Parallel Bottom-Up Clustering Algorithm with Applications to Circuit Partitioning in VSLI Design,” Proc. ACM/IEEE Design Automation Conf., pp. 755-760, 1993.

Digital Library

[6]

G. Cybenko, “Dynamic Load Balancing for Distributed Memory Multiprocessors,” J. Parallel and Distributed Computing, vol. 7, no. 2, pp. 279-301, 1989.

Digital Library

[7]

K. Devine B. Hendrickson E. Boman M. St. John and C. Vaughan, “Design of Dynamic Load-Balancing Tools for Parallel Applications,” Proc. Int'l. Conf. Supercomputing, 2000.

Digital Library

[8]

R. Diekmann A. Frommer and B. Monien, “Efficient Schemes for Nearest Neighbor Load Balancing,” Parallel Computing, vol. 25, pp. 789-812, 1999.

Digital Library

[9]

P. Diniz S. Plimpton B. Hendrickson and R. Leland, “Parallel Algorithms for Dynamically Partitioning Unstructured Grids,” Proc. Seventh SIAM Conf. Parallel Procedures, 1995.

[10]

C. Fiduccia and R. Mattheyses, “A Linear Time Heuristic for Improving Network Partitions,” Proc. 19th IEEE Design Automation Conf., pp. 175-181, 1982.

Digital Library

[11]

J. Flaherty R. Loy C. Ozturan M. Shephard B. Szymanski J. Teresco and L. Ziantz, “Parallel Structures and Dynamic Load Balancing for Adaptive Finite Element Computation,” Applied Numerical Math, vol. 26, pp. 241-263, 1998.

Digital Library

[12]

H. Gabow, “Data Structures for Weighted Matching and Nearest Common Ancestors with Linking,” Proc. First Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 434-443, 1990.

Digital Library

[13]

A. Gupta, “Fast and Effective Algorithms for Graph Partitioning and Sparse Matrix Reordering,” IBM J. Research and Development, vol. 41, nos. 1/2, pp. 171-183, 1996.

Digital Library

[14]

K. Hall, “An r-Dimensional Quadratic Placement Algorithm,” Management Science, vol. 17, no. 3, pp. 219-229, 1970.

Digital Library

[15]

S. Hauck and G. Borriello, “An Evaluation of Bipartitioning Technique,” Proc. Conf. Advanced Research in VLSI, 1995.

Digital Library

[16]

B. Hendrickson and R. Leland, “The Chaco User's Guide, Version 2.0.,” Technical Report SAND94-2692, Sandia Nat'l Laboratories, 1994.

[17]

B. Hendrickson and R. Leland, “An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations,” SIAM J. Scientific Computing, vol. 16, no. 2, pp. 452-469, 1995.

Digital Library

[18]

B. Hendrickson and R. Leland, “A Multilevel Algorithm for Partitioning Graphs,” Proc. Supercomputing, 1995.

Digital Library

[19]

G. Horton, “A Multi-Level Diffusion Method for Dynamic Load Balancing,” Parallel Computing, vol. 9, pp. 209-218, 1993.

[20]

Y. Hu and R. Blake, “An Improved Diffusion Algorithm for Dynamic Load Balancing,” Parallel Computing, vol. 25, pp. 417-444, 1999.

Digital Library

[21]

Y. Hu R. Blake and D. Emerson, “An Optimal Migration Algorithm for Dynamic Load Balancing,” Concurrency: Practice and Experience, vol. 10, pp. 467-483, 1998.

[22]

G. Karypis and V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,” SIAM J. Scientific Computing, vol. 20, no. 1, pp. 359-392, 1998.

Digital Library

[23]

G. Karypis and V. Kumar, “MetIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, Version 4. 0.,” Technical Report, Dept. of Computer Science and Eng., Univ. of Minnesota, 1998.

[24]

G. Karypis and V. Kumar, “Multilevel k-Way Partitioning Scheme for Irregular Graphs,” J. Parallel and Distributed Computing, vol. 48, no. 1, 1998.

Digital Library

[25]

G. Karypis K. Schloegel and V. Kumar, “PARmeTIS: Parallel Graph Partitioning and Sparse Matrix Ordering Library,” technical report, Dept. of Computer Science and Eng., Univ. of Minnesota, 1997.

[26]

B. Kernighan and S. Lin, “An Efficient Heuristic Partitioning Graphs,” The Bell System Technical J., vol. 49, no. 2, pp. 291-307, 1970.

[27]

B. Monien R. Preis and R. Diekmann, “Quality Matching and Local Improvement for Multilevel Graph-Partitioning,” technical report, Univ. of Paderborn, 1999.

[28]

B. Nour-Omid A. Raefsky and G. Lyzenga, “Solving Finite Element Equations on Concurrent Computers,” Am. Soc. Mechancial Eng. A.K. Noor, ed. pp. 291-307, 1986.

[29]

L. Oliker and R. Biswas, “PLUM: Parallel Load Balancing for Adaptive Unstructured Meshes,” J. Parallel and Distributed Computing, vol. 52, no. 2, pp. 150-177, 1998.

Digital Library

[30]

C. Ou and S. Ranka, “Parallel Incremental Graph Partitioning Using Linear Programming,” Proc. Supercomputing, pp. 458-467, 1994.

Digital Library

[31]

C. Ou S. Ranka and G. Fox, “Fast and Parallel Mapping Algorithms for Irregular and Adaptive Problems,” J. Supercomputing, vol. 10, pp. 119-140, 1996.

Digital Library

[32]

A. Patra and D. Kim, “Efficient Mesh Partitioning for Adaptive hp Finite Element Meshes,” technical report, Dept. of Mechanical Eng., State University of New York, Buffalo, 1999.

[33]

J. Pilkington and S. Baden, “Dynamic Partitioning of Non-Uniform Structured Workloads with Spacefilling Curves,” technical report, Dept. of Computer Science and Eng., Univ. of California 1995.

[34]

A. Pothen H. Simon and K. Liou, “Partitioning Sparse Matrices with Eigenvectors of Graphs,” SIAM J. Matrix Analysis and Applications, vol. 11, no. 3, pp. 430-452, 1990.

Digital Library

[35]

A. Pothen H. Simon L. Wang and S. Bernard, “Towards a Fast Implementation of Spectral Nested Dissection,” Proc. Supercomputing, pp. 42-51, 1992.

Digital Library

[36]

K. Schloegel G. Karypis and V. Kumar, “Multilevel Diffusion Schemes for Repartitioning of Adaptive Meshes,” J. Parallel and Distributed Computing, vol. 47, no. 2, pp. 109-124, 1997.

Digital Library

[37]

K. Schloegel G. Karypis and V. Kumar, “Graph Partitioning for High Performance Scientific Simulations,” CRPC Parallel Computing Handbook, Morgan Kaufmann, 2000.

Digital Library

[38]

K. Schloegel G. Karypis V. Kumar R. Biswas and L. Oliker, “A Performance Study of Diffusive vs. Remapped Load-Balancing Schemes” ISCA 11th Int'l Conf. Parallel and Distributed Computing Systems, pp. 59-66, 1998.

[39]

H. Simon A. Sohn and R. Biswas, “HARP: A Fast Spectral Partitioner,” Proc. Ninth ACM Symp. Parallel Algorithms and Architectures, pp. 43-52, 1997.

Digital Library

[40]

A. Sohn, “S-HARP: A Parallel Dynamic Spectral Partitioner,” technical report, Dept. of Computer and Information Science, New Jersey Institute of Technology, 1997.

[41]

A. Sohn R. Biswas and H. Simon, “Impact of Load Balancing on Unstructured Adaptive Grid Computations for Distributed-Memory Multiprocessors,” Proc. Eighth IEEE Symp. Parallel and Distributed Processing, pp. 26-33, 1996.

Digital Library

[42]

A. Sohn and H. Simon, “JOVE: A Dynamic Load Balancing Framework for Adaptive Computations on an SP-2 Distributed-Memory Multiprocessor,” Technical Report 94-60, Dept. of Computer and Information Science, New Jersey Institute of Technology, 1994.

[43]

N. Touheed P. Selwood P. Jimack and M. Berzins, “A Comparison of Some Dynamic Load-Balancing Algorithms for a Parallel Adaptive Flow Solver,” Parallel Computing, vol. 26, no. 1, pp. 535-554, 2000.

Digital Library

[44]

A. Vidwans Y. Kallinderis and V. Venkatakrishnan, “Parallel Dynamic Load-Balancing Algorithm for Three-Dimensional Adaptive Unnstructured Grids,” AIAA J., vol. 32, pp. 497-505, 1994.

[45]

C. Walshaw and M. Cross, “Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm,” SIAM J. Scientific Computing, vol. 22, no. 1, pp.63-80, 2000.

Digital Library

[46]

C. Walshaw M. Cross and M. Everett, “Dynamic Mesh Partitioning: A Unified Optimisation and Load-Balancing Algorithm,” Technical Report 95/IM/06, Centre for Numerical Modelling and Process Analysis, Univ. of Greenwich, 1995.

[47]

C. Walshaw M. Cross and M. Everett, “Mesh Partitioning and Load-Balancing for Distributed Memory Parallel Systems,” Proc. Parallel and Distbuted Computing for Computer Mechanics, 1997.

[48]

C. Walshaw M. Cross and M. Everett, “Parallel Dynamic Graph Partitioning for Adaptive Unstructured Meshes,” J. Parallel and Distributed Computing, vol. 47, no. 2, pp. 102-108, 1997.

Digital Library

[49]

J. Watts and S. Taylor, ”A Practical Approach to Dynamic Load Balancing,” Trans. Parallel and Distributed Systems, vol. 9, pp. 235-248, 1998.

Digital Library

[50]

C. Xu and F. Lau, “The Generalized Dimension Exchange Method for Load Balancing in k-Ary ncubes and Variants,” J. Parallel and Distributed Computing, vol. 24, pp. 72-85, 1995.

Digital Library

Cited By

Tang JZhang JWu XZhang YZhou N(2022)Parallel implementation for dynamic mesh optimization on distributed computer systemProceedings of the 2022 6th High Performance Computing and Cluster Technologies Conference10.1145/3560442.3560448(38-43)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3560442.3560448
Xu YCai WEckhoff DNair SKnoll ACai WMeng TWilsey PJin K(2017)A Graph Partitioning Algorithm for Parallel Agent-Based Road Traffic SimulationProceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3064911.3064914(209-219)Online publication date: 16-May-2017
https://dl.acm.org/doi/10.1145/3064911.3064914
Jiao LLi JXu TDu WFu X(2016)Optimizing cost for online social networks on geo-distributed cloudsIEEE/ACM Transactions on Networking10.1109/TNET.2014.235936524:1(99-112)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2359365
Show More Cited By

Index Terms

Wavefront Diffusion and LMSR: Algorithms for Dynamic Repartitioning of Adaptive Meshes

Recommendations

Dynamic repartitioning of adaptively refined meshes
SC '98: Proceedings of the 1998 ACM/IEEE conference on Supercomputing

One ingredient which is viewed as vital to the successful conduct of many large-scale numerical simulations is the ability to dynamically repartition the underlying adaptive finite element mesh among the processors so that the computations are balanced ...
A unified algorithm for load-balancing adaptive scientific simulations
SC '00: Proceedings of the 2000 ACM/IEEE conference on Supercomputing

Adaptive scientific simulations require that periodic repartitioning occur dynamically throughout the course of the computation. The repartitionings should be computed so as to minimize both the inter-processor communications incurred during the ...
Performance and Scalability Analysis of Teraflop-Scale Parallel Architectures Using Multidimensional Wavefront Applications

The authors develop a model for the parallel performance of algorithms that consist of concurrent, two-dimensional wavefronts implemented in a message-passing environment. The model, based on a LogGP machine parameterization, combines the separate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 12, Issue 5

May 2001

95 pages

ISSN:1045-9219

Editor:
John A. Stankovic
Univ. of Virginia, Charlottesville

Issue’s Table of Contents

Copyright © Copyright © 2001 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 May 2001

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tang JZhang JWu XZhang YZhou N(2022)Parallel implementation for dynamic mesh optimization on distributed computer systemProceedings of the 2022 6th High Performance Computing and Cluster Technologies Conference10.1145/3560442.3560448(38-43)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3560442.3560448
Xu YCai WEckhoff DNair SKnoll ACai WMeng TWilsey PJin K(2017)A Graph Partitioning Algorithm for Parallel Agent-Based Road Traffic SimulationProceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3064911.3064914(209-219)Online publication date: 16-May-2017
https://dl.acm.org/doi/10.1145/3064911.3064914
Jiao LLi JXu TDu WFu X(2016)Optimizing cost for online social networks on geo-distributed cloudsIEEE/ACM Transactions on Networking10.1109/TNET.2014.235936524:1(99-112)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2359365
Xu YCai WAydt HLees MBuckley SMiller J(2014)Efficient graph-based dynamic load-balancing for parallel large-scale agent-based traffic simulationProceedings of the 2014 Winter Simulation Conference10.5555/2693848.2694282(3483-3494)Online publication date: 7-Dec-2014
https://dl.acm.org/doi/10.5555/2693848.2694282
Sodan AGupta GHan LLiu LLafreniere B(2008)Time and space adaptation for computational grids with the ATOP-Grid middlewareFuture Generation Computer Systems10.1016/j.future.2007.08.00424:6(561-581)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1016/j.future.2007.08.004
Cambazoglu BAykanat C(2007)Hypergraph-Partitioning-Based Remapping Models for Image-Space-Parallel Direct Volume Rendering of Unstructured GridsIEEE Transactions on Parallel and Distributed Systems10.5555/1191546.119172818:1(3-16)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.5555/1191546.1191728
Baños RGil COrtega JMontoya F(2004)A Parallel Multilevel Metaheuristic for Graph PartitioningJournal of Heuristics10.1023/B:HEUR.0000026898.11874.e710:3(315-336)Online publication date: 1-May-2004
https://dl.acm.org/doi/10.1023/B%3AHEUR.0000026898.11874.e7
Moulitsas IKarypis GSlocomb C(2001)Multilevel algorithms for generating coarse grids for multigrid methodsProceedings of the 2001 ACM/IEEE conference on Supercomputing10.1145/582034.582079(45-45)Online publication date: 10-Nov-2001
https://dl.acm.org/doi/10.1145/582034.582079

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents