Search

The Nix operating system permits different roles to be assigned to the cores. One of the roles is to be able to run user-space code with no interrupts from the operating system, which is particularly useful for high-performance computing. System calls are especially expensive to a core playing this role. This paper presents a new implementation of optimistic semaphores that avoid performing expensive system calls in an uncontended scenario. The implementation is straightforward and somewhat unorthodox: a semaphore is based on a data structure and a lock that are shared between user space and kernel space. This study aims at evaluating if such an approach is viable. In addition, the implementation includes a non-deterministic choice operation over a collection of semaphores, altsems. This novel operation facilitates the creation of higher-level communication mechanisms, such as sockets and channels. To support this claim, we implemented a new kind of buffered communication channels named tubes, tailored for communicating processes running on different heterogeneous cores. The paper describes the implementation of the semaphores and the tubes, a comparative analysis of optimistic and non-optimistic semaphores on Nix, and a comparative analysis of tubes and other kinds of communication channels that are available on the Nix operating system. Copyright © 2014 John Wiley & Sons, Ltd.

Software solutions for mutual exclusion developed over a 30-year period, starting with complex ad hoc algorithms and progressing to simpler formal ones. While it is easy to dismiss software solutions for mutual exclusion, as this family of algorithms is antiquated and most platforms support atomic hardware instructions, there is still a need for these algorithms in threaded, embedded systems running on low-cost processors lacking atomic instructions. While N-thread solutions are usually short 10-25 lines of code, each is ingenious with exceptionally subtle aspects, often making it difficult to prove correctness or construct an implementation. This work examines correctness and performance of the implementations. An extensive survey of existing algorithms is presented, with explanations of the intuition behind the algorithms and how they work. Several errors were found and corrections made, as well as a few small improvements, in the existing algorithms; two new high-performance algorithms were developed. Finally, a worst-case high-contention performance experiment is performed to compare the algorithms and contrast them with three common locks based on hardware atomic instructions. The results show our two new algorithms are highly competitive with an equivalent hardware lock Mellor-Crummey and Scott over a range of 1-32 processors. Hence, threading is a viable alternative to event-driven programming for complex embedded systems without atomic instructions. Copyright © 2014 John Wiley & Sons, Ltd.

This paper presents algorithms for concurrently reading and modifying a red-black tree RBTree. The algorithms allow wait-free, linearly scalable lookups in the presence of concurrent inserts and deletes. They have deterministic response times for a given tree size and uncontended read performance that is at least 60% faster than other known approaches. The techniques used to derive these algorithms arise from a concurrent programming methodology called relativistic programming. Relativistic programming introduces write-side delay primitives that allow the writer to pay most of the cost of synchronization between readers and writers. Only minimal synchronization overhead is placed on readers. Relativistic programming avoids unnecessarily strict ordering of read and write operations while still providing the capability to enforce linearizability. This paper shows how relativistic programming can be used to build a concurrent RBTree with synchronization-free readers and both lock-based and transactional memory-based writers. Copyright © 2013 John Wiley & Sons, Ltd.

SUMMARY Transactional memory is currently being advocated as a promising alternative to lock-based synchronization because it simplifies multithreaded programming. In this way, future many-core chip multiprocessor architectures may need to provide hardware support for transactional memory. On the other hand, energy consumption constitutes nowadays a first class consideration in multicore processor designs. In this work, we characterize the performance and energy consumption of two well-known hardware transactional memory systems that employ opposite policies for data versioning and conflict management. More specifically, we compare a LogTM-SE eager-eager system and a version of the Scalable Transactional Coherence and Consistency lazy-lazy system that enable parallel commits. To do so, we extended the Multifacet GEMS simulator to estimate the energy consumed in the on-chip caches according to CACTI and used the interconnection network energy model given by Orion 2. Results show that the energy consumption of the eager-eager system is 38% higher in average than in the lazy-lazy case, whereas performance differences between the two systems are 26% in average. We found that even though lazy-lazy beats eager-eager on average, there are considerable deviations in performance depending on the particular characteristics of each application and the settings of both systems. Finally, from this characterization, we observe that a significant part of the energy consumed in some applications in eager-eager is spent on the back-off delay phase and explore more energy-efficient hardware back-off mechanisms. For lazy-lazy systems, the way in which memory lines are assigned to the L2 cache banks affects the number of parallel commits in some applications, and we study an alternative fine-grained assignment. Copyright © 2012 John Wiley & Sons, Ltd.

Summary This paper presents a new starvation-free software algorithm for the N-thread mutual-exclusion problem. In the absence of contention, the algorithm requires only eight write and four read operations to enter and leave the critical section; to the best of our knowledge, this is optimal. For algorithms with starvation, five write and two read read operations are optimal. In the presence of contention, the algorithm has excellent performance comparable to the best-known software solutions using only atomic load and store and to a hardware-assisted lock (MCS) using stronger atomic primitives and used within the Linux kernel. It is rare for software-only algorithms for mutual exclusion to perform well for both minimal and maximal contention workloads, making the new algorithm largely self-tuning when exposed to swings in access patterns.

We have designed and implemented a lightweight process (thread) library called ‘Lesser Bear’ for SMP computers. Lesser Bear has thread-level parallelism and high portability. Lesser Bear executes threads in parallel by creating UNIX processes as virtual processors and a memory-mapped file as a huge shared-memory space. To schedule thread in parallel, the shared-memory space has been divided into working spaces for each virtual processor, and a ready queue has been distributed. However the previous version of Lesser Bear sometimes requires a lock operation for dequeueing. We therefore proposed a scheduling mechanism that does not require a lock operation. To achieve this, each divided space forms a link topology through the queues, and we use a lock-free algorithm for the queue operation. This mechanism is applied to Lesser Bear and evaluated by experimental results. Copyright © 2002 John Wiley & Sons, Ltd.

Developing concurrent applications is not a trivial task. As programs grow larger and become more complex, advanced concurrency control mechanisms are needed to ensure that application consistency is not compromised. Managing mutual exclusion on a per-object basis is not sufficient to guarantee isolation of sets of semantically-related actions. In this paper, we consider ‘atomic blocks’, a simple and lightweight concurrency control paradigm that enables arbitrary blocks of code to access multiple shared objects in isolation. We evaluate various strategies for implementing atomic blocks in Java, in such a way that concurrency control is transparent to the programmer, isolation is preserved, and concurrency is maximized. We discuss these concurrency control strategies and evaluate them in terms of complexity and performance. Copyright © 2002 John Wiley & Sons, Ltd.

We have designed and implemented a light-weight process (thread) library called ‘Lesser Bear’ for SMP computers. Lesser Bear has high portability and thread-level parallelism. Creating UNIX processes as virtual processors and a memory-mapped file as a huge shared-memory space enables Lesser Bear to execute threads in parallel. Lesser Bear requires exclusive operation between peer virtual processors, and treats a shared-memory space as a critical section for synchronization of threads. Therefore, thread functions of the previous Lesser Bear are serialized. In this paper, we present a scheduling mechanism to execute thread functions in parallel. In the design of the proposed mechanism, we divide the entire shared-memory space into partial spaces for virtual processors, and prepare two queues (Protect Queue and Waiver Queue) for each partial space. We adopt an algorithm in which lock operations are not necessary for enqueueing. This algorithm allows us to propose a scheduling mechanism that can reduce the scheduling overhead. The mechanism is applied to Lesser Bear and evaluated by experimental results. Copyright © 2001 John Wiley & Sons, Ltd.

This article reports the use of case studies to evaluate the performance degradation caused by the kernel-level lock. We define the lock ratio as a ratio of the execution time for critical sections to the total execution time of a parallel program. The kernel-level lock ratio determines how effective programs work on symmetric multiprocessor (SMP) systems. We have measured the lock ratios and the performance of three types of parallel programs on SMP systems with Linux 2.0: matrix multiplication, parallel make, and WWW server programs. Experimental results show that the higher the lock ratio of parallel programs, the worse their performance becomes. Copyright © 2001 John Wiley & Sons, Ltd.

Summary A software locking mechanism commonly protects shared resources for multithreaded applications. This mechanism can, especially in chip-multiprocessor systems, result in a large synchronization overhead. For real-time systems in particular, this overhead increases the worst-case execution time and may void a task set's schedulability. This paper presents 2 hardware locking mechanisms to reduce the worst-case time required to acquire and release synchronization locks. These solutions are implemented for the chip-multiprocessor version of the Java Optimized Processor. The 2 hardware locking mechanisms are compared with a software locking solution as well as the original locking system of the processor. The hardware cost and performance are evaluated for all presented locking mechanisms. The performance of the better-performing hardware locks is comparable with that of the original single global lock when contending for the same lock. When several noncontending locks are used, the hardware locks enable true concurrency for critical sections. Benchmarks show that using the hardware locks yields performance ranging from no worse than the original locks to more than twice their best performance. This improvement can allow a larger number of real-time tasks to be reliably scheduled on a multiprocessor real-time platform. Copyright © 2016 John Wiley & Sons, Ltd.