Fine-Grain Checkpointing with In-Cache-Line Logging

Non-Volatile Memory offers the possibility of implementing high-performance, durable data structures. However, achieving performance comparable to well-designed data structures in non-persistent (transient) memory is difficult, primarily because of the cost of ensuring the order in which memory writes reach NVM. Often, this requires flushing data to NVM and waiting a full memory round-trip time. In this paper, we introduce two new techniques: Fine- Grained Checkpointing, which ensures a consistent, quickly recoverable data structure in NVM after a system failure, and In-Cache-Line Logging, an undo-logging technique that enables recovery of earlier state without requiring cache- line flushes in the normal case. We implemented these techniques in the Masstree data structure, making it persistent and demonstrating the ease of applying them to a highly op- timized system and their low (5.9-15.4%) runtime overhead cost.

Software Support for Non-Volatile Memory (NVM) Programming

David Teksen Aksun

Non-Volatile Memory (NVM) is an emerging type of memory device that provides fast, byte-addressable, and high-capacity durable storage. NVM sits on the memory bus and allows durable data structures designs similar to the in-memory equivalent ones. Expensive serialization/deserialization operations, usually associated with block-based storage, are not necessary. Unfortunately, using NVM is not as simple as placing a data structure in NVM and expecting persistence. As NVM sits on the memory bus, processor caches buffer the cache lines from it that are referenced by load and store instructions. The volatility of the caches and possible power failures at a random point in a program complicate the design and require ways to handle these failures. Prior work focused on implementing crash-consistency mechanisms to correctly recover a program's data after a failure. The goal was to minimize the use of costly cache line write-back and fence instructions, which are necessary for correct durability. Moreover, commercial NVM devices are slower compared to DRAM and affect the design. In addition to performance overheads, correctly implementing crash consistency is hard. The programmers need to carefully reason about cache line write-back instructions and the order of persistent writes. Finding bugs can take from minutes to hours. In this thesis, we use checkpointing as an effective crash-consistency mechanism with low overhead for building durable data structures. We also describe an inter-procedural dataflow analysis for fast detection of NVM programming bugs. We show the practicality of these ideas through three primary contributions and their implementations. Firstly, we present InCLL to address NVM checkpointing. InCLL is a novel technique that uses fine-grained checkpointing and in-cache-line logging to minimize the number of explicit write-back and fence instructions in the fast path of data structure modifications. We evaluate InCLL both on DRAM and Optane devices for the Masstree data structure. Secondly, we present a new checkpointing design, CpNvm, which minimizes NVM write-back instructions on the critical path of the execution. We achieve low overheads for Masstree and Memcached for write-heavy workloads, and almost no overheads for read-only workloads. In addition, we present FlowNvm to find NVM programming bugs. FlowNvm can identify NVM programming pattern violations and anti-patterns at compile-time using inter-procedural dataflow analysis.

EPFL2021

GPGPU-Accelerated Parallel and Fast Simulation of Thousand-core Platforms

David Atienza Alonso, Luca Benini, Shivani Raghav, Martino Ruggiero

The multicore revolution and the ever-increasing complexity of computing systems is dramatically changing system design, analysis and programming of computing platforms. Future architectures will feature hundreds to thousands of simple processors and on-chip memories connected through a network-on-chip. Architectural simulators will remain primary tools for design space exploration, software development and performance evaluation of these massively parallel architectures. However, architectural simulation performance is a serious concern, as virtual platforms and simulation technology are not able to tackle the complexity of thousands of core future scenarios. The main contribution of this paper is the development of a new simulation approach and technology for many core processors which exploit the enormous parallel processing capability of low-cost and widely available. General Purpose Graphic Processing Units (GPGPU). The simulation of many-core architectures exhibits indeed a high level of parallelism and is inherently parallelizable, but GPGPU acceleration of architectural simulation requires an in-depth revision of the data structures and functional partitioning traditionally used in parallel simulation. We demonstrate our GPGPU simulator on a target architecture composed by several cores (i.e. ARM ISA based), with instruction and data caches, connected through a Network-on-Chip (NoC). Our experiments confirm the feasibility of our approach.

IEEE/ACM Press2011

Bridging the Latency Gap between NVM and DRAM for Latency-bound Operations

Anastasia Ailamaki, Georgios Psaropoulos

Non-Volatile Memory (NVM) technologies exhibit 4× the read access latency of conventional DRAM. When the working set does not fit in the processor cache, this latency gap between DRAM and NVM leads to more than 2× runtime increase for queries dominated by latency-bound operations such as index joins and tuple reconstruction. We explain how to easily hide NVM latency by interleaving the execution of parallel work in index joins and tuple reconstruction using coroutines. Our evaluation shows that interleaving applied to the non-trivial implementations of these two operations in a production-grade codebase accelerates end-to-end query runtimes on both NVM and DRAM by up to 1.7× and 2.6× respectively, thereby reducing the performance difference between DRAM and NVM by more than 60%.

ACM2019

Software Support for Non-Volatile Memory (NVM) Programming

David Teksen Aksun

EPFL2021