research-article

Atomic quake: using transactional memory in an interactive multiplayer game server

Authors:

Ferad Zyulkyarov,

Vladimir Gajinov,

Osman S. Unsal,

Adrián Cristal,

Eduard Ayguadé,

Mateo ValeroAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 4

Pages 25 - 34

https://doi.org/10.1145/1594835.1504183

Published: 14 February 2009 Publication History

Abstract

Transactional Memory (TM) is being studied widely as a new technique for synchronizing concurrent accesses to shared memory data structures for use in multi-core systems. Much of the initial work on TM has been evaluated using microbenchmarks and application kernels; it is not clear whether conclusions drawn from these workloads will apply to larger systems. In this work we make the first attempt to develop a large, complex, application that uses TM for all of its synchronization. We describe how we have taken an existing parallel implementation of the Quake game server and restructured it to use transactions. In doing so we have encountered examples where transactions simplify the structure of the program. We have also encountered cases where using transactions occludes the structure of the existing code. Compared with existing TM benchmarks, our workload exhibits non-block-structured transactions within which there are I/Ooperations and system call invocations. There are long and short running transactions (200-1.3M cycles) with small and large read and write sets (a few bytes to 1.5MB). There are nested transactions reaching up to 9 levels at runtime. There are examples where error handling and recovery occurs inside transactions. There are also examples where data changes between being accessed transactionally and accessed non-transactionally. However, we did not see examples where the kind of access to one piece of data depended on the value of another.

References

[1]

M. Abadi, T. Harris, and M. Mehrara. Transactional memory with strong atomicity using off-the-shelf memory protection hardware. In PPoPP '09: Proc. 14th ACM SIGPLAN symposium on principles and practice of parallel programming, Feb. 2009.

Digital Library

[2]

A. Abdelkhalek and A. Bilas. Parallelization and performance of interactive multiplayer game servers. In IPDPS '04: Proc. 18th international parallel and distributed processing symposium, pages 72--81, Apr. 2004.

[3]

A.-R. Adl-Tabatabai, B. T. Lewis, V. Menon, B. R. Murphy, B. Saha, and T. Shpeisman. Compiler and runtime support for efficient software transactional memory. In PLDI '06: Proc. 2006 ACM SIGPLAN conference on programming language design and implementation, pages 26--37, June 2006.

Digital Library

[4]

L. Baugh, N. Neelakantam, and C. Zilles. Using hardware memory protection to build a high-performance, strongly-atomic hybrid transactional memory. In ISCA '08: Proc. 35th international symposium on computer architecture, pages 115--126, June 2008.

Digital Library

[5]

C. Blundell, E. C. Lewis, and M. M. K. Martin. Deconstructing transactional semantics: The subtleties of atomicity. In WDDD '05: Proc. 4th workshop on duplicating, deconstructing and debunking, pages 48--55, June 2005.

[6]

C. Blundell, E. C. Lewis, and M. M. K. Martin. Unrestricted transactional memory: Supporting I/O and system calls within transactions. Technical Report TR-CIS-06-09, University of Pennsylvania, Department of Computer and Information Science, May 2006.

[7]

C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC '08: Proc. 11th IEEE International Symposium on Workload Characterization, September 2008.

[8]

M. J. Carey, D. J. DeWitt, C. Kant, and J. F. Naughton. A status report on the OO7 OODBMS benchmarking effort. In OOPSLA '94: Proc. 9th annual conference on object-oriented programming systems, language, and applications, pages 414--426, Oct. 1994.

Digital Library

[9]

W. Chuang, S. Narayanasamy, G. Venkatesh, J. Sampson, M. V. Biesbrouck, G. Pokam, B. Calder, and O. Colavin. Unbounded page-based transactional memory. In ASPLOS '06: Proc. 12th international conference on architectural support for programming languages and operating systems, pages 347--358, Oct. 2006.

Digital Library

[10]

P. Damron, A. Fedorova, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Hybrid transactional memory. In ASPLOS '06: Proc. 12th international conference on architectural support for programming languages and operating systems, pages 336--346, Oct. 2006.

Digital Library

[11]

D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In DISC '06: Proc. 20th international symposium on distributed computing, pages 194--208, Sept. 2006.

Digital Library

[12]

R. Guerraoui, M. Kapalka, and J. Vitek. STMBench7: A benchmark for software transactional memory. In EuroSys '07: Proc. 2nd European systems conference, Mar. 2007.

Digital Library

[13]

D. Harmanci, P. Felber, M. Sukraut, and C. Fetzer. TMunit: A transactional memory unit testing and workload generation tool. Technical Report RR-I-08-08.1, Université de Neuchâtel, Institut d'Informatique, Aug. 2008.

[14]

T. Harris, S. Marlow, S. Peyton Jones, and M. Herlihy. Composable memory transactions. In PPoPP '05: Proc. 10th ACM SIGPLAN symposium on principles and practice of parallel programming, pages 48--60, Feb 2005.

Digital Library

[15]

T. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing memory transactions. In PLDI '06: Proc. 2006 ACM SIGPLAN conference on programming language design and implementation, pages 14--25, June 2006.

Digital Library

[16]

M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP '08: Proc. 13th ACM SIGPLAN symposium on principles and practice of parallel programming, pages 207--216, Feb. 2008.

Digital Library

[17]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software transactional memory for dynamic-sized data structures. In PODC '03: Proc. 22nd Annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, pages 92--101, July 2003.

Digital Library

[18]

M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA '93: Proc. 20th Annual International Symposium on Computer Architecture, pages 289--300, May 1993.

Digital Library

[19]

ID Software. Quake. http://www.idsoftware.com/games/quake/quake.

[20]

Intel Corporation. Intel C++ STM Compiler Prototype Edition 2.0 Language Extensions and User's Guide, Mar. 2008. http://softwarecommunity.intel.com/isn/Downloads/whatif/stm/Intel-C-STM-Language-Extensions-Users-Guide-V2_0.pdf.

[21]

M. Isard and A. Birrell. Automatic mutual exclusion. In Proc. 11th Workshop on Hot Topics in Operating Systems, May 2007.

Digital Library

[22]

S.-Y. Lee and R.-L. Liou. A multi-granularity locking model for concurrency control in object-oriented database systems. IEEE Transactions on Knowledge and Data Engineering, pages 144--156, Feb. 1996.

Digital Library

[23]

V. Menon, S. Balensiefer, T. Shpeisman, A.-R. Adl-Tabatabi, R. L. Hudson, B. Saha, and A. Welc. Practical weak-atomicity semantics for Java STM. In SPAA '08: Proc. 20th annual symposium on parallelism in algorithms and architectures, pages 314--325, June 2008.

Digital Library

[24]

Y. Ni, V. Menon, A.-R. Adl-Tabatabai, A. L. Hoskin, J. E. B. Moss, B. Saha, and T. Shpeisman. Open nesting in software transactional memory. In PPoPP '07: Proc. 12th ACM SIGPLAN symposium on principles and practice of parallel programming, pages 68--78, Mar. 2007.

Digital Library

[25]

Y. Ni, A. Welc, A.-R. Adl-Tabatabai, M. Bach, S. Berkowits, J. Cownie, R. Geva, S. Kozhukow, R. Narayanaswamy, J. Olivier, S. Preis, B. Saha, A. Tal, and X. Tian. Design and implementation of transactional constructs for C/C++. In OOPSLA '08: Proc. 23rd ACM SIGPLAN conference on Object oriented programming systems languages and applications, pages 195--212, Oct. 2008.

Digital Library

[26]

C. Perfumo, N. Sonmez, S. Stipic, A. Cristal, O. Unsal, T. Harris, and M. Valero. The limits of software transactional memory (STM): Dissecting Haskell STM applications on a many-core environment. In CF '08: Proc. ACM international conference on computing frontiers, pages 67--78, May 2008.

Digital Library

[27]

R. Rajwar, M. Herlihy, and K. Lai. Virtualizing transactional memory. In ISCA '05: Proc. 32nd annual international symposium on computer architecture, pages 494--505, June 2005.

Digital Library

[28]

M. F. Ringenburg and D. Grossman. AtomCaml: first-class atomicity via rollback. In ICFP '05: Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, pages 92--104, New York, NY, USA, 2005. ACM.

Digital Library

[29]

T. Shpeisman, V. Menon, A.-R. Adl-Tabatabi, S. Balensiefer, D. Grossman, R. L. Hudson, K. F. Moore, and B. Saha. Enforcing isolation and ordering in STM. In PLDI '07: Proc. ACM SIGPLAN conference on programming language design and implementation, pages 78--88, June 2007.

Digital Library

[30]

A. Shriraman, S. Dwarkadas, and M. L. Scott. Flexible decoupled transactional memory support. In Proceedings of the 35th International Symposium on Computer Architecture (ISCA), pages 139--150, June 2008.

Digital Library

[31]

M. F. Spear, V. J. Marathe, L. Dalessandro, and M. L. Scott. Privatization techniques for software transactional memory. In Proc. 26th ACM Symp. on Principles of Distributed Computing (PODC), pages 338--339. Aug. 2007.

Digital Library

[32]

A. S. Tanenbaum. Distributed Operating Systems. 1994.

Digital Library

[33]

C. Wang, W.-Y. Chen, Y. Wu, B. Saha, and A.-R. Adl-Tabatabai. Code generation and optimization for transactional memory constructs in an unmanaged language. In CGO '07: Proc. 2007 international symposium on code generation and optimization, pages 34--48, Mar. 2007.

Digital Library

[34]

A. Welc, B. Saha, and A.-R. Adl-Tabatabi. Irrevocable transactions and their applications. In SPAA '08: Proc. 20th annual symposium on parallelism in algorithms and architectures, pages 285--296, June 2008.

Digital Library

[35]

S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In ISCA '95: Proc. 22nd annual international symposium on computer architecture, pages 24--38, June 1995.

Digital Library

[36]

F. Zyulkyarov, S. Cvijic, O. Unsal, A. Cristal, E. Ayguade, T. Harris, and M. Valero. WormBench: A configurable workload for evaluating transactional memory systems. In MEDEA '08: Proc. 2008 workshop on memory performance: dealing with applications, systems and architecture, Oct. 2008.

Digital Library

Cited By

Yu JGe XJaeger TFletcher CCui W(2022)Pagoda: Towards Binary Code Privacy Protection with SGX-based Execute-Only Memory2022 IEEE International Symposium on Secure and Private Execution Environment Design (SEED)10.1109/SEED55351.2022.00019(133-144)Online publication date: Sep-2022
https://doi.org/10.1109/SEED55351.2022.00019
Li CGuan LLin JLuo BCai QJing JWang J(2021)Mimosa: Protecting Private Keys Against Memory Disclosure Attacks Using Hardware Transactional MemoryIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2019.289766618:3(1196-1213)Online publication date: 1-May-2021
https://doi.org/10.1109/TDSC.2019.2897666
Rohloff AAllen ZLin KOkrend JNie CLiu YTseng H(2021)OpenUVR: an Open-Source System Framework for Untethered Virtual Reality Applications2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS52030.2021.00026(223-236)Online publication date: May-2021
https://doi.org/10.1109/RTAS52030.2021.00026
Show More Cited By

Index Terms

Atomic quake: using transactional memory in an interactive multiplayer game server
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

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

Transactional Memory (TM) is being studied widely as a new technique for synchronizing concurrent accesses to shared memory data structures for use in multi-core systems. Much of the initial work on TM has been evaluated using microbenchmarks and ...
WFR-TM

Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies
ASPLOS '13

Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 44, Issue 4

PPoPP '09

April 2009

294 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1594835

Issue’s Table of Contents

PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming
February 2009
322 pages
ISBN:9781605583976
DOI:10.1145/1504176
General Chair:
Daniel Reed
Microsoft Research, USA
,
Program Chair:
Vivek Sarkar
Rice University, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 February 2009

Published in SIGPLAN Volume 44, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
565
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)4

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yu JGe XJaeger TFletcher CCui W(2022)Pagoda: Towards Binary Code Privacy Protection with SGX-based Execute-Only Memory2022 IEEE International Symposium on Secure and Private Execution Environment Design (SEED)10.1109/SEED55351.2022.00019(133-144)Online publication date: Sep-2022
https://doi.org/10.1109/SEED55351.2022.00019
Li CGuan LLin JLuo BCai QJing JWang J(2021)Mimosa: Protecting Private Keys Against Memory Disclosure Attacks Using Hardware Transactional MemoryIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2019.289766618:3(1196-1213)Online publication date: 1-May-2021
https://doi.org/10.1109/TDSC.2019.2897666
Rohloff AAllen ZLin KOkrend JNie CLiu YTseng H(2021)OpenUVR: an Open-Source System Framework for Untethered Virtual Reality Applications2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS52030.2021.00026(223-236)Online publication date: May-2021
https://doi.org/10.1109/RTAS52030.2021.00026
Maruf AYang ZDavis BKim DWong JDurand MBhimani J(2021)Understanding Flash-Based Storage I/O Behavior of Games2021 IEEE 14th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD53861.2021.00068(521-526)Online publication date: Sep-2021
https://doi.org/10.1109/CLOUD53861.2021.00068
Park SAhmad ALee BLigatti JOu XKatz JVigna G(2020)BlackMirror: Preventing Wallhacks in 3D Online FPS GamesProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security10.1145/3372297.3417890(987-1000)Online publication date: 30-Oct-2020
https://dl.acm.org/doi/10.1145/3372297.3417890
Kordic BPopovic MPopovic MGoldstein MAmitay MDayan D(2019)A Protein Structure Prediction Program Architecture Based on a Software Transactional MemoryProceedings of the 6th Conference on the Engineering of Computer Based Systems10.1145/3352700.3352701(1-9)Online publication date: 2-Sep-2019
https://dl.acm.org/doi/10.1145/3352700.3352701
Yu ZZuo YZhao Y(2019)Convoider: A Concurrency Bug Avoider Based on Transparent Software Transactional MemoryInternational Journal of Parallel Programming10.1007/s10766-019-00642-1Online publication date: 12-Sep-2019
https://doi.org/10.1007/s10766-019-00642-1
Konczak JWojciechowski PGuerraoui R(2017)Operation-Level Wait-Free Transactional Memory with Support for Irrevocable OperationsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.273487928:12(3570-3583)Online publication date: 1-Dec-2017
https://doi.org/10.1109/TPDS.2017.2734879
Smiljković VÜnsal OCristal AValero M(2017)Determinism at Standard-Library Level in TM-Based ApplicationsInternational Journal of Parallel Programming10.1007/s10766-015-0383-445:1(17-29)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10766-015-0383-4
Bihari BYang UWong Mde Supinski B(2016)Transactional Memory for Algebraic Multigrid SmoothersOpenMP: Memory, Devices, and Tasks10.1007/978-3-319-45550-1_23(320-335)Online publication date: 21-Sep-2016
https://doi.org/10.1007/978-3-319-45550-1_23
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents