Parallel priority queue and list contraction: The BSP approach

Alexandras V. Gerbessiotis; Constantinos J. Siniolakis; Alexandre Tiskin

doi:10.1007/bfb0002764

Parallel priority queue and list contraction: The BSP approach

Alexandras V. Gerbessiotis, Constantinos J. Siniolakis, Alexandre Tiskin

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings
Publisher	Springer Verlag
Pages	409-416
Number of pages	8
ISBN (Print)	9783540634409
DOIs	https://doi.org/10.1007/bfb0002764
State	Published - 1997
Externally published	Yes
Event	3rd International Conference on Parallel Processing, Euro-Par 1997 - Passau, Germany Duration: Aug 26 1997 → Aug 29 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1300 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd International Conference on Parallel Processing, Euro-Par 1997
Country/Territory	Germany
City	Passau
Period	8/26/97 → 8/29/97

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0002764

Cite this

Gerbessiotis, A. V., Siniolakis, C. J., & Tiskin, A. (1997). Parallel priority queue and list contraction: The BSP approach. In Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings (pp. 409-416). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1300 LNCS). Springer Verlag. https://doi.org/10.1007/bfb0002764

Gerbessiotis, Alexandras V. ; Siniolakis, Constantinos J. ; Tiskin, Alexandre. / Parallel priority queue and list contraction : The BSP approach. Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings. Springer Verlag, 1997. pp. 409-416 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e7448ec96c7149438608ac8606f804b4,

title = "Parallel priority queue and list contraction: The BSP approach",

abstract = "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.",

author = "Gerbessiotis, {Alexandras V.} and Siniolakis, {Constantinos J.} and Alexandre Tiskin",

year = "1997",

doi = "10.1007/bfb0002764",

language = "English (US)",

isbn = "9783540634409",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "409--416",

booktitle = "Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings",

address = "Germany",

note = "3rd International Conference on Parallel Processing, Euro-Par 1997 ; Conference date: 26-08-1997 Through 29-08-1997",

}

Gerbessiotis, AV, Siniolakis, CJ & Tiskin, A 1997, Parallel priority queue and list contraction: The BSP approach. in Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1300 LNCS, Springer Verlag, pp. 409-416, 3rd International Conference on Parallel Processing, Euro-Par 1997, Passau, Germany, 8/26/97. https://doi.org/10.1007/bfb0002764

Parallel priority queue and list contraction: The BSP approach. / Gerbessiotis, Alexandras V.; Siniolakis, Constantinos J.; Tiskin, Alexandre.
Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings. Springer Verlag, 1997. p. 409-416 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1300 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Parallel priority queue and list contraction

T2 - 3rd International Conference on Parallel Processing, Euro-Par 1997

AU - Gerbessiotis, Alexandras V.

AU - Siniolakis, Constantinos J.

AU - Tiskin, Alexandre

PY - 1997

Y1 - 1997

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

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

U2 - 10.1007/bfb0002764

DO - 10.1007/bfb0002764

M3 - Conference contribution

AN - SCOPUS:21744460708

SN - 9783540634409

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 1997 Parallel Processing - Third International Conference, Proceedings

PB - Springer Verlag

Y2 - 26 August 1997 through 29 August 1997

ER -

Gerbessiotis AV, Siniolakis CJ, Tiskin A. Parallel priority queue and list contraction: The BSP approach. In Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings. Springer Verlag. 1997. p. 409-416. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0002764

Parallel priority queue and list contraction: The BSP approach

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this