Sanjeev Kumar
ABSTRACT
High performance parallel programs are currently difficult to write and debug. One major source of difficulty is protecting concurrent accesses to shared data with an appropriate synchronization mechanism. Locks are the most common mechanism but they have a number of disadvantages, including possibly unnecessary serialization, and possible deadlock. Transactional memory is an alternative mechanism that makes parallel programming easier. With transactional memory, a transaction provides atomic and serializable operations on an arbitrary set of memory locations. When a transaction commits, all operations within the transaction become visible to other threads. When it aborts, all operations in the transaction are rolled back.Transactional memory can be implemented in either hardware or software. A straightforward hardware approach can have high performance, but imposes strict limits on the amount of data updated in each transaction. A software approach removes these limits, but incurs high overhead. We propose a novel hybrid hardware-software transactional memory scheme that approaches the performance of a hardware scheme when resources are not exhausted and gracefully falls back to a software scheme otherwise.
- C. S. Ananian, K. Asanovic, B. C. Kuszmaul, C. E. Leiserson, and S. Lie. Unbounded transactional memory. In Proceedings of the 11th International Symposium on High-Performance Computer Architecture, 2005. Google Scholar
Digital Library
- R. J. Anderson and J. C. Setubal. On the parallel implementation of Goldberg' s maximum flow algorithm. In Proceedings of the 4th annual Symposium on Parallel Algorithms and Architectures, 1992. Google ScholarDigital Library
- M. Cintra, J. F. Martínez, and J. Torrellas. Architectural support for scalable speculative parallelization in shared-memory multiprocessors. In Proceedings of the Twenty-seventh Annual International Symposium on Computer Architecture, 2000. Google ScholarDigital Library
- C. Flanagan and S. Qadeer. A type and effect system for atomicity. In Proceedings of the Conference on Programming Language Design and Implementation, 2003. Google ScholarDigital Library
- M. Franklin and G. S. Sohi. Arb: A mechanism for dynamic reordering of memory references. IEEE Transactions on Computers, May 1996. Google ScholarDigital Library
- M. J. Garzaran, M. Prvulovic, J. M. Llabería, V. Viñals, L. Rauchwerger, and J. Torrellas. Tradeoffs in buffering memory state for thread-level speculation in multiprocessors. In Proceedings of the 9th Annual International Symposium on High Performance Computer Architecture, 2003. Google ScholarDigital Library
- S. Gopal, T. N. Vijaykumar, J. E. Smith, and G. S. Sohi. Speculative versioning cache. In Proceedings of the 4th Annual Internationsl Symposium on High Performance Computer Architecture, 1998. Google ScholarDigital Library
- J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers Inc., 1992. Google ScholarDigital Library
- R. Guerraoui, M. Herlihy, and S. Pochon. Toward a theory of transactional contention management. In Proceedings of the Symposium on Principles of Distributed Computing, 2005. Google ScholarDigital Library
- L. Hammond, M. Willey, and K. Olukotun. Data speculation support for a chip multiprocessor. In Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems, 1998. Google ScholarDigital Library
- L. Hammond, V. Wong, M. Chen, B. D. Carlstrom, J. D. Davis, B. Hertzberg, M. K. Prabhu, H. Wijaya, C. Kozyrakis, and K. Olukotun. Transactional memory coherence and consistency. In Proceedings of the 31st Annual International Symposium on Computer Architecture, 2004. Google ScholarDigital Library
- T. Harris and K. Fraser. Language support for lightweight transactions. In Proceedings of the International Conference Object-Oriented Programming, Systems, Languages, and Applications, 2003. Google ScholarDigital Library
- T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In Proceedings of the International Symposium on Principles and Practice of Parallel Programming, 2005. Google ScholarDigital Library
- M. Herlihy. Transactional memory. PLDI' 05 Keynote Address, 2005.Google Scholar
- M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software Transactional Memory for Dynamic-Sized Data Structures. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, 2003. Google ScholarDigital Library
- M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture, 1993. Google ScholarDigital Library
- J. F. Martínez and J. Torrellas. Speculative synchronization: Applying thread-level speculation to explicitly parallel applications. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, 2002. Google ScholarDigital Library
- J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems, 9(1):21--65, 1991. Google ScholarDigital Library
- K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. Logtm: Log-based transactional memory. In Proceedings of the 12th Annual International Symposium on High Performance Computer Architecture, 2006.Google ScholarCross Ref
- M. Prvulovic, M. J. Garzaran, L. Rauchwerger, and J. Torrellas. Removing architectural bottlenecks to the scalability of speculative parallelization. In Proceedings of the 27th Annual International Symposium on Computer Architecture, 2001. Google ScholarDigital Library
- R. Rajwar and J. R. Goodman. Transactional lock-free execution of lock-based programs. In Proceedings of the 10th Symposium on Architectural Support for Programming Languages and Operating Systems, 2002. Google ScholarDigital Library
- R. Rajwar, M. Herlihy, and K. Lai. Virtualizing transactional memory. In Proceedings of the 32nd Annual International Symposium on Computer Architecture, 2005. Google ScholarDigital Library
- R. Rajwar and M. Hill. http://www.cs.wisc.edu/trans-memory/biblio/. Transactional Memory Bibliography, 2005.Google Scholar
- W. N. Scherer III and M. L. Scott. Advanced contention management for dynamic software transactional memory. In Proceedings of the Symposium on Principles of Distributed Computing, 2005. Google ScholarDigital Library
- N. Shavit and D. Touitou. Software transactional memory. In Proceedings of the 14th Annual ACM symposium on Principles of distributed computing, 1995. Google ScholarDigital Library
- G. S. Sohi, S. Breach, and S. Vijaykumar. Multiscalar processors. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, 1995. Google ScholarDigital Library
- J. Steffan, C. Colohan, A. Zhai, and T. C. Mowry. A scalable approach to thread-level speculation. In Proceedings of the 27th Annual International Symposium on Computer Architecture, 2000. Google ScholarDigital Library
Index Terms
- Hybrid transactional memory
Recommendations
Hybrid transactional memory
ASPLOS XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systemsTransactional memory (TM) promises to substantially reduce the difficulty of writing correct, efficient, and scalable concurrent programs. But "bounded" and "best-effort" hardware TM proposals impose unreasonable constraints on programmers, while more ...
An effective hybrid transactional memory system with strong isolation guarantees
ISCA '07: Proceedings of the 34th annual international symposium on Computer architectureWe propose signature-accelerated transactional memory (SigTM), ahybrid TM system that reduces the overhead of software transactions. SigTM uses hardware signatures to track the read-set and write-set forpending transactions and perform conflict ...
Unbounded page-based transactional memory
Proceedings of the 2006 ASPLOS ConferenceExploiting thread level parallelism is paramount in the multicore era. Transactions enable programmers to expose such parallelism by greatly simplifying the multi-threaded programming model. Virtualized transactions (unbounded in space and time) are ...
Comments