✦ LIBER ✦

Parallel priority queues

✍ Scribed by Maria Cristina Pinotti; Geppino Pucci

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 475 KB
Volume: 40
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(05)80007-9

No coin nor oath required. For personal study only.

✦ Synopsis

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 new d~ta structures, the n-Bandwid~_h-Heap (n-H) and !he n-Bandwidth-Leftist-Heap (n-L), that are obtained as extensions of the well-known sequential binary-heap and leftist-heap, respectively. Using these structures, it is shown that insertion of n ne~ items in a PPQ of m elements can be performed in parallel time O(h +log n), where h = log(m/n), while deletion of the n smallest iteras can be performed in time O(h + log log n).

📜 SIMILAR VOLUMES

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

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

Randomized Priority Queues for Fast Para

Randomized Priority Queues for Fast Parallel Access

✍ Peter Sanders 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 167 KB

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

-preemptive priority queues

✍ Kilhwan Kim 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 500 KB

In this paper, we propose a new priority discipline, called the (N, n)-preemptive priority discipline. Under this discipline, the preemption of the service of a low-class customer is determined by two thresholds N and n of the queue length of high-class customers. We consider M/G/1 priority queueing