A Partitioning Strategy for Nonuniform Problems on Multiprocessors

Marsha J. Berger

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)570-580
Number of pages11
JournalIEEE Transactions on Computers
Issue number5
StatePublished - May 1987

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'A Partitioning Strategy for Nonuniform Problems on Multiprocessors'. Together they form a unique fingerprint.

Cite this