A Survey of Cache Bypassing Techniques

Sparsh MittalJournal of Low Power Electronics and Applications 2016 · DOI

TL;DR

As processors pack more cores, simply making caches bigger isn't working due to area and power constraints. This paper surveys "cache bypassing" techniques, which intelligently skip placing certain data in caches to improve performance and energy efficiency without the cost of larger caches. It's a crucial area for optimizing modern CPUs, GPUs, and their hybrid systems.

What Problem Does This Paper Address?

Modern processors are increasingly multi-core, leading to a higher demand for on-chip cache memory. However, physical limitations like area and power budgets make it infeasible to infinitely scale cache sizes. Furthermore, workloads with poor data locality can actually be hindered by caches, as every access adds latency and can even displace useful data. Cache bypassing emerges as a solution to increase effective cache capacity without the overhead of larger physical caches. The challenge lies in developing intelligent bypassing techniques that avoid performance degradation due to increased bandwidth congestion or miss rates, and that can adapt to diverse processing units (CPUs, GPUs) and memory technologies (SRAM, NVM, DRAM).

Methods

This paper is a survey, so it doesn't introduce new methods but rather categorizes and analyzes existing ones. The core idea behind cache bypassing techniques (CBTs) is to predict whether a data block is likely to be reused soon. Based on this prediction, the data block is either placed in the cache or "bypassed" directly to the next level of the memory hierarchy (or main memory).

The survey classifies CBTs based on several key parameters:

  • Decision Criteria: How the decision to bypass is made. This includes:
  • Reuse Count/Distance: Tracking how many times a block is accessed or how far apart accesses are.
  • Miss Behavior: Analyzing the type of cache miss (e.g., conflict vs. capacity).
  • Program Counter (PC) based prediction: Using the instruction pointer to infer future behavior.
  • Learning/Adaptive Approaches: Techniques that adjust their predictions over time.
  • Granularity: Whether bypassing is applied at the block, sub-block, or page level.
  • Cache Hierarchy Organization: How bypassing interacts with different cache levels (L1, L2, LLC) and hierarchy types (inclusive, exclusive, non-inclusive).
  • Memory Technology: How bypassing applies to SRAM, NVM, and stacked DRAM caches.
  • Processing Unit: Techniques tailored for CPUs, GPUs, and heterogeneous CPU-GPU systems.
  • Overhead Reduction Strategies: Methods like set sampling and probabilistic bypassing to minimize the performance impact of the bypassing logic itself.

Datasets

Not discussed in the paper. The paper surveys existing techniques and their evaluations, which would have used various benchmarks and workloads relevant to CPU, GPU, and heterogeneous computing, but specific datasets are not detailed.

Key Insights and Ideas

  • Bypassing is a Trade-off: While bypassing can significantly improve performance and energy efficiency by avoiding cache pollution and reducing traffic, naive bypassing can lead to severe performance degradation due to increased bandwidth congestion and higher miss rates. Intelligent prediction is key.
  • Context Matters: The effectiveness of bypassing techniques is highly dependent on the target architecture (CPU vs. GPU), the memory technology (SRAM vs. NVM vs. DRAM), and the cache hierarchy. A technique optimized for one might not work well for another.
  • GPUs Present Unique Challenges: The lock-step execution model and massive parallelism in GPUs mean that cache management decisions must be carefully coordinated across threads to avoid performance bottlenecks. Memory divergence is a critical factor.
  • NVM and DRAM Caches Benefit Greatly: Technologies like NVM have limitations (e.g., write endurance, high write latency) that make cache bypassing particularly beneficial for reducing writes and improving lifetime. Similarly, large DRAM caches can suffer from pollution, which bypassing can mitigate.
  • Implementation Overhead is a Concern: The logic for predicting reuse and making bypass decisions can itself introduce overhead. Techniques like set sampling and probabilistic prediction aim to reduce this.
  • Co-management is Crucial: Bypassing often works best when integrated with other cache management strategies like prefetching, replacement policies, and even thread scheduling.

Key Results

The paper is a survey, so it doesn't present its own experimental results. Instead, it synthesizes findings from numerous research papers. The general consensus across these studies is that well-designed cache bypassing techniques can:

  • Improve Performance: Reduce miss rates and execution times, especially for applications with poor data locality or streaming access patterns. Specific speedups are reported in individual studies, but a general figure is not provided.
  • Save Energy: By reducing traffic to and from caches, and by enabling more aggressive cache power management.
  • Mitigate Cache Pollution: Prevent frequently accessed data from being evicted by less useful data.
  • Address Limitations of Emerging Memory Technologies: Help overcome challenges with NVM and DRAM caches.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Heterogeneous Systems: Most existing CBTs were designed for discrete CPUs or GPUs. The rise of integrated CPU-GPU systems presents new challenges for cache management, requiring novel techniques.
  • Synergistic Integration: The interaction of cache bypassing with other cache management techniques (cache reconfiguration, compression, prefetching) needs further investigation for optimal adoption in commercial processors.
  • Fault Tolerance: Exploring the use of bypassing for tolerating faults due to process variation or limited write endurance is a promising area.
  • Approximate Computing: The potential for trading off storage/computation accuracy for energy/performance gains in approximate computing scenarios, where some blocks could be bypassed and approximated, is highlighted as an interesting future direction.
  • Design Complexity: Developing effective bypassing strategies for complex heterogeneous systems while managing implementation overhead remains a significant challenge.

Summary updated

Abstract

With increasing core-count, the cache demand of modern processors has also increased. However, due to strict area/power budgets and presence of poor data-locality workloads, blindly scaling cache capacity is both infeasible and ineffective. Cache bypassing is a promising technique to increase effective cache capacity without incurring power/area costs of a larger sized cache. However, injudicious use of cache bypassing can lead to bandwidth congestion and increased miss-rate and hence, intelligent techniques are required to harness its full potential. This paper presents a survey of cache bypassing techniques for CPUs, GPUs and CPU-GPU heterogeneous systems, and for caches designed with SRAM, non-volatile memory (NVM) and die-stacked DRAM. By classifying the techniques based on key parameters, it underscores their differences and similarities. We hope that this paper will provide insights into cache bypassing techniques and associated tradeoffs and will be useful for computer architects, system designers and other researchers.
BibTeX
@article{mittal2016survey,
  author = {Sparsh Mittal},
  title = {{A Survey of Cache Bypassing Techniques}},
  journal = {Journal of Low Power Electronics and Applications},
  year = {2016},
  doi = {10.3390/jlpea6020005},
}
Figure