Software Transactional Memory Validation - Time and Space Considerations

摘要

With single thread performance hitting the power wall, hardware ar chitects have turned to chip-level multiprocessing to increase processor perfor mance. As a result, issues related to the construction of scalable and reliable multi-threaded applications have become increasingly important. One of the most pressing problems in concurrent programming has been synchronizing accesses to shared data among multiple concurrent threads. Traditionally, accesses to shared memory have been synchronized using lock based techniques resulting in scalability, composability and safety problems. Recently, transactional memory has been shown to eliminate many problems as sociated with lock-based synchronization, and transactional constructs have been added to languages to facilitate programming with transactions. Hardware trans actional memory (HTM) is at this point readily available only in the simulated environments. Furthermore, some of the TM systems relying on the hardware support are hybrid solutions that require TM operations to be supported in soft ware as well. Therefore, providing an efficient software transactional memory (STM) implementation has been an important area of research. One of the largest overheads in an STM implementation is incurred in the validation procedure (that is, in ensuring correctness of transactional read operations). This paper presents novel solutions to reduce the validation overhead in an STM. We first present a validation algorithm that is linear in the number of read operations executed by a transaction, and yet does not add any overhead to trans actional reads and writes. We then present an algorithm that uses bitmaps to en code information about transactional operations and further reduces both the time and space overheads related to validation. We evaluate the effectiveness of both algorithms in the context of a state-of-the-art STM implementation.