The Library
Parallel priority queue and list contraction: The BSP approach
Tools
UNSPECIFIED (2002) Parallel priority queue and list contraction: The BSP approach. COMPUTING AND INFORMATICS, 21 (1). pp. 59-90. ISSN 1335-9150.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
In this work we present efficient and practical randomized data structures on the Bulk-Synchronous Parallel (BSP) model of computation along with all experimental study of their performance. In particular, we study data structures for the realization of Parallel Priority Queues, (PPQs). We show that our algorithms are communication efficient and achieve optimality to within small multiplicative constant factors for a wide range of parallel machines. We also present an experimental ;study of our PPQ algorithms oil a Cray T3D. Finally, we present new randomized and deterministic BSP algorithms for list and tree contraction.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Journal or Publication Title: | COMPUTING AND INFORMATICS | ||||
Publisher: | SLOVAK ACADEMY SCIENCES INST INFORMATICS | ||||
ISSN: | 1335-9150 | ||||
Official Date: | 2002 | ||||
Dates: |
|
||||
Volume: | 21 | ||||
Number: | 1 | ||||
Number of Pages: | 32 | ||||
Page Range: | pp. 59-90 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |