Improving Mode Transitioning in Phased Transactional Memory Implementations

Transactional memory (TM) is a programming abstraction developed for shared memory architectures, which allows the user to write parallel programs without having to worry about concurrent access to shared objects. This programming abstraction is specially designed for programs with irregular memory accesses and data-driven behavior, for which developing parallel implementations using blocking concurrency control mechanisms such as locks is complicated, making them prone to logic errors such as deadlocks or livelocks. Various implementations of transactional memory have been developed. These implementations can use hardware available in modern computer architecture, or software runtimes that provide all the concurrent synchronization needed. Both software and hardware implementations have a series of benefits and drawbacks that make them suboptimal as a single solution for all applications in general. Phased Transactional Memory (Phased TM), is a TM implementation that seeks to exploit the benefits of both HW and SW implementations by executing transactions in HW/SW phases (a.k.a. modes), selected according to the characteristics of each transaction. A particular problem of Phased TM implementations is the decision-making process that is required to decide (at runtime) the execution mode and the proper moment to switch to another mode. This Thesis proposes novel decision-making mechanisms that not only take advantage of the HW (i.e. fast-path mode) but also seek to reduce the number of mode transitions thus avoiding unnecessary overheads. For this, two transitioning mechanisms were developed considering a three-mode Phased TM implementation: Hardware, Software, and Global Lock modes. The first implementation presented in this Thesis, Graph-oriented TM (GoTM) was inspired by the data-driven and monotonically convergent behavior of graph applications. It uses a commit throughput measurement of each execution mode (HW or SW) as the main metric, to accelerate typical applications in large-scale graph analytics. The second mechanism, Commit throughput TM (CTM), elaborates further on the commit throughput metric, to develop a general solution that aims to avoid over-fitting. CTM is based on two new proposed metrics: (a) a relative commit throughput metric that compares the program performance evolution (increase or decrease) at each execution mode; and (b) a (simulated) cache capacity evaluation that estimates the speculative storage requirement of currently executing transactions, which is used to avoid persistent capacity-related aborts. Our experimental results, obtained using applications for large-scale graph analytics and the STAMP benchmark show that Phased TM is a mechanism that improves performance and scalability of various real-life applications, provided it offers efficient mode transitioning mechanisms.