Flexible Support for Fast Parallel Commutative Updates

Vignesh Balaji, Dhruva Tirumala, Brandon LuciaarXiv 2017 · OpenReview

TL;DR

This paper introduces CCache, a novel hardware-software system that significantly boosts parallel performance by enabling cores to work on private copies of data modified by commutative operations. CCache achieves this through on-demand privatization, avoiding the memory overhead and contention associated with traditional data duplication and locking mechanisms.

What Problem Does This Paper Address?

Modern multi-core processors are powerful, but fully exploiting their parallelism in shared-memory systems is hindered by synchronization and data movement overheads. When multiple threads need to access and modify the same data, they must synchronize (e.g., using locks) to maintain consistency. This serialization limits parallelism. Data duplication offers an alternative by giving each thread its own copy, but this increases memory footprint and can lead to cache contention. The authors identify a sweet spot: operations that are "commutative" (their order doesn't matter for the final result) can be performed in parallel on private copies, and then merged later. However, existing solutions for exploiting commutativity are either limited to specific hardware-defined operations or require complex software/compiler support. This paper aims to provide a flexible, hardware-supported solution for commutative operations that avoids the drawbacks of existing methods.

Methods

CCache introduces a new programming model and architectural extensions to a standard multicore processor.

  • On-Demand Privatization: Instead of pre-allocating private copies, CCache dynamically creates a private copy of a data item (called "commutatively accessible data" or CData) the first time a core performs a "commutative operation" (COp) on it. This is done via new c_read and c_write instructions.
  • Privatized Execution: Cores operate on these private copies without needing synchronization or cache coherence protocols for CData. This eliminates a major source of performance bottlenecks.
  • Software-Defined Merging: When a core finishes its operations on a privatized copy, it uses a programmer-defined "merge function" to combine its updated value with the main memory copy. This merge function is registered via a new merge_init instruction.
  • Architectural Support: CCache adds a small "source buffer" per core to store the original, un-modified copy of CData and a "CCache bit" in L1 cache lines to identify CData. Crucially, it does not modify the existing cache coherence protocol.
  • Optimizations: The paper introduces soft_merge to delay merges until data is evicted from the cache, and a "dirty-merge" optimization that skips merging if the data hasn't been modified.

Datasets

The paper evaluates CCache using four parallel applications:

  • Key-Value Store
  • K-Means clustering
  • PageRank
  • Breadth-First Search (BFS)

For each application, they implemented variants using fine-grained locking (FGL), static data duplication (DUP), and CCache. They also tested with different input sizes, ranging from 25% to 400% of the L3 cache capacity, and used graph inputs for PageRank and BFS.

Key Insights and Ideas

  • The "Best of Both Worlds": CCache effectively bridges the gap between the memory/contention overhead of data duplication and the parallelism limitations of locking, by enabling on-demand privatization for commutative operations.
  • Flexibility is Key: The ability for programmers to define arbitrary merge functions is a major advantage, allowing CCache to support a wide range of commutative operations beyond simple arithmetic. This contrasts sharply with hardware-specific solutions.
  • Minimal Hardware Change, Maximum Impact: The core idea of CCache is that significant performance gains can be achieved with relatively minor architectural additions (source buffer, CCache bit) without touching the complex cache coherence protocol.
  • On-Demand is Efficient: Dynamically privatizing data only when needed avoids the constant memory overhead of static duplication, leading to better L3 cache utilization, especially for larger working sets.
  • Merge Functions are the Bridge: The merge function is the critical piece that allows independent parallel work to be correctly integrated back into a coherent shared state, acting as a form of partial reduction.

Key Results

  • Significant Speedups: CCache achieved speedups of up to 3.2X compared to fine-grained locking (FGL) and up to 10X compared to static data duplication (DUP) across various benchmarks.
  • Improved L3 Cache Utilization: CCache demonstrated better L3 cache utilization than DUP, even when CCache had half the L3 cache capacity, leading to performance improvements of 1.07-1.9X over static duplication in those scenarios.
  • Reduced Invalidation Traffic: CCache significantly reduced coherence traffic (invalidation messages) compared to FGL and DUP, contributing to its performance gains.
  • Broad Applicability: The system showed performance benefits not only for simple commutative operations but also for more complex ones like saturating counters and complex number multiplication, demonstrating its flexibility.

Limitations and Future Work

  • Programmer Burden: While CCache simplifies data duplication, programmers still need to identify commutative operations and define appropriate merge functions.
  • Cache Line Alignment: CData must be cache-line aligned, and padding might be needed to ensure cache lines don't contain both CData and normal data.
  • Limited Cache Access: Programs must ensure they don't access more than w-1 distinct cache lines without an intervening merge, where w is the number of ways in the cache, to avoid deadlock.
  • Context Switches/Interrupts: Handling context switches and interrupts for CData requires either delaying the switch/interrupt until a merge completes or saving/restoring the CData state, which increases process state size.
  • Future Work: The authors suggest extending CCache to support approximable operations (where exact results aren't critical) and to help remediate conflicts in parallel execution models that use conflict checking. They also highlight the potential for CCache's merge-on-evict optimization to improve locality and reduce merges.

Summary updated

Abstract

Privatizing data is a useful strategy for increasing parallelism in a shared memory multithreaded program. Independent cores can compute independently on duplicates of shared data, combining their results at the end of their computations. Conventional approaches to privatization, however, rely on explicit static or dynamic memory allocation for duplicated state, increasing memory footprint and contention for cache resources, especially in shared caches. In this work, we describe CCache, a system for on-demand privatization of data manipulated by commutative operations. CCache garners the benefits of privatization, without the increase in memory footprint or cache occupancy. Each core in CCache dynamically privatizes commutatively manipulated data, operating on a copy. Periodically or at the end of its computation, the core merges its value with the value resident in memory, and when all cores have merged, the in-memory copy contains the up-to-date value. We describe a low-complexity architectural implementation of CCache that extends a conventional multicore to support on-demand privatization without using additional memory for private copies. We evaluate CCache on several high-value applications, including random access key-value store, clustering, breadth first search and graph ranking, showing speedups upto 3.2X.
BibTeX
@misc{balaji2017flexible,
  author = {Vignesh Balaji and Dhruva Tirumala and Brandon Lucia},
  title = {{Flexible Support for Fast Parallel Commutative Updates}},
  year = {2017},
  eprint = {1709.09491},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.09491},
}
Figure