QuakeTM: parallelizing a complex sequential application using transactional memory

ABSTRACT

"Is transactional memory useful?" is the question that cannot be answered until we provide substantial applications that can evaluate its capabilities. While existing TM applications can partially answer the above question, and are useful in the sense that they provide a first-order TM experimentation framework, they serve only as a proof of concept and fail to make a conclusive case for wide adoption by the general computing community.

This paper presents QuakeTM, a multiplayer game server; a complex real life TM application that was parallelized from the sequential version with TM-specific considerations in mind. QuakeTM consists of 27,600 lines of code spread across 49 files and exhibits irregular parallelism for which a task parallel model fits well. We provide a coarse-grained TM implementation characterized with eight large transactional blocks as well as a fine-grained implementation which consists of 58 different critical sections and compare these two approaches. In spite of the fact that QuakeTM scales, we show that more effort is needed to decrease the overhead and the abort rate of current software transactional memory systems to achieve a good performance. We give insights into development challenges, suggest techniques to solve them and provide extensive analysis of the transactional behavior of QuakeTM, with an emphasis and discussion of the TM promise of making parallel programming easier.

REFERENCES

• 1: Martín Abadi , Tim Harris , Mojtaba Mehrara, Transactional memory with strong atomicity using off-the-shelf memory protection hardware, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 2: A. Abdelkhalek and A. Bilas. Parallelization and performance of interactive multiplayer game servers. In IPDPS'04: Proc. 18thIinternational Parallel and Distributed Processing Symposium, Apr. 2004, pages 72--81.
• 3: A. Abdelkhalek, A. Bilas and A. Moshovos. Behavior and performance of interactive multi-player game servers. In ISPASS'01: Proc. of the 2001 International IEEE Symposium on Performance Analysis of Systems and Software, Nov. 2001, pages 355--366.
• 4: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 5: Mohammad Ansari , Christos Kotselidis , Ian Watson , Chris Kirkham , Mikel Luján , Kim Jarvis, Lee-TM: A Non-trivial Benchmark Suite for Transactional Memory, Proceedings of the 8th international conference on Algorithms and Architectures for Parallel Processing, p.196-207, June 09-11, 2008, Agia Napa, Cyprus [doi>10.1007/978-3-540-69501-1_21]
• 6: L. Dalessandro, V. J. Marathe, M. F. Spear and M. L. Scott. Capabilities and Limitations of Library-Based Software Transactional Memory in C++. In TRANSACT'07: Proc. 2nd ACM SIGPLAN Workshop on Transactional Computing, Aug 2007.
• 7: Henry Fuchs , Gregory D. Abram , Eric D. Grant, Near real-time shaded display of rigid objects, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.65-72, July 25-29, 1983, Detroit, Michigan, United States
• 8: Rachid Guerraoui , Michal Kapalka , Jan Vitek, STMBench7: a benchmark for software transactional memory, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 9: Maurice Herlihy , Eric Koskinen, Transactional boosting: a methodology for highly-concurrent transactional objects, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345237]
• 10: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 11: Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 12: M. McGuire. Quake 2 BSP File Format. http://www.flipcode.com/archives/Quake_2_BSP_File_Format.shtml
• 13: C. C. Minh, J. Chung, C. Kozyrakis and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC'08: Proc. 11th IEEE International Symp. on Workload Characterization, Sep. 2008, pp. 35--46.
• 14: Yang Ni , Adam Welc , Ali-Reza Adl-Tabatabai , Moshe Bach , Sion Berkowits , James Cownie , Robert Geva , Sergey Kozhukow , Ravi Narayanaswamy , Jeffrey Olivier , Serguei Preis , Bratin Saha , Ady Tal , Xinmin Tian, Design and implementation of transactional constructs for C/C++, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 15: Cristian Perfumo , Nehir Sönmez , Srdjan Stipic , Osman Unsal , Adrián Cristal , Tim Harris , Mateo Valero, The limits of software transactional memory (STM): dissecting Haskell STM applications on a many-core environment, Proceedings of the 5th conference on Computing frontiers, May 05-07, 2008, Ischia, Italy [doi>10.1145/1366230.1366241]
• 16: Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123001]
• 17: Michael L. Scott , Michael F. Spear , Luke Dalessandro , Virendra J. Marathe, Delaunay Triangulation with Transactions and Barriers, Proceedings of the 2007 IEEE 10th International Symposium on Workload Characterization, p.107-113, September 27-29, 2007 [doi>10.1109/IISWC.2007.4362186]
• 18: Cheng Wang , Wei-Yu Chen , Youfeng Wu , Bratin Saha , Ali-Reza Adl-Tabatabai, Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language, Proceedings of the International Symposium on Code Generation and Optimization, p.34-48, March 11-14, 2007 [doi>10.1109/CGO.2007.4]
• 19: Adam Welc , Bratin Saha , Ali-Reza Adl-Tabatabai, Irrevocable transactions and their applications, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378584]
• 20: Ferad Zyulkyarov , Vladimir Gajinov , Osman S. Unsal , Adrián Cristal , Eduard Ayguadé , Tim Harris , Mateo Valero, Atomic quake: using transactional memory in an interactive multiplayer game server, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 21: Richard M. Yoo , Yang Ni , Adam Welc , Bratin Saha , Ali-Reza Adl-Tabatabai , Hsien-Hsin S. Lee, Kicking the tires of software transactional memory: why the going gets tough, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378582]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Design, Experimentation, Performance

Keywords:
game server, transactional memory