Practical Persistent Multi-word Compare-and-Swap Algorithms for Many-core CPUs

Kento Sugiura, Manabu Nishimura, Yoshiharu Ishikawa

TL;DR

This paper introduces a new, significantly faster persistent multi-word compare-and-swap (PMwCAS) algorithm for many-core CPUs. By removing redundant operations and optimizing the handling of data durability, their approach achieves up to a 10x speedup over existing methods, making persistent memory programming more efficient.

What Problem Does This Paper Address?

Persistent memory (PMem) offers the promise of byte-addressable, durable storage, blurring the lines between RAM and traditional storage. However, ensuring data consistency and durability across multiple memory locations simultaneously is a major challenge. Existing solutions like persistent multi-word compare-and-swap (PMwCAS) algorithms, while addressing this, suffer from performance bottlenecks, especially on modern many-core processors. These bottlenecks stem from redundant compare-and-swap (CAS) and cache flush instructions, which lead to excessive cache invalidations and slow down operations, particularly under high contention. This paper aims to bridge this performance gap by proposing a more efficient PMwCAS algorithm tailored for many-core architectures.

Methods

The core contribution of this paper is a novel PMwCAS algorithm that significantly reduces performance overhead. The authors achieve this by:

  • Removing Redundant CAS and Flush Instructions: Unlike previous PMwCAS algorithms that employ numerous CAS and cache flush operations, this new algorithm streamlines these operations. This directly addresses the primary cause of performance degradation identified in prior work.
  • Eliminating Dirty Flags: The original PMwCAS algorithm used "dirty flags" to ensure data durability. This paper proposes to remove these flags, which require extra write operations and cache flushes. Instead, the PMwCAS descriptors themselves are leveraged as write-ahead logs, providing the necessary information for recovery without the overhead of separate dirty flags.
  • Optimized Descriptor Management: The algorithm utilizes a descriptor to manage the state of each PMwCAS operation. This descriptor stores information about the operation's progress (Failed, Succeeded, or Completed) and the target addresses, expected values, and desired values for each CAS.
  • Write-Ahead Log Functionality: The PMwCAS descriptors are designed to act as write-ahead logs. This allows for consistent recovery of operations after machine failures by rolling forward or backward based on the descriptor's state.
  • Efficient Reservation and Finalization: The algorithm includes distinct reservation and finalization (commit or abort) phases. It employs a test-and-test-and-set (TTAS) algorithm for embedding descriptors to avoid cache invalidations and uses a back-off mechanism to prevent busy-waiting during reads.

Datasets

Not discussed in the paper. The evaluation uses synthetic datasets generated by the authors' benchmarking program.

Key Insights and Ideas

  • The Cost of Redundancy: The paper strongly demonstrates that seemingly small inefficiencies, like redundant CAS and flush instructions, can lead to dramatic performance degradations on many-core systems.
  • Descriptors as More Than Just State: Leveraging PMwCAS descriptors not only for state tracking but also as write-ahead logs is a clever way to reduce overhead and simplify recovery mechanisms.
  • Dirty Flags are Often Unnecessary: The removal of dirty flags, while maintaining consistency, highlights that existing mechanisms (like descriptors) can often fulfill the same purpose with better performance.
  • Many-Core Architectures Amplify Inefficiencies: The performance gap between the proposed and original algorithms widens significantly with an increasing number of threads, underscoring the importance of efficient algorithms for modern hardware.
  • False Sharing is Less of a Concern for PMem than CPU Caches: While false sharing can be detrimental to CPU cache performance, its impact on Intel Optane persistent memory is shown to be negligible due to its larger read/write units and internal write buffering.

Key Results

  • Up to 10x Speedup: The proposed PMwCAS algorithms (both with and without dirty flags) achieve up to ten times higher throughput compared to the original algorithm in high-competitive environments.
  • Significant Latency Reduction: Correspondingly, latency is reduced by up to a tenth.
  • Performance on Many-Core: The proposed methods maintain high throughput even with a large number of threads, unlike the original algorithm which degrades significantly.
  • One-Word CAS Limitations: While effective for multi-word operations, the proposed method without dirty flags shows limitations for one-word CAS compared to a dedicated software PCAS, primarily due to the need for double flushes.
  • Parameter Sensitivity: Performance degrades as the number of target words increases, and it is recommended to keep this number as small as possible. Access skew also impacts performance, with high contention leading to performance degradation for all methods.

Limitations and Future Work

  • One-Word CAS Performance: The paper acknowledges that for single-word CAS operations, their approach is not as performant as a dedicated software PCAS due to the necessity of double flushes.
  • Target Word Count: The performance of PMwCAS operations degrades with an increasing number of target words, suggesting that developers should minimize this number.
  • Future Work: The authors plan to improve a persistent B+-tree, BzTree, using their PMwCAS implementation.

Summary updated

BibTeX
@article{sugiura2024practical,
  author = {Kento Sugiura and Manabu Nishimura and Yoshiharu Ishikawa},
  title = {{Practical Persistent Multi-word Compare-and-Swap Algorithms for Many-core CPUs}},
  journal = {J. Inf. Process.},
  year = {2024},
  doi = {10.2197/ipsjjip.32.1003},
}

Loading related content...

Figure