research-article

Lazy Release Persistency

Authors:

Mahesh Dananjaya,

Vasilis Gavrielatos,

Vijay NagarajanAuthors Info & Claims

ASPLOS '20: Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems

Pages 1173 - 1186

https://doi.org/10.1145/3373376.3378481

Published: 13 March 2020 Publication History

Abstract

Fast non-volatile memory (NVM) has sparked interest in log-free data structures (LFDs) that enable crash recovery without the overhead of logging. However, recovery hinges on primitives that provide guarantees on what remains in NVM upon a crash. While ordering and atomicity are two well-understood primitives, we focus on ordering and its efficacy in enabling recovery of LFDs. We identify that one-sided persist barriers of acquire-release persistency (ARP)--the state-of-the-art ordering primitive and its microarchitectural implementation--are not strong enough to enable recovery of an LFD. Therefore, correct recovery necessitates the inclusion of the more expensive full barriers. In this paper, we propose strengthening the one-sided barrier semantics of ARP. The resulting persistency model, release persistency (RP), guarantees that NVM will hold a consistent-cut of the execution upon a crash, thereby satisfying the criterion for correct recovery of an LFD. We then propose lazy release persistency (LRP), a microarchitectural mechanism for efficiently enforcing RP's one-sided barriers. Our evaluation on 5 commonly used LFDs suggests that LRP provides a 14%-44% performance improvement over the state-of-the-art full barrier.

References

[1]

Mohammad Alshboul, James Tuck, and Yan Solihin. 2018. Lazy Persistency: A High-Performing and Write-Efficient Software Persistency Technique (ISCA '18). IEEE Press, 439--451. https://doi.org/10.1109/ISCA.2018.00044

[2]

Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov, Maged M. Michael, and Martin Vechev. 2011. Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot Be Eliminated (POPL '11). ACM, New York, NY, USA, 487--498. https://doi.org/10.1145/1926385.1926442

[3]

Guy E. Blelloch, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun. 2018. The Parallel Persistent Memory Model (SPAA '18). ACM, New York, NY, USA, 247--258. https://doi.org/10.1145/3210377.3210381

[4]

Hans-J. Boehm. 2012. Can Seqlocks Get Along with Programming Language Memory Models? (MSPC '12). ACM, New York, NY, USA, 12--20. https://doi.org/10.1145/2247684.2247688

[5]

Hans-J. Boehm and Dhruva R. Chakrabarti. 2016. Persistence Programming Models for Non-volatile Memory (ISMM 2016). ACM, New York, NY, USA, 55--67. https://doi.org/10.1145/2926697.2926704

[6]

Dhruva R. Chakrabarti, Hans-J. Boehm, and Kumud Bhandari. 2014. Atlas: Leveraging Locks for Non-volatile Memory Consistency (OOPSLA '14). ACM, New York, NY, USA, 433--452. https://doi.org/10.1145/2660193.2660224

[7]

Joel Coburn, Adrian M. Caulfield, Ameen Akel, Laura M. Grupp, Rajesh K. Gupta, Ranjit Jhala, and Steven Swanson. 2011. NV-Heaps: Making Persistent Objects Fast and Safe with Next-generation, Non-volatile Memories (ASPLOS XVI). ACM, New York, NY, USA, 105--118. https://doi.org/10.1145/1950365.1950380

[8]

Jeremy Condit, Edmund B. Nightingale, Christopher Frost, Engin Ipek, Benjamin Lee, Doug Burger, and Derrick Coetzee. 2009. Better I/O Through Byte-addressable, Persistent Memory (SOSP '09). ACM, New York, NY, USA, 133--146. https://doi.org/10.1145/1629575.1629589

[9]

Tudor David, Aleksandar Dragojevic, Rachid Guerraoui, and Igor Zablotchi. 2018. Log-Free Concurrent Data Structures. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). USENIX Association, Boston, MA, 373--386. https://www.usenix.org/conference/atc18/presentation/david

[10]

Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. 2018. A Persistent Lock-free Queue for Non-volatile Memory (PPoPP '18). ACM, New York, NY, USA, 28--40. https://doi.org/10.1145/3178487.3178490

[11]

Yaosheng Fu and David Wentzlaff. 2014. PriME: A parallel and distributed simulator for thousand-core chips. In 2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) . 116--125. https://doi.org/10.1109/ISPASS.2014.6844467

[12]

Kourosh Gharachorloo, Anoop Gupta, and John L. Hennessy. 1991. Two Techniques to Enhance the Performance of Memory Consistency Models. In ICPP (1) . 355--364.

[13]

Vaibhav Gogte, Stephan Diestelhorst, William Wang, Satish Narayanasamy, Peter M. Chen, and Thomas F. Wenisch. 2018. Persistency for Synchronization-free Regions (PLDI 2018). ACM, New York, NY, USA, 46--61. https://doi.org/10.1145/3192366.3192367

[14]

Vincent Gramoli. 2015. More Than You Ever Wanted to Know About Synchronization: Synchrobench, Measuring the Impact of the Synchronization on Concurrent Algorithms (PPoPP 2015). ACM, New York, NY, USA, 1--10. https://doi.org/10.1145/2688500.2688501

[15]

Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In Proceedings of the 15th International Conference on Distributed Computing (DISC '01). Springer-Verlag, London, UK, UK, 300--314. http://dl.acm.org/citation.cfm?id=645958.676105

Digital Library

[16]

Maurice Herlihy and Nir Shavit. 2008. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

Digital Library

[17]

Intel. 2015. Intel and Micron Produce Breakthrough Memory Technology . https://newsroom.intel.com/news-releases/intel-and-micron-produce-breakthrough-memory-technology/.

[18]

Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. 2016. Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model. In Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27--29, 2016. Proceedings. 313--327. https://doi.org/10.1007/978--3--662--53426--7_23

[19]

Joseph Izraelevitz, Jian Yang, Lu Zhang, Juno Kim, Xiao Liu, Amirsaman Memaripour, Yun Joon Soh, Zixuan Wang, Yi Xu, Subramanya R. Dulloor, Jishen Zhao, and Steven Swanson. 2019. Basic Performance Measurements of the Intel Optane DC Persistent Memory Module . CoRR, Vol. abs/1903.05714 (2019). arxiv: 1903.05714 http://arxiv.org/abs/1903.05714

[20]

Arpit Joshi, Vijay Nagarajan, Marcelo Cintra, and Stratis Viglas. 2015. Efficient Persist Barriers for Multicores (MICRO-48). ACM, New York, NY, USA, 660--671. https://doi.org/10.1145/2830772.2830805

[21]

Arpit Joshi, Vijay Nagarajan, Marcelo Cintra, and Stratis Viglas. 2018. DHTM: Durable Hardware Transactional Memory (ISCA '18). IEEE Press, 452--465. https://doi.org/10.1109/ISCA.2018.00045

[22]

Pete Keleher, Alan L. Cox, and Willy Zwaenepoel. 1992. Lazy Release Consistency for Software Distributed Shared Memory . SIGARCH Comput. Archit. News, Vol. 20, 2 (April 1992), 13--21. https://doi.org/10.1145/146628.139676

Digital Library

[23]

Aasheesh Kolli, Vaibhav Gogte, Ali Saidi, Stephan Diestelhorst, Peter M. Chen, Satish Narayanasamy, and Thomas F. Wenisch. 2017. Language-level Persistency (ISCA '17). ACM, New York, NY, USA, 481--493. https://doi.org/10.1145/3079856.3080229

[24]

Aasheesh Kolli, Jeff Rosen, Stephan Diestelhorst, Ali Saidi, Steven Pelley, Sihang Liu, Peter M. Chen, and Thomas F. Wenisch. 2016. Delegated Persist Ordering (MICRO-49). IEEE Press, Piscataway, NJ, USA, Article 58, bibinfonumpages13 pages. http://dl.acm.org/citation.cfm?id=3195638.3195709

[25]

Youyou Lu, Jiwu Shu, Long Sun, and Onur Mutlu. 2014. Loose-Ordering Consistency for persistent memory. In 2014 IEEE 32nd International Conference on Computer Design (ICCD). 216--223. https://doi.org/10.1109/ICCD.2014.6974684

[26]

Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. 2005. Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation (PLDI '05). ACM, New York, NY, USA, 190--200. https://doi.org/10.1145/1065010.1065034

Digital Library

[27]

Maged M. Michael. 2002. High Performance Dynamic Lock-free Hash Tables and List-based Sets (SPAA '02). ACM, New York, NY, USA, 73--82. https://doi.org/10.1145/564870.564881

[28]

Maged M. Michael and Michael L. Scott. 1996. Simple, Fast, and Practical Non-blocking and Blocking Concurrent Queue Algorithms (PODC '96). ACM, New York, NY, USA, 267--275. https://doi.org/10.1145/248052.248106

[29]

Sanketh Nalli, Swapnil Haria, Mark D. Hill, Michael M. Swift, Haris Volos, and Kimberly Keeton. 2017. An Analysis of Persistent Memory Use with WHISPER (ASPLOS '17). ACM, New York, NY, USA, 135--148. https://doi.org/10.1145/3037697.3037730

[30]

Dushyanth Narayanan and Orion Hodson. 2012. Whole-system Persistence (ASPLOS XVII). ACM, New York, NY, USA, 401--410. https://doi.org/10.1145/2150976.2151018

[31]

Aravind Natarajan and Neeraj Mittal. 2014. Fast Concurrent Lock-free Binary Search Trees (PPoPP '14). ACM, New York, NY, USA, 317--328. https://doi.org/10.1145/2555243.2555256

[32]

Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott. 2017. Dalí: A Periodically Persistent Hash Map. In 31st International Symposium on Distributed Computing (DISC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Andréa W. Richa (Ed.), Vol. 91. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 37:1--37:16. https://doi.org/10.4230/LIPIcs.DISC.2017.37

[33]

Steven Pelley, Peter M. Chen, and Thomas F. Wenisch. 2014. Memory Persistency (ISCA '14). IEEE Press, Piscataway, NJ, USA, 265--276. http://dl.acm.org/citation.cfm?id=2665671.2665712

[34]

Azalea Raad and Viktor Vafeiadis. 2018. Persistence Semantics for Weak Memory: Integrating Epoch Persistency with the TSO Memory Model . Proc. ACM Program. Lang., Vol. 2, OOPSLA, Article 137 (Oct. 2018), bibinfonumpages27 pages. https://doi.org/10.1145/3276507

Digital Library

[35]

Jinglei Ren, Jishen Zhao, Samira Khan, Jongmoo Choi, Yongwei Wu, and Onur Mutlu. 2015. ThyNVM: Enabling Software-Transparent Crash Consistency in Persistent Memory Systems (MICRO-48). Association for Computing Machinery, New York, NY, USA, 672--685. https://doi.org/10.1145/2830772.2830802

[36]

Michael L. Scott. 2013. Shared-Memory Synchronization. Morgan & Claypool Publishers.

[37]

Seunghee Shin, James Tuck, and Yan Solihin. 2017. Hiding the Long Latency of Persist Barriers Using Speculative Execution (ISCA '17). Association for Computing Machinery, New York, NY, USA, 175--186. https://doi.org/10.1145/3079856.3080240

[38]

Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H. Campbell. 2011. Consistent and Durable Data Structures for Non-volatile Byte-addressable Memory (FAST'11). USENIX Association, Berkeley, CA, USA, 5--5. http://dl.acm.org/citation.cfm?id=1960475.1960480

[39]

Haris Volos, Andres Jaan Tack, and Michael M. Swift. 2011. Mnemosyne: Lightweight Persistent Memory (ASPLOS XVI). ACM, New York, NY, USA, 91--104. https://doi.org/10.1145/1950365.1950379

[40]

William Wang and Stephan Diestelhorst. 2019. Persistent Atomics for Implementing Durable Lock-Free Data Structures for Non-Volatile Memory (Brief Announcement) (SPAA '19). Association for Computing Machinery, New York, NY, USA, 309--311. https://doi.org/10.1145/3323165.3323166

[41]

Andrew Waterman, Yunsup Lee, David A. Patterson, Krste Asanovic, Volume I User level Isa, Andrew Waterman, Yunsup Lee, and David Patterson. 2014. The RISC-V Instruction Set Manual.

[42]

Song Wu, Fang Zhou, Xiang Gao, Hai Jin, and Jinglei Ren. 2019. Dual-Page Checkpointing: An Architectural Approach to Efficient Data Persistence for In-Memory Applications. ACM Trans. Archit. Code Optim., Vol. 15, 4, Article Article 57 (Jan. 2019), bibinfonumpages27 pages. https://doi.org/10.1145/3291057

Digital Library

[43]

Deli Zhang and Damian Dechev. 2016. An Efficient Lock-Free Logarithmic Search Data Structure Based on Multi-dimensional List . 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS) (2016), 281--292.

Cited By

Zeng JZhang TJung C(2024)Compiler-Directed Whole-System Persistence2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00074(961-977)Online publication date: 29-Jun-2024
https://doi.org/10.1109/ISCA59077.2024.00074
Soh YSwanson SZhao J(2023)ENTS: Flush-and-Fence-Free Failure Atomic TransactionsProceedings of the International Symposium on Memory Systems10.1145/3631882.3631907(1-16)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1145/3631882.3631907
Pandey SKamath ABasu AAamodt TJerger NSwift M(2023)Scoped Buffered Persistency Model for GPUsProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575749(688-701)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575749
Show More Cited By

Index Terms

Lazy Release Persistency
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
2. Hardware
  1. Emerging technologies

Recommendations

Yashme: detecting persistency races
ASPLOS '22: Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems

Persistent memory (PM) or Non-Volatile Random-Access Memory (NVRAM) hardware such as Intel’s Optane memory product promises to transform how programs store and manipulate information. Ensuring that persistent memory programs are crash consistent is a ...
Lazy persistency: a high-performing and write-efficient software persistency technique
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer Architecture

Emerging Non-Volatile Memories (NVMs) are expected to be included in future main memory, providing the opportunity to host important data persistently in main memory. However, achieving persistency requires that programs be written with failure-safety ...
Memory persistency
ISCA '14

Emerging nonvolatile memory technologies (NVRAM) promise the performance of DRAM with the persistence of disk. However, constraining NVRAM write order, necessary to ensure recovery correctness, limits NVRAM write concurrency and degrades throughput. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS '20: Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems

March 2020

1412 pages

ISBN:9781450371025

DOI:10.1145/3373376

General Chair:
James Larus
EPFL
,
Program Chairs:
Luis Ceze
University of Washington
,
Karin Strauss
Microsoft

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]

Sponsors

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 March 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

Engineering and Physical Sciences Research Council

Conference

ASPLOS '20

Sponsor:

ASPLOS '20: Architectural Support for Programming Languages and Operating Systems

March 16 - 20, 2020

Lausanne, Switzerland

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
481
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zeng JZhang TJung C(2024)Compiler-Directed Whole-System Persistence2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00074(961-977)Online publication date: 29-Jun-2024
https://doi.org/10.1109/ISCA59077.2024.00074
Soh YSwanson SZhao J(2023)ENTS: Flush-and-Fence-Free Failure Atomic TransactionsProceedings of the International Symposium on Memory Systems10.1145/3631882.3631907(1-16)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1145/3631882.3631907
Pandey SKamath ABasu AAamodt TJerger NSwift M(2023)Scoped Buffered Persistency Model for GPUsProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575749(688-701)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575749
Gorjiara HLuo WLee AXu GDemsky BJhala RDillig I(2022)Checking robustness to weak persistency modelsProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523723(490-505)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523723
Yadalam SShah NYu XSwift M(2022)ASAP: A Speculative Approach to Persistence2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA53966.2022.00070(892-907)Online publication date: Apr-2022
https://doi.org/10.1109/HPCA53966.2022.00070
Vemmou MDaglis A(2021)COSPlay: Leveraging Task-Level Parallelism for High-Throughput Synchronous PersistenceMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480075(86-99)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480075
Xu YIzraelevitz JSwanson SSherwood TBerger EKozyrakis C(2021)Clobber-NVM: log less, re-execute moreProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446730(346-359)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446730
Jeong JJung CSherwood TBerger EKozyrakis C(2021)PMEM-spec: persistent memory speculation (strict persistency can trump relaxed persistency)Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446698(517-529)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446698
Shahri SArmin Vakil Ghahani SKolli A(2020)(Almost) Fence-less Persist Ordering2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO50266.2020.00052(539-554)Online publication date: Oct-2020
https://doi.org/10.1109/MICRO50266.2020.00052

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.

Media

Figures

Other

Tables

View Table of Contents