Collaborative Research: Restricted Caches, An Experimental and Theoretical Study

处理器速度和主存访问速度之间的差距可能会导致处理器将大量时间花费在内存访问上。随着差距的扩大，这种内存延迟已经成为处理器性能的一个日益严重的瓶颈。现有的高速缓存设计已经很好地填补了这一差距，但随着差距的继续扩大，需要新的高速缓存设计。一种有前途的新类型的受限高速缓存，包括偏斜高速缓存、辅助高速缓存、牺牲性高速缓存和其他多边高速缓存。实验表明，一些受限高速缓存提供了比传统的组关联高速缓存更大的改进潜力。他们还揭示了一些在传统缓存中不可能出现的有趣现象。例如，偏斜缓存似乎表现出自重组。然而，对于这种行为或为什么这些受限缓存表现良好，没有理论上的解释。研究人员研究了不同受限缓存结构的性能和管理它们的算法。研究人员首先确定了受限缓存和传统的完全关联缓存之间的潜在结构差异：并不是所有的缓存线都是相同的。具体地说，在受限缓存中，与传统的组相联缓存不同，存在一对内存块，它们的合法缓存行集合不相同且具有非空交集。基于这一观点，研究者使用新的技术来评估和比较不同的缓存结构。大多数其他关于缓存的分析研究只关注给定缓存结构的算法的性能，而没有明确地比较不同缓存结构的有效性。研究人员还使用各种技术，如资源扩充、标准竞争分析和基于轨迹的模拟，研究了这些缓存结构的各种算法的性能。他们的结果表明，传统的缓存管理算法在受限缓存上的行为与在传统集关联缓存上的行为截然不同，例如，与传统缓存竞争最强的最近最少使用(LRU)算法在受限缓存中根本不具有竞争力，除非允许显式重新排列缓存中的项。最后，研究人员建立了一个RACE仓库，以方便不同的基于痕迹的模拟研究的比较，并帮助新的研究人员学习这一评估技术。

The gap between processor speed and main memory access speedcan cause processors to spend much of their time waiting on memory accesses.As the gap has grown, this memory latency has become anincreasingly significant bottleneck in processor performance.Existing cache designs have worked well to fill the gap,but new cache designs are needed as the gap continues to grow.A promising new class, restricted caches, includesskew caches, assist caches, victim caches, and other multi-lateral caches.Experiments have indicated that some restricted cachesoffer significant potential for improvement over traditionalset-associative caches. They also have revealed some interestingphenomenon that are not possible in traditional caches. For example,skew caches seem to exhibit self-reorganization.However, no theoretical explanation exists for this behavior or forwhy these restricted caches perform well.The investigators study the performance of distinct restricted cachestructures and algorithms for managing them.The investigators first identify an underlying structural differencebetween restricted caches and traditional fully-associativecaches: all cache lines are not identical. Specifically, in arestricted cache, unlike in a traditional set-associative cache,there exist pairs of memory blocks whose sets of legal cache linesare not identical and have a non-empty intersection.Using this insight, the investigators evaluate andcompare different cache structures using new techniques.Most other analytical studies of caches focus only on the performanceof algorithms for a given cache structure and do not explicitlycompare the effectiveness of distinct cache structures. Theinvestigators also study the performance of various algorithmsfor these cache structures using a variety of techniques suchas resource augmentation, standard competitive analysis,and trace-based simulation. Their results indicate that traditionalcache management algorithms behave very differently on restrictedcaches than they do on traditional set-associative caches.For example, the least recently used (LRU) algorithm that is stronglycompetitive for traditional caches is not competitive at all forrestricted caches unless explicit rearrangement of items in thecache is allowed. Finally, the investigators construct atrace warehouse to facilitate the comparison of distinct trace-basedsimulation studies as well as to help new researchers learn thisthis evaluation technique.