A Partitioning Strategy for Nonuniform Problems on Multiprocessors

Marsha J. Berger

doi:10.1109/TC.1987.1676942

A Partitioning Strategy for Nonuniform Problems on Multiprocessors

Marsha J. Berger

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	570-580
Number of pages	11
Journal	IEEE Transactions on Computers
Volume	C-36
Issue number	5
DOIs	https://doi.org/10.1109/TC.1987.1676942
State	Published - May 1987

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Access to Document

10.1109/TC.1987.1676942

Cite this

@article{1aff6fa40f98430e97d2c287fe5cd3ef,

title = "A Partitioning Strategy for Nonuniform Problems on Multiprocessors",

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.",

author = "Berger, {Marsha J.}",

year = "1987",

month = may,

doi = "10.1109/TC.1987.1676942",

language = "English (US)",

volume = "C-36",

pages = "570--580",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "5",

}

TY - JOUR

T1 - A Partitioning Strategy for Nonuniform Problems on Multiprocessors

AU - Berger, Marsha J.

PY - 1987/5

Y1 - 1987/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023346636&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023346636&partnerID=8YFLogxK

U2 - 10.1109/TC.1987.1676942

DO - 10.1109/TC.1987.1676942

M3 - Article

AN - SCOPUS:0023346636

SN - 0018-9340

VL - C-36

SP - 570

EP - 580

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 5

ER -

A Partitioning Strategy for Nonuniform Problems on Multiprocessors

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this