Prediction and bounds on shared cache demand from memory access interleaving
Prediction and bounds on shared cache demand from memory access interleaving
复制标题
DOI：
10.1145/3210563.3210565
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Jacob Brock;C. Ding;Rahman Lavaee;Fangzhou Liu;Liang Yuan
中科院分区：
文献类型：
--
作者：
Jacob Brock;C. Ding;Rahman Lavaee;Fangzhou Liu;Liang Yuan
通常共享多功能机器中的高速缓存，并且缓存性能取决于属于不同程序的内存如何相互交织。各种性能的可能性包括所有可能的交织，这些交织太多了，无法通过实验来研究任何非平凡程序的混合。本文提出了一种理论，以表征由于非数据共享程序的并行执行，记忆访问交织的效果。该理论使用已建立的指标，称为“足迹”（可用于计算完全缔合的LRU缓存中的遗漏比率）来衡量缓存需求，并考虑了各种相互交织的可能性。该论文证明了交织痕迹的足迹的下限，然后根据组成痕迹的足迹制定了上限。它还显示了在许多现有技术中使用的足迹组成的正确性，并在其准确性上确切的界限。
Cache in multicore machines is often shared, and the cache performance depends on how memory accesses belonging to different programs interleave with one another. The full range of performance possibilities includes all possible interleavings, which are too numerous to be studied by experiments for any mix of non-trivial programs. This paper presents a theory to characterize the effect of memory access interleaving due to parallel execution of non-data-sharing programs. The theory uses an established metric called the footprint (which can be used to calculate miss ratios in fully-associative LRU caches) to measure cache demand, and considers the full range of interleaving possibilities. The paper proves a lower bound for footprints of interleaved traces, and then formulates an upper bound in terms of the footprints of the constituent traces. It also shows the correctness of footprint composition used in a number of existing techniques, and places precise bounds on its accuracy.