Compiler and Runtime Techniques for Software Transactional Memory in Partitioned Global Address Space Languages and Runtime Libraries

The Partitioned Global Address Space (PGAS) model has emerged as a promising abstraction for programming large-scale systems. In PGAS, threads share a common heap address space, which may in reality be partitioned and distributed across independent memories. Concurrency control mechanisms are thus required to ensure threads see each other's updates in a consistent manner. The real challenge in building such mechanisms is that the memory locations that need to be updated in an atomic fashion may reside in different memory partitions. In this dissertation, we develop solutions based on Software-based Transactional Memory (STM) mechanisms to address the programmability and performance aspects of this challenging problem. STM mechanisms primarily guarantee that transactions, i.e. code sequences that access shared state, either execute as a single atomic operation or retry their operation in case such guarantees cannot be provided.

This dissertation makes the following contributions: First, we showcase the programmability benefits of providing language support for atomic transactions over lock-based approaches. Second, we develop first-of-its-kind compiler techniques for mapping these high-level language constructs to low-level STM designs. Third, we develop STM runtime implementations that not only guarantee correctness for concurrently executing transactions, but does so in an efficient manner. For instance, we demonstrate for the first time how STM procedures can be implemented in a non-blocking manner, and use them to overlap computation and communication within a transaction. In general, we demonstrate the feasibility of these techniques by implementing them in Chapel, a parallel programming language being developed by Cray Inc. as part of DARPA's HPCS program, and GASNet, a runtime library that implements the PGAS abstraction. Overall, we show that STM implementations can be scaled to hundreds (if not thousands) of nodes executing tens of thousands of threads, while exhibiting performance that exceeds, if not just matches, the performance of lock-based approaches.