A randomized sorting algorithm on the BSP model

Author

Gerbessiotis, Alexandros V. ; Siniolakis, Constantinos J.

Author_Institution

Comput. Lab., Oxford Univ., UK

fYear

1997

fDate

1-5 Apr 1997

Firstpage

293

Lastpage

297

Abstract

The authors present a new randomized sorting algorithm on the bulk-synchronous parallel (BSP) model. The algorithm improves upon the parallel slack of previous algorithms to achieve optimality. Tighter probabilistic bounds are also established. It uses sample sorting and utilizes recently introduced search algorithms for a class of data structures on the BSP model. Moreover the methods are within a 1+o(1) multiplicative factor of the respective sequential methods in terms of speedup for a wide range of the BSP parameters

Keywords

computational complexity; data structures; parallel algorithms; parallel programming; randomised algorithms; search problems; sorting; BSP model; bulk-synchronous parallel model; data structures; multiplicative factor; optimality; parallel slack; probabilistic bounds; randomized sorting algorithm; sample sorting; search algorithms; speedup; Communication networks; Computer architecture; Computer networks; Concurrent computing; Data structures; Laboratories; Parallel processing; Parallel programming; Sorting; Throughput;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1997. Proceedings., 11th International

Conference_Location

Genva

ISSN

1063-7133

Print_ISBN

0-8186-7793-7

Type

conf

DOI

10.1109/IPPS.1997.580912

Filename

580912