臺灣博碩士論文加值系統

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.

Table of contents
Abstract i
List of figures iii
1 Introduction 1
2 Related Works 3
2.1. Software Transactional Memory 3
2.2. Ruby Programming Language 4
3 Implementation 6
3.1. Transactional Locking II 6
3.1.1. Basic Structure 6
3.1.2. Read-Only Transactions 6
3.1.3. Write Transactions 7
3.2. GobiesVM 8
3.2.1. System Architecture 8
3.2.2. STM implementation 8
4 Evaluation 12
4.1. Minimal code modification and logic simplification 16
4.2. Word counting 18
4.3. Matrix addition 21
4.4. Pi approximation 23
4.5. Thread safety 25
5 Conclusion and Future Work 27
References 28

[1] N. Shavit and D. Touitou, "Software Transactional Memory'', Published in Distributed Computing, vol. 10, Issue 2, pp99-116, Feburary 1st 1997
[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
[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
[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.
[5] R. J. Meier, Native Transactional Memory in a Dynamic Programming Language'', May 2013
[6] S. Peyton-Jones, "Beautiful Concurrency'', May 1st 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
[8] D. Dice, O. Shalev, and N. Shavit, "Transactional Locking II'', Published in Proceedings of 20th International Symposium, DISC 2006, pp. 194-208, September 18-20, 2006
[9] K. Sasada, "YARV: yet anohter RubyVM: innovating the ruby interpreter'', Published in Proceeding of OOPSLA '05 Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pp. 158-159, 2005
[10] B. Ford, "Packrat Parsing: Simple, Powerful, Lazy, Linear Time'', Presented at International Conference of Functional Programming, October 4-6, 2002
[11] B. Ford, "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation'', Presented at Symposium on Principles of Programming Languages, January 14-16, 2004
[12] R. Odaira, J. G. Castanos, H. Tomari, "Eliminating Global Interpreter Locks in Ruby through Hardware Transactional Memory'', Published in Proceeding PPoPP '14 Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 131-142, 2014