(PLDI 2021) Mirror: Making Lock-Free Data Structures Persistent
Non-volatile main memory in the form of fast, dense, byte-addressable non-volatile memory has recently become available with the launch of the Intel Optane memory platform. However, designing algorithms and data structures that are crash-resilient, is complex and error-prone as caches and machine registers are still volatile and the data residing in memory after a crash might not contain a consistent view of the program state. This complex setting has often led to durable data structures being inefficient or incorrect, especially in the concurrent setting.
In this paper, we present Mirror—a simple general automatic transformation that adds durability to lock-free data structures, with a low performance overhead. Moreover, in the current non-volatile main memory configuration, where non-volatile memory operates side-by-side with a standard faster DRAM (as in the Optane platform), our mechanism exploits the hybrid system to obtain a drastic performance improvement. Evaluation shows a significant performance advantage over NVTraverse, which is the state-of-the-art similar transformation in the literature. Unlike some previous transformations, Mirror does not require any restriction on the lock-free data structure format.
Thu 16 JunDisplayed time zone: Pacific Time (US & Canada) change
15:30 - 16:50
|(PLDI 2020) Automatic Generation of Efficient Sparse Tensor Format Conversion Routines|
|(PLDI 2020) NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey|
|(PLDI 2021) Mirror: Making Lock-Free Data Structures Persistent|
|(POPL 2021) Provably Space Efficient Parallel Functional Programming|