More Web Proxy on the site http://driver.im/

research-article

Flexible scheduling of transactional memory on trees

Authors:

Bogdan S. Chlebus,

Maurice Herlihy,

Miroslav Popovic,

Gokarna SharmaAuthors Info & Claims

Volume 978, Issue C

https://doi.org/10.1016/j.tcs.2023.114184

Published: 02 November 2023 Publication History

Abstract

We study the efficiency of executing transactions in a distributed transactional memory system. The system is modeled as a static network with the topology of a tree. Contrary to previous approaches, we allow the flexibility for both transactions and their requested objects to move simultaneously among the nodes in the tree. Given a batch of transactions and shared objects, the goal is to produce a schedule of executing the transactions that minimizes the cost of moving the transactions and the objects in the tree. We consider both techniques for accessing a remote object with respect to a transaction movement. In the first technique, instead of moving, transactions send control messages to remote nodes where the requested objects are gathered. In the second technique, the transactions migrate to the remote nodes where the objects are gathered to access them. When all the transactions use a single object, we give an offline algorithm that produces optimal schedules for both techniques. For the general case of multiple objects per transaction, in the first technique, we obtain a schedule with a constant-factor approximation of optimal. In the second technique, with transactions migrating, we give a k factor approximation where k is the maximum number of objects per transaction.

Highlights

•

Studies transaction scheduling problem on Trees in the dual-flow model.

•

Allows flexibility for moving both transactions and objects during execution.

•

SINGLE-OBJECT algorithm provides optimal communication cost when all transactions access the same single shared object.

•

MULTIPLE-OBJECTS-CTRLMSG algorithm provides the schedule with O ( 1 )-approximation in communication cost.

•

MULTIPLE-OBJECTS-TXMIGR algorithm finds a schedule with O ( k )-approximation in communication cost.

References

[1]

C. Busch, B.S. Chlebus, M. Herlihy, M. Popovic, P. Poudel, G. Sharma, Flexible scheduling of transactional memory on trees, in: Stabilization, Safety, and Security of Distributed Systems - 24th International Symposium, in: LNCS, vol. 13751, SSS 2022, Clermont-Ferrand, France, November 15–17, 2022, Springer, 2022, pp. 146–163.

[2]

M. Herlihy, J.E.B. Moss, Transactional memory: architectural support for lock-free data structures, in: Proceedings of the 20th Annual International Symposium on Computer Architecture, ACM, 1993, pp. 289–300.

[3]

N. Shavit, D. Touitou, Software transactional memory, Distrib. Comput. 10 (2) (1997) 99–116.

[4]

P. Hammarlund, A.J. Martinez, A.A. Bajwa, D.L. Hill, E.G. Hallnor, H. Jiang, M.G. Dixon, M. Derr, M. Hunsaker, R. Kumar, R.B. Osborne, R. Rajwar, R. Singhal, R. D'Sa, R. Chappell, S. Kaushik, S. Chennupaty, S. Jourdan, S. Gunther, T. Piazza, T. Burton, Haswell: the fourth-generation Intel core processor, IEEE MICRO 34 (2) (2014) 6–20.

[5]

R.A. Haring, M. Ohmacht, T.W. Fox, M. Gschwind, D.L. Satterfield, K. Sugavanam, P. Coteus, P. Heidelberger, M.A. Blumrich, R.W. Wisniewski, A. Gara, G.L. Chiu, P.A. Boyle, N.H. Christ, C. Kim, The IBM blue gene/q compute chip, IEEE MICRO 32 (2) (2012) 48–60.

[6]

T. Nakaike, R. Odaira, M. Gaudet, M.M. Michael, H. Tomari, Quantitative comparison of hardware transactional memory for Blue Gene/Q, zEnterprise EC12, Intel Core, and POWER8, in: Proceedings of the 42nd Annual International Symposium on Computer Architecture, ACM, 2015, pp. 144–157.

[7]

H.W. Cain, M.M. Michael, B. Frey, C. May, D. Williams, H.Q. Le, Robust architectural support for transactional memory in the power architecture, in: Proceedings of the 40th Annual International Symposium on Computer Architecture (ISCA 2013), ACM, 2013, pp. 225–236.

[8]

M. Herlihy, Y. Sun, Distributed transactional memory for metric-space networks, Distrib. Comput. 20 (3) (2007) 195–208.

[9]

G. Sharma, C. Busch, Distributed transactional memory for general networks, Distrib. Comput. 27 (5) (2014) 329–362.

[10]

K. Siek, P.T. Wojciechowski, Atomic RMI: a distributed transactional memory framework, Int. J. Parallel Program. 44 (3) (2016) 598–619.

[11]

J. Armstrong, Programming Erlang: Software for a Concurrent World, Pragmatic Bookshelf, 2007.

[12]

K. Hwang, J. Dongarra, G.C. Fox, Distributed and Cloud Computing: From Parallel Processing to the Internet of Things, Morgan Kaufmann Publishers, 2011.

[13]

P. Ruth, J. Rhee, D. Xu, R. Kennell, S. Goasguen, Autonomic live adaptation of virtual computational environments in a multi-domain infrastructure, in: Proceedings of the 3rd International Conference on Autonomic Computing (ICAC 2006), IEEE Computer Society, 2006, pp. 5–14.

[14]

E. Tilevich, Y. Smaragdakis, J-Orchestra: automatic Java application partitioning, in: Proceedings of the 16th European Conference on Object-Oriented Programming (ECOOP 2002), in: LNCS, vol. 2374, Springer, 2002, pp. 178–204.

[15]

K. Arnold, R. Scheifler, J. Waldo, B. O'Sullivan, A. Wollrath, Jini Specification, Addison-Wesley Longman Publishing, 1999.

[16]

M.M. Saad, B. Ravindran, Snake: control flow distributed software transactional memory, in: Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011), in: LNCS, vol. 6976, Springer, 2011, pp. 238–252.

[17]

D.E. Comer, The Cloud Computing Book: The Future of Computing Explained, Chapman and Hall/CRC, 2021.

[18]

H. Attiya, V. Gramoli, A. Milani, Directory protocols for distributed transactional memory, in: Transactional Memory, Foundations, Algorithms, Tools, and Applications, in: LNCS, vol. 8913, Springer, 2015, pp. 367–391.

[19]

C. Busch, M. Herlihy, M. Popovic, G. Sharma, Time-communication impossibility results for distributed transactional memory, Distrib. Comput. 31 (6) (2018) 471–487.

[20]

C. Busch, M. Herlihy, M. Popovic, G. Sharma, Dynamic scheduling in distributed transactional memory, in: Proceedings of the 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS 2020), IEEE, 2020, pp. 874–883.

[21]

C. Busch, M. Herlihy, M. Popovic, G. Sharma, Fast scheduling in distributed transactional memory, Theory Comput. Syst. 65 (2) (2021) 296–322.

[22]

G. Sharma, C. Busch, A load balanced directory for distributed shared memory objects, J. Parallel Distrib. Comput. 78 (2015) 6–24.

[23]

R. Palmieri, S. Peluso, B. Ravindran, Transaction execution models in partially replicated transactional memory: the case for data-flow and control-flow, in: Transactional Memory, Foundations, Algorithms, Tools, and Applications, in: LNCS, vol. 8913, Springer, 2015, pp. 341–366.

[24]

Siek, K.; Wojciechowski, P.T. : Atomic RMI 2: highly parallel pessimistic distributed transactional memory. CoRR arXiv:1606.03928 [abs].

[25]

M.M. Saad, B. Ravindran, HyFlow: a high performance distributed software transactional memory framework, in: Proceedings of the 20th ACM International Symposium on High Performance Distributed Computing (HPDC 2011), ACM, 2011, pp. 265–266.

[26]

R.L. Bocchino Jr., V.S. Adve, B.L. Chamberlain, Software transactional memory for large scale clusters, in: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP 2008), ACM, 2008, pp. 247–258.

[27]

D. Hendler, A. Naiman, S. Peluso, F. Quaglia, P. Romano, A. Suissa, Exploiting locality in lease-based replicated transactional memory via task migration, in: Proceedings of the 27th International Symposium on Distributed Computing (DISC 2013), in: LNCS, vol. 8205, Springer, 2013, pp. 121–133.

[28]

B. Zhang, B. Ravindran, R. Palmieri, Distributed transactional contention management as the traveling salesman problem, in: Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014), in: LNCS, vol. 8576, Springer, 2014, pp. 54–67.

[29]

P. Poudel, G. Sharma, GraphTM: an efficient framework for supporting transactional memory in a distributed environment, in: Proceedings of the 21st International Conference on Distributed Computing and Networking (ICDCN 2020), ACM, 2020.

[30]

S. Rai, G. Sharma, C. Busch, M. Herlihy, Load balanced distributed directories, in: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018), in: LNCS, Springer, 2018, pp. 221–238.

[31]

M. Couceiro, P. Romano, N. Carvalho, L.E.T. Rodrigues, D2STM: dependable distributed software transactional memory, in: Proceedings of the 15th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC 2009), IEEE Computer Society, 2009, pp. 307–313.

[32]

S. Hirve, R. Palmieri, B. Ravindran, Hipertm: high performance, fault-tolerant transactional memory, Theor. Comput. Sci. 688 (2017) 86–102.

[33]

T. Kobus, M. Kokocinski, P.T. Wojciechowski, Hybrid replication: state-machine-based and deferred-update replication schemes combined, in: Proceedings of the IEEE 33rd International Conference on Distributed Computing Systems (ICDCS 2013), IEEE Computer Society, 2013, pp. 286–296.

[34]

K. Manassiev, M. Mihailescu, C. Amza, Exploiting distributed version concurrency in a transactional memory cluster, in: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP 2006), ACM, 2006, pp. 198–208.

[35]

S. Peluso, P. Romano, F. Quaglia, SCORe: a scalable one-copy serializable partial replication protocol, in: Proceedings of ACM/IFIP/USENIX 13th International Middleware Conference (Middleware 2012), in: LNCS, vol. 7662, Springer, 2012, pp. 456–475.

[36]

S. Peluso, P. Ruivo, P. Romano, F. Quaglia, L.E.T. Rodrigues, When scalability meets consistency: genuine multiversion update-serializable partial data replication, in: Proceedings of the 2012 IEEE 32nd International Conference on Distributed Computing Systems, IEEE Computer Society, 2012, pp. 455–465.

[37]

C. Kotselidis, M. Ansari, K. Jarvis, M. Luján, C.C. Kirkham, I. Watson, DiSTM: a software transactional memory framework for clusters, in: Proceedings of the 2008 International Conference on Parallel Processing (ICPP 2008), IEEE Computer Society, 2008, pp. 51–58.

[38]

M. Herlihy, V. Luchangco, M. Moir, A flexible framework for implementing software transactional memory, in: Proceedings of the 21th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2006), ACM, 2006, pp. 253–262.

[39]

H. Attiya, L. Epstein, H. Shachnai, T. Tamir, Transactional contention management as a non-clairvoyant scheduling problem, Algorithmica 57 (1) (2010) 44–61.

[40]

A. Dragojevic, R. Guerraoui, A.V. Singh, V. Singh, Preventing versus curing: avoiding conflicts in transactional memories, in: Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, (PODC 2009), ACM, 2009, pp. 7–16.

[41]

R. Guerraoui, M. Herlihy, B. Pochon, Toward a theory of transactional contention managers, in: Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing (PODC 2005), ACM, 2005, pp. 258–264.

[42]

G. Sharma, C. Busch, A competitive analysis for balanced transactional memory workloads, Algorithmica 63 (1–2) (2012) 296–322.

[43]

G. Sharma, C. Busch, Window-based greedy contention management for transactional memory: theory and practice, Distrib. Comput. 25 (3) (2012) 225–248.

[44]

R.M. Yoo, H.S. Lee, Adaptive transaction scheduling for transactional memory systems, in: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2008), ACM, 2008, pp. 169–178.

[45]

A. Baldassin, R. Murari, J.P.L. de Carvalho, G. Araujo, D. Castro, J. Barreto, P. Romano, NV-PhTM: an efficient phase-based transactional system for non-volatile memory, in: Proceedings of the 26th International Conference on Parallel and Distributed Computing (Euro-Par 2020), in: LNCS, vol. 12247, Springer, 2020, pp. 477–492.

[46]

M. Liu, M. Zhang, K. Chen, X. Qian, Y. Wu, W. Zheng, J. Ren, DudeTM: building durable transactions with decoupling for persistent memory, in: Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2017), ACM, 2017, pp. 329–343.

[47]

A. Kolli, S. Pelley, A.G. Saidi, P.M. Chen, T.F. Wenisch, High-performance transactions for persistent memories, in: Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2016), ACM, 2016, pp. 399–411.

Index Terms

Flexible scheduling of transactional memory on trees

Index terms have been assigned to the content through auto-classification.

Recommendations

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 ...
Stable Scheduling in Transactional Memory
Algorithms and Complexity
Abstract
We study computer systems with transactions executed on a set of shared objects. Transactions arrive continually subjects to constrains that are framed as an adversarial model and impose limits on the average rate of transaction generation and the ...
On transactional scheduling in distributed transactional memory ystems
SSS'10: Proceedings of the 12th international conference on Stabilization, safety, and security of distributed systems

We present a distributed transactional memory (TM) scheduler called Bi-interval that optimizes the execution order of transactional operations to minimize conflicts. Bi-interval categorizes concurrent requests for a shared object into read and write ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 978, Issue C

Nov 2023

202 pages

ISSN:0304-3975

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 02 November 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents