KIT | KIT-Bibliothek | Impressum | Datenschutz

Randomized priority queues for fast parallel access

Sanders, Peter


Applications like parallel search or discrete event simulation often
assign priority or importance to pieces of work. An effective way
to exploit this for parallelization is to use a priority queue data
structure for scheduling the work; but a bottleneck free
implementation of parallel priority queue access by many processors
is required to make this approach scalable. We present simple and
portable randomized algorithms for parallel priority queues on
distributed memory machines with fully distributed storage.
Accessing O(n) out of m elements on an n-processor network
with diameter d requires amortized time O(d + log m/n)
with high probability for many network types. On logarithmic
diameter networks, the algorithms are as fast as the best previously
known EREW-PRAM methods. Implementations demonstrate that the approach is
already useful for medium scale parallelism.

Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Informatik – Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Publikationstyp Buch
Publikationsjahr 1997
Sprache Englisch
Identifikator urn:nbn:de:swb:90-AAA43976
KITopen-ID: 4397
Erscheinungsvermerk Karlsruhe 1997. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1997,7.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page