A graph theoretic approach to cache-conscious placement of data for direct mapped caches
A graph theoretic approach to cache-conscious placement of data for direct mapped caches
复制标题
用于直接映射缓存的缓存感知数据放置的图论方法
DOI：
10.1145/1806651.1806670
复制
发表时间：
2010
影响因子：
6.6
通讯作者：
P. V. Beek
中科院分区：
文献类型：
--
作者：
Mirza Beg;P. V. Beek
缓存的设计目的是通过将经常访问的数据的副本移至更靠近处理器的位置来分摊内存访问的成本。多年来，处理器速度和内存访问延迟之间的差距越来越大，使得缓存成为程序性能的瓶颈。增强缓存性能有助于加快程序速度。因此，研究人员提出了几种硬件和软件技术来优化缓存，以最大限度地减少未命中的次数。其中包括内存中的编译时数据放置技术，可提高缓存性能。出于这项工作的目的，我们关注在给定有限数据对象集的访问顺序的情况下在内存中布置数据的问题，以便最大限度地减少缓存未命中。即使在编译时已知数据访问的顺序，该问题也很难得到最佳解决。在本文中，我们表明，给定直接映射缓存、其大小和数据访问顺序，可以识别不存在冲突未命中的实例。我们描述了一种算法，如果存在可以完全避免冲突未命中的方法，则该算法可以将数据分配给缓存以实现最少的未命中次数。我们还描述了在缓存大小强制冲突未命中的情况下将数据分配给缓存的启发式实现。实验表明，与原始分配相比，我们的技术使缓存未命中次数减少了 30%。
Caches were designed to amortize the cost of memory accesses by moving copies of frequently accessed data closer to the processor. Over the years the increasing gap between processor speed and memory access latency has made the cache a bottleneck for program performance. Enhancing cache performance has been instrumental in speeding up programs. For this reason several hardware and software techniques have been proposed by researchers to optimize the cache for minimizing the number of misses. Among these are compile-time data placement techniques in memory which improve cache performance. For the purpose of this work, we concern ourselves with the problem of laying out data in memory given the sequence of accesses on a finite set of data objects such that cache-misses are minimized. The problem has been shown to be hard to solve optimally even if the sequence of data accesses is known at compile time. In this paper we show that given a direct-mapped cache, its size, and the data access sequence, it is possible to identify the instances where there are no conflict misses. We describe an algorithm that can assign the data to cache for minimal number of misses if there exists a way in which conflict misses can be avoided altogether. We also describe the implementation of a heuristic for assigning data to cache for instances where the size of the cache forces conflict misses. Experiments show that our technique results in a 30% reduction in the number of cache misses compared to the original assignment.