2006 · 37 citations · 22 references
ComputingComputer ScienceComputer SystemsComputer ArchitectureFormal MethodsParallel ComputingConcurrency AnalysisConcurrency ControlConcurrent System VerificationMemory ConsistencyMemory Consistency ModelsSoftware TestingConcurrency Bug DetectionConsistency TestingConsistency VerificationLock-free SynchronizationMemory Consistency VerificationModel Checking For ConcurrencyTransactional MemoryTransactional Memory Consistency
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.
22
Maurice Herlihy, J. Eliot B. Moss · 1993 · 2.2K citations
Nir Shavit, Dan Touitou · 1995 · 1.2K citations · Full text
LogTM: Log-based Transactional Memory
K.E. Moore, Jayaram Bobba, Michelle J. Moravan et al. · 2006 · 685 citations
Transactional Memory Coherence and Consistency
Lance Hammond, Vicky Wong, Mike Y. Chen et al. · ACM SIGARCH Computer Architecture News · 2004 · 647 citations
Unbounded Transactional Memory
C. Scott Ananian, Krste Asanović, Bradley C. Kuszmaul et al. · 2005 · 440 citations
Computing, Computer Systems, Memory +11