Paper Info
Title
Testing implementations of transactional memory
Abstract
Transactional memory is an attractive design concept for scalable multiprocessors because it offers efficient lock-free synchronization and greatly simplifies parallel software. Given the subtle issues involved with concurrency and atomicity, however, it is important that transactional memory systems be carefully designed and aggressively tested to ensure their correctness. In this paper, we propose an axiomatic framework to model the formal specification of a realistic transactional memory system which may contain a mix of transactional and non-transactional operations. Using this framework and extensions to analysis algorithms originally developed for checking traditional memory consistency, we show that the widely practiced pseudo-random testing methodology can be effectively applied to transactional memory systems. Our testing methodology was successful in finding previously unknown bugs in the implementation of TCC, a transactional memory system. We study two flavors of the underlying analysis algorithm, one incomplete and the other complete, and show that the complete algorithm while being theoretically intractable is very efficient in practice.
Year
DOI
Venue
2006
10.1145/1152154.1152177
Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques
Keywords
Field
DocType
testing,verification,random testing,specification,transactional memory,formal specification
Atomicity,Software transactional memory,Commitment ordering,Programming language,Concurrency,Computer science,Parallel computing,Correctness,Real-time computing,Formal specification,Transactional memory,Transactional leadership
Conference
ISBN
Citations 
PageRank 
1-59593-264-X
16
0.77
References 
Authors
13
6
Name
Order
Citations
PageRank
Chaiyasit Manovit11146.48
Sudheendra Hangal253635.73
Hassan Chafi3111861.11
Austen Mcdonald449936.78
Christos Kozyrakis55817355.99
Kunle Olukotun64532373.50