Abstract
Transactional Memory (TM) provides a strong abstraction to tackle the challenge of synchronizing concurrent tasks that access shared state. Yet, most TMs do not allow a single transaction to contain parallel code. We propose an efficient parallel nesting algorithm to explore existing latent parallelism within a transaction. If this intra-transaction parallelism has reduced conflict probability (compared to the inter-transaction parallelism), then it may be worthy to execute less transactions at a given time, but have each one parallelized and using several available cores.
We provide practical support for parallel nesting in the first lock-free parallel nesting algorithm with support for multi-versions. Our prototype builds over an available multi-version TM, which we outperform on standard benchmarks by up to 2.8×. We show improvements over parallel nesting alternatives of up to 3.6×.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, K., Fineman, J.T., Sukha, J.: Nested parallelism in transactional memory. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2008, pp. 163–174. ACM (2008)
Ansari, M., Kotselidis, C., Watson, I., Kirkham, C., Luján, M., Jarvis, K.: Lee-TM: A non-trivial benchmark suite for transactional memory. In: Bourgeois, A.G., Zheng, S.Q. (eds.) ICA3PP 2008. LNCS, vol. 5022, pp. 196–207. Springer, Heidelberg (2008)
Baek, W., Bronson, N., Kozyrakis, C., Olukotun, K.: Implementing and evaluating nested parallel transactions in software transactional memory. In: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2010, pp. 253–262. ACM (2010)
Barreto, J., Dragojević, A., Ferreira, P., Guerraoui, R., Kapalka, M.: Leveraging parallel nesting in transactional memory. In: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2010, pp. 91–100. ACM (2010)
Intel Corporation. Intel Architecture Instruction Set Extensions Programming Reference. 319433-012 edn. (February 2012)
Diegues, N., Cachopo, J.: Practical Parallel Nesting for Software Transactional Memory. Technical Report RT/22/2013, INESC-ID Lisboa (July 2013)
Diegues, N., Cachopo, J.: On the design space of Parallel Nesting. In: The 4th Workshop on the Theory of Transactional Memory, WTTM 2012 (2012)
Diegues, N., Fernandes, S., Cachopo, J.: Parallel Nesting in a lock-free multi-version Software Transactional Memory. In: The 7th ACM SIGPLAN Workshop on Transactional Computing, TRANSACT 2012 (2012)
Fernandes, S., Cachopo, J.: Lock-free and scalable multi-version software transactional memory. In: Proceedings of the 16th ACM symposium on Principles and Practice of Parallel Programming, PPoPP 2011, pp. 179–188. ACM (2011)
Guerraoui, R., Kapalka, M.: On the correctness of transactional memory. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2008, pp. 175–184. ACM (2008)
Guerraoui, R., Kapalka, M., Vitek, J.: STMBench7: a benchmark for software transactional memory. In: Proceedings of the 2nd ACM EuroSys European Conference on Computer Systems 2007, EuroSys 2007, pp. 315–324. ACM (2007)
Herlihy, M., Moss, J.E.B.: Transactional memory: architectural support for lock-free data structures. In: Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA 1993, pp. 289–300. ACM (1993)
Kumar, R., Vidyasankar, K.: HParSTM: A hierarchy-based STM protocol for supporting nested parallelism. In: The 6th ACM SIGPLAN Workshop on Transactional Computing, TRANSACT 2011 (2011)
Liu, Y., Diestelhorst, S., Spear, M.F.: Delegation and nesting in best-effort hardware transactional memory. In: Proceedings of the 24th Annual Symposium on Parallelism in Algorithms and Architectures, SPAA 2012, pp. 38–47 (2012)
Minh, C.C., Chung, J., Kozyrakis, C., Olukotun, K.: STAMP: Stanford transactional applications for multi-processing. In: IEEE International Symposium on Workload Characterization, IISWC 2008, pp. 35–46 (2008)
Moss, J.E.B., Hosking, A.L.: Nested transactional memory: model and architecture sketches. Science of Computer Programming 63(2), 186–201 (2006)
Perelman, D., Fan, R., Keidar, I.: On maintaining multiple versions in stm. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010, pp. 16–25. ACM (2010)
Ramadan, H., Witchel, E.: The Xfork in the road to coordinated sibling transactions. In: The 4th ACM SIGPLAN Workshop on Transactional Computing, TRANSACT 2009 (2009)
Volos, H., Welc, A., Adl-Tabatabai, A.-R., Shpeisman, T., Tian, X., Narayanaswamy, R.: NePalTM: design and implementation of nested parallelism for transactional memory systems. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2009, pp. 291–292. ACM (2009)
Wang, A., Gaudet, M., Wu, P., Amaral, J.N., Ohmacht, M., Barton, C., Silvera, R., Michael, M.: Evaluation of blue Gene/Q hardware support for transactional memories. In: Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques, PACT 2012, pp. 127–136. ACM (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Diegues, N., Cachopo, J. (2013). Practical Parallel Nesting for Software Transactional Memory. In: Afek, Y. (eds) Distributed Computing. DISC 2013. Lecture Notes in Computer Science, vol 8205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41527-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-41527-2_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41526-5
Online ISBN: 978-3-642-41527-2
eBook Packages: Computer ScienceComputer Science (R0)