relaxed semantics

The strict semantics of many concurrent data structures are often useful when designing algorithms. However, such semantics make achieving high degrees of parallelism problematic for data structures such as FIFO queues, where operations contend for a few shared access points (the head and tail in this case). Thus, such data structures suffer large synchronization overheads under high contention, severely limiting scalability.

Relaxed concurrent data structures were introduced as a way to alleviate such synchronization bottlenecks. They achieve this by weakening the ordering semantics of the data structure, essentially trading some order (in a controlled manner) for parallelism. This post introduces the d-CBO queue, which is a state-of-the-art relaxed FIFO queue.

In the age of multicore computing, developers face the challenge of designing data structures that efficiently utilize the available hardware parallelism. One of the most important data structures is the priority queue, which is used in a variety of applications ranging from graph algorithms to data compression. Computer scientists often are taught some heap-based design of priority queues during university, where smart incremental updates enable good performance. However, trying to parallelize these designs is complex, as is often the case with strictly incremental algorithms. In this post, we will investigate the MultiQueue, which is a relaxed priority queue that trades strict sequential semantics for massively increased scalability.

In the middle of a flurry of work on relaxed semantics, Henzinger et al. published the paper Quantitative Relaxation of Concurrent Data Structures in 2013. Its primary contribution is ironing out a framework for the theory of relaxed semantics. The idea is to allow incorrect transitions between states in the data structure specification while being able to associate different paths or transitions with different costs. Furthermore, they create a relaxed out-of-order stack. Here we will concisely but informally present the theory, and in the end, quickly outline the stack.