EVA STAR Trefferanzeige

Volltext Volltext.pdf1.pdf (172 KB)
URN (für Zitat) http://nbn-resolving.org/urn:nbn:de:swb:90-AAA43976
Titel Randomized priority queues for fast parallel access.
Autor Sanders, Peter
Institution Fakultät für Informatik (INFORMATIK)
Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Dokumenttyp Buch
Jahr 1997
Erscheinungsvermerk Karlsruhe 1997. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1997,7.)
Abstract
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.