An experimental study of BSP sorting algorithms

Author

Gerbessiotis, A.V. ; Siniolakis, C.J.

Author_Institution

Comput. Lab., Oxford Univ., UK

fYear

1998

fDate

21-23 Jan 1998

Firstpage

479

Lastpage

485

Abstract

The bulk-synchronous parallel (BSP) model of computation has been proposed as a unifying and bridging model for the design, analysis and implementation of parallel algorithms that are both scalable and portable among diverse parallel machines. The authors implement, using the Oxford BSP Toolset, BSPlib, a number of BSP deterministic and randomized sorting algorithms on a variety of parallel systems, including the SGI Power Challenge and the CRAY T3D. The experimental results illustrate the efficiency, portability and reusability of the algorithms across such diverse hardware platforms, and reinforce their claim that the BSP model can be used as a kind of programming paradigm

Keywords

deterministic algorithms; parallel algorithms; parallel machines; parallel programming; randomised algorithms; software portability; sorting; BSP sorting algorithms; BSPlib; CRAY T3D; Oxford BSP Toolset; SGI Power Challenge; bulk-synchronous parallel computation model; deterministic sorting algorithms; efficiency; parallel machines; portability; portable parallel algorithms; programming paradigm; randomized sorting algorithms; reusability; scalable parallel algorithms; Algorithm design and analysis; Communication networks; Computational modeling; Computer networks; Concurrent computing; Hardware; Parallel programming; Portable computers; Sorting; Throughput;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1998. PDP '98. Proceedings of the Sixth Euromicro Workshop on

Conference_Location

Madrid

Print_ISBN

0-8186-8332-5

Type

conf

DOI

10.1109/EMPDP.1998.647236

Filename

647236