𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallel heap: An optimal parallel priority queue

✍ Scribed by Narsingh Deo; Sushil Prasad

Publisher
Springer US
Year
1992
Tongue
English
Weight
619 KB
Volume
6
Category
Article
ISSN
0920-8542

No coin nor oath required. For personal study only.

✦ Synopsis

We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of O(p) highest priority items and insertions of O(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n.

πŸ“œ SIMILAR VOLUMES

Parallel priority queues
Parallel priority queues
✍ Maria Cristina Pinotti; Geppino Pucci πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 475 KB

This paper introduces the Parallel Priority Queue (PPQ) abstract data t:ype. A PPQ stores a set of integer-valued items and provides operations such as insertion of n new items or deletion of the n smallest ones. Algorithms for realizing PPQ operations on an n-proc~or CREW-PPdL.M are based, on two n

Priority queues on parallel machines
Priority queues on parallel machines
✍ G.S. Brodal πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 547 KB

We present time and work optimal priority queues for the CREW PRAM, supporting FIND I NDMIN IN in constant time with one processor and MAKE AKEQUEUE UEUE, INSERT NSERT, MELD ELD, FIND-IND-MIN I N, EXTRACT XTRACT MIN IN, DELETE ELETE and DECREASE ECREASEKEY EY in constant time with Olog n processors.

Load Sharing with Parallel Priority Queu
Load Sharing with Parallel Priority Queues
✍ I. Parberry πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 898 KB

For maximum efficiency in a multiprocessor system the load should be shared evenly over all processors; that is, there should be no idle processors when tasks are available. The delay in a load-sharing algorithm is the larger of the maximum time that any processor can be idle before a task is assign

Architecture independent parallel select
Architecture independent parallel selection with applications to parallel priority queues
✍ Alexandros V. Gerbessiotis; Constantinos J. Siniolakis πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 344 KB

We present a randomized selection algorithm whose performance is analyzed in an architecture independent way on the bulk-synchronous parallel (BSP) model of computation along with an application of this algorithm to dynamic data structures, namely parallel priority queues. We show that our algorithm