Article

Free access

Automatic load balanced paritioning strategies for PDE computations

Authors:

J. R. RiceAuthors Info & Claims

ICS '89: Proceedings of the 3rd international conference on Supercomputing

Pages 99 - 107

https://doi.org/10.1145/318789.318801

Published: 01 June 1989 Publication History

PDF eReader

Abstract

In this paper we study the partitioning and allocation of computations associated with the numerical solution of partial differential equations (PDEs). Strategies for the mapping of such computations to parallel MIMD architectures can be applied to different levels of the solution process. We introduce and study heuristic approaches defined on the associated geometric data structures (meshes). Specifically, we study methods for decomposing finite element and finite difference meshes into balanced, nonoverlapping subdomains which guarantee minimum communication and synchronization among the underlying associated subcomputations. Two types of algorithms are considered: clustering techniques based on sequential orderings of the discrete geometric data and optimization based techniques involving geometric or graphical metric criteria. These algorithms support the automatic mode of a geometry decomposition tool developed in the parallel ELLPACK environment which is implemented under X11-window systems. A brief description of this tool is presented.

References

[1]

E.R. Barnes, "An algorithm for partitioning the nodes of a graph", S/AM Journal Algebraic and Discrete Methods, Vol. 3, pp. 541-550, Dec. (1982).

Crossref

Google Scholar

[2]

M.J. Bergcr and S. Bokhari, "A partitioning strategy for non-uniform problems as multiprocessors", ICASE Report No. 85-55, Nov. 0985).

Google Scholar

[3]

N. Christofides and P. Brooker, "The Optimal partitioning of graphs", SIAM Journal of Applied Mathematics, Vol. 30, pp. 55-69 (1976).

Crossref

Google Scholar

[4]

W.E. Donath and A.J. Hoffmann, "Lower bounds for the partitioning of graphs", iBM Journal of Research and Development, Vol. 17, pp. 420425, Sept. (1973).

Google Scholar

[5]

C. Farhat, "A simple and efficient automatic FEM domain decomposer'', Computers and Structures, Vol. 28, pp. 579--602 (1988).

Crossref

Google Scholar

[6]

G.C. Fox, "A graphical approach to load balancing and sparse matrix vector multiplication on the hypercube", in Numerical Algorithms for Modern Parallel Computer Architectures, IMA Vol. Math. App., 13 (M. Schultz, ed.), Springer-Verlag, pp. 37-61 (1987).

Google Scholar

[7]

G.C. Fox, "A review of automatic load balancing and decomposition methods for the hypercube", in Numerical Algorithms for Modern Parallel Computer Architectures, IMA Vol. Math. App., 13 (M. Schultz, ed.), Springer-Verlag, pp. 63-76 (1987).

Google Scholar

[8]

M.R. Garey and D.S. johnson, "Computers and Intractability' ', W.H. Freeman and Company, (1979).

Google Scholar

[9]

M.K. Goldberg and R. Gardner, "On the minimal cut problem", Progress in Graph Theory, (1984).

Google Scholar

[10]

C.E. Houstis, E.N. Houstis, J.R. Rice, S.M. Samartzis and D.L. Alexandrakis, "The algorithm mapper: A System for modeling and evaluating parallel applications/architectures pairs", in Fourth Generation Mathematical Software Systems (Houstis, Rice and Vichnevetsky, eds.), North-Holland (1989), to appear.

Google Scholar

[11]

E.N. Houstis, T.S. Papa theodorou and J.R. Rice, "Parallel ELLPACK: An expert system for the parallel processing of partial differential equations", Math. Comp. Simul., Vol. 31 (1989), to appear.

Google Scholar

[12]

E.N. Houstis, P.N. Papachiou, J.R. Rice and M.S. Samartzis, "Domain decomposer: A software tool for partitioning PDE computations based on geometry decomposition strategies", Purdue University Technical report, in preparation.

Google Scholar

[13]

B.W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs", The Bell System Technical Journal, Feb. (1970), pp. 291-307.

Crossref

Google Scholar

[14]

Lenna~, Pirktl, "On the use of cluster analysis for partitioning and allocation computational objects in distributed computing systems", Computer Science and Statistics: The Interface, James E. Gentle (ed.), North-Holland, pp. 361-364, (1983).

Google Scholar

Cited By

View all

Diekmann RPreis RSchlimbach FWalshaw C(2006)Aspect ratio for mesh partitioningEuro-Par’98 Parallel Processing10.1007/BFb0057872(347-351)Online publication date: 30-Jun-2006
https://doi.org/10.1007/BFb0057872
Diekmann RSchlimbach FWalshaw C(2005)Quality balancing for parallel adaptive FEMSolving Irregularly Structured Problems in Parallel10.1007/BFb0018537(170-181)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0018537
Diekmann RMeyer DMonien B(2005)Parallel decomposition of unstructured FEM-meshesParallel Algorithms for Irregularly Structured Problems10.1007/3-540-60321-2_17(199-215)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-60321-2_17
Show More Cited By

Index Terms

Recommendations

Balanced POD for linear PDE robust control computations

A mathematical model of a physical system is never perfect; therefore, robust control laws are necessary for guaranteed stabilization of the nominal model and also "nearby" systems, including hopefully the actual physical system. We consider the ...
MULTITHREADED MODEL FOR DYNAMIC LOAD BALANCING PARALLEL ADAPTIVE PDE COMPUTATIONS
ODE/PDE analysis of corneal curvature

The starting point for this paper is a nonlinear, two-point boundary value ordinary differential equation (BVODE) that defines corneal curvature according to a static force balance. A numerical solution to the BVODE is computed by first converting the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICS '89: Proceedings of the 3rd international conference on Supercomputing

June 1989

484 pages

ISBN:0897913094

DOI:10.1145/318789

Chairmen:
George Paul
IBM
,
T. Papatheodorou
CTI, Greese
,
D. Gannon,
E. N. Pudue

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICS89

Sponsor:

AICA
Computer Tech Inst.
SIGARCH
SIAM

ICS89: International Conference on Supercomputing 89

June 5 - 9, 1989

Crete, Greece

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
277
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)5

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Diekmann RPreis RSchlimbach FWalshaw C(2006)Aspect ratio for mesh partitioningEuro-Par’98 Parallel Processing10.1007/BFb0057872(347-351)Online publication date: 30-Jun-2006
https://doi.org/10.1007/BFb0057872
Diekmann RSchlimbach FWalshaw C(2005)Quality balancing for parallel adaptive FEMSolving Irregularly Structured Problems in Parallel10.1007/BFb0018537(170-181)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0018537
Diekmann RMeyer DMonien B(2005)Parallel decomposition of unstructured FEM-meshesParallel Algorithms for Irregularly Structured Problems10.1007/3-540-60321-2_17(199-215)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-60321-2_17
Chrisochoides NNave D(2000)Simultaneous mesh generation and partitioning for Delaunay meshesMathematics and Computers in Simulation10.1016/S0378-4754(00)00192-054:4-5(321-339)Online publication date: 15-Dec-2000
https://dl.acm.org/doi/10.1016/S0378-4754%2800%2900192-0
Diekmann RPreis RSchlimbach FWalshaw C(2000)Shape-optimized mesh partitioning and load balancing for parallel adaptive FEMParallel Computing10.1016/S0167-8191(00)00043-026:12(1555-1581)Online publication date: 1-Nov-2000
https://dl.acm.org/doi/10.1016/S0167-8191%2800%2900043-0
Houstis ERice JWeerawarana SCatlin APapachiou PWang KGaitatzes M(2000)PELLPACK: A Problem Solving Environment for PDE Based Applications on Multicomputer PlatformsEnabling Technologies for Computational Science10.1007/978-1-4615-4541-5_14(171-185)Online publication date: 2000
https://doi.org/10.1007/978-1-4615-4541-5_14
Houstis ERice JWeerawarana SCatlin APapachiou PWang KGaitatzes M(1998)PELLPACKACM Transactions on Mathematical Software10.1145/285861.28586424:1(30-73)Online publication date: 1-Mar-1998
https://dl.acm.org/doi/10.1145/285861.285864
Chrisochoides N(1994)An alternative to data mapping for parallel PDE solvers: parallel grid generationProceedings of Scalable Parallel Libraries Conference10.1109/SPLC.1993.365584(36-44)Online publication date: 1994
https://doi.org/10.1109/SPLC.1993.365584
Chrisochoides NHoustis EHoustis C(1991)Geometry based mapping strategies for PDE computationsProceedings of the 5th international conference on Supercomputing10.1145/109025.109060(115-127)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/109025.109060
Houstis ERice JChrisochoides NKarathanasis HPapachiou PSamartzis MVavalis EWang KWeerawarana SSameh Avan der Vorst H(1990)//ELLPACKProceedings of the 4th international conference on Supercomputing10.1145/77726.255144(96-107)Online publication date: 1-Jun-1990
https://dl.acm.org/doi/10.1145/77726.255144
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Balanced POD for linear PDE robust control computations

MULTITHREADED MODEL FOR DYNAMIC LOAD BALANCING PARALLEL ADAPTIVE PDE COMPUTATIONS

ODE/PDE analysis of corneal curvature