Search

This paper considers the modeling and the analysis of the performance of lock-free concurrent data structures that can be represented as linear combinations of fixed size retry loops. Our main contribution is a new way of modeling and analyzing a general class of lock-free algorithms, achieving predictions of throughput that are close to what we observe in practice. We emphasize two kinds of conflicts that shape the performance: i hardware conflicts, due to concurrent calls to atomic primitives; ii logical conflicts, caused by concurrent operations on the shared data structure. We propose also a common framework that enables a fair comparison between lock-free implementations by covering the whole contention domain, and comes with a method for calculating a good back-off strategy. Our experimental results, based on a set of widely used concurrent data structures and on abstract lock-free designs, show that our analysis follows closely the actual code behavior.

In this paper, we port a parallel full-system emulator to RISC host to achieve higher performance by utilize all the multi-core resources from physical CPU, in contrast the traditional full-system emulator is sequentially in SMP emulation and can only use one core of host machine. We mainly deal with the atomic instruction translation to RISC ll/sc pairs, and apply lightweight lock-free FIFO queue algorithms using both interleaving and non-interleaving ll/sc pairs. The tests show that the performance of parallel full-system emulator have high efficiency.

Concurrent data structures are often used with large concurrent software. An iterator that traverses the data structure items is a highly desirable interface that often exists for sequential data structures but is missing from almost all concurrent data-structure implementations. In this paper we introduce a technique for adding a linearizable wait-free iterator to a wait-free or a lock-free data structure that implements a set. We use this technique to implement an iterator for the wait-free and lock-free linked-lists and for the lock-free skip-list.

We introduce fast and scalable algorithms that implement bounded- and unbounded-size lock-free k-FIFO queues on parallel, shared memory hardware. Logically, a k-FIFO queue can be understood as queue where elements may be dequeued out-of-order up to k-1, or as pool where the oldest element is dequeued within at most k dequeue operations. The presented algorithms enable up to k enqueue and k dequeue operations to be performed in parallel. Unlike previous designs, however, the algorithms also implement linearizable emptiness and full checks without impairing scalability. We show experimentally that there exist optimal and robust k that result in best access performance and scalability. We then demonstrate that our algorithms outperform and outscale all state-of-the-art concurrent pool and queue algorithms that we considered in all micro- and most macrobenchmarks. Moreover, we demonstrate a prototypical controller which identifies optimal k automatically at runtime achieving better performance than with any statically configuredi¾?k.

We extend state-of-the-art lock-free linked lists by building linked lists with special care for locality of traversals. These linked lists are built of sequences of entries that reside on consecutive chunks of memory. When traversing such lists, subsequent entries typically reside on the same chunk and are thus close to each other, e.g., in same cache line or on the same virtual memory page. Such cache-conscious implementations of linked lists are frequently used in practice, but making them lock-free requires care. The basic component of this construction is a chunk of entries in the list that maintains a minimum and a maximum number of entries. This basic chunk component is an interesting tool on its own and may be used to build other lock-free data structures as well.

A significant problem of lock-free concurrent data structures in an environment without garbage collection is to ensure safe memory reclamation of objects that are removed from the data structure. An elegant solution to this problem is Michael's hazard pointers method. The formal verification of concurrent algorithms with hazard pointers is yet challenging. This work presents a mechanized proof of the major correctness and progress aspects of a lock-free stack with hazard pointers.

Highly concurrent and reliable data objects are vital for parallel programming. Lock-free shared data objects are highly concurrent and guarantee that at least one operation, from a set of concurrently executed operations, finishes after a finite number of steps regardless of the state of the other operations. Lock-free data objects provide progress guarantees on the object level. In this paper, we first examine the progress guarantees provided by lock-free shared data objects that have been constructed by composing other lock-free data objects. We observe that although lock-free data objects are composable when it comes to linearizability, when it comes to progress guarantees they are not. More specifically we show that when a lock-free data object is used as a component (is shared) by two or more lock-free data objects concurrently, these objects can no longer guarantee lock-free progress. This makes it impossible for programmers to directly compose lock-free data objects and guarantee lock-freedom. To help programmability in concurrent settings, this paper presents a new synchronization mechanism for composing lock-free data objects. The proposed synchronization mechanism provides an interface to be used when calling a lock-free object from other lock-free objects, and guarantees lock-free progress for every object constructed. An experimental evaluation of the performance cost that the new mechanism introduces, as expected, for providing progress guarantees is also presented.

Working on shared mutable data requires synchronization through barriers, locks or transactional memory mechanisms. To avoid this overhead a thread may privatize part of the data and work on it locally. By privatizing a data item a thread is guaranteed that it is the only one accessing this data, i.e., that it accesses the data item in exclusion. The most robust and yet lock-free privatization algorithms, are lockfree reference counting (LFRC). These algorithms attach a counter to each node, which counts the number of references to the node. However, these counters are shared by all threads in the system and thus are contention prone, and must be updated with expensive atomic operations such as CAS. We present a new privatization algorithm, Public Guard (PG); an algorithm which eliminates most of the contention of LFRC algorithms, while maintaining their robustness and non blocking nature. Our evaluation shows that PG improves performance by up to 50% in many work loads. Another problematic issue with LFRC, that we address in this paper, is that a counter of a private node, may be accessed by a slow thread. This may prevent LFRC from freeing memory to the system. In another contribution of this paper we suggest a method with minimal overhead to allow LFRC to reclaim memory.

The imminent arrival of best-effort transactional hardware has spurred new interest in the construction of nonblocking data structures, such as those that require atomic updates to k words of memory (for some small value of k). Since transactional memory itself (TM) was originally proposed as a universal construction for crafting scalable lock-free data structures, we explore the possibility of using this emerging transactional hardware to implement a scalable, unbounded transactional memory that is simultaneously nonblocking and compatible with strong language-level semantics. Our results show that it is possible to use this new hardware to build nonblocking TM systems that perform as well as their blocking counterparts. We also find that while the construction of a lock-free TM is possible, correctness arguments are complicated by the many caveats and corner cases that are built into current transactional hardware proposals.

We present an efficient and practical non-blocking implementation of a concurrent array-based FIFO queue that is suitable for preemptive multi threaded systems. It is well known that concurrent FIFO queues relying on mutual exclusion cause blocking, which have several drawbacks and degrade overall system performance. Link-based non-blocking queue algorithms have a memory management problem whereby a removed node from the queue can neither be freed nor reused because other threads may still be accessing the node. Existing solutions to this problem introduce a fair amount of overhead and are shown to be less efficient compared to array-based algorithms, which inherently do not suffer from this problem. In addition to being independent in advance knowledge of the number of threads that can access the queue, our new algorithm improves on previously proposed algorithms in that it does not re quire any special instruction other than a load-linked/store-conditional atomic instruction operating on pointer-wide number of bits.

FIFO Queues have over the years been the subject of significant research. Such queues are used as buffers both in a variety of applications, and in recent years as a key tool in buffering data in high speed communication networks. Overall, the most popular dynamic-memory lock-free FIFO queue algorithm in the literature remains the MS-queue algorithm of Michael and Scott. Unfortunately, this algorithm, as well as many others, offers no more parallelism than that provided by allowing concurrent accesses to the head and tail. In this paper we present the Baskets Queue - a new, highly concurrent lock-free linearizable dynamic memory FIFO queue. The Baskets Queue introduces a new form of parallelism among enqueue operations that creates baskets of mixed-order items instead of the standard totally ordered list. The operations in different baskets can be executed in parallel. Surprisingly however, the end result is a linearizable FIFO queue, and in fact, we show that a basket queue based on the MS-queue outperforms the original MS-queue algorithm in various benchmarks.

LFTHREADS is a thread library entirely based on lock-free methods, i.e. no spin-locks or similar synchronization mechanisms are employed in the implementation of the multithreading. Since lock-freedom is highly desirable in multiprocessors/multicores due to its advantages in parallelism, fault-tolerance, convoy-avoidance and more, there is an increased demand in lock-free methods in parallel applications, hence also in multiprocessor/multicore system services. This is why a lock-free multithreading library is important. To the best of our knowledge LFTHREADS is the first thread library that provides a lock-free implementation of blocking synchronization primitives for application threads. Lock-free implementation of objects with blocking semantics may sound like a contradicting goal. However, such objects have benefits: e.g. library operations that block and unblock threads on the same synchronization object can make progress in parallel while maintaining the desired thread-level semantics and without having to wait for any "slow" operations among them. Besides, as no spin-locks or similar synchronization mechanisms are employed, processors are always able to do useful work. As a consequence, applications, too, can enjoy enhanced parallelism and fault-tolerance. The synchronization in LFTHREADS is achieved by a new method, which we call responsibility hand-off (RHO), that does not need any special kernel support.

Distributed algorithms are inherently complex to verify. In this paper we show how to verify that a concurrent lock-free implementation of a stack is correct by mechanizing the proof that it is linearizable, linearizability being a correctness notion for concurrent objects. Our approach consists of two parts: the first part is independent of the example and derives proof obligations local for one process which imply linearizabilty. The conditions establish a (special sort of non-atomic) refinement relationshipbetween the specification and the concurrent implementation. These are used in the second part to verify the lock-free stack implementation. We use the specification language Z to describe the algorithms and the KIV theorem prover to mechanize the proof.

Message Passing Interface (MPI) is the most commonly used method for programming distributed-memory systems. Most MPI implementations use a rendezvous protocol for transmitting large messages. One of the features desired in a MPI implementation is the ability to asynchronously progress the rendezvous protocol. This is important to provide potential for good computation and communication overlap to applications. There are several designs that have been proposed in previous work to provide asynchronous progress. These designs typically use progress helper threads with support from the network hardware to make progress on the communication. However, most of these designs use locking to protect the shared data structures in the critical communication path. Secondly, multiple interrupts may be necessary to make progress. Further, there is no mechanism to selectively ignore the events generated during communication. In this paper, we propose an enhanced asynchronous rendezvous protocol which overcomes these limitations. Specifically, our design does not require locks in the communication path. In our approach, the main application thread makes progress on the rendezvous transfer with the help of an additional thread. The communication between the two threads occurs via system signals. The new design can achieve near total overlap of communication with computation. Further, our design does not degrade the performance of non-overlapped communication. We have also experimented with different thread scheduling policies of Linux kernel and found out that the round robin policy provides the best performance. With the new design we have been able to achieve 20% reduction in time for a matrix multiplication kernel with MPI+OpenMP paradigm on 256 cores.

This paper explores the feasibility of re-expressing concurrent algorithms with explicit locks in terms of lock free code written using Haskell's implementation of software transactional memory. Experimental results are presented which show that for multi-processor systems the simpler lock free implementations offer superior performance when compared to their corresponding lock based implementations.

Even though self-healing techniques for transactional processes have attracted enough attention in recent years, several critical issues regarding the distributed systems have not been addressed. For example, if we do the recovery under sustained attacks, in which condition the recovery can terminate? Is a synchronized clock necessary for distributed recovery? In this paper, we proposed a dead-lock free algorithm for coordinated recovery and answered related questions. We also proved that under specific situations, we have to freeze the recovery scheme to guarantee that the recovery can make progress.

This paper proposes the improved concurrency control technique with lock-free querying for multi-dimensional index structure. In highly concurrent workloads due to frequent updates for storing location of moving object, the variants of R-tree structure cannot provide the real-time response. Because query processing is frequently blocked by node-split or region propagation as the locations of objects change. This paper improves the query performance by using the new versioning technique. It does not physically modify data, but creates new version for compensating data intactness. Search operation can access data without any locking or latching by reading old version. In the performance evaluation, it is proven that search operation of the proposed tree is at least two times faster than a previous work.

We propose obstruction-free step complexity, a new complexity measure for nonblocking algorithms. We believe that this measure provides a more pragmatic quanti.cation of nonblocking algorithms than previous measures, providing better guidance for designers of practical nonblocking algorithms. In our opinion, the main shortcoming of existing complexity measures for nonblocking algorithms is that they are targeted towardsworst-case behavior inworstcase scenarios, and say little about behavior inmore common cases.This is true for the sensitivity measure of Attiya and Dagan [1], and the d-local step complexity of Afek et al. [2]. These measures are directed at evaluating the behavior of algorithms under contention, i.e., when concurrent operations actively interfere with each other’s progress. However, in practice, a well-designed system manages contention so that it does not impact performance too greatly. Thus, these previous measures do not evaluate the behaviour that is likely to be observed.

This paper presents a lock-free parallel algorithm for mark&sweep garbage collection (GC) in a realistic model using synchronization primitives compare-and-swap (CAS) and load-linked/store-conditional (LL/SC) offered by machine architectures. Mutators and collectors can simultaneously operate on the data structure. In particular no strict alternation between usage and cleaning up is necessary contrary to what is common in most other GC algorithms. We first design and prove an algorithm with a coarse grain of atomicity and subsequently apply the reduction theorem to implement the higher-level atomic steps by means of the low-level primitives CAS or LL/SC. Even so, the structure of our algorithm and its correctness properties, as well as the complexity of reasoning about them, makes neither automatic nor manual verification feasible. We have therefore chosen the higher-order interactive theorem prover PVS for mechanical support.

This paper studies implementations of concurrent objects that exploit the absence of step contention. These implementations use only reads and writes when a process is running solo. The other processes might be busy with other objects, swapped-out, failed, or simply delayed by a contention manager. We study in this paper two classes of such implementations, according to how they handle the case of step contention. The first kind, called obstruction-free implementations, are not required to terminate in that case. The second kind, called solo-fast implementations, terminate using powerful operations (e.g., C&S). We present a generic obstruction-free object implementation that has a linear contention-free step complexity (number of reads and writes taken by a process running solo) and uses a linear number of read/write objects. We show that these complexities are asymptotically optimal, and hence generic obstruction-free implementations are inherently slow. We also prove that obstruction-free implementations cannot be gracefully degrading, namely, be nonblocking when the contention manager operates correctly, and remain (at least) obstruction-free when the contention manager misbehaves. Finally, we show that any object has a solo-fast implementation, based on a solo-fast implementation of consensus. The implementation has linear contention-free step complexity, and we conjecture solo-fast implementations must have non-constant step complexity, i.e., they are also inherently slow.

The potential of multiprocessor systems is often not fully realized by their system services. Certain synchronization methods, such as lock-based ones, may limit the parallelism. It is significant to see the impact of wait/lock-free synchronization design in key services for multiprocessor systems, such as the memory allocation service. Efficient, scalable memory allocators for multithreaded applications on multiprocessors is a significant goal of recent research projects. We propose a lock-free memory allocator, to enhance the parallelism in the system. Its architecture is inspired by Hoard, a successful concurrent memory allocator, with a modular, scalable design that preserves scalability and helps avoiding false-sharing and heap blowup. Within our e.ort on designing appropriate lock-free algorithms to construct this system, we propose a new non-blocking data structure called flat-sets, supporting conventional “internal” operations as well as “inter-object” operations, for moving items between flat-sets. We implemented the memory allocator in a set of multiprocessor systems (UMA Sun Enterprise 450 and ccNUMA Origin 3800) and studied its behaviour. The results show that the good properties of Hoard w.r.t. false-sharing and heap-blowup are preserved, while the scalability properties are enhanced even further with the help of lock-free synchronization.

The ideal semantics of the instructions LL/SC/VL (Load-Linked, Store-Conditional, Validate) are inherently immune to the ABA problem which is a fundamental problem that affects most lock-free algorithms. This paper presents practical lock-free and wait-free implementations of arbitrary-sized LL/SC/VL variables using 64-bit CAS (Compare-and-Swap). The implementations improve on Jayanti and Petrovic’s 64-bit wait-free implementations by reducing the space overhead per variable to a small constant, and not requiring advance knowledge of the maximum number of participating threads, while maintaining minimal amortized expected time and work complexities.

Lock-free shared data structures in the setting of distributed computing have received a fair amount of attention Major motivations of lock-free data structures include increasing fault tolerance of a (possibly heterogeneous) system and alleviating the problems associated with critical sections such as priority inversion and deadlock For parallel computers with tightly-coupled processors and shared memory, these issues are no longer major concerns While many of the results are applicable especially when the model used is shared memory multiprocessors, no prior studies have considered improving the performance of a parallel implementation by way of lock-free programming As a matter of fact, often times in practice lock-free data structures in a distributed setting do not perform as well as those that use locks As the data structures and algorithms for parallel computing are often drastically different from those in distributed computing, it is possible that lock-free programs perform better In this paper we compare the similarity and difference of lock-free programming in both distributed and parallel computing environments and explore the possibility of adapting lock-free programming to parallel computing to improve performance Lock-free programming also provides a new way of simulating PRAM and asynchronous PRAM algorithms on current parallel machines.

First-in-first-out (FIFO) queues are among the most fundamental and highly studied concurrent data structures. The most effective and practical dynamic-memory concurrent queue implementation in the literature is the lock-free FIFO queue algorithm of Michael and Scott, included in the standard Java TM Concurrency Package.

This paper describes an extension of the lock-free message passing idea to the native implementation of the MPI-2 collective operations for the shared memory based platforms. A handy notation is introduced for the description of the collective algorithms. The results of benchmarking demonstrate viability and competitiveness of this approach by comparing the performance of Sun HPC and Fujitsu MPI-2 with and without proposed native collective optimizations.

This paper presents the first lock-free algorithm for shared double-ended queues (deques) based on the single-address atomic primitives CAS (Compare-and-Swap) or LL/SC (Load-Linked and Store-Conditional). The algorithm can use single-word primitives, if the maximum deque size is static. To allow the deque’s size to be dynamic, the algorithm employs single-address double-width primitives. Prior lock-free algorithms for shared deques depend on the strong DCAS (Double-Compare-and-Swap) atomic primitive, not supported on most processor architectures. The new algorithm offers significant advantages over prior lock-free shared deque algorithms with respect to performance and the strength of required primitives. In turn, lock-free algorithms provide significant reliability and performance advantages over lock-based implementations.

We present a new non-blocking implementation of concurrent linked-lists supporting linearizable insertion and deletion operations. The new algorithm provides substantial benefits over previous schemes: it is conceptually simpler and our prototype operates substantially faster.