Minimum distance: a method for partitioning recurrences for multiprocessors

Author

Peir, Jih-Kwon ; Cytron, Ron

Author_Institution

IBM T.J. Watson Res. Center, Yorktown Heights, NY, USA

Volume

38

Issue

8

fYear

1989

fDate

8/1/1989 12:00:00 AM

Firstpage

1203

Lastpage

1211

Abstract

Parallel execution of nonvectorizable uniform recurrences is considered. When naively scheduled, such recurrences could create unacceptable communication and synchronization on a multiprocessor. The minimum-distance method partitions such recurrences into totally independent computations without increasing redundancy or perturbing numerical stability. The independent computations are well suited for execution on a multiprocessor, but they may not utilize all available processors. How extra processors can be applied to the independent computations is addressed. The methods are especially attractive for multiprocessors comprised of clusters

Keywords

computer networks; multiprocessing systems; clusters; minimum distance; multiprocessors; nonvectorizable uniform recurrences; numerical stability; parallel execution; partitioning recurrences; totally independent computations; Clustering algorithms; Concurrent computing; Data analysis; Data communication; Helium; Numerical stability; Parallel processing; Partitioning algorithms; Processor scheduling; Program processors;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.30873

Filename

30873