𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Load Sharing with Parallel Priority Queues

✍ Scribed by I. Parberry

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
898 KB
Volume
50
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 assigned to it, and the maximum time that it must wait to be relieved of an excess task. A simple parallel priority queue architecture for load sharing in a (p)-processor multiprocessor system is proposed. This architecture uses (O(p \log (n / p))) special-purpose processors (where (n) is the maximal size of the priority queue), an interconnection pattern of bounded degree, and achieves delay (O(\log p)), which is optimal for any bounded degree system. c 1995 Academic Press, Inc.

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

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

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