Software Transactional Memory in a Dynamic Programming Language at Virtual Machine Level

Software Transactional Memory in a Dynamic Programming Language at Virtual Machine Level

許斯凱(SZU-KAI HSU)

指導教授 ： 林柏青

國立中正大學/工學院/資訊工程學系/碩士(2014年)

並列摘要

As computer hardware evolves, the importance of parallel programming paradigm increases. As more and more multi-core processors emerge, traditional sequential programming paradigm no longer suffices. Yet only few modern dynamic programming languages can leverage such advantage. Ruby, for example, despite its wide adoption, only includes threads as a simple parallel primitive. The global virtual machine lock of official Ruby runtime makes it impossible to exploit full parallelism. Though various alternative Ruby implementations do eliminate the global virtual machine lock, they only provide developers dated locking mechanism for data synchronization. However, traditional locking mechanism error-prone by nature. Software Transactional Memory is one of the promising alternatives among others. It applies the concept of database transaction to memory manipulations, which ensures atomicity, consistency, isolation, and durability. The abstraction of transactions also avoids some common synchronization errors in the context of locking mechanism. This paper introduces a new virtual machine: GobiesVM to provide a native software transactional memory based solution for dynamic programming languages to exploit parallelism. We also proposed a simplified variation of Transactional Locking II algorithm. Our version combines the original read-set and the write-set into a single object set which makes the algorithm more comprehensive and reduces overhead regarding multiple set maintenance. The empirical results of our experiments show that support of STM at virtual machine level enables developers to write straightforward code without compromising parallelism or sacrificing thread safety. Existing source code only requires minimal or even none modification, which allows developers to easily switch their legacy codebase to a parallel environment. The performance evaluations of GobiesVM also indicate the difference between sequential and parallel execution is significant.

並列關鍵字

Virtual Machine ； Ruby ； Software Transactional Memory ； Parallel ； Data Synchronization

參考文獻

[1] N. Shavit and D. Touitou, "Software Transactional Memory'', Published in Distributed Computing, vol. 10, Issue 2, pp99-116, Feburary 1st 1997

[3] C. Wang, W. Chen, Y. Wu, B. Saha, and A. Adl-Tabatabai, "Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language'', Published in Proceeding CGO '07 Proceedings of the International Symposium on Code Generation and Optimization, Pp. 34-48, 2007

[7] T. Haerder and A. Reuter, "Principles of transaction-oriented database recovery'', Published in ACM Computing Surveys (CSUR), vol 15 Issue 4, pp. 287-317, December 1983

[2] T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy, "Composable memory transactions'', Published in Proceeding PPoPP '05 Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 48-60, 2005

[4] M. Mohamedin, B. Ravindran, and R. Palmieri, "ByteSTM: Virtual Machine-Level Java Software Transactional Memory'', Presented at 15th International Conference, COORDINATION 2013, Held as Part of the 8th International Federated Conference on Distributed Computing Techniques, DisCoTec 2013, Florence, Italy, June 3-5, 2013.