A Partitioning Strategy for Nonuniform Problems on Multiprocessors

Research output: Contribution to journalArticle

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.

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

ASJC Scopus subject areas

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

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

  • Cite this