A Gaussian Set Sampling Model for Efficient Shared Cache Profiling on Multi-Cores

Yi Zhang, Zhanwei Ling, Mingsong Lv, Nan GuanIEEE Access 2019 · DOI

Introduction

In modern multi-core processor architectures, the Last Level Cache (LLC) is a critical shared resource. As multiple applications execute simultaneously, they compete for limited cache space, leading to "cache contention" that can significantly degrade performance. Profiling this contention is essential for system optimization and hardware design. However, modern LLCs are massive, often containing thousands of cache sets. Traditional profiling methods face a difficult trade-off: full-set monitoring provides high accuracy but incurs prohibitive performance overhead, while simple random sampling often lacks the precision needed for reliable analysis.

This study introduces a novel mathematical approach to LLC profiling. By identifying that cache access patterns across sets follow a continuous probability distribution—specifically a Gaussian or "bell curve" distribution—the researchers developed a sampling model that achieves high fidelity with minimal system interference.

The Stress-Program Proxy

To measure cache contention without directly instrumenting the target application, the authors employ a "stress-program proxy." This method involves running a specialized process alongside the target workload. The stress program is designed to repeatedly access specific cache sets.

Mechanism of the stress-program proxy for measuring cache contention.

As shown in the diagram above, the stress program would ideally occupy the entire set if no other program were present. When a target program is running, it "hogs" a portion of the cache sets. By recording the number of cache misses the stress program experiences in each set, researchers can accurately infer the cache footprint of the target program. This indirect measurement technique forms the data foundation for the subsequent statistical modeling.

Gaussian Modeling and the "Gaussian 25" Method

The core innovation of this research is the observation that cache miss distributions are not stochastic but follow a predictable Gaussian pattern. Using Maximum Likelihood Estimation (MLE), the raw data from the stress program is fitted to a Gaussian model.

Because a Gaussian curve is mathematically defined by its mean ($\mu$) and standard deviation ($\sigma$), the entire distribution can be reconstructed by sampling only a few strategic points. The authors proposed the Gaussian 25 sampling model, which focuses on five key regions:

  1. The peak ($\mu$)
  2. The two inflection points ($\mu \pm \sigma$)
  3. The distribution boundaries (start and end points)

By sampling just five cache sets within each of these five regions—totaling only 25 sets—the model can predict the behavior of the entire cache. In a typical 2,048-set LLC, this represents a sampling rate of approximately 1.2%, drastically reducing the data overhead compared to traditional methods.

Experimental Evaluation

The model was validated on a quad-core Intel Core i7-2600 processor featuring an 8MB LLC organized into 2,048 sets. The researchers utilized nine diverse benchmarks from the SPEC CPU 2006 suite to represent a wide range of real-world computational workloads.

Cache miss distributions across 2,048 sets for various SPEC CPU 2006 benchmarks.

As illustrated in the benchmark data, while the specific "shape" of contention varies between programs like gcc, lbm, and bzip2, they consistently exhibit continuous distributions that lend themselves to statistical modeling rather than brute-force counting.

Key Results and Discussion

The Gaussian model demonstrated exceptional performance across several metrics:

  • Model Accuracy: The "Goodness of Fit" ($R^2$) exceeded 0.85 for the majority of benchmarks, confirming that the Gaussian distribution is a robust representation of cache behavior.
  • Sampling Efficiency: The Gaussian 25 method achieved an average error rate of 6.9%. This performance is nearly identical to the established "Continuous 128" method (6.2% error), yet it requires 80% fewer samples.
  • Low Interference: By monitoring only 25 sets, the profiling process introduces negligible slowdown to the target applications, solving the "observer effect" where the act of measuring a system changes its behavior.

Compared to random sampling of the same size (Random 25), the Gaussian-informed approach was significantly more accurate. Random sampling at such low densities frequently misses the critical peaks and valleys of cache contention, whereas the Gaussian model's focus on mathematical features ensures that the most informative data points are captured.

Conclusion

This research shifts the paradigm of cache profiling from a counting problem to a statistical estimation problem. By leveraging the underlying Gaussian nature of cache access patterns, the Gaussian 25 model provides a highly efficient, low-overhead solution for monitoring shared resources in multi-core systems. Future work may extend this model to handle dynamic program phases in real-time and explore its applicability to non-linear cache replacement policies found in specialized hardware.

Summary updated

BibTeX
@article{zhang2019gaussian,
  author = {Yi Zhang and Zhanwei Ling and Mingsong Lv and Nan Guan},
  title = {{A Gaussian Set Sampling Model for Efficient Shared Cache Profiling on Multi-Cores}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2936439},
}
Figure