Transactional Memory (TM) is among the most promising techniques for simplifying the development of correct parallel programs. Dozens of different techniques have been developed to implement TM, with each appearing ideally suited to some combination of application and hardware characteristics. Unfortunately, when the wrong algorithm is chosen for a workload, pathologically bad performance can result.
The problem is particularly acute in programs whose behavior varies over time: the best TM implementation for one phase of execution may be unacceptable during another phase. This research will create new algorithms for dynamic adaptivity, so that the implementation of TM can be changed repeatedly during program execution, thereby maximizing performance during each program phase.
The research will explore both mechanism and policy. It will create new algorithms and heuristics for selecting TM implementations. It will also model the behavior of a wide array of TM algorithms and workloads on multiple architectures, in order to create a knowledge base suitable for guiding adaptivity. To achieve maximum performance, the research will consider a broad set of characteristics, to include TM implementation details, bottlenecks, and overheads; risk of pathology; properties of the hardware environment; and workload requirements such as frequency of inter-thread synchronization, I/O, and nontransactional access to shared data. This research will also develop novel static analyses and a dynamic optimization framework to avoid any overhead while providing robust, adaptive TM. Prototypes and source code will be distributed as open-source software.
This project entailed a comprehensive study of algorithms and mechanisms for adapting the behavior of transactional programs in response to program behavior, as well as adaptation of general-purpose transactional systems to optimize for specific platform characteristics, such as CPU type, number of cores, and operating system. Among the most significant outcomes were the development of an adaptive framework for transactional memory (TM) algorithms, which was integrated into the open-source RSTM library; the creation of architecture-specific TM algorithms for the ARM and x86 architectures; the creation of a transactional memcached application,which serves both as a benchmark and a vehicle for understanding the emerging specification for adding TM to C++; the release of new TM libraries for the GCC compiler, and the creation of several novel lock-free and wait-free data structures, useful both within TM implementations, and as stand-alone objects. During the course of the research, 15 research papers were published, to include 2 journal papers and 8 papers at top-tier conferences. The software developed in support of those papers was released as open-source,and is being used by researchers worldwide. Three Ph.D. students and three masters students were directly supported during portions of their education through this research. The award provided a catalyst for collaborations with The University of Rochester, The University of Delaware, AMD, TU-Dresden, and Oracle. The award also supported numerous outreach activities that aim to broaden the STEM pipelineby introducing elementary school children (grades K-5) to topics in computer science.
