Search

The Transactional Data Structure Library (TDSL) methodology improves the programmability and performance of concurrent software by making it possible for programmers to compose multiple concurrent data structure operations into coarse-grained transactions. Like transactional memory, TDSL enables arbitrarily many operations on arbitrarily many data structures to appear to other threads as a single atomic, isolated transaction. Like concurrent data structures, the individual operations on a TDSL data structure are optimized to avoid artificial contention. We introduce techniques for reducing false conflicts in TDSL implementations. Our approach allows expressing the postconditions of operations entirely via semantic properties, instead of through low-level structural properties. Our design is general enough to support lists, deques, ordered and unordered maps, and vectors. It supports richer programming interfaces than are available in existing TDSL implementations. It is also capable of precise memory management, which is necessary in low-level languages like C++.

C++ has supported a provisional version of Transactional Memory (TM) since 2015, via a technical specification. However, TM has not seen widespread adoption, and compiler vendors have been slow to implement the technical specification. We conjecture that the proposed TM support is too difficult for programmers to use, too complex for compiler designers to implement and verify, and not industry-proven enough to justify final standardization in its current form. To address these problems, we present a different design for supporting TM in C++. By forbidding explicit self-abort, and by introducing an executor-based mechanism for running transactions, our approach makes it easier for developers to get code up and running with TM. Our proposal should also be appealing to compiler developers, as it allows a spectrum of levels of support for TM, with varying performance, and varying reliance on hardware TM support in order to provide scalability. While our design does not enable some of the optimizations admitted by the current technical specification, we show that it enables the implementation of robust support for TM in a small, orthogonal compiler extension. Our implementation is able to handle a wide range of transactional programs, delivering low instrumentation overhead and scalability and performance on par with the current state of the art. Based on this experience, we believe our approach to be a viable means of reinvigorating the standardization of TM in C++.

This chapter describes how to use consensus objects to build a universal construction, an algorithm for implementing a linearizable concurrent object for any sequential object type. It presents two algorithms, a lock-free one and a wait-free one. These universal constructions demonstrate the consensus objects are universal; that is, they can be used to implement a wait-free linearizable implementation of any object type.

This chapter covers several useful patterns for distributed coordination: combining, counting, diffraction, and sampling. Some of these techniques are deterministic; others use randomization. We cover two basic structures underlying these patterns, trees and combinatorial networks. Although these techniques support a high degree of parallelism with high throughput, they can also increase latency for uncontended execution.

This chapter begins our study of practical concurrency by exploring the impact of system architecture on the performance of spin locks. Understanding the memory hierarchy and how processors communicate is critical to being able to write effective concurrent programs. We examine how to exploit knowledge of the architecture to design locking algorithms that reduce contention and so improve performance.

This chapter begins our study of the foundations of concurrent computation by examining its most basic primitive, the read–write register. A register is a single location of shared memory. We characterize a register by the values it can store, the number of threads that can access it and what operations they can do, and the properties it guarantees. Starting from a one-bit register that supports only a single reader and a single writer, and guarantees the values read only if the read does not overlap a write, we present a series of constructions of increasingly powerful registers, culminating in an arbitrary-sized atomic multi-reader, multi-writer register. We also show how to use atomic registers to implement an atomic snapshot object, which can read multiple registers atomically. Although most of the algorithms presented in this chapter are impractical for real systems, they illustrate useful techniques for designing and reasoning about concurrent systems.

Some applications break down naturally into many parallel tasks. This chapter shows how to decompose and analyze such applications, introducing the notions of work and span. The chapter also introduces thread pools, an efficient and robust mechanism for executing such applications that insulates the programmer from platform-dependent details. Finally, it examines work stealing and other techniques for distributing the tasks among threads in a thread pool, and shows how to implement work stealing efficiently using specialized double-ended queues.

We present the skip vector, a novel highperformance concurrent data structure based on the skip list. The key innovation in the skip vector is to flatten the index and data layers of the skip list into vectors. This increases spatial locality, reduces synchronization overhead, and avoids much of the costly pointer chasing that skip lists incur. We evaluate a skip vector implementation in C++. Our implementation coordinates interactions among threads by utilizing optimistic traversal with sequence locks. To ensure memory safety, it employs hazard pointers; this leads to tight bounds on wasted space, but due to the skip vector design, does not lead to high overhead. Performance of the skip vector for small data set sizes is higher than for a comparable skip list, and as the amount of data increases, the benefits of the skip vector over a skip list increase.

We study the problem of ensuring the correctness of concurrent programs that perform mutating foreach and range operations over concurrent data structures. We introduce three algorithms which vary in the location and the granularity of concurrency control metadata. Our algorithms make the linearization of bulk operations visible to concurrent elemental operations, which enables them to scale well, keep overhead low, and operate within tight memory bounds. In our experimental evaluation, we demonstrate that our techniques do not hinder the performance of elemental operations in elemental-only workloads, and allow scalability among concurrent mutating bulk operations. Furthermore, in mixed workloads, our algorithms outperform the baseline, sometimes by an order of magnitude or more.

Storing data structures in high-capacity byte-addressable persistent memory instead of DRAM or a storage device offers the opportunity to (1) reduce cost and power consumption compared with DRAM, (2) decrease the latency and CPU resources needed for an I/O operation compared with storage, and (3) allow for fast recovery as the data structure remains in memory after a machine failure. The first commercial offering in this space is Intel® Optane™ Direct Connect (Optane™ DC) Persistent Memory. Optane™ DC promises access time within a constant factor of DRAM, with larger capacity, lower energy consumption, and persistence. We present an experimental evaluation of persistent transactional memory performance, and explore how Optane™ DC durability domains affect the overall results. Given that neither of the two available durability domains can deliver performance competitive with DRAM, we introduce and emulate a new durability domain, called PDRAM, in which the memory controller tracks enough information (and has enough reserve power) to make DRAM behave like a persistent cache of Optane™ DC memory.In this paper we compare the performance of these durability domains on several configurations of five persistent transactional memory applications. We find a large throughput difference, which emphasizes the importance of choosing the best durability domain for each application and system. At the same time, our results confirm that recently published persistent transactional memory algorithms are able to scale, and that recent optimizations for these algorithms lead to strong performance, with speedups as high as 6× at 16 threads.

Byte-addressable, non-volatile, random access memory (NVM) has the potential to dramatically accelerate the performance of storage-intensive workloads. For applications with irregular data access patterns, and applications that rely on ad-hoc data structures, the most promising model for interacting with NVM is a transactional model. However, the specifics of the model matter significantly. We introduce two models for programming persistent transactions. We show how to build concurrent persistent transactional memory from traditional software transactional memories. We then introduce general and model-specific optimizations that can substantially improve the performance of persistent transactions. Our evaluation shows a substantial improvement in the both the latency and scalability of persistent transactions.

Priority queues are a fundamental data structure, and in highly concurrent software, scalable priority queues are an important building block. However, they have a fundamental bottleneck when extracting elements, because of the strict requirement that each extract() returns the highest priority element. In many workloads, this requirement can be relaxed, improving scalability. We introduce ZMSQ, a scalable relaxed priority queue. It is the first relaxed priority queue that supports each of the following important practical features: (i) guaranteed success of extraction when the queue is nonempty, (ii) blocking of idle consumers, (iii) memory-safety in non-garbage-collected environments, and (iv) relaxation accuracy that does not degrade as the thread count increases. In addition, our experiments show that ZMSQ is competitive with state-of-the-art prior algorithms, often significantly outperforming them.

There is a mechanical transformation by which algorithms for software transactional memory can be transformed to work with persistent memory. While correct, this transformation does not take into account differences between the persistent and volatile programming models. We show that fundamental properties of the data regions accessed by a persistent software transaction allow for a variety of optimizations not available in the volatile setting, and these lead to significant performance gains.

Emerging non-volatile memory (NVM) technologies are expected to become more prevalent in caches and main memory due to better scalability into smaller dimensions. Unfortunately, they come with the price of long write latency and high write energy. We propose to provide language supports to exploit the programmer's knowledge of the applications to reduce unnecessary writes to NVM-based caches and main memory. This will allow programmers to write code that will reduce the number of cache write backs that will not be needed in the future program execution. This can be done with "hints" that a programmer can add to their code to help the system software and hardware to identify regions of code that can be optimized. A study of the potential benefits of this proposed mechanism is performed on a sequence alignment tool used for bioinformatics. We found that up to 60% of write backs from an L2 cache and up to 10% of write backs from an L1 cache were not needed.

Language-level transactions are said to provide “atomicity,” implying that the order of operations within a transaction should be invisible to concurrent transactions and thus that independent operations within a transaction should be safe to execute in any order. In this article, we present a mechanism for dynamically reordering memory operations within a transaction so that read-modify-write operations on highly contended locations can be delayed until the very end of the transaction. When integrated with traditional transactional conflict detection mechanisms, our approach reduces aborts on hot memory locations, such as statistics counters, thereby improving throughput and reducing wasted work. We present three algorithms for delaying highly contended read-modify-write operations within transactions, and we evaluate their impact on throughput for eager and lazy transactional systems across multiple workloads. We also discuss complications that arise from the interaction between our mechanism and the need for strong language-level semantics, and we propose algorithmic extensions that prevent errors from occurring when accesses are aggressively reordered in a transactional memory implementation with weak semantics.

The Go language lacks built-in data structures that allow fine-grained concurrent access. In particular, its map data type, one of only two generic collections in Go, limits concurrency to the case where all operations are read-only; any mutation (insert, update, or remove) requires exclusive access to the entire map. The tight integration of this map into the Go language and runtime precludes its replacement with known scalable map implementations.This paper introduces the Interlocked Hash Table (IHT). The IHT is the result of language-driven data structure design: it requires minimal changes to the Go map API, supports the full range of operations available on the sequential Go map, and provides a path for the language to evolve to become more amenable to scalable computation over shared data structures. The IHT employs a novel optimistic locking protocol to avoid the risk of deadlock, and allows large critical sections that access a single IHT element, and can easily support multikey atomic operations. These features come at the cost of relaxed, though still straightforward, iteration semantics. In experimentation in both Java and Go, the IHT performs well, reaching up to 7× the performance of the state of the art in Go at 24 threads. In Java, the IHT performs on par with the best Java maps in the research literature, while providing iteration and other features absent from other maps.

Transactional Memory (TM) promises both to provide a scalable mechanism for synchronization in concurrent programs, and to offer ease-of-use benefits to programmers. The most straightforward use of TM in real-world programs is in the form of Transactional Lock Elision (TLE). In TLE, critical sections are attempted as transactions, with a fall-back to a lock if conflicts manifest. Thus TLE expects to improve scalability, but not ease of programming. Still, until TLE can deliver performance improvements, transactional styles of programming are unlikely to gain popularity.In this paper, we describe our experiences employing TLE in two real-world programs: the PBZip2 file compression tool, and the x265 video encoder/decoder. We discuss the obstacles we encountered, propose solutions to those obstacles, and introduce open challenges. In experiments using the GCC compiler's hardware and software support for TM, we observe that both are able to outperform the original lock-based code, potentially heralding the readiness of TM to be used more broadly for TLE, if not for truly transactional styles of programming.

In this paper, we introduce revocable reservations, a transactional memory mechanism to reserve locations in one transaction and check whether they are unchanged in a subsequent transaction without preventing reserved locations from being reclaimed in the interim. We describe several implementations of revocable reservations, and show how to use revocable reservations to implement lists and trees with a transactional analog to hand-over-hand locking. Our evaluation of these data structures shows that revocable reservations allow precise and immediate reclamation within transactional data structures, without sacrificing scalability or introducing excessive latency.

The addition of transactional memory (TM) support to existing languages provides the opportunity to create new soft- ware from scratch using transactions, and also to simplify or extend legacy code by replacing existing synchronization with language-level transactions. In this paper, we describe our experiences transactionalizing the memcached application through the use of the GCC implementation of the Draft C++ TM Specification. We present experiences and recommendations that we hope will guide the effort to integrate TM into languages, and that may also contribute to the growing collective knowledge about how programmers can begin to exploit TM in existing production-quality software.

The last decade has seen an explosion in new and innovative memory technologies. While certain technologies, like transactional memory, have seen adoption at the language level, others, such as sandboxed memory, scratchpad memory, and persistent memory, have not received any systematic programming language support. This is true even though the underlying compiler-level mechanisms for these mechanisms are similar. In this paper, we argue that programming languages must be enhanced to expose heterogeneous memory technologies to programmers, so that they can enjoy the benefits of those technologies and be able to reason about programs that use the advanced features of novel memory technologies. We sketch a language design that allows programmers to specify memory requirements and behaviors, for both data and code. We further describe how a compiler can support such a language and suggest hardware improvements that can improve efficiencies of heterogeneous memories.

Time-based transactional memories typically rely on a shared memory counter to ensure consistency. Unfortunately, such a counter can become a bottleneck. In this article, we identify properties of hardware cycle counters that allow their use in place of a shared memory counter. We then devise algorithms that exploit the x86 cycle counter to enable bottleneck-free transactional memory runtime systems. We also consider the impact of privatization safety and hardware ordering constraints on the correctness, performance, and generality of our algorithms.

Memcached and other in-memory distributed key-value stores play a critical role in large-scale web applications, by reducing traffic to persistent storage and providing an easy-to-access look-aside cache in which programmers can store arbitrary data. These caches typically have a narrow interface, consisting only of gets, sets, and compare-and-set. In the worst case, this interface can cause significant inefficiencies as clients get large data items, perform small changes, and then set the updated items back into the cache.We extend memcached to allow clients to execute code directly in the cache. An idealized evaluation on micro-benchmarks based on workload traces from a Cable/Internet service provider shows compelling performance, leading to a recommendation that further research be conducted to make in-cache fetch-and-phi safe and programmer-friendly, and that researchers consider whether a truly distributed cloud platform should make it easier for programmers to execute custom code at all levels of the software stack.

Few transactional memory implementations allow for condition synchronization among transactions. The problems are many, most notably the lack of consensus about a single appropriate linguistic construct, and the lack of mechanisms that are compatible with hardware transactional memory. In this paper, we introduce a broadly useful mechanism for supporting condition synchronization among transactions. Our mechanism supports a number of linguistic constructs for coordinating transactions, and does so without introducing overhead on in-flight hardware transactions. Experiments show that our mechanisms work well, and that the diversity of linguistic constructs allows programmers to chose the technique that is best suited to a particular application.

A significant obstacle to the acceptance of transactional memory (TM) in real-world parallel programs is the abundance of substantially different TM algorithms. Each TM algorithm appears well-suited to certain workload characteristics, but the best choice of algorithm is sensitive to program inputs, available cores, and program phases. Furthermore, operating system and hardware characteristics can affect which algorithm is best, with tradeoffs changing across iterations of a single ISA. This paper introduces methods for constructing policies to dynamically select the most appropriate TM algorithm based on static and dynamic information. We leverage intraprocedural static analysis to create a static profile of the application. We also introduce a low-overhead framework for dynamic profiling of a running transactional application. Armed with these complementary descriptions of a program's behavior, we present novel expert adaptivity policies as well as machine learning policies that are trained off-line using simple microbenchmarks. In our evaluation, we find that both the expert and learned policies provide better performance than any single TM algorithm across the entire STAMP benchmark suite. In addition, policies that combine expert and learned policies offer the best combination of performance, maintainability, and flexibility.

The availability of commercial hardware transactionalmemory (TM) systems has not yet been met with a rise in the numberof large-scale programs that use memory transactions explicitly. Asignificant impediment to the use of TM is the lack of tool support, specifically profilers that can identify and explain performance anomalies. In this paper, we introduce an end-to-end system that enables lowoverheadperformance profiling of large-scale transactional programs. We present algorithms and an implementation for Intel's Haswellprocessors. With our system, it is possible to record a transactionalprogram's execution with minimal overhead, and then replay it withina custom profiling tool to identify causes of contention and aborts, down to the granularity of individual memory accesses. Evaluationshows that our algorithms have low overhead, and our tools enableprogrammers to effectively explain performance anomalies.

Transactional memory (TM) is a promising synchronization mechanism for the next generation of multicore processors. Best-effort Hardware Transactional Memory (HTM) designs, such as Sun's prototype Rock processor and AMD's proposed Advanced Synchronization Facility (ASF), can efficiently execute many transactions, but abort in some cases due to various limitations. Hybrid TM systems can use a compatible software TM (STM) in such cases. We introduce a family of hybrid TMs built using the recent NOrec STM algorithm that, unlike existing hybrid approaches, provide both low overhead on hardware transactions and concurrent execution of hardware and software transactions. We evaluate implementations for Rock and ASF, exploring how the differing HTM designs affect optimization choices. Our investigation yields valuable input for designers of future best-effort HTMs.

Cediranib (4-[(4-fluoro-2-methyl-1 H -indol-5-yl)oxy]-6-methoxy-7-[3-(1-pyrrolidinyl)propoxy]quinazoline; RECENTIN™), a vascular endothelial growth factor (VEGF) tyrosine kinase inhibitor (TKI) of all three VEGF receptors, is currently in Phase III clinical trials for the first-line treatment of colorectal cancer and the treatment of recurrent glioblastoma. During its clinical development a unique human metabolite, an N + -glucuronide, was identified as a major circulating metabolite and one of the major metabolites excreted into faeces. Given the possibility of four sites for the conjugation of the glucuronic acid moiety, determination of the location of the conjugation site on cediranib was warranted. A small quantity of the N + -glucuronide metabolite of cediranib was initially generated using recombinant human uridine glucuronosyltransferase 1A4 (UGT1A4) enzymes. The metabolite generated was characterised by HPLC-UV and mass spectrometric (HPLC–MS n ) detection and confirmed by 1 H NMR spectroscopy. However, the exact site of conjugation could not be determined without generating more of the metabolite. Hence a subsequent biosynthetic scale-up experiment was devised to generate a sufficiently large quantity for full structural characterisation by 1 H NMR spectroscopy. The identity of the N + -glucuronide metabolite generated in the UGT1A4 scale-up experiment was confirmed by HPLC–MS n and displayed the same retention time, molecular mass and mass fragmentation data as the metabolite generated in previous human liver microsomal and hepatocyte incubations. 1 H NMR spectroscopy clearly showed the characteristic anomeric doublet at approximately 4.7 ppm, which, following irradiation during selective Rotating frame Overhauser Effect Spectroscopy (ROESY) experiments, enabled the site of glucuronidation to be confirmed on the pyrrolidine nitrogen. With the exception of the N + -glucuronide metabolite, all other human metabolites of cediranib were observed following incubation with hepatocytes from rat and cynomolgus monkey, the species used for toxicology testing of the drug [6] . As the N + -glucuronide was not detected in the preclinical species, it is suggested that its formation is more likely in human and higher primates (great apes), a finding widely supported in the literature.

With New York City confronting significant fiscal difficulties, its municipal unions and their members will be under enormous pressure to agree to significant concessions and possibly layoffs over the next several years. Their ability to fight these demands for concessions will be shaped to a great extent by the strategies that they adopted during the city's even more severe fiscal crisis of the mid 1970s—a pivotal moment in the city's and nation's histories. This earlier crisis, which marked an important early moment in the development of neoliberalism, led to thousands of layoffs of city workers and a three-year wage freeze as well as shifting the city's politics significantly to the right as the city's financial and political elite successfully took advantage of the crisis to advance their political and economic agenda. During that period, the municipal unions chose to not directly contest this rightward shift. Instead, they adopted a narrow interest-group strategy and accepted that they would need to work within the constraints of an emergent neoliberal regime predicated upon fiscal austerity and increasingly pro-business tax and economic development policies. This earlier decision continues to shape the municipal unions to this day and will likely hamper their ability to fight the present-day demands for concessions, much less lead them to work with other constituencies to build a progressive alternative to resolving the city's fiscal problems.

The in vitro metabolism of cediranib (4-[(4-fluoro-2-methyl-1H-indol-5-yl)oxy]-6-methoxy-7-[3-(1-pyrrolidinyl)propoxy]quinazoline), a vascular endothelial growth factor (VEGF) tyrosine kinase inhibitor (TKI) of all three VEGF receptors in late-stage development for the treatment of colorectal cancer and recurrent glioblastoma was investigated in hepatic proteins from preclinical species and humans using radiolabeled material. In human hepatocyte cultures, oxidative and conjugative metabolic pathways were identified, with pyrrolidine N(+)-glucuronidation being the major route. The primary oxidative pathways were di-and trioxidations and pyrrolidine N-oxidation. All metabolites with the exception of the N(+)-glucuronide metabolite were observed in rat and cynomolgus monkey hepatocyte preparations. Additional metabolism studies in liver microsomes from these or other preclinical species (CD-1 mouse, Han Wistar rat, Dunkin Hartley guinea pig, Göttingen mini-pig, New Zealand White rabbit, beagle dog, and cynomolgus and rhesus monkey) indicated that the N(+)-glucuronide metabolite was not formed in these additional species. Incubations with recombinant flavin-containing monooxygenase (FMO) and UDP-glucuronosyltransferase (UGT) enzymes and inhibition studies using the nonselective cytochrome P450 (P450) chemical inhibitor 1-aminobenzotriazole in human hepatocytes indicated that FMO1 and FMO3 contributed to cediranib N-oxidation, whereas UGT1A4 had a major role in cediranib N(+)-glucuronidation. P450 enzymes had only a minor role in the metabolism of cediranib. In conclusion, species differences in the formation of the N(+)-glucuronide metabolite of cediranib were observed. All other metabolites of cediranib found in humans were also detected in rat and cynomolgus monkey. Non-P450 enzymes are predominantly involved in the metabolism of cediranib, and this suggests that clinical drug interactions involving other coadministered drugs are unlikely.

Drawing inspiration from several previous projects, we present an ownership-record-free software transactional memory (STM) system that combines extremely low overhead with unusually clean semantics. While unlikely to scale to hundreds of active threads, this "NOrec" system offers many appealing features: very low fast-path latency--as low as any system we know of that admits concurrent updates; publication and privatization safety; livelock freedom; a small, constant amount of global metadata, and full compatibility with existing data structure layouts; no false conflicts due to hash collisions; compatibility with both managed and unmanaged languages, and both static and dynamic compilation; and easy acccommodation of closed nesting, inevitable (irrevocable) transactions, and starvation avoidance mechanisms. To the best of our knowledge, no extant STM system combines this set of features. While transactional memory for processors with hundreds of cores is likely to require hardware support, software implementations will be required for backward compatibility with current and near-future processors with 2--64 cores, as well as for fall-back in future machines when hardware resources are exhausted. Our experience suggests that NOrec may be an ideal candidate for such a software system. We also observe that it has considerable appeal for use within the operating system, and in systems that require both closed nesting and publication safety.