Search

This paper focuses on a large class of concurrent data structures that we call pool-like objects (e.g., stack, double-ended queue, and queue). Performance and progress guarantee are two important characteristics for concurrent data structures. In the aspect of performance, weakening the internal order in a pool-like object is an effective technique to reduce the synchronization cost among threads accessing the object, but no objects with weakened internal order provide a progress guarantee as strong as wait-freedom. Meanwhile, wait-free algorithms tend to be inefficient, which is mainly attributed to the helping mechanisms. Based on the philosophy of existing helping mechanisms, a wait-free pool-like object with weakened internal order would suffer from unnecessary process of getting the latest object state and synchronization. This paper takes a state-of-the-art implementation of stacks with weakened internal order as an example, and transforms it into a highly-efficient wait-free stack named WF-TS-Stack. The transformation method includes a helping mechanism with state reuse and a relaxed removal scheme. In addition, we use a simple and effective scheme to further improve the performance of WF-TS-Stack in Non-Uniform Memory Access (NUMA) architectures. Our evaluation with representative benchmarks shows that WF-TS-Stack outperforms its original building blocks by up to 1.45× at maximum concurrency. We also discuss how to yield an efficient double-ended queue (deque) variant of WF-TS-Stack, because deque is a more generalized pool-like object.

The prevalence of multicore processors necessitates the design of efficient concurrent data structures. Shared concurrent stacks are widely used as inter-thread communication structures in parallel applications. Wait-free stacks can ensure that each thread completes operations on them in a finite number of steps. This characteristic is valuable for parallel applications and operating systems, especially in real-time environments. Unfortunately, because wait-free algorithms are typically hard to design and considered inefficient, practical wait-free stacks are rare. In this paper, we present a practical, fast array-based concurrent stack with wait-free progress guarantee, named FA-Stack. A series of optimizations are proposed to bound the number of steps required to complete every push and pop operation. In addition, FA-Stack adopts a time-stamped scheme to reclaim memory. We use linearizability , a correctness condition for concurrent data structures, to prove that FA-Stack is a wait-free linearizable stack with respect to the Last in First Out (LIFO) semantics. Our evaluation with representative benchmarks shows that FA-Stack is an efficient wait-free stack. For example, compared to Sim-Stack (a state-of-the-art wait-free stack), FA-Stack improves the throughput of halfhalf benchmark by up to 2.4 $\times$ .

The last two decades witnessed the success of many efficient designs of concurrent data structures. A large set of them has a common base principle: each operation is split into a read-only traversal phase, which scans the data structure without locking or monitoring, and a read-write commit phase, which atomically validates the output of the traversal phase and applies the needed modifications to the data structure. In this paper we introduce Optimistic Transactional Boosting (OTB), an optimistic methodology for extending those designs in order to support the composition of multiple operations into one atomic execution by building a single traversal phase and a single commit phase for the whole atomic execution. As a result, OTB-based data structures are optimistic and composable . The former because they defer any locking and/or monitoring to the commit phase of the entire atomic execution; the latter because they allow the execution of multiple operations atomically. Additionally, in this paper we provide a theoretical model for analyzing OTB-based data structures and proving their correctness. In particular, we extended a recent approach that models concurrent data structures by including the two notions of optimism and composition of operations.

Memory fences are widely used to ensure the correctness for synchronization constructs on machines with relaxed consistency models. However, they are expensive and usually impose over-constrained ordering that causes unnecessary CPU stalls. In this paper, we observe that memory fences in TSO are merely intended to order synchronization variables. Based on this observation, we rethink the hardware-software interface of synchronization constructs on multicore processors and propose a new design called Sync-Order that differentiates synchronization variables ( sync-vars ) from normal ones. Sync-Order reduces hardware complexity such that the processor only needs to serialize the ordering among sync-vars . Its simplicity makes it easy to be integrated to the directory controller and it supports distributed directory, a missing feature in prior designs. We show that Sync-Order eliminates traditional fences on all sides of synchronization constructs (instead of only one side in prior work) and requires small effort for a programmer or compiler to annotate sync-vars . Our experimental results show that Sync-Order significantly reduces CPU stalls and boosts the performance of a set of synchronization constructs and concurrent data structures by 10 percent; meanwhile, the fence overhead of full applications from SPLASH-2 and PARSEC is reduced from 42 to 3 percent.

Lock-free objects offer significant performance and reliability advantages over conventional lock-based objects. However, the lack of an efficient portable lock-free method for the reclamation of the memory occupied by dynamic nodes removed from such objects is a major obstacle to their wide use in practice. We present hazard pointers, a memory management methodology that allows memory reclamation for arbitrary reuse. It is very efficient, as demonstrated by our experimental results. It is suitable for user-level applications - as well as system programs - without dependence on special kernel or scheduler support. It is wait-free. It requires only single-word reads and writes for memory access in its core operations. It allows reclaimed memory to be returned to the operating system. In addition, it offers a lock-free solution for the ABA problem using only practical single-word instructions. Our experimental results on a multiprocessor system show that the new methodology offers equal and, more often, significantly better performance than other memory management methods, in addition to its qualitative advantages regarding memory reclamation and independence of special hardware support. We also show that lock-free implementations of important object types, using hazard pointers, offer comparable performance to that of efficient lock-based implementations under no contention and no multiprogramming, and outperform them by significant margins under moderate multiprogramming and/or contention, in addition to guaranteeing continuous progress and availability, even in the presence of thread failures and arbitrary delays.

Although many high-performance computer systems are now multiprocessor-based, little work has been done in real-time concurrency control of transaction executions in a multiprocessor environment. Real-time concurrency control protocols designed for uniprocessor or distributed environments may not fit the needs of multiprocessor-based real-time database systems because of a lower concurrency degree of transaction executions and a larger number of priority inversions. This paper proposes the concept of a priority cap to bound the maximum number of priority inversions in multiprocessor-based real-time database systems to meet transaction deadlines. We also explore the concept of two-version data to increase the system concurrency level and to explore the abundant computing resources of multiprocessor computer systems. The capability of the proposed methodology is evaluated in a multiprocessor real-time database system under different workloads, database sizes and processor configurations. It is shown that the benefits of the priority cap in reducing the blocking time of urgent transactions are far greater than the losses involved in committing less urgent transactions. The idea of two-version data also greatly improves the system performance because of a much higher concurrency degree in the system.

The paper presents a simple and effective method for the concurrent manipulation of linearly ordered data structures on hypercube systems. The method Is based on the existence of an augmented binomial search tree, called the pruned binomial tree, rooted at any arbitrary processor node of the hypercube such that; every edge of the tree corresponds to a direct link between a pair of hypercube nodes; and the tree spans any arbitrary sequence of n consecutive nodes containing the root, using a fanout of at most [log/sub 2/ n] and a depth of at most [log/sub 2/ n]+1. Search trees spanning nonoverlapping processor lists are formed using only local information, and can be used concurrently without contention problems. Thus, they can be used for performing operations such as broadcast and merge simultaneously on sets with nonuniform sizes. Extensions of the tree to k-ary n-cubes and faulty hypercubes are presented. Applications of this concurrent data structure to low- and intermediate-level image processing algorithms, and for dictionary operations involving multiple keys, are also outlined. >