Article

Article title TOWARDS CRITICAL SECTIONS SPECULATED EXECUTION OF PARALLEL PROGRAMS ON MULTI-CORE SYSTEMS
Authors I.I. Kulagin, M.G. Kurnosov
Section SECTION II. MATHEMATICAL AND SOFTWARE OF SUPERCOMPUTERS
Month, Year 11, 2016 @en
Index UDC 004.272.26
DOI 10.18522/2311-3103-2016-11-5464
Abstract Software transactional memory (STM) is an approach to developing the thread-safe programs. In contrast to locking a block of code by mutex, the main idea of this approach is to protect memory areas from concurrent access by threads. In this paper, we investigate efficiency of software transactional memory implementation in GCC compiler. The GCC implementation of software transactional memory implements specification that proposed by Intel company – Intel TM ABI. Software tools for instrumentation and profiling STM-programs are proposed. Profile-guided method for reducing false conflicts in STM-programs is presented. False conflict is a conflict that exists on the level of runtime library but not when the memory accessing occurs. The instrumentation module analyzes the code of transactional sections and puts calls for registration of some events (begin transactions, transactional read/write, commit transactions and abort transactions). The profiling of the instrumented program allows obtaining the dynamic properties of execution transactional code like size of used data, read/write addresses, timestamp of events, etc. The static instrumentation allows optimizing the dynamic properties of execution transactional sections. The method for reducing false conflicts performs the tuning of transactional memory parameters value in GCC implementation (libitm runtime-library) by using the profiling results (profile-guided optimization) like the mean memory size of transactional read/write operations. The efficiency of reducing the false conflicts is investigated on the STAMP benchmarks. These benchmarks contain eight tests which operate with hash tables, lists, arrays protected by software transactional memory. Using the proposed method of tests the time is reduced approximately to 20 %. Suboptimal parameter values of STM runtime-library have been obtained by the proposed profile-guided method.

Download PDF

Keywords Software transactional memory; instrumentation; profile-guided optimization; multithreaded programming; compilers.
References 1. Herlihy M., Shavit N. The Art of Multiprocessor Programming. Morgan Kaufmann PublishersInc., San Francisco, CA, USA, 2008.
2. Hendler D., Shavit N., Yerushalmi L. A scalable lock-free stack algorithm, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. SPAA ’04, 2004, pp. 206-215.
3. Moir M. et al. Using elimination to implement scalable and lock-free FIFO queues, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures. ACM, 2005, pp. 253-262.
4. Shavit N., Touitou D. Elimination trees and the construction of pools and stacks: preliminary version, Proceedings of the seventh annual ACM symposium on Parallel algorithms and archi-tectures. ACM, 1995, pp. 54-63.
5. Lozi J.P. et al. Remote Core Locking: Migrating Critical-Section Execution to Improve the Performance of Multithreaded Applications, USENIX Annual Technical Conference, 2012, pp. 65-76.
6. Afek Y., Korland G., Natanzon M., Shavit N. Scalable Producer-Consumer Pools based on Elimination-Diffraction Trees, European Conference on Parallel Processing, 2010, pp. 151-162.
7. Kuznetsov S.D. Transaktsionnaya pamat. [Transactional memory]. Available at: http://citforum.ru/programming/digest/transactional_memory/. (in Russian).
8. Shavit N., Touitou D. Software Transactional Memory, In PODC’95: Proceedings of thefourteenth annual ACM symposium on Principles of distributed computing, New York, NY, USA, Aug. 1995. ACM, pp. 204-213.
9. Pascal Felber, Christof Fetzer, Patrick Marlier, and Torvald Riegel. Time-based SoftwareTransactional Memory. IEEE Transactions on Parallel and Distributed Systems, De-cember 2010, Vol. 21, Issue 12. pp. 1793-1807.
10. Torvald Riegel, Pascal Felber, and Christof Fetzer. A Lazy Snapshot Algorithm with EagerValidation, 20th International Symposium on Distributed Computing (DISC), 2006.
11. Victor Luchango, Jens Maurer, Mark Moir. Transactional memory for C++ [PDF]. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3718.pdf.
12. Rochester Software Transactional Memory Runtime. Project web site [HTML]. www.cs.rochester.edu/research/synchronization/rstm/.
13. Michael F. Spear, Luke Dalessandro, Virendra J. Marathe, and Michael L. Scott. A compre-hensive strategy for contention management in software transactional memory, In PPoPP ’09: Proc. 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, February 2009, pp. 141-150.
14. Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill, and David A. Wood. LogTM: Log-based transactional memory, In HPCA ’06: Proc. 12th International Symposium on High-Performance Computer Architecture, February 2006, pp. 254-265.
15. Michael F. Spear, Maged M. Michael, and Christoph von Praun. RingSTM: scalable transac-tions with a single atomic instruction, In SPAA ’08: Proc. 20th Annual Symposium on Paral-lelism in Algorithms and Architectures, June 2008, pp. 275-284.
16. Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II, In DISC ’06: Proc. 20th In-ternational Symposium on Distributed Computing, September 2006. Springer Verlag Lecture Notes in Computer Science, Vol. 4167, pp. 194-208.
17. Pascal Felber, Christof Fetzer, Torvald Riegel. Dynamic performance tuning of word-based software transactional memory. PPOPP 2008, pp. 237-246.
18. Craig Zilles and Ravi Rajwar. Implications of false conflict rate trends for robust software transactional memory, In IISWC ’07: Proc. 2007 IEEE.
19. Olszewski M., Cutler J., Steffan J.G. JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques. PACT ’07. 2007, pp. 365-375.
20. Intel Corporation. Intel Transactional Memory Compiler and Runtime Application Binary Interface. Revision: 1.0.1, November 2008.

Comments are closed.