Applying HTM to an OLTP System: No Free Lunch

Transactional memory is a promising way for implementing efficient synchronization mechanisms for multicore processors. Intel's introduction of hardware transactional memory (HTM) into their Haswell line of processors marks an important step toward mainstream availability of transactional memory. Transaction processing systems require execution of dozens of critical sections to insure isolation among threads, which makes them one of the target applications for exploiting HTM. In this study, we quantify the opportunities and limitations of directly applying HTM to an existing OLTP system that uses fine-grained synchronization. Our target is Shore-MT, a modern multithreaded transactional storage manager that uses a variety of fine-grained synchronization mechanisms to provide scalability on multicore processors. We find that HTM can improve performance of the TATP workload by 13-17% when applied judiciously. However, attempting to replace all synchronization reduces performance compared to the baseline case due to high percentage of aborts caused by the limitations of the current HTM implementation. Copyright 2015 ACM.

Inferring Scalability from Program Pseudocode

Mihai Letia

Recent trends have led hardware manufacturers to place multiple processing cores on a single chip, making parallel programming the intended way of taking advantage of the increased processing power. However, bringing concurrency to average programmers is considered to be one of the major challenges in computer science today. The difficulty lies not only in writing correct parallel programs, but also in achieving the required efficiency and performance. For parallel programs, performance is not only about obtaining low execution times on a fixed number of cores, but also about maintaining efficiency as the number of available cores is increased. Ideally, programmers should have in their toolkit techniques that can be used when designing parallel programs, before any code is available for testing on production hardware, and which are then able to predict scalability once the program is implemented. Existing methods are either unreliable at predicting scalability, such as the case of disjoint-access parallelism, or do not apply to lock-based programs, which currently make up a large part of existing concurrent programs. Furthermore, using some of these techniques is so complicated that it outweighs the time required to implement, debug and test the program on real hardware. In this thesis we study the problem of predicting the scalability of concurrent programs without implementing them. This allows programmers in the design phase of a concurrent algorithm to choose only one or a few promising solutions that will be implemented, debugged and tested on production hardware. We first consider disjoint-access parallelism, an existing property that applies only to a very restricted class of programs. After an extensive practical evaluation spanning across a variety of scenarios, we find it to be ineffective at predicting scalability. For predicting the scalability of more general concurrent algorithms, we propose the obstruction degree, a new scalability metric based on the consistency requirements of algorithms. It applies to programs using locks, invalidation primitives and transactional memory. Our metric allows programmers to compare two given algorithms as well as predict their scalability limit, the maximum number of processors to which they can scale, thus allowing programmers to choose the appropriate size hardware for running their programs. We also examine the composition of relaxed memory transactions in order to combine the ease of programming offered by transactional memory with the increased scalability of transactions that circumvent the traditional transactional model. We present outheritance, a property we show to be both necessary and sufficient for ensuring the correct composition of relaxed transactions, and we show how to calculate the obstruction degree of compositions that use this new property. We use outheritance to build OE-STM, a new software transactional memory algorithm having elastic transactions that correctly compose.

EPFL2014

Scalable Synchronization in Shared-Memory Systems: Extrapolating, Adapting, Tuning

Georgios Chatzopoulos

As hardware evolves, so do the needs of applications. To increase the performance of an application, there exist two well-known approaches. These are scaling up an application, using a larger multi-core platform, or scaling out, by distributing work to multiple machines. Both approaches are typically implemented using the shared-memory and message-passing programming models. In both programming models, and for a wide range of workloads, there is contention for access to data, and applications need synchronization. On modern multi-core platforms with tens of cores and network interconnects with sub-millisecond latencies, synchronization bottlenecks can significantly limit the scalability of an application. This dissertation studies the scalability of synchronization in shared-memory settings and focuses on the changes brought upon by modern hardware advances in processors and network interconnects. As we show, current approaches to understanding the scalability of applications, as well as prevalent synchronization primitives, are not designed for modern workloads and hardware platforms. We then propose methods and techniques that take advantage of hardware and workload knowledge to better serve application needs. We first look into better understanding the scalability of applications, using low-level performance metrics in both hardware and software. We introduce ESTIMA, an easy-to-use tool for extrapolating the scalability of in-memory applications. The key idea underlying ESTIMA is the use of stalled cycles in both hardware (e.g., cycles spent waiting for cache line fetches or busy locks), as well as software (e.g., cycles spent on synchronization, or on failed Software Transactional Memory transactions). ESTIMA measures stalled cycles on a few cores and extrapolates them to more cores, estimating the amount of waiting in the system. We then focus on locking, a common way of synchronizing data accesses in a shared-memory setting. Typically, contention for data limits the scalability of an application. A poor choice of locking algorithm can further impact scalability. We introduce GLS, a middleware that makes lock-based programming simple and effective. In contrast to classic lock libraries, GLS does not require any effort from the programmer for allocating and initializing locks, nor for selecting the appropriate locking strategy. GLS relies on GLK, a generic lock algorithm that dynamically adapts to the contention level on the lock object, delivering the best performance among simple spinlocks, scalable queue-based locks, and blocking locks. Finally, we study the performance of distributed systems that offer transactions, by exposing shared-memory semantics. Recently, such systems have seen renewed interest due to advancements in networking hardware for datacenters. We show how such systems require significant manual tuning to achieve good performance in a popular category of workloads (OLTP), and argue that doing so is error-prone, as well as time-consuming, and it needs to be repeated when the workload or the hardware change. We then introduce SPADE, a physical design tuner for OLTP workloads on modern RDMA clusters. SPADE automatically decides on data partitioning, index and storage parameters, and the right mix of direct remote data accesses and function shipping to maximize performance. To achieve this, SPADE uses low-level hardware and network performance characteristics gathered through micro-benchmarks.

EPFL2018

Reflexes: programming abstractions for highly responsive computing in Java

Jesper Honig Spring

Achieving sub-millisecond response times in a managed language environment such as Java introduces significant implementation challenges. The Achilles' heel of Java is its reliance on automatic memory management for reclaiming dead objects. Typically, the garbage collectors used in commercial Java virtual machines are designed to maximize the performance of applications at the expense of predictability. Moreover, it is non-deterministic as to when and for how long the garbage collector will run. As a consequence garbage collection introduces execution interference that can easily reach hundreds of milliseconds, preventing the timeliness requirements of the real-time systems from being satisfied. Another source of interference relates to the integration of real-time tasks with a time-oblivious application. Typical programming practices for sharing data between threads involve synchronized access to some shared data structure through mutual exclusion. In a real-time system this might lead to unbounded blocking of the real-time thread, so-called priority inversion, causing serious deadlines infringements. Faced with these challenges a system designer typically has two options: to deploy a realtime garbage collector (RTGC), or to restrict the programming model. RTGCs achieve much improved predictability over traditional stop-the-world garbage collectors by interleaving the application execution with the garbage collection. Recent advances in real-time garbage collection algorithms have reduced latency to approximately 1 millisecond. Nevertheless, some applications, e.g., safety critical applications certified according to DO-178B, have temporal requirements beyond what is possible with state-of-the-art RTGCs. Moreover, real-time garbage collectors still face the problem of priority inversion. This thesis presents Reflexes, a simple, statically type-safe restricted programming model facilitating the construction of highly-responsive applications in Java. Reflexes are designed to make it easy to write and integrate simple periodic tasks or complex stream processors, both observing real-time timing constraints in the sub-millisecond range, into larger time-oblivious Java applications. Reflex tasks run in a part of memory free from garbage collection interference, and maintain a class-based separation between object lifetimes, enabling reclamation of periodic garbage in constant time. Tasks are organized in a graph and communicate through uni-directional, non-blocking channels. Furthermore, Reflexes enable non-blocking interaction between real-time tasks and time-oblivious code using methods with transactional semantics, circumventing typical problems of priority inversion when using common programming practices for synchronizing access to shared data. Reflexes specify a set of static safety checks preventing dangling pointers and preventing a Reflex from observing heap-allocated objects in an inconsistent state as they are, e.g., when being copied by a garbage collector. These checks are enforced statically by an extension of the standard Java compiler to guarantee correctness. We describe two implementations of Reflexes: a stand-alone prototype implementation built on top of a research Java real-time virtual machine, and an implementation based on an integration of Reflexes with two existing restricted programming models into a single unified framework, Flexotask, running on top of an industrial-strength Java real-time virtual machine. Whereas the prototype implementation of Reflexes is limited to a virtual machine with uni-processor support and exploits non-standard features of the virtual machine, the latter implementation leverages the multi-processor support of an industrial-strength virtual machine with minimal extensions. For both implementations we report separately on a number of encouraging results from empirical experiments using benchmark and real-world applications. Specifically, our experiments show that Reflexes in both cases are capable of achieving sub-millisecond response time with a high degree of predictability.

EPFL2008