Thesis (Ph. D.)--University of Rochester. Department of Computer Science, 2015.
Multithreaded programming requires synchronization, to coordinate access to shared resources. As more and more processor cores become available on a single machine, synchronization tends to be the performance bottleneck of many multithreaded programs. This thesis focuses on two important synchronization scenarios: lock-based critical sections and transactional atomic blocks.
Since speculation is a well-known means of increasing parallelism among concurrent executions that are usually but not always independent, this thesis first explores the manual addition of speculation to lock-based critical sections (in concurrent data structures). With simple language extensions accompanied by compiler assistance, a technique which we refer to as CSpec, the programmer can exploit high-level program knowledge to move speculative work out of lock-based critical sections, thereby improving scalability while still maintaining correctness.
Speculation is also a major approach to improved parallelism in transactional memory systems. Frequent failures of speculative execution, however, may render the technique unprofitable. In recently emerged best-effort hardware transactional memory, speculation fails mainly due to two reasons: hardware overflow and data conflicts. In this thesis we develop a programming technique and compiler support, ParT, to reduce the duration and memory footprint of hardware transactions, leading to lower abort rates while preserving deadlock-free composability. To reduce the incidence of conflict, we propose an automatic, high-level mechanism,
Staggered Transactions, that uses advisory locks to serialize (just) the portions of the transactions in which conflicting accesses occur.
In all proposed techniques, compiler assistance is essential to maintaining ease of programming. We thus conclude that compiler assistance can significantly improve speculation in multithreaded systems.
