Lower bounds for Transactional memory

Abstract

Transactional memory allows the user to declare sequences of instructions as speculative transactions that can either commit or abort. If a transaction commits, it appears to be executed sequentially, so that the committed transactions constitute a correct sequential execution. If a transaction aborts, none of its update operations can aect other transactions. The TM implementation endeavors to execute these instructions in a manner that eciently utilizes the concurrent computing facilities provided by multicore architectures.
The TM abstraction, in its original manifestation, extended the processor’s instruction set with instructions to indicate which memory accesses must be transactional. Most popular TM designs, subsequent to the original proposal have implemented all the functionality in software. More recently, processors have included hardware extensions to support small transactions. Hardware transactions may be spuriously aborted due to several reasons: cache capacity overflow, interrupts etc. This has led to proposals for hybrid TMs in which the fast, but potentially unreliable hardware transactions are complemented with slower, but more reliable software transactions.
The complexity of TM implementations, whether realized in hardware
or software, is characterized by several measures: ordering semantics for
transactions, conditions under which transactions must terminate, conditions under which transactions must commit/abort, bound on the number of versions that can be maintained, choice of the complexity metric and complexity of read-only or updating transactions as well as a multitude of other implementation strategies. In this work, we survey known complexity bounds for implementing TM as a shared object and the implicit assumptions underlying these results.