Efficiently Calculating Relaxation Errors

Abstract

Relaxed data structures have been designed to leverage the parallelism of modern processors more effectively than current strict concurrent data structures can. This kind of data structure relaxes the semantics for performance at the cost of correctness. For instance, to avoid contention between threads, a relaxed FIFO queue may return an element close to the head rather than the head itself. This out-of-order operation can be measured through relaxation errors, most notably rank errors. A current problem within the field of relaxed data structures is that the process of computing rank errors is rarely discussed, and only final results are presented. Furthermore, the methods presented are inefficient and require computationally intensive calculations. Therefore, there is a need in the field for faster and more efficient algorithms to compute rank errors. In this thesis, we present several approaches and algorithms for calculating the rank errors of FIFO (First-In-First-Out) queues and benchmark them against one another. Specifically, we introduce two algorithms that are hundreds of times faster than the current methods in the field. Additionally, the best-performing algorithms are adapted to calculate delay errors for FIFO queues and rank errors for LIFO (Last-In-First-Out) queues, demonstrating that their performance can be extended to other neighboring problems. Finally, we implement approximations of the calculations to enhance performance at the cost of correctness.