research-article

Public Access

GraphTM: An Efficient Framework for Supporting Transactional Memory in a Distributed Environment

Authors:

Gokarna SharmaAuthors Info & Claims

ICDCN '20: Proceedings of the 21st International Conference on Distributed Computing and Networking

Article No.: 11, Pages 1 - 10

https://doi.org/10.1145/3369740.3369774

Published: 19 February 2020 Publication History

Abstract

In this paper, we present GraphTM, an efficient and scalable framework for processing transactions in a distributed environment. The distributed environment is modeled as a graph where each node of the graph is a processing node that issues transactions. The objects that transactions use to execute are also on the graph nodes (the initial placement may be arbitrary). The transactions execute on the nodes which issue them after collecting all the objects that they need following the data-flow model of computation. This collection is done by issuing the requests for the objects as soon as transaction starts and wait until all required objects for the transaction come to the requesting node. The challenge is on how to schedule the transactions so that two crucial performance metrics, namely (i) total execution time to commit all the transactions, and (ii) total communication cost involved in moving the objects to the requesting nodes, are minimized. We implemented GraphTM in Java and assessed its performance through 3 micro-benchmarks and 5 complex benchmarks from STAMP benchmark suite on 5 different network topologies, namely, clique, line, grid, cluster, and star, that make an underlying communication network for a representative set of distributed systems commonly used in practice. The results show the efficiency and scalability of our approach.

References

[1]

Robert L. Bocchino, Vikram S. Adve, and Bradford L. Chamberlain. 2008. Software transactional memory for large scale clusters. In PPoPP. 247--258.

[2]

Costas Busch, Maurice Herlihy, Miroslav Popovic, and Gokarna Sharma. 2017. Fast Scheduling in Distributed Transactional Memory. In SPAA. ACM, 173--182.

[3]

Costas Busch, Maurice Herlihy, Miroslav Popovic, and Gokarna Sharma. 2018. Time-communication impossibility results for distributed transactional memory. Distributed Computing 31, 6 (2018), 471--487.

Digital Library

[4]

Harold W. Cain, Maged M. Michael, Brad Frey, Cathy May, Derek Williams, and Hung Q. Le. 2013. Robust architectural support for transactional memory in the power architecture. In ISCA. 225--236.

[5]

Paolo Costa, Hitesh Ballani, Kaveh Razavi, and Ian Kash. 2015. R2C2: A Network Stack for Rack-scale Computers. In SIGCOMM. 551--564.

[6]

Maria Couceiro, Paolo Romano, Nuno Carvalho, and Luís Rodrigues. 2009. D2STM: Dependable Distributed Software Transactional Memory. In PRDC. 307--313.

[7]

Luke Dalessandro, Michael F. Spear, and Michael L. Scott. 2010. NOrec: Streamlining STM by Abolishing Ownership Records. In PPOPP. 67--78. https://doi.org/10.1145/1693453.1693464

Digital Library

[8]

Pascal Felber, Christof Fetzer, Patrick Marlier, and Torvald Riegel. 2010. Time-Based Software Transactional Memory. IEEE Trans. Parallel Distrib. Syst. 21, 12 (2010), 1793--1807.

Digital Library

[9]

Pascal Felber, Christof Fetzer, and Torvald Riegel. 2008. Dynamic performance tuning of word-based software transactional memory. In PPOPP. 237--246.

[10]

Wilson W. L. Fung, Inderpreet Singh, Andrew Brownsword, and Tor M. Aamodt. 2011. Hardware transactional memory for GPU architectures. In MICRO. 296--307.

[11]

Vincent Gramoli, Rachid Guerraoui, and Vasileios Trigonakis. 2018. TM2C: a software transactional memory for many-cores. Distributed Computing 31, 5 (2018), 367--388.

Digital Library

[12]

Ruud Haring, Martin Ohmacht, Thomas Fox, Michael Gschwind, David Satterfield, Krishnan Sugavanam, Paul Coteus, Philip Heidelberger, Matthias Blumrich, Robert Wisniewski, Alan Gara, George Chiu, Peter Boyle, Norman Chist, and Changhoan Kim. 2012. The IBM Blue Gene/Q Compute Chip. IEEE Micro 32, 2 (2012), 48--60.

Digital Library

[13]

Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer, III. 2003. Software Transactional Memory for Dynamic-sized Data Structures. In PODC. 92--101.

[14]

Maurice Herlihy and J. Eliot B. Moss. 1993. Transactional Memory: Architectural Support for Lock-free Data Structures. In ISCA. 289--300.

Digital Library

[15]

Maurice Herlihy and Ye Sun. 2007. Distributed transactional memory for metric-space networks. Distributed Computing 20, 3 (2007), 195--208.

Digital Library

[16]

Sachin Hirve, Roberto Palmieri, and Binoy Ravindran. 2014. Archie: a speculative replicated transactional system. In Middleware. 265--276.

[17]

Intel. 2012. http://software.intel.com/en-us/blogs/2012/02/07/transactional-synchronization-in-haswell. (2012).

[18]

Christos Kotselidis, Mohammad Ansari, Kim Jarvis, Mikel Lujan, Chris Kirkham, and Ian Watson. 2008. DiSTM: A software transactional memory framework for clusters. In ICPP. 51--58.

[19]

Dawei Li, Jie Wu, Zhiyong Liu, and Fa Zhang. 2017. Towards the Tradeoffs in Designing Data Center Network Architectures. IEEE Transactions on Parallel and Distributed Systems 28, 1 (Jan. 2017), 260--273.

Digital Library

[20]

Kaloian Manassiev, Madalin Mihailescu, and Cristiana Amza. 2006. Exploiting Distributed Version Concurrency in a Transactional Memory Cluster. In PPoPP. 198--208.

[21]

Sudhanshu Mishra, Alexandru Turcu, Roberto Palmieri, and Binoy Ravindran. 2013. HyflowCPP: A Distributed Transactional Memory Framework for C++. In NCA. 219--226.

[22]

Mohamed Mohamedin, Sebastiano Peluso, Masoomeh Javidi Kishi, Ahmed Hassan, and Roberto Palmieri. 2018. Nemo: NUMA-aware Concurrency Control for Scalable Transactional Memory. In ICPP. 38:1--38:10.

[23]

Takuya Nakaike, Rei Odaira, Matthew Gaudet, Maged M. Michael, and Hisanobu Tomari. 2015. Quantitative comparison of hardware transactional memory for Blue Gene/Q, zEnterprise EC12, Intel Core, and POWER8. In ISCA. 144--157.

[24]

Sebastiano Peluso, Pedro Ruivo, Paolo Romano, Francesco Quaglia, and Luís Rodrigues. 2012. When Scalability Meets Consistency: Genuine Multiversion Update-Serializable Partial Data Replication. In ICDCS. 455--465.

[25]

Mohamed M. Saad and Binoy Ravindran. 2011. HyFlow: A High Performance Distributed Software Transactional Memory Framework. In HPDC. 265--266.

[26]

Nir Shavit and Dan Touitou. 1997. Software Transactional Memory. Distrib. Comput. 10, 2 (1997), 99--116.

[27]

Alexandru Turcu, Binoy Ravindran, and Roberto Palmieri. 2013. Hyflow2: A High Performance Distributed Transactional Memory Framework in Scala. In PPPJ. 79--88.

[28]

Paweł T. Wojciechowski and Konrad Siek. 2016. Atomic RMI 2: Distributed Transactions for Java. In AGERE. 61--69.

[29]

Bo Zhang and Binoy Ravindran. 2010. Brief announcement: on enhancing concurrency in distributed transactional memory. In PODC. 73--74.

[30]

Bo Zhang, Binoy Ravindran, and Roberto Palmieri. 2014. Distributed Transactional Contention Management as the Traveling Salesman Problem. In SIROCCO. 54--67.

Cited By

Busch CChlebus BHerlihy MPopovic MPoudel PSharma G(2023)Flexible scheduling of transactional memory on treesTheoretical Computer Science10.1016/j.tcs.2023.114184(114184)Online publication date: Sep-2023
https://doi.org/10.1016/j.tcs.2023.114184
Busch CChlebus BHerlihy MPopovic MPoudel PSharma G(2022)Flexible Scheduling of Transactional Memory on TreesStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_10(146-163)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21017-4_10

Index Terms

GraphTM: An Efficient Framework for Supporting Transactional Memory in a Distributed Environment
1. Computing methodologies
  1. Distributed computing methodologies
    1. Distributed algorithms
  2. Modeling and simulation
    1. Simulation evaluation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms
  2. Models of computation
    1. Concurrency
      1. Distributed computing models

Recommendations

Processing Distributed Transactions in a Predefined Order
ICDCN '21: Proceedings of the 22nd International Conference on Distributed Computing and Networking

Consider distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then ...
CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing

Transactional memory (TM) is a key concurrent programming abstraction. Several software-based transactional memory (STM) implementations have been developed in recent years. All STM implementations must guarantee transaction atomicity but different STM ...
Flexible Scheduling of Transactional Memory on Trees
Stabilization, Safety, and Security of Distributed Systems
Abstract
We study the efficiency of executing transactions in a distributed transactional memory system. The system is modeled as a wired network with the topology of a tree. Contrary to previous approaches, we allow the flexibility for both transactions ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDCN '20: Proceedings of the 21st International Conference on Distributed Computing and Networking

January 2020

460 pages

ISBN:9781450377515

DOI:10.1145/3369740

Copyright © 2020 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]

In-Cooperation

ACM: Association for Computing Machinery
Jadavpur University: Jadavpur University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 February 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

National Science Foundation

Conference

ICDCN 2020

ICDCN 2020: 21st International Conference on Distributed Computing and Networking

January 4 - 7, 2020

Kolkata, India

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
160
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)5

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Busch CChlebus BHerlihy MPopovic MPoudel PSharma G(2023)Flexible scheduling of transactional memory on treesTheoretical Computer Science10.1016/j.tcs.2023.114184(114184)Online publication date: Sep-2023
https://doi.org/10.1016/j.tcs.2023.114184
Busch CChlebus BHerlihy MPopovic MPoudel PSharma G(2022)Flexible Scheduling of Transactional Memory on TreesStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_10(146-163)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21017-4_10

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents