SCC4TM
Speculative Concurrency Control for Transactional Memory
| Start | 1. September 2011 |
| End | 31. December 2014 |
| Financing | Hamburg University of Technology |
Project Description
In recent years multi-core architectures penetrated the PC-market. This influenced the way applications are programmed. Increasingly, programs concurrently execute tasks in separate execution threads. To avoid inconsistencies the access to common data must be controlled in this case. One way to do this is to grant exclusive access to the data to a single execution thread. Thus, other execution threads must wait to get access granted, even if they only operate on data not used by the currently executing thread. Alternatively the data space can be partitioned and executing threads only get exclusive access to the partitions they work on. This increases the degree of concurrency but bears the danger of deadlocks among threads. As an example consider the case that execution thread A has exclusive access to data a and also needs access to data b currently held by execution thread B. If B is waiting to get access to a then a deadlock exists and both threads wait forever. A technology to free programmers from the burden of requesting and releasing access to data is transactional memory (TM). Access to data is automatically regulated guaranteeing data consistency with a mechanism called concurrency control (CC). Access to shared data is organized into so called transactions. If the CC detects an inconsistency or a deadlock during the execution of a transaction, all changes made by the transaction up to this point are undone. This action is called Rollback. As a negative side effect, it can happen that actions that not caused inconsistencies or deadlocks are also discarded. To avoid this from happening there exist proposals to subdivide a transaction in small chunks, to allow a roll back closer to the point at which the conflict arose. Unfortunately these proposals place the burden on the programmer and increase the complexity of concurrent programming. Furthermore, the complexity of the concurrency control is increased leading to a higher processing time that is no longer available to the application. The goal of this project is to improve concurrency control for TM by making use of the available additional cores. Execution threads will be split into several such threads, each executed by a separate core. Several solutions will be explored, such as to swap out the task of CC into a separate thread. Another approach is to apply speculative execution, a technique known from pipelined processors, to the level of threads in TM.
Publications
Holger Machens and Volker Turau. Opacity of Memory Management in Software Transactional Memory. Technical Report Report arXiv:1308.2881, arXiv.org e-Print Archive - Computing Research Repository (CoRR), Cornell University, August 2013.
@TechReport{Telematik_MT_2013_OPACITY_of_MM_in_TM,
author = {Holger Machens and Volker Turau},
title = {Opacity of Memory Management in Software Transactional Memory},
number = {Report arXiv:1308.2881},
institution = {arXiv.org e-Print Archive - Computing Research Repository (CoRR)},
address = {Cornell University},
month = aug,
year = 2013,
}
Abstract:
Opacity of Transactional Memory is proposed to be established by incremental validation. Quiescence in terms of epoch-based memory reclamation is applied to deal with doomed transactions causing memory access violations. This method unfortunately involves increased memory consumption and does not cover reclamations outside of transactions. This paper introduces a different method which combines incremental validation with elements of sandboxing to solve these issues.