Browsing by Subject "Transactional memory"

Now showing 1 - 5 of 5

Large-scale transactional execution of FPGA-accelerated irregular applications
(2017-05-03) Ma, Xiaoyu, Ph. D.; Chiou, Derek; Pingali, Keshav; Gerstlauer, Andreas; Erez, Mattan; Hofstee, Harm Peter
Irregular workloads are programs organized around pointer-based data structures such as graphs. They are widely used in many fields such as computer/human network analysis, machine learning, data mining, graphics, electronic design automation, and so on. Many irregular applications have massive data-level parallelism because they iterate over a large number of graph nodes or edges using the same operators. This dissertation proposes large-scale transactional execution, as well as an architecture to achieve this approach. We apply this approach to irregular applications by executing a large number of graph operations concurrently and as transactions to deal with potential conflicts. Before this work, large-scale transactional execution was generally considered impractical because doing so might incur too many conflicts that would negate the potential benefits of the parallelization. We propose a set of techniques to address the high conflict issue and argue that given the large size and topology of many modern graphs, large-scale, multi-threaded, transactional execution can provide performance, energy efficiency, and programability benefits. We present challenges of realizing such an architecture, including the requirement of scalable conflict detection, livelock avoidance and transactional state overflow handling, and propose solutions. While the proposed techniques are also applicable to CPUs and ASICs, we focus on using FPGAs and implement the proposed architecture as a synthesizable FPGA RTL design. We compare our implementation in performance and energy efficiency against an Intel Haswell-based baseline platform. In addition, we perform an extensive study of various micro-architectural design choices in large-scale transactional execution architecture and evaluate their impact on performance. Finally, we explore the use of fine-grained locks to replace transactions to further improve performance.
Operating system transactions
(2010-12) Porter, Donald E.; Witchel, Emmett; Alvisi, Lorenzo; McKinley, Kathryn S.; Shmatikov, Vitaly; Swift, Michael
Applications must be able to synchronize accesses to operating system (OS) resources in order to ensure correctness in the face of concurrency and system failures. This thesis proposes system transactions, with which the programmer specifies atomic updates to heterogeneous system resources and the OS guarantees atomicity, consistency, isolation, and durability (ACID). This thesis provides a model for system transactions as a concurrency control mechanism. System transactions efficiently and cleanly solve long-standing concurrency problems that are difficult to address with other techniques. For example, malicious users can exploit race conditions between distinct system calls in privileged applications, gaining administrative access to a system. Programmers can eliminate these vulnerabilities by eliminating these race conditions with system transactions. Similarly, failed software installations can leave a system unusable. System transactions can roll back an unsuccessful software installation without disturbing concurrent, independent updates to the file system. This thesis describes the design and implementation of TxOS, a variant of Linux 2.6.22 that implements system transactions. The thesis contributes new implementation techniques that yield fast, serializable transactions with strong isolation and fairness between system transactions and non-transactional activity. Using system transactions, programmers can build applications with better performance or stronger correctness guarantees from simpler code. For instance, wrapping an installation of OpenSSH in a system transaction guarantees that a failed installation will be rolled back completely. These atomicity properties are provided by the OS, requiring no modification to the installer itself and adding only 10% performance overhead. The prototype implementation of system transactions also minimizes non-transactional overheads. For instance, a non-transactional compilation of Linux incurs negligible (less than 2%) overhead on TxOS. Finally, this thesis describes a new lock-free linked list algorithm, called OLF, for optimistic, lock-free lists. OLF addresses key limitations of prior algorithms, which sacrifice functionality for performance. Prior lock-free list algorithms can safely insert or delete a single item, but cannot atomically compose multiple operations (e.g., atomically move an item between two lists). OLF provides both arbitrary composition of list operations as well as performance scalability close to previous lock-free list designs. OLF also removes previous requirements for dynamic memory allocation and garbage collection of list nodes, making it suitable for low-level system software, such as the Linux kernel. We replace lists in the Linux kernel's directory cache with OLF lists, which currently requires a coarse-grained lock to ensure invariants across multiple lists. OLF lists in the Linux kernel improve performance of a filesystem metadata microbenchmark by 3x over unmodified Linux at 8 CPUs. The TxOS prototype demonstrates that a mature OS running on commodity hardware can provide system transactions at a reasonable performance cost. As a practical OS abstraction for application developers, system transactions facilitate writing correct application code in the presence of concurrency and system failures. The OLF algorithm demonstrates that application developers can have both the functionality of locks and the performance scalability of a lock-free linked list.
Orchestration and atomicity
(2013-08) Kitchin, David Wilson; Misra, Jayadev; Cook, William Randall
This dissertation presents the concurrent programming language Ora, an extension of the Orc orchestration language with the capability to execute transactions. A new formal definition of transactions is given, in terms of two complementary properties: atomicity and coatomicity. These properties are described in terms of a partial order of events, rather than as properties of a totally ordered program trace. Atomicity and coatomicity are ensured in Ora programs by a novel algorithm for multiversion concurrency control.
Seven aspects of software transactional memory
(2009-12) Hughes, Thomas Francis; Julien, Christine, D. Sc.; Julien, Christine; Khurshid, Sarfraz
This paper explores different aspects of transactional memory to identify general patterns and analyze what direction software transactional memory research may be headed. Hybrid hardware-accelerated transactional memory is shown as a better long-term solution than purely software or hardware transactional memory, based on performance and the fundamental issue of software complexity. The appendix provides a chronologically ordered summary of significant transactional memory implementations and transactional memory specific benchmarks.
Transactional memory concurrency : new models and systems
(2009-08) Ramadan, Hany E.; Witchel, Emmett
Transactional memory (TM) aims to bring the benefits of ACID transactions to the volatile world of program synchronization. Architectural trends are making software transactions more appealing, as more programmers struggle with the problems of locks as they exploit multi-core processors. This thesis applies TM, which until recently has been restricted to small benchmarks, to a large, real-life system: the Linux operating system kernel. I describe TxLinux, a version of Linux, which is the first OS to use transactional memory for synchronization. TxLinux runs on MetaTM, a simulator co-designed with TxLinux, which models an x86-based Hardware Transactional Memory (HTM) system. The TxLinux/MetaTM effort yields a characterization of real-life OS transactions, exposes previously unconsidered complications (including interaction with interrupts and stack memory) and allows sensitivity studies of various TM microarchitectural parameters. It also provides a flexible platform for future OS, TM and architecture research. Next, I examine ways to increase concurrency by investigating the factors that inhibit concurrency in existing TM models and systems. These include avoidable implementation limitations, overly restrictive serialization models, and inexpressive APIs. After examining the nature of each limitation, I propose a solution for each one. I postulate that the conventional wisdom that every transaction is "for itself" and primarily relates to other transactions by conflicting with them, is a pervasive misperception. This thesis aims to demonstrate that there are other ways of thinking about the relation of one transaction to another. I present three different transaction models to show how (i) co-existence, (ii) cooperation, and (iii) coordination, can each solve important problems facing TM programmers today. Co-existence of multiple transactions on the same processor is enabled using the suspended transactions model. This model, used by TxLinux, can reduce aborts and removes transaction length limitations imposed by interrupts. Cooperation of transactions that access the same data, using the dependence-aware transactions model, can transparently turn transaction aborts into commits. Drawing on serializability theory and notions of spheres of control (which predate ACID transactions), this model is able to accept more execution schedules than any existing TM design. Lastly, the coordination of multiple transactions in the coordinated sibling transactions model, provides programmers a simple and unified way of expressing intratransaction parallelism. This helps move transactions beyond being a drop-in replacement for locks (SLE-style) to instead helping programmers find more parallel work within their programs (both in speculative and non-speculative forms). All three models aim at increasing concurrency, while shifting complexity away from the programmer and into the TM system. I evaluate all three models, using either the MetaTM HTM, or one of the several software (STM) systems this thesis also develops.