𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Priority queues on parallel machines

✍ Scribed by G.S. Brodal

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
547 KB
Volume
25
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

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. A priority queue can be build in time Olog n with Ona log n processors. A pipelined version of the priority queues adopt to a processor array of size Olog n, supporting the operations MAKE AKEQUEUE U EU E, INSERT NSERT, MELD ELD, FIND INDMIN I N, EXTRACT XTRACT MIN I N, DELETE ELETE and DE-E-CREASE CREASEKEY EY in constant time. By applying the k-bandwidth technique we get a data structure for the CREW PRAM which supports MULTI ULTIINSERT NSERT k operations in Olog k time and MULTI U LTI EXTRACT XTRACT MIN IN k in Olog log k time.

πŸ“œ 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

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

Parallel heap: An optimal parallel prior
Parallel heap: An optimal parallel priority queue
✍ Narsingh Deo; Sushil Prasad πŸ“‚ Article πŸ“… 1992 πŸ› Springer US 🌐 English βš– 619 KB

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 p

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