A Partitioning Strategy for Nonuniform Problems on Multiprocessors
- 1 May 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (5) , 570-580
- https://doi.org/10.1109/tc.1987.1676942
Abstract
We consider the partitioning of a problem on a domain with unequal work estimates in different subdomains in a way that balances the workload across multiple processors. Such a problem arises for example in solving partial differential equations using an adaptive method that places extra grid points in certain subregions of the domain. We use a binary decomposition of the domain to partition it into rectangles requiring equal computational effort. We then study the communication costs of mapping this partitioning onto different multiprocessors: a mesh- connected array, a tree machine, and a hypercube. The communication cost expressions can be used to determine the optimal depth of the above partitioning.Keywords
This publication has 10 references indexed in Scilit:
- Adaptive mesh refinement for hyperbolic partial differential equationsPublished by Elsevier ,2004
- A Communication-Time TradeoffSIAM Journal on Computing, 1987
- The Fast Adaptive Composite Grid (FAC) Method for Elliptic EquationsMathematics of Computation, 1986
- Automatic adaptive grid refinement for the Euler equationsAIAA Journal, 1985
- The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel ComputerIEEE Transactions on Computers, 1983
- On the Mapping ProblemIEEE Transactions on Computers, 1981
- Rapid Solution of Finite Element Equations on Locally Refined Grids by Multi-Level Methods.Published by Defense Technical Information Center (DTIC) ,1980
- Multidimensional divide-and-conquerCommunications of the ACM, 1980
- Design of an Adaptive, Parallel Finite-Element SystemACM Transactions on Mathematical Software, 1979
- A Permutation NetworkJournal of the ACM, 1968