Hardware Support for Relaxed Concurrency Support In Transactional Memory

Serializability Order Number TM (SONTM) is a Hardware Transactional Memory (HTM) design that replicates the well-known interval-based OCC which was originally proposed for software implementation. Classical Backward Optimistic Concurrency Control (BOCC) protocols introduces false aborts, because they assume read/write conflict as long as the read set of a reading transaction has a non-empty intersection with write sets of transactions whose write phase overlaps with its read phase. In fact, if the reading transaction only reads values after the committing transactions have updated them, the schedule should be serializable. In classical OCC, however, this will be rejected, because the protocol does not track the actual ordering of reads and writes on data items, and always assumes the worst for safety if the ordering cannot be inferred from the global commit counter. Second, classical BOCC serializes transactions in the order that they enter the validation phase. If the directions of actual read/write dependencies differ from the order that transactions enter validation, then one of the transactions should be aborted to avoid cyclic dependencies. This may introduce many artificial aborts, in which case if transactions enter validation phase in a different order, then all of them can commit successfully.

Interval-based OCC was proposed to solve these two problems. In an interval-based OCC design, each data item is assigned two timestamps: a write timestamp (WTS) which records the last committed transaction’s ID that wrote this item; A read timestamp (RTS) which records the last committed transaction’s ID that read this item. Each transaction has a lower bound (LB) and upper bound (UB), which defines its valid timestamp range that allows it to serialize with committed transactions. Active transactions serialize with committed transactions using the RTS and WTS of data items when they are read and globally written. Transactions read the RTS of read data items during the read phase, and the RTS as well as WTS of written data items during the validation phase. It then updates its own lower bound to be the maximum of RTS in the read set and WTS in the write set. The validation succeeds if LB is strictly smaller than UB after validation is performed. A commit timestamp, which is also the transaction’s ID, is chosen from the interval defined by LB and UB. After the interval is chosen, the committing transaction broadcasts the commit decision as well as the read and write set to all active transactions. On receiving such a commit broadcast, active transactions must set their UB as the broadcasted transaction ID, if they have one or more uncommitted reads that are also in the committed write set, or set LB as the transaction ID if they have one or more uncommitted writes that are also in the committed read and write set. After each of these broadcast, transactions always check whether a violation happens by comparing LB and UP. The last step of commit is to update RTS and WTS of data items in the read and write set. The write set is also flushed back to global storage.

SONTM essentially integrates the idea of interval based OCC into the design of transactional memory. Each processor is extended with two registers: one for holding the lower bound, and another for upper. The lower bound register is initialized to zero, and the upper bound register to the maximum possible value. Read and write sets are kept as bloom filters. Write timestamps of every cache line in the system is kept in a hash table, which is stored in the main memory. The hash table is allocated and managed by system software, and is located on a known location in the virtual address space (such that each process in the system can have their own transaction context). Processors retrieve and update the timestamps of any data item in the main memory by calculating its offset into the hash table, and then read or write the timestamp entry. The hash table may introduce aliasing, where multiple addresses are mapped to the same entry and hence share the same write timestamp. We argue, however, that aliasing of write timestamps do not affect correctness as long as values smaller than the current one stored in the hash table are ignored during an update. False positives on conflict detection are possible, which only affects performance. According to the benchmark presented in the paper, though, the affect is negligible.

Read timestamps, however, are stored in a different way. The reason that read timestamps are not stored as a centralized structure as write timestamps is that this would require transactions to update the RTS of every item in the read set at commit time. Since for most transactions, the read set is usually much larger than the write set, this may incur noticeable overhead. The read timestamps are stored by pushing the read set bloom filter of committed transactions into a processor local stack. The bloom filter is stored with the ID of the committed transaction. The stack has only limited capacity, so when it is about to overflow, the bottommost entry is merged with the next entry, and the ID of it is updated to the larger between the two. Transactions must acquire the read timestamp of data items by broadcasting requests to all processors. On receiving such a request, the processor searches the stack in any order, testing the bloom filter with the address, and returns the largest ID of the entry among all hits. Similar to WTS aliasing, this mechanism may return inaccurate RTS. This, however, does not affect correctness, as the returned RTS is always larger than or equal to the actual RTS. This will cause some false aborts, degrading performance, but will never result in non-serializable scheduls. Broadcasting requests for RTS may seem inefficient, but as we shall see later, this only happens during the validation phase, where the entire write set is known, and bulk requests can be used to reduce the communication overhead.

The last component of SONTM is three dependency vectors. They record potential dependencies between active transactions. The direction of the dependency can only be determined after one of the two transactions in the potential dependency commits. At this point, the committed transaction broadcasts its ID in some special way, and the active transaction updates its LB or UB accordingly. The three vectors are: WAR vector, WAW vector and RAW vector. The width of these vectors is the number of processors minus one. If position i of a vector X (X = RAW/WAW/WAR) is set, then we know that the current processor has a potential dependency of type X with processor i, and the current processor is the destination of the dependency. Dependency vectors are marked when a coherence request hits a processor, and the read/write set bloom filter signals a possible conflict. The responding processor replies with requested data, together with a NACK flag, indicating a potential dependency. On receiving the response, the requesting processor marks the corresponding bit in the vector. Note that SONTM decouples read/write set maintenance from cache line states. A cache line can be evicted from the cache without aborting the transaction. A evicted cache line that has been transactionally read and written must keep its bit in the directory as a sticky state. Later requests to the line will always hit processors that have speculatively read or written them. The usage of sticky states is first introduced by LogTM, and requires slight modification to the directory implementation.

SONTM maintains serializability with committed transactions by reading the WTS at the time of speculative reads, and reading both WTS and RTS at the time of validation. Validation does not check the validity of the read set, because read serialiation has been done at the time the data item is acquired. This is precisely what is described for interval-based OCC, and we do not cover it in much details. Serializability with active transactions are performed during validation. The committing processor first chooses a transaction ID from the interval defined by LB and UB. In the paper it is suggested that the ID should be chosen as (UB - 1), but in theory any number is fine. What happens next is to notify other processors of the commit event, and urge them to update their LB and UB accordingly. There are six cases to consider: (1) RAW and reader commits. The writer should update its LB, because the content of the write has not been published yet. The reader only reads old value, and should be serialized before the writer. (2) WAW and later writer commits. The first writer should update its LB also, because when it commits it will overwrite a committed value. (3) WAR and the writer commits. The reader should update its UB, because when it commits, the value it has read has been overwritten. The reader must therefore be serialized before the writer. (4) RAW and the writer commits. The reader should update its UB for the same reason as in (3). (5) WAW and the earlier writer commits. The later writer should update its LB for the same reason as in (2). (6) WAR and the reader commits. The writer should update its LB for the same reason as in (1). The major difficulty of sending notifications is that procrssors only maintain the dependency vector when it is the destination of the dependency. In SONTM, a committing processor knows whom to notify for case (1), (2) and (3), so it just include the identities of the source processor in the broadcast message. For case (4), (5) and (6), the committing processor has no idea whom will be the destination. It therefore also includes identiti into the message. Processors receiving the message checks whether the committing processor is in one or more of its vectors. If it is the case, then the receiving processor updates the LB and UB registers accordingly. Commit operations in SONTM are serialized using a global token. Processors must obtain and release the token before and after the commit operation. After validation and commit notification, the committing processor writes back dirty values from the write log, and also updates the write timestamp for items in the log. Race conditions could happen if another processor attempts to read the data item and/or the WTS while the committing processor is performing write back. Since commit phases are generally believed to be short, it might be just fine to abort the transaction if it happens to collide with a committing transaction. This can be easily detected by checking the owner of the commit token.