More Web Proxy on the site http://driver.im/

Article

Free access

A unified algorithm for load-balancing adaptive scientific simulations

Authors:

Kirk Schloegel,

George Karypis,

Vipin KumarAuthors Info & Claims

SC '00: Proceedings of the 2000 ACM/IEEE conference on Supercomputing

Pages 59 - es

Published: 01 November 2000 Publication History

Abstract

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 iterative mesh-based computation and the data redistribution costs required to balance the load. Recently developed schemes for computing repartitionings provide the user with only a limited control of the tradeoffs among these objectives. This paper describes a new Unified Repartitioning Algorithm that can tradeoff one objective for the other dependent upon a user-defined parameter describing the relative costs of these objectives. We show that the Unified Repartitioning Algorithm is able to reduce the precise overheads associated with repartitioning as well as or better than other repartitioning schemes for a variety of problems, regardless of the relative costs of performing inter-processor communication and data redistribution. Our experimental results show that this scheme is extremely fast and scalable to large problems.

References

[1]

R.Biswas and R.C.Strawn.A new procedure for dynamic adaption of three-dimensional unstructured grids.Applied Numerical Mathematics 13:437 -452,1994.]]

Digital Library

[2]

J.Castanos and J.Savage.Repartitioning unstructured adaptive meshes.In Proc. Intl. Parallel and Distributed Processing Symposium 2000.]]

Digital Library

[3]

K.Devine,B.Hendrickson,E.Boman,M.St.John,and C.Vaughan.Design of dynamic load-balancing tools for parallel applications.In Proc.of theIntl.Conferenceon Supercomputing 2000.]]

Digital Library

[4]

P.Diniz,S.Plimpton,B.Hendrickson,and R Leland.Parallel algorithms for dynamically partitioning unstructured grids. Proc. 7th SIAM Conf. Parallel Proc.,1995.]]

[5]

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.Appl. Numer. Maths 26:241 -263,1998.]]

Digital Library

[6]

B.Jeremic and C.Xenophontos.Application of the p-version of the finite element method to elasto-plasticity with localization of deformation.Communications in Numerical Methods in Engineering 15(12):867 -876, 1999.]]

[7]

G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359-392, 1998.]]

Digital Library

[8]

G. Karypis and V. Kumar. Parallel multilevel k-way partitioning scheme for irregular graphs. Siam Review, 41(2):278-300, 1999.]]

Digital Library

[9]

G.Karypis,K.Schloegel,and V.Kumar.ParMeTiS Parallel graph partitioning and sparse matrix ordering library. Technical report,University of Minnesota,Department of Computer Science and Engineering,1997.]]

[10]

B.Maerten,D.Roose,A.Basermann,J.Fingberg,and G.Lonsdale.DRAMA:A library for parallel dynamic load balancing of finite element applications.In Ninth SIAM Conference on Parallel Processing for Scientific Computing 1999.]]

Digital Library

[11]

L.Oliker and R.Biswas.PLUM:Parallel load balancing for adaptive unstructured meshes.Journal of Parallel and Distributed Computing 52(2):150-177,1998.]]

Digital Library

[12]

C.Ou and S.Ranka.Parallel incremental graph partitioning using linear programming.Proceedings Supercomputing '94 pages 458 -467,1994.]]

[13]

C.Ou,S.Ranka,and G.Fox.Fast and parallel mapping algorithms for irregular and adaptive problems.Journal of Supercomputing 10:119 -140,1996.]]

Digital Library

[14]

A.Patra and D.Kim. Efficient mesh partitioning for adaptive hp finite element meshes.Technical report,Dept.of Mech. Engr.,SUNY at Buffalo,1999.]]

[15]

J.Pilkington and S.Baden.Dynamic partitioning of non-uniformstructured workloads with space .lling curves.Technical report,Dept.of Computer Science and Engineering,Univ.of California,1995.]]

[16]

K.Schloegel,G.Karypis,and V.Kumar.Multilevel diffusion schemes for repartitioning of adaptive meshes.Journal of Parallel and Distributed Computing 47(2):109-124,1997.]]

Digital Library

[17]

K.Schloegel,G.Karypis,and V.Kumar.Wavefront diffusion and LMSR:Algorithms for dynamic repartitioning of adaptive meshes.Technical Report TR 98-034,University of Minnesota,Department of Computer Science and Engineering,1998.]]

[18]

K.Schloegel,G.Karypis,and V.Kumar.Parallel multilevel algorithms for multi-constraint graph partitioning.In Proc. EuroPar 2000 2000.Accepted as a Distinguished Paper.]]

Digital Library

[19]

K.Schloegel,G.Karypis,V.Kumar,R.Biswas,and L.Oliker.A performance study of di .usive vs.remapped loadbalancing schemes.ISCA 11th Intl. Conf. on Parallel and Distributed Computing Systems pages 59 -66,1998.]]

[20]

A.Sohn.S-HARP:A parallel dynamic spectral partitioner.Technical report,Dept.of Computer and Information Science, NJIT,1997.]]

[21]

A.Sohn and H.Simon.JOVE:A dynamic load balancing framework for adaptive computations on an SP-2 distributedmemory multiprocessor.Technical Report 94-60,Dept.of Computer and Information Science,NJIT,1994.]]

[22]

R.VanDriessche and D.Roose.Dynamic load balancing of iteratively refined grids by an enhanced spectral bisection algorithm.Technical report,Dept.of Computer Science,K.U.Leuven,1995.]]

[23]

A.Vidwans,Y.Kallinderis,and V.Venkatakrishnan.Parallel dynamic load-balancing algorithm for three-dimensional adaptive unstructured grids.AIAA Journal 32:497 -505,1994.]]

[24]

C.Walshaw,M.Cross,and M.G.Everett.Dynamic mesh partitioning:A uni .ed optimisation and load-balancing algorithm.Technical Report 95/IM/06,Centre for Numerical Modelling and Process Analysis,University of Greenwich, 1995.]]

[25]

C.Walshaw,M.Cross,and M.G.Everett.Parallel dynamic graph partitioning for adaptive unstructured meshes.Journal of Parallel and Distributed Computing 47(2):102 -108,1997.]]

Digital Library

Cited By

Pearce OAhmed HLarsen RRichards D(2016)Enabling work migration in CoMD to study dynamic load imbalance solutionsProceedings of the 7th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computing Systems10.5555/3019057.3019067(98-107)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3019057.3019067
Lieber MGößner KNagel WDongarra JHolmes DCollis ALarsson Träff JSmith L(2016)The Potential of Diffusive Load Balancing at Large ScaleProceedings of the 23rd European MPI Users' Group Meeting10.1145/2966884.2966887(154-157)Online publication date: 25-Sep-2016
https://dl.acm.org/doi/10.1145/2966884.2966887
Pearce OGamblin Tde Supinski BSchulz MAmato N(2015)Decoupled load balancingACM SIGPLAN Notices10.1145/2858788.268853950:8(267-268)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688539
Show More Cited By

Index Terms

A unified algorithm for load-balancing adaptive scientific simulations

Recommendations

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

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 ...
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 ...
An adaptive dynamic load balancing method for multiphase irregular problems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '00: Proceedings of the 2000 ACM/IEEE conference on Supercomputing

November 2000

889 pages

ISBN:0780398025

Conference Chair:
Louis Turcotte
Rose-Hulman Institute of Technology

Copyright © Copyright (c) 2000 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

In-Cooperation

SIAM: Society for Industrial and Applied Mathematics

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 November 2000

Check for updates

Author Tags

Qualifiers

Article

Conference

SC '00

Sponsor:

SIGARCH
IEEE-CS

SC '00: International Conference for High Performance Computing, Networking, Storage and Analysis

November 4 - 10, 2000

Texas, Dallas, USA

Acceptance Rates

SC '00 Paper Acceptance Rate 62 of 179 submissions, 35%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
461
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pearce OAhmed HLarsen RRichards D(2016)Enabling work migration in CoMD to study dynamic load imbalance solutionsProceedings of the 7th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computing Systems10.5555/3019057.3019067(98-107)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3019057.3019067
Lieber MGößner KNagel WDongarra JHolmes DCollis ALarsson Träff JSmith L(2016)The Potential of Diffusive Load Balancing at Large ScaleProceedings of the 23rd European MPI Users' Group Meeting10.1145/2966884.2966887(154-157)Online publication date: 25-Sep-2016
https://dl.acm.org/doi/10.1145/2966884.2966887
Pearce OGamblin Tde Supinski BSchulz MAmato N(2015)Decoupled load balancingACM SIGPLAN Notices10.1145/2858788.268853950:8(267-268)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688539
Pearce OGamblin Tde Supinski BSchulz MAmato NCohen AGrove D(2015)Decoupled load balancingProceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/2688500.2688539(267-268)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2688500.2688539
Pearce OGamblin Tde Supinski BArsenlis TAmato NBode AGerndt MStenström PRauchwerger LMiller BSchulz M(2014)Load balancing n-body simulations with highly non-uniform densityProceedings of the 28th ACM international conference on Supercomputing10.1145/2597652.2597659(113-122)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2597652.2597659
Pearce OGamblin Tde Supinski BSchulz MAmato NBanerjee UGallivan KBilardi GKatevenis M(2012)Quantifying the effectiveness of load balance algorithmsProceedings of the 26th ACM international conference on Supercomputing10.1145/2304576.2304601(185-194)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1145/2304576.2304601
Bennett PLathrop SCosta JKramer W(2011)Sustained systems performance monitoring at the U. S. Department of Defense high performance computing modernization programState of the Practice Reports10.1145/2063348.2063352(1-11)Online publication date: 12-Nov-2011
https://dl.acm.org/doi/10.1145/2063348.2063352
Meyerhenke HMonien BSchamberger S(2009)Graph partitioning and disturbed diffusionParallel Computing10.1016/j.parco.2009.09.00635:10-11(544-569)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1016/j.parco.2009.09.006
Steensland J(2007)Reducing data migration in the context of adaptive partitioning for AMRProceedings of the 19th IASTED International Conference on Parallel and Distributed Computing and Systems10.5555/1647539.1647562(110-115)Online publication date: 6-Nov-2007
https://dl.acm.org/doi/10.5555/1647539.1647562
Nordén MLöf HRantakokko JHolmgren S(2007)Dynamic data migration for structured AMR solversInternational Journal of Parallel Programming10.1007/s10766-007-0056-z35:5(477-491)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1007/s10766-007-0056-z
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents