Reading 7. HTM. Compare&Swap decomposition

Jensen,Hagensen, and Broughton, UCRL 1987: support for optimistic synchronization using single memory location.

Complex compare&swap instruction can be splitted into simplier parts:

• sync load. One memory location are loaded into special register (called xa-address), that indicates the processor requires exclusive access to this address, and loads the accessed data into a general register.
• sync store. Stores data to previously saved address in xa-address if no other processor stored anything there (i.e. no conflict occurred) or conflict resolution decided to allow write by this processor.
• sync clear. Clears xa-address.

A simple locking can be implemented in those instructions as follows:

// if (lock == 0) { lock = ProcessID; } % atomically
// else goto LockHeld...                % lock was held
Retry:
sync_load R10, lock           ; declare exclusive intent
jump_q .neq (R10,0), LockHeld ; test for zero
sync_clear                    ; lock non-zero, hence abort
load R10, ProcessID           ; prepare to update lock
sync_store R10, lock          ; update lock if not aborted
goto Retry                    ; try the update again
MyLock:                         ; got the lock

Implementation

sync_store instruction broadcasts write operation on all processors thus detecting conflicts with other processors having same xa-address. If such conflict detected, one processor clears own xa-address or aborts store operation (depends on conflict resolution scheme).

Real-world usage

MIPS, Alpha, PowerPC implemented variations to this scheme

Classification

Strong or weak isolation		Strong
Transaction granularity		Cache line
Direct or deferred update		Conditional direct store (single word)
Concurrency control		Optimistic (single word)
Conflict detection		N/A
Inconsistent reads		None
Conflict resolution		Processor id or first to request ownership
Nested transaction		N/A

Sources

• J.R. Larus, R.Rajwar Transactional Memory, 4.3.3
• E. H. Jensen, G. W. Hagensen and J. M. Broughton, “A new approach to exclusive data access in shared memory multiprocessors,” Lawrence Livermore National Laboratory, Technical Report UCRL-97663, Nov. 1987.