Progress-Based Distributed Queues - Exploring the effects of a novel heuristic with partial queues using fetch-and-add

Abstract

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.