TY - GEN

T1 - Parallel priority queue and list contraction: The BSP approach

AU - Gerbessiotis, Alexandras V.

AU - Siniolakis, Constantinos J.

AU - Tiskin, Alexandre

PY - 1997/1/1

Y1 - 1997/1/1

N2 - In this paper we present efficient and practical extensions of the randomized Parallel Priority Queue (PPQ) algorithms of Ranade et al., and efficient randomized and deterministic algorithms for the problem of list contraction on the Bulk-Synchronous Parallel (BSP) model. We also present an experimental study of their performance. We show that our algorithms are communication efficient and achieve small multiplicative constant factors for a wide range of parallel machines.

AB - In this paper we present efficient and practical extensions of the randomized Parallel Priority Queue (PPQ) algorithms of Ranade et al., and efficient randomized and deterministic algorithms for the problem of list contraction on the Bulk-Synchronous Parallel (BSP) model. We also present an experimental study of their performance. We show that our algorithms are communication efficient and achieve small multiplicative constant factors for a wide range of parallel machines.

UR - http://www.scopus.com/inward/record.url?scp=21744460708&partnerID=8YFLogxK

U2 - 10.1007/bfb0002764

DO - 10.1007/bfb0002764

M3 - Conference contribution

AN - SCOPUS:21744460708

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 409

EP - 416

BT - Euro-Par'97 Parallel Processing (Euro-Par 1997)

ER -