當一個平行程式所使用的執行緒之間共享一個記憶體位置時，須確保對該記憶體位置的存取符合基元性。傳統為符合基元性皆對記憶體位置進行鎖定，但不幸的是，對一個程式設計師而言，鎖定機制使用上非常困難且須注意非常多小細節以至於容易出錯，例如死結的預防、避免、偵測及恢復等議題。幸運的是，鎖定機制並非唯一可提供基元性存取的機制。在資料庫領域所使用的記憶體管理可取代鎖定機制在存取共享的記憶體時，提供包括基元性、一致性、獨立性及可序列化等安全特性。
本論文延續蘇盈誠學長先前的研究，其提出Barrier TM利用上述記憶體管理提供的安全特性，模擬一個多人連線第一人稱射擊遊戲的遊戲伺服器系統，在確保物理運算需求間不會發生衝突的情況下釋放物理運算需求，並且在運算結束後進行總物理更新，將所有運算結果利用平行的多執行緒進行更新，以達到比傳統使用單一執行緒進行更新能有更好的效能。
但結果發現，Barrier TM在最差情形且核心數量高於4之後的特定情況下，會發生極為嚴重的碰撞，尤其核心數越多越嚴重，使得整體效能仍不敵傳統鎖定機制，而本研究提出的Pair TM除了維持記憶體管理的安全特性之外，並改善此碰撞暴增的問題同時減少交易的等待時間，使得在最差情形且當核心數量高於4之後的特定情況下，整體效能亦能勝過傳統鎖定機制。

When threads of a parallel program share a memory location, we have to ensure that the use of shared location will follow the atomicity. In order to provide atomicity we still use a lock in traditional way. Unfortunately, the lock mechanism acquires the programmers to take care of many details, such as deadlock prevention, deadlock avoidance, deadlock detection, deadlock recovery or any other concurrency control problems, so that it is error-prone,. Fortunately, lock mechanism is not the only way to provide atomicity. Transactional Memory(TM) is a mechanism that may replace the traditional method for doing this. It provides safety characteristics that include atomicity, consistency, isolation, and serilizability to using shared resources.
This paper extends the scope of Barrier TM researched by Jason Su. The method presents a simulation of a multi-player First Person Shooting (FPS) game server system, making sure that the requests of physics calculation released to the physics steps will have no conflicts by using multi-thread update the results parallel to achieve more efficiency than traditional way with single thread. As a result, it leverages the strength of TM.
But the result from the case study reveals that, in the situation of worst case and with more than four cores, the number of conflicts cause the performance of the Barrier TM to be unacceptable. In this paper, we present a Pair TM that can not only leverage the safety characteristics of TM, but also improve the problem of Barrier TM so that its overall performance can defeat the traditional lock mechanism.

外文部分
Agrawal, K., Lee, I.-T., & Sukha, J. (2009). Safe open-nested transactions through ownership. PPOPP 2009 Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 151-162.
Ahmad, Y., & Nath, S. (2008, April 7-12). COLR-Tree: Communication-efficient spatio-temporal indexing for a sensor data web portal. IEEE 24th International Conference on Data Engineering, pp. 784-793.
Amdahl, G. (1967). Validity of the single processor approach to achieving large scale computing capabilities. In proceedings of the spring joint computer conference, pp. 483-485.
Baldassin, A., & Burckhardt, S. (2009). Lightweight software transactions for games. First USENIX Workshop on Hot Topics in Parallelism, p. 13.
Bilas, A., & Abdelkhale, A. (2004). Parallelization and performance of interactive multiplayer game servers. Parallel and Distributed Processing Symposium, International.
Bruce Dawson. (2010, June). Coding for multiple cores on Xbox 360 and Microsoft windows.
Cascaval, C., Blundell, C., Michael, M., Cain, H., Wu, P., Chiras, S., et al. (2008). Software transactional memory: why is it only a research toy? Commun. ACM. 51(11), pp. 40-46.
Chappell, R., Stark, J., Kim, S., Reinhardt, S., & Patt, Y. (1999). Simultaneous subordinate microthreading(SSMT). In Proceedings of the Annual International Symposium on Computer Architecture, pp. 186-195.
Collins, J., Wang, H., Tullsen, D., Hughes, C., Lee, Y., Lavery, D., et al. (2001). Speculative precomputation: long-range prefetching of delinquent loads. In Proceedings of the Annual International Symposium on Computer Architecture, pp. 14-25.
Dalessandro, L., & Scott, M. (2009). Strong isolation is a weak idea. In TRANS-ACT.
Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., & Nussbaum, D. (2006, October). Hybrid transactional memory. Proceedings of the Twelfth International Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS).
Dash, A., & Demsky, B. (2011). Integrating Caching and Prefetching Mechanisms in a Distributed Transactional Memory. IEEE Transactions on Parallel and Distributed Systems-PrePrints.
Dice, D., Shalev, O., & Shavit, N. (2006). Transactional locking II. In Proc. of the 20th Intl. Symp. on Distributed Computing.
Dragojević, A., Felber, P., Gramoli, V., & Guerraoui, R. (2011). Why STM can be more than a Research Toy. Commun. ACM. 4(54), pp. 70-77.
Dragojevic, A., Guerraoui, R., & Kapalka, M. (2009). Stretching transactional memory. PLDI 2009 Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, (pp. 155-165).
Esch, M., & Botev, J. (2010). Distance-aware avatar interaction in online virtual environments. Advances in Future Internet, International Conference, pp. 56-62.
Frigo, M., Leiserson, E., & Randall, H. (1998). The implementation of the Cilk-5 multithreaded language. In Proceedings of the Conference on Programming Language Design and Implementation, (pp. 212-223).
Gajinov, V., Zyulkyarov, F., Unsal, S., Cristal, A., Ayguade, E., Harris, T., et al. (2009). QuakeTM: parallelizing a complex sequential application using transactional memory. ICS '09 Proceedings of the 23rd international conference on Supercomputing, pp. 126-135.
Half-Life. (2011). Counter-Strike Gameplay & Maps. Retrieved from Planet Half-life: http://planethalflife.gamespy.com/View.php?view=CSGameInfo.Detail&id=12&game=5
Half-Life. (2011). Half-Life. Retrieved from Planet Half-Life: http://planethalflife.gamespy.com/
Hammond, L., Willey, M., & Olukotun, K. (1998). Data speculation support for a chip multiprocessor. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating systems, (pp. 58-69).
Harris, T., & Fraser, K. (2003). Language support for lightweight transactions. ACM SIGPLAN Notices - Special Issue: Proceedings of the OOPSLA '03 conference, (p. 38). California, USA.
Harris, T., Plesko, M., Shinnar, A., & Tarditi, D. (2006, June). Optimizing memory transactions. PLDI '06: ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation.
Herlihy, M., & Moss, E. (1993). Transactional memory: Architectural support for lock-free data structures. In Proceedings of the Annual International Symposium on Computer Architecture, pp. 289-300.
Herlihy, M., & Moss, J. (1993, May). Transactional memory: Architectural support for lock-free data structures. In Proc. of the 20th Int'l Symp. on Computer Architecture(ISCA'93), pp. 289-300.
Jefferson, R. (1985). Virtual time. ACM Trans. Program. Lang. Syst., pp. 404-425.
Kumar, S., Chu, M., Hughes, J., Kundu, P., & Nguyen, A. (2006, March). Hybrid transactional memory. In the Proceedings of ACM symp. on Principles and Practice of Parallel Programming.
Larus, J., & Rajwar, R. (2007). Transactional Memory. USA: Morgan & Claypool Publishers.
Lev, Y., Luchanggco, V., Marathe, J., Moir, M., Nussbaum, D., & Olszewski, M. (2009). Anatomy of a scalable software transactional memory. 2009, 4th ACM SIGPLAN Workshop on Transactional Computing.
Lupei, D., Simion, B., Pinto, D., Misler, M., Burcea, M., Krick, W., et al. (2010). Transactional memory support for scalable and transparent parallelization of multiplayer games. EuroSys '10 Proceedings of the 5th European conference on Computer systems, pp. 41-54.
Lupei, D., Simion, B., Pinto, D., Misler, M., Burcea, M., Krick, W., et al. (2010, April 13-16). Transactional memory support for scalable and transparent parallelization of multiplayer games. Proceeding EuroSys '10 Proceedings of the 5th European conference on Computer systems, pp. 41-54.
McCloskey, B., Zhou, F., Gay, D., & Brewer, E. (2006). Autolocker: synchronization inference for atomic sections. POPL 2006 Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, (pp. 246-358).
Mehrara, M., Hao, J., Hsu, P., & Mahlke, S. (2009). Parallelizing sequential applications on commodity hardware using a low-cost software transactional memory. In Proceedings of the Conference on Programming Language Design and Implementation, pp. 166-176.
Miloš Milovanović, Roger Ferrer, Vladimir Gajinov, Osman S. Unsal, Adrian Cristal, Eduard Ayguadé, et al. (2007). Multithreaded software transactional memory and OpenMP. Proceedings of the 2007 workshop on MEmory performance: DEaling with Applications, systems and architecture, pp. 81-88.
Minh, C., Trautmann, M., Chung, J., Mcdonald, A., Bronson, N., Casper, J., et al. (2007, June 9-13). An effective hybrid transactional memory system with strong isolation guarantees. ISCA, pp. 69-80.
Moir, M., Ellen, F., Lev, Y., & Luchangco, V. (2007). SNZI: scalable NonZero indicators. PODC 2007 Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing.
Ni, Y., Menon, V., Adl-Tabatabai, A.-R., Hosking, A., Hudson, R., Moss, J., et al. (2007). Open nesting in software transactional memory. POPP 2007 Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 68-78.
Plattner, H. (2009). A common database approach for OLTP and OLAP using an in-memory column database. SIGMOD Conference 2009 Proceedings of the 35th SIGMOD international conference on Management of data, pp. 1-2.
Rossbach, C., Hofmann, O., & Witchel, E. (2009, June). Is transactional memory programming actually easier? In Proceedings of the 8th Annual Workshop on.
Saha, B., Adl-Tabatabai, A., & Jacobson, Q. (2006). Architectural support for software transactional memory. 39th International Symposium on Microarchitecture(MICRO).
Shavit, N., & Dice, D. (2010). TLRW: Return of the read-write lock. SPAA 2010 Conference Program, pp. 284-293.
Shavit, N., & Touitou, D. (1995). Software transactional memory. Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, pp. 204-213.
Shriraman, A., Marathe, V., Dwarkadas, S., Scott, M., Eisenstat, D., Heriot, C., et al. (2006). Hardware acceleration of software transactional memory. TRANSACT.
Spear, F., Marathe, J., Dalessandro, L., & Scott, L. (2007). Privatization techniques for software transactional memory. PODC 2007 Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pp. 338-339.
Steffan, J., & Mowry, T. (1998). The potential for using thread-level data speculation to faciliate automatic parallelization. In Proceedings of the International Symposium on High-Performance Computer Architecture, pp. 2-13.
Sundaramoorthy, K., Purser, Z., & Rotenburg, E. (2000). Slipstream processors: improving both performance and fault tolerance. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating systems, pp. 257-268.
Tim Harris, Simon Marlow, Simon Peyton-Jones, & Maurice Herlihy. (2005). Composable memory transactions. Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 91-100.
Wikipedia. (2012, January 3). Hyper-threading. Retrieved from Wikipedia: http://en.wikipedia.org/wiki/Hyper-threading
Wikipedia. (2012, January 10). Quake III Arena. Retrieved from wikipedia: http://en.wikipedia.org/wiki/Quake_III_Arena
Wikipedia. (2012, January 6). Team Fortress 2. Retrieved from Wikipedia: http://en.wikipedia.org/wiki/Team_Fortress_2
Zilles, C., Emer, J., & Sohi, G. (1999). The use of multithreading for exeption handling. In Proceedings of the Annual international Symposium on Microarchitecture, pp. 219-229.
Zyulkyarov, F., Gajinov, V., Unsal, O., Cristal, A., Ayguade, E., Harris, T., et al. (2009, April 4). Atomic quake: using transactional memory in an interactive multiplayer game server. PPoPP '09 Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 25-34.
Zyulkyarov, F., Stipic, S., Harris, T., Unsal, O., Cristal, A., Hur, I., et al. (2010). Discovering and understanding performance bottlenecks in transactional applications. PACT 2010 Proceedings of the 19th international conference on Parallel architectures and compilation techniques, pp. 285-294.
蘇盈誠. (2011). A Case Study on Leveraging the Strengths of Transactional Memory While Maintaining System Performance. NCKU, Department of Accountancy, Tainan City.

中文部分
松浦健一郎. (2005年2月). 射擊遊戲演算法與程式原理Shooting game algorithm maniax. 新北市: 博碩文化.
施松村, 陸茵, 楊名全, DeitelH. M., DeitelP. J., & NietoT. R. (2009). VB.NET程式設計藝術(Visual Basic .NET how to program) (第 第二版 版). 台北市: 台灣培生教育出版股份有限公司.
葉思義, 李震宇, 盧元峰, & KirmseAndrew. (2006). 遊戲程式設計精華IV Game programming gems 4. 台北市: 碁峰.
劉非予, 蔡瑞彌, & ReedAaron. (2009年July月). XNA 3.0實戰手冊. 台北市: 悅知文化、精誠資訊股份有限公司.
龍俊成, 葉琮哲, 吳昌隆, & 許克寬. (2005). 三維空間第一人稱射擊遊戲實作 - 使用DirectX. 逢甲大學, 資訊工程系, 台中市.