Log-based transactional memory

Transactional memory gives programmers the ability to declare the synchronization properties their programs need, without requiring that they develop a mechanism (e.g., a locking scheme) to enforce these properties. Ideally, an implementation of transactional memory should: (1) make the expected common case (short transactions that commit) fast; (2) defer rare and difficult-to-implement cases to software; (3) allow transactions of any size and duration; and, (4) allow programmers to nest transactions to arbitrary depths. Log-Based Transactional Memory (LogTM) is framework for transactional memory that combines software-based version management (with limited hardware support) and conservative hardware conflict detection to support arbitrary-size transactions with limited hardware. Version management requires maintaining multiple versions of data values: old values, the values at the start of the transaction, and new values, which are generated inside a transaction. Any memory location modified in a transaction will hold its new value if the transaction commits, and its old value if the transaction aborts. LogTM performs version management by eagerly updating memory in place during transactions and saving old values in a per-thread transaction log. No further action is needed to commit a transaction since new values are kept in place. To abort a transaction, LogTM restores saved values from the log. Fortunately, (for most workloads) aborts are rare. Because aborts are infrequent, LogTM can reduce hardware complexity by performing aborts in software without degrading performance. Conflict detection identifies overlaps between the write set of each transaction with the read set or write set of other concurrent transactions. Like other hardware transactional memory systems, LogTM detects conflicts on cached data by augmenting the cache coherence mechanism, e.g., by adding a read (R) and write (W) bit to each cache line. LogTM implementations extend this mechanism (e.g., with sticky states, which enable the directory to continue to send coherence messages to a processor for a blocks it has evicted from its cache) so that processors can conservatively detect conflicts even for blocks not present in the cache.