探索並拓展軟體事務性記憶體的可排程性以增進其效能

Exploring and Expanding the Scheduling Scope to Enhance the Performance of Software Transactional Memory Systems

賴明緯(Ming-Wei Lai)

指導教授 ： 郭斯彥

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202201972

摘要

本研究透過改良任務排程以增進軟體事務性記憶體 (Software Transactional Memory) 的執行效能及可擴展性。軟體事務性記憶體是一種並行控制的程式設計法，利用隔離 (isolated) 且不可拆分 (atomic) 的事務區段 (transactions) 取代直接操作底層的鎖 (lock)；然而，這種設計法在執行高頻率記憶體操作衝突的應用程式時會有顯著地效能及可擴展性下降。因此，過往文獻往往設計不同機制閒置部分執行緒以規避記憶體操作衝突，但卻反倒招致無謂的計算資源浪費。

本論文試圖指出：現行機制囿於無謂的事務執行順序規範，才只能利用執行緒閒置以避免衝突。倘若妥善地鬆弛相關限制，便能突破過往事務排程侷限，在使用所有執行緒的條件下仍能降低衝突。後續更進一步介紹依此精神實作的羅密歐 (Romeo) 擴充函式功能，並藉其探索不同排程演算法，為軟體事務性記憶體的效能帶來進展。

關鍵字

事務性記憶體 ； 排程 ； 平行運算

並列摘要

Software Transactional Memory (STM) systems provide a convenient interface for writing parallel programs. By maintaining isolated and atomic transactions, the system relieves the burden of programmers from directly operating on low-level locks. However, when memory conflicts frequently occur, the system could face severely degraded performance and scalability. Previous studies have proposed different mechanisms to alleviate the issue; however, to the best of the author’s knowledge, the solutions generally include idling threads to lessen contention, incurring computation resource wastes and overheads.

The current study aims to enhance scalability and speed up execution in Software Transactional Memory (STM) systems by improving transaction scheduling strategy. First, it points out that conventional STM systems are prone to limited scheduling opportunities. Second, it introduces the Romeo API implementation that extends the current STM infrastructure to relax execution orders. Finally, benefiting from the extra scheduling options, it evaluates different scheduling strategies that improve the performance and scalability of STM in high-contention applications.

並列關鍵字

transnational memory ； scheduling ； parallel computing

參考文獻

[1] 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, San Diego, CA, USA, May 1993 (A. J. Smith, ed.), pp. 289–300, ACM, 1993.

[2] T. Harris, J. R. Larus, and R. Rajwar, Transactional Memory, 2nd edition. Synthesis Lectures on Computer Architecture, Morgan Claypool Publishers, 2010.

[3] R. M. Yoo and H. S. Lee, “Adaptive transaction scheduling for transactional memory systems,” in SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, June 14-16, 2008 (F. M. auf der Heide and N. Shavit, eds.), pp. 169–178, ACM, 2008.

[4] P. di Sanzo, A. Pellegrini, M. Sannicandro, B. Ciciani, and F. Quaglia, “Adaptive model-based scheduling in software transactional memory,” IEEE Trans. Computers, vol. 69, no. 5, pp. 621–632, 2020.

[5] A. Dragojevic, R. Guerraoui, A. V. Singh, and V. Singh, “Preventing versus curing: avoiding conflicts in transactional memories,” in Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, PODC 2009, Calgary, 45 doi:10.6342/NTU202201972 Alberta, Canada, August 10-12, 2009 (S. Tirthapura and L. Alvisi, eds.), pp. 7–16, ACM, 2009.