Startseite > Publikationen > Publikationen


Bäumker, Armin;Dittrich, Wolfgang;Meyer auf der Heide, Friedhelm;Rieping, Ingo:

Realistic Parallel Algorithms: Priority Queue Operations and Selection for the BSP Model.

Euro-Par 1996 II: S. 369-376, Jun. 1996


In this paper, we explore parallel implementations of the abstract data type priority queue. We use the BSP* model, an extension of Valiant's BSP model which rewards blockwise communication, i.e. sending a few large messages instead of many small ones. We present two randomized approaches for different relations between the size of the data structure and the number of parallel updates to be performed. Both yield work optimal algorithms that need asymptotically less communication than computation time and use large messages. All previous work optimal algorithms need asymptotically as much communication as computation or do not consider blockwise communication. We use a work optimal randomized selection algorithm as a building block. This might be of independent interest. It uses less communication than computation time, if the keys are distributed at random. A similar selection algorithm was independently developed by Gerbessiotis and Siniolakis for the standard BSP model. We improve upon previous work by both reducing the amount of communication and by using large messages.




author = {B{\"a}umker, Armin and Dittrich, Wolfgang and Meyer auf der Heide, Friedhelm and Rieping, Ingo},
title = {Realistic Parallel Algorithms: Priority Queue Operations and Selection for the BSP Model},
journal = {Euro-Par 1996},
volume = {II},
pages = {369-376},
month = jun,
year = {1996},

BibTeX in die Zwischenablage kopieren