Tera-scale Computing

Runtime Environment for Tera-scale Platforms

NEW CONCURRENCY ABSTRACTION: TRANSACTIONAL MEMORY

Parallel programming poses many new challenges to the developer. A major one is synchronizing access to shared data between multiple threads. Traditionally, programmers have used locks for synchronization, but this method has well-known pitfalls such as deadlock and lack of composition. Transactional memory provides a new language construct that avoids the pitfalls of lock-based synchronization and eases concurrency control.

The McRT core services include a Transactional Memory (TM) library that supports the implementation of TM for C/C++ (unmanaged) and Java (managed). The TM library uses 2-phase locking to implement pessimistic write concurrency, and it uses versioning to implement optimistic read concurrency [27]. Every datum that may be accessed inside a transaction is associated with a transaction record—a pointer-sized word that mediates access to the shared datum. On a write, the TM library acquires exclusive ownership of the transaction record, performs an in-place update, and records the old value and the version number in an internal undo-log. On a read, the TM library records the version number of the transaction record (corresponding to the data address) in an internal read log. Before committing, the TM library validates a transaction by checking that the version numbers of the transaction records in the read set have not been changed. Upon committing, the lock is released and the version number is incremented. On an abort, the library uses the values in the undo-log to roll back the updates.

The TM library is also integrated with other runtime services such as memory management [16]. For example if a transaction allocates memory during its execution, the memory is automatically freed when the transaction aborts. Using a language-neutral API, we integrated the TM library with the Intel^® C/C++ compiler v10 and the StarJIT and JITtrino compilers for Java. These compilers take language-level transactional code blocks and insert calls to the appropriate runtime functions for every shared memory access inside the code block. This allows programmers to directly use TM rather than locks for concurrency control.

Figure 5: Transactions vs. locks on a hashmap
click image for larger view
 

Figure 5 compares the performance of locks and transactions on a hashmap data structure. It measures the time taken to complete a set of insert, delete, and update operations on lock-based and transactional versions of the hashmap [2] on a 16-way SMP machine. The transactional version of the hashmap was obtained by replacing the critical sections in the coarse-grain synchronization version with atomic sections. As expected, coarse-grained locking (Sync(coarse)) does not scale, but both the transactional and the fine-grain version scale comparably, even though the transactional version uses coarse-grain synchronization.

Figure 6: Transactions vs. locks on FMM (SPLASH2)
click image for larger view
 

Figure 6 shows a similar result on the FMM benchmark, which is part of the SPLASH2 suite. The transactional version of the benchmark was obtained by replacing the coarse-grain critical sections with transactions. Again, the transactional version scales as well as the fine-grain version even though it uses coarse-grain synchronization.

These results show that McRT allows a programmer to leverage the software engineering benefits of transactional memory, such as composability and coarse-grain reasoning, while getting the performance of fine-grain locking. We expect this to be a key enabler in promoting multithreaded programming for tera-scale platforms.

Back to Top