Progress-Based Distributed Queues - Exploring the effects of a novel heuristic with partial queues using fetch-and-add
Ladda ner
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2024
Författare
Hermansson, Sebastian
Johansson, Elias
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
With the increasing use of multi-threaded processors comes the challenge of scaling
with a higher number of threads. To that end, the semantics of a data structure can
be relaxed to lessen contention and achieve better performance. The data structure
of interest in this thesis is a relaxed first-in-first-out queue called d-RA, which is
made up of partial queues. It utilizes a length-based heuristic, that chooses a queue
to perform an operation on. However, it employs relatively slow lock-free partial
queues and uses a heuristic that is not definitively proven to be optimal. Furthermore,
relaxed first-in-first-out queues lack real-world applications as they can not
be used if the order of operations is strict.
This thesis improves on the d-RA algorithm by using faster partial queues and a new
progress-based heuristic, which generally increases the data structure’s throughput,
causes it to scale with more threads, and lowers the level of relaxation. Additionally,
we use relaxed queues in an unordered breadth-first-search to calculate the shortest
paths in graphs where they are shown to outperform concurrent queues.
Beskrivning
Ämne/nyckelord
relaxed first-in-first-out queue , relaxed data structure , lock-free , linearizable