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_readandc_writeinstructions. - 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_initinstruction. - 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_mergeto 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-1distinct cache lines without an intervening merge, wherewis 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