Benutzer:Bahodil/Parallele Prioritätsliste
aus Wikipedia, der freien Enzyklopädie
Ergänzungen: Sequentielle Vorrangwarteschlange
Standard Operationen
- insert, Einfügen eines Elementes mit assoziierter Priorität
- is_empty, Prüfen, ob Wartschlange leer ist
Erweiterte Opertationen
- peek, gibt Element mit der höchsten Priorität zurück, ohne die Warteschlange zu verändern
- merge, Zusammenfügen von zwei Warteschlangen
- Tabelle mit Laufzeiten für verlinkte Implementierung
Weitere Anwendungen
- Bandbreitenmanagement
- A*-Algorithmus
Parallele Prioritätslisten
Es gibt verschiedene Möglichkeiten Prioritätslisten zu parallelisieren...
Einzelne Operationen parallelisieren
- Der maximale Speedup ist O(log n)
- Beschreibung der einzelnen Operationen (insert, delete_min, decrease_key, remove) [1]
- Vor und Nachteile
gleichzeitiger paralleler Zugriff
- Beschreibung der Zugriffsmethoden (CRCW, CREW) [2]
- Vor und Nachteile
k-Element-Operationen
- Beschreibung der neuen Operationen, k_insert, k_delete_min, k_decrease_key (evtl. Schaubild) [4]
- Vor und Nachteile
Zusammenfassender Vergleich
evtl. mit Tabelle
Literatur
- ↑ Gerth S. Brodal: Priority queues on parallel machines. In: Springer-Verlag (Hrsg.): Algorithm Theory - SWAT 96. 1996, S. 416-427.
- ↑ Galen C. Hunt, Maged M. Michael: An efficient algorithm for concurrent priority queue heaps. In: Information Processing Letters. 60, Nr. 3, 1996, S. 151-157. doi:10.1016/S0020-0190(96)00148-2.
- ↑ Håkan Sundell, Philippas Tsigas: Fast and lock-free concurrent priority queues for multi-thread systems. In: Journal of Parallel and Distributed Computing. 65, Nr. 5, 2005, S. 609-627. doi:10.1109/IPDPS.2003.1213189.
- ↑ Peter Sanders: Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox. Springer-Verlag, 2019, ISBN 9783030252090, S. 226-228.
