Top

International Journal of Parallel Programming

Published in:

28-03-2016

Restart Optimization for Transactional Memory with Lazy Conflict Detection

Authors: Miloš Cvetanović, Zaharije Radivojević, Veljko Milutinović

Published in: International Journal of Parallel Programming | Issue 3/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper presents an optimization algorithm for transactional memory with lazy conflict detection. The proposed optimization attempts to minimize the execution time of restarted transactions. Minimizing happens during restart, by avoiding the re-execution of a section of a transaction that is unaffected by the restart. The proposed optimization builds on previous research and differs in that it eliminates the need for the prediction of conflicting accesses and introduces incremental context saving. Moreover, the paper introduces analytical models for estimating the execution time of transactions, with and without the restart optimization, that are developed using the continuous-time model. A critical evaluation comparing analytical models with the simulation results is discussed in the paper.

previous article Parallelization Strategies for Spatial Agent-Based Models

next article Adaptive Optimization -Minimization Solvers on GPU

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

McDonald, A., Carlstrom, B.D., Chung, J., Minh, C.C., Chafi, H., Kozyrakis, C., Olukotun, K.: Transactional memory: the hardware–software interface. IEEE Micro 27(1), 67–76 (2007)CrossRefMATH

Harris, T., Cristal, A., Unsal, O.S., Ayguade, E., Gagliardi, F., Smith, B., Valero, M.: Transactional memory: an overview. IEEE Micro 27(3), 8–29 (2007)CrossRef

Moore, K.E., Bobba, J., Moravan, M.J., Hill, M.D., Wood, D.A.: LogTM: log-based transactional memory. In: The Twelfth International Symposium on High-Performance Computer Architecture, pp. 254–265 (2006)

Ananian, C.S., Asanovic, K., Kuszmaul, B.C., Leiserson, C.E., Lie, S.: Unbounded transactional memory. IEEE Micro 26(1), 59–69 (2006)CrossRef

Meunier, Q.L., Pétrot, F.: Lightweight transactional memory systems for NoCs based architectures: design, implementation and comparison of two policies. J. Parallel Distrib. Comput. 70(10), 1024–1041 (2010)CrossRefMATH

Bobba, J., Moore, K., Volos, H., Yen, L., Hill, M.D., Swift, M., Wood, D.A.: Performance pathologies in hardware transactional memory. IEEE Micro 28(1), 32–41 (2008)CrossRef

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

Shavit, N., Touitou, D.: Software transactional memory. In: Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, pp. 204–213 (1995)

Vallejo, E., Sanyal, S., Harris, T., Vallejo, F., Beivide, R., Unsal, O., Cristal, A., Valero, M.: Hybrid transactional memory with pessimistic concurrency control. Int. J. Parallel Prog. 39(3), 375–396 (2011)CrossRef

10.

Sonmez, N., Arcas, O., Pflucker, O., Unsal, O.S., Cristal, A., Hur, I., Singh, S., Valero, M.: TMbox: a flexible and reconfigurable 16-core hybrid transactional memory system. In: IEEE 19th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), pp. 146–153 (2011)

11.

Hammond, L., Carlstrom, B.D., Wong, V., Chen, M., Kozyrakis, C., Olukotun, K.: Transactional coherence and consistency: simplifying parallel hardware and software. IEEE Micro 24(6), 92–103 (2004)CrossRef

12.

Waliullah, M.M., Stenstrom, P.: Intermediate checkpointing with conflicting access prediction in transactional memory systems. In: IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2008), pp. 1–11 (2008)

13.

Waliullah, M.M., Stenstrom, P.: Removal of conflicts in hardware transactional memory systems. Int. J. Parallel Prog. 42(1), 198–218 (2014)CrossRef

14.

Ceze, L., Tuck, J., Torrellas, J., Cascaval, C.: Bulk disambiguation of speculative threads in multiprocessors. In: Proceedings of the 33rd Annual International Symposium on Computer Architecture (ISCA ’06), pp. 227–238 (2006)

15.

Quislant, R., Gutierrez, E., Plata, O., Zapata, E.L.: Hardware signature designs to deal with asymmetry in transactional data sets. IEEE Trans. Parallel Distrib. Syst. 24(3), 506–519 (2013)CrossRef

16.

Tomic, S., Perfumo, C., Kulkarni, C., Armejach, A., Cristal, A., Unsal, O., Harris, T., Valero, M.: EazyHTM: eager-lazy hardware transactional memory. In: Proceedings of the 42nd International Symposium on Microarchitecture, pp. 145–155 (2009)

17.

Lupon, M., Magklis, G., Gonzalez, A.: FASTM: a log-based hardware transactional memory with fast abort recovery. In: Proceedings of the 2009 18th International Conference on Parallel Architectures and Compilation Techniques (PACT ’09), pp. 293–302 (2009)

18.

Ros, A., Acacio, M., Garcia, J.M.: A direct coherence protocol for many-core chip multiprocessors. IEEE Trans. Parallel Distrib. Syst. 21(12), 1779–1792 (2010)CrossRef

19.

Heindl, A., Pokam, G.: An analytic framework for performance modeling of software transactional memory. Comput. Netw. 53(8), 1202–1214 (2009)CrossRefMATH

20.

Heindl, A., Pokam, G., Adl-Tabatabai, A.: An analytic model of optimistic software transactional memory. In: IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS 2009), pp. 153–162 (2009)

21.

Heindl, A., Pokam, G.: An analytic model for optimistic STM with lazy locking. In: Proceedings of the 16th International Conference on Analytical and Stochastic Modeling Techniques and Applications (ASMTA ’09), pp. 339–353 (2009)

22.

He, Z., Hong, B.: Modeling the run-time behavior of transactional memory. In: IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), pp. 307–315 (2010)

23.

Sanzo, P., Di Ciciani, B., Palmieri, R., Quaglia, F., Romano, P.: On the analytical modeling of concurrency control algorithms for software transactional memories: the case of commit-time-locking. Perform. Eval. 69(5), 187–205 (2012)CrossRef

24.

Poe, J., Chang-Burm, C., Tao, L.: Using analytical models to efficiently explore hardware transactional memory and multi-core co-design. In: The 20th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD ’08), pp. 159–166 (2008)

25.

Minh, C.C., Chung, J., Kozyrakis, C., Olukotun, K.: STAMP: Stanford transactional applications for multi-processing. In: IEEE International Symposium on Workload Characterization (IISWC 2008), pp. 35-46 (2008)

26.

Hughes, C., Poe, J., Qouneh, A., Tao, L.: On the (dis)similarity of transactional memory workloads. In: IEEE International Symposium on Workload Characterization (IISWC 2009), pp. 108–117 (2009)

27.

Newman, R., Dennis, C.: JPC: an x86 PC emulator in pure Java. In: Spinellis, D., Gousios, G. (eds.) Beautiful Architecture: Leading Thinkers Reveal the Hidden Beauty in Software Design, pp. 199–234. O’Reilly Media, Sebastopol (2009)

28.

Radivojevic, Z., Cvetanovic, M.: Integration of the JPC simulator into the configurable cache memory simulator. In: Proceedings of the 54th ETRAN Conference (ETRAN LIV), pp. RT.4.10.1–RT.4.10.4 (2010)

Title: Restart Optimization for Transactional Memory with Lazy Conflict Detection
Authors: Miloš Cvetanović
Zaharije Radivojević
Veljko Milutinović
Publication date: 28-03-2016
Publisher: Springer US
Published in: International Journal of Parallel Programming / Issue 3/2017
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-016-0411-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2017

Panda: A Compiler Framework for Concurrent CPUGPU Execution of 3D Stencil Computations on GPU-accelerated Supercomputers

Scalable Loop Self-Scheduling Schemes for Large-Scale Clusters and Cloud Systems

Parallelization Strategies for Spatial Agent-Based Models

Adaptive Optimization -Minimization Solvers on GPU

Programming GPGPU Graph Applications with Linear Algebra Building Blocks

Adaptive Runtime-Assisted Block Prefetching on Chip-Multiprocessors

Premium Partner