Collaborative Research: Restricted Caches, An Experimental and Theoretical Study

协作研究：受限缓存，实验和理论研究

• 批准号: 0105283
• 负责人: Eric Torng
• 金额: $ 22.36万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0105283&HistoricalAwards=false
• 关键词: Collaborative; Research; Restricted; Caches; Experimental

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.

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