CAR-STM: Scheduling-Based Collision Avoidance and Resolution for Software Transactional Memory
- Project number: 202-08-01
- Students: Adi Suissa
- Supervisor: Danny Hendler, Shlomi Dolev
Transactional memory (TM) is a key concurrent programming abstraction for multiprocessors. Several software-based transactional memory (STM) implementations have been developed in recent years. All STM implementations must guarantee transaction atomicity but different STM implementations may provide different progress guarantees. In order to ensure progress, an STM implementation must resolve transaction conflicts. This is done either by the implementation itself or by delegating conflict resolution to a separate contention manager module that tries to resolve transaction collisions once they are detected.
This work studies a novel approach for increasing STM efficiency: rather than handle collisions post factum, we propose proactive collision reduction by pre-assigning transactions that are more likely to collide to the same core. We present CAR-STM, a scheduling-based mechanism for STM collision avoidance and resolution, that can be incorporated into existing STM implementations. In addition to proactive collision avoidance that is based on application-specific hints, CAR-STM's transaction scheduling supports novel and highly efficient contention managers that resolves conflicts by serializing the execution of colliding transactions.
We have incorporated CAR-STM into the University of Rochester's STM (RSTM) and compared the performance of the new implementation with that of the original RSTM by using STMBench7. Our results show that the new implementation provides orders-of-magnitude reduction of execution times and improved throughput for almost all concurrency levels. Additionally, since CAR-STM greatly reduces the unpredictable influence of operating-system scheduling on STM performance, the new implementation provides much more stable performance. In contrast, the performance of the original RSTM implementation on STMBench7 workloads exhibits extremely high variance.
