Practical algorithms for selection on coarse-grained parallel computers

Author

Al-Furiah, Ibraheem ; Aluru, Srinivas ; Goil, Sanjay ; Ranka, Sanjay

Author_Institution

Sch. of Comput. & Inf. Sci., Syracuse Univ., NY, USA

Volume

8

Issue

8

fYear

1997

fDate

8/1/1997 12:00:00 AM

Firstpage

813

Lastpage

824

Abstract

In this paper, we consider the problem of selection on coarse-grained distributed memory parallel computers. We discuss several deterministic and randomized algorithms for parallel selection. We also consider several algorithms for load balancing needed to keep a balanced distribution of data across processors during the execution of the selection algorithms. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on the experimental results. The results clearly demonstrate the role of randomization in reducing communication overhead

Keywords

hypercube networks; parallel algorithms; randomised algorithms; resource allocation; CM-5; coarse-grained parallel computers; communication overhead; deterministic algorithms; distributed memory parallel computers; load balancing; randomization; randomized algorithms; Application software; Computer Society; Concurrent computing; Distributed computing; Hypercubes; Iterative algorithms; Load management; Multidimensional systems; Parallel algorithms; Partitioning algorithms;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.605768

Filename

605768