Accurate Linearizations for Relaxed FIFO queues

Abstract

The increased use of multi-core processors in personal computers and servers has introduced the problem of time-consuming inter-thread communication during data exchanges. In response to this problem, data structures with a relaxed sequential specification are currently researched and developed. One type of relaxed data structure is out-of-order relaxed FIFO queues, which enable high throughput by containing multiple access points. This results in a FIFO queue which allows the order of operations to not be exactly first-in-first-out, resulting in a rank error for operations which are out-of-order. Rank error is an accuracy measurement for operations on relaxed queues and is often used when evaluating a newly developed relaxed queue. The current method of measuring rank error for operations on a queue is based on an approximation of when operations take effect. This may not exactly represent how out-of-order the operations on a relaxed queue is. In this thesis, we investigate if it is possible to measure a lower rank error for operations on relaxed queues than what the current method measures. We present three algorithms aiming to achieve this (LP, OA and IC) and test them on operations on the relaxed 2Dd and d-CBO queues. Algorithm IC measures up to 18% less rank error than the current method measures, for a relaxed queue. We conclude that our findings motivate further research on this topic and suggest that the development of an extensive framework of algorithms may provide a useful tool for researchers in the field of relaxed data structures.