Collaborative Research: Restricted Caches, An Experimental and Theoretical Study

点击翻译按钮获取中文摘要

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.