Оптимизация обнаружения конфликтов в параллельных программах с транзакционной памятью

Иван Иванович Кулагин, Михаил Георгиевич Курносов

Аннотация


В настоящее время активно развивается альтернативный подход к созданию масштабируемых и потокобезопасных параллельных программ для многопроцессорных систем с общей памятью – технология транзакционной памяти (transactional memory). Ожидается, что она войдет в стандарт языка С++17. В данной работе предложен метод оптимизации обнаружения конфликтов (конкурентного доступа потоков к общим областям памяти), возникающих при выполнении параллельных программ на базе транзакционной памяти. Реализован модуль компилятора GCC для профилирования параллельных программ и адаптивной настройки параметров реализации транзакционной памяти под программу. Эффективность метода исследована на тестовых программах из пакета STAMP.


Ключевые слова


программная транзакционная память, параллельное программирование, профилирование, компиляторы

Полный текст:

PDF

Литература


M. Herlihy, N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008.

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. P. 206–215.

Кузнецов С.Д. Транзакционная память [HTML]. www.citforum.ru/programming/digest/transactional_me

N. Shavit, D. Touitou. Software Transactional Memory. In PODC’95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, New York, NY, USA, Aug. 1995. ACM, 204–213.

Pascal Felber, Christof Fetzer, Patrick Marlier, and Torvald Riegel, Time-based Software Transactional Memory, IEEE Transactions on Parallel and Distributed Systems, Volume 21, Issue 12, pp. 1793-1807, December 2010.

Torvald Riegel, Pascal Felber, and Christof Fetzer. A Lazy Snapshot Algorithm with Eager Validation, 20th International Symposium on Distributed Computing (DISC), 2006.

Victor Luchango, Jens Maurer, Mark Moir. Transactional memory for C++ [PDF]. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3718.pdf

Rochester Software Transactional Memory Runtime. www.cs.rochester.edu/research/synchronization/rstm/.

Project web site [HTML].

Michael F. Spear, Luke Dalessandro, Virendra J. Marathe, and Michael L. Scott. A comprehensive 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, P – 141-150.

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, P. – 254-265.

Michael F. Spear, Maged M. Michael, and Christoph von Praun. RingSTM: scalable transactions with a single atomic instruction. In SPAA ’08: Proc. 20th Annual Symposium on Parallelism in Algorithms and Architectures, June 2008, P. 275–284.

Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In DISC ’06: Proc. 20th International Symposium on Distributed Computing, September 2006. Springer Verlag Lecture Notes in Computer Science volume 4167, P. – 194-208.

Pascal Felber, Christof Fetzer, Torvald Riegel. Dynamic performance tuning of word-based software transactional memory. PPOPP 2008. P. – 237-246.

Craig Zilles and Ravi Rajwar. Implications of false conflict rate trends for robust software transactional memory. In IISWC ’07: Proc. 2007 IEEE.

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. P. 365–375.

Intel Corporation. Intel Transactional Memory Compiler and Runtime Application Binary Interface. Revision: 1.0.1, November 2008.




DOI: http://dx.doi.org/10.14529/cmse160404