Kilo TM Correctness: ABA Tolerance and Validation-Commit Indivisibility
Wilson Wai Lun Fung, Inderpreet Singh, Tor M. Aamodt · 2012
Kilo TM is a hardware transactional memory (TM) system proposed for GPU architec-tures [1]. In Kilo TM, each transaction detects the existence of conflicts with other trans-actions via value-based conflict detection [2, 3]. With value-based conflict detection, each transaction buffers its writes to memory in a write-log and saves the values of its reads from memory in a read-log during execution. Upon its completion, the transaction compares the saved values of its read-set with the latest values in memory before it commits. We refer this comparison as validation. Any difference between the saved value and the latest value in memory indicates the existence of a conflict. Kilo TM uses value-based conflict detection because it avoids direct communication between transactions, and it does not require any essential on-chip storage (Kilo TM uses on-chip storage to improve commit parallelism). More details regarding the design of Kilo TM are available in our paper for the 44th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 2011) [1]. A general concern for the correctness of value-based conflict detection is the possibility of subtle bugs due to the ABA problem. We show that value-based conflict detection can tolerate the ABA problem, and like NOrec [3], we can create a logical order for Kilo TM in