Moinuddin K. Qureshi
Abstract
As processor speeds increase and memory latency becomes more critical, intelligent design and management of secondary caches becomes increasingly important. The efficiency of current set-associative caches is reduced because programs exhibit a non-uniform distribution of memory accesses across different cache sets. We propose a technique to vary the associativity of a cache on a per-set basis in response to the demands of the program. By increasing the number of tag-store entries relative to the number of data lines, we achieve the performance benefit of global replacement while maintaining the constant hit latency of a set-associative cache. The proposed variable-way, or V-Way, set-associative cache achieves an average miss rate reduction of 13% on sixteen benchmarks from the SPEC CPU2000 suite. This translates into an average IPC improvement of 8%.
- {1} A. Agarwal, J. Hennessy, and M. Horowitz. cache performance of operating systems and multiprogramming. In ACM Transactions on Computer Systems, 6, pages 393-431, November 1988. Google Scholar
Digital Library
- {2} L. A. Belady. A study of replacement algorithms for a virtual-storage computer. In IBM Systems journal, pages 78-101, 1966.Google Scholar
- {3} B. Calder, D. G, and J. Emer. Predictive sequential associative cache. In Proceedings of the Second IEEE International Symposium on High Performance Computer Architecture, pages 244-253, 1996. Google ScholarDigital Library
- {4} Z. Chishti, M. D. Powell, and T. N. Vijaykumar. Distance associativity for high-performance energy-efficient non-uniform cache architectures. In Proceedings of the 36th Annual ACM/IEEE International Symposium on Microarchitecture, pages 55-66, 2003. Google ScholarDigital Library
- {5} F. J. Corbato. A paging experiment with the multics system. MIT project MAC Report MAC-M-384, May 1968.Google Scholar
- {6} Digital Equipment Corporation, Hudson, MA. Digital Semiconductor 21164 Alpha Microprocessor Product Brief, Mar. 1997. Technical Document EC-QP97D-TE.Google Scholar
- {7} E. G. Hallnor and S. K. Reinhardt. A fully associative software-managed cache design. In Proceedings of the 27th Annual International Symposium on Computer Architecture, pages 107-116, 2000. Google ScholarDigital Library
- {8} T. L. Jhonson. Run-time adaptive cache management. PhD thesis, University of Illinois, Urbana, IL, May 1998.Google Scholar
- {9} N. P. Jouppi. Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. In Proceedings of the 17th Annual International Symposium on Computer Architecture, pages 364-373, 1990. Google ScholarDigital Library
- {10} M. Kharbutli, K. Irwin, Y. Solihin, and J. Lee. Using prime numbers for cache indexing to eliminate conflict misses. In Proceedings of the Tenth IEEE International Symposium on High Performance Computer Architecture, pages 288-299, 2004. Google ScholarDigital Library
- {11} C. Kim, B. D., and S. Keckler. An adaptive, nonuniform cache structure for wiredelay dominated onchip caches. pages 211-222, 2002.Google Scholar
- {12} A. R. Lebeck. Cache conscious programming in undergraduate computer science. In ACM SIGCSE Technical Symposium on Computer Science Education (SIGCSE 99), 1999. Google ScholarDigital Library
- {13} J.-K. Peir, Y. Lee, and W. W. Hsu. Capturing dynamic memory reference behavior with adaptive cache topology. In Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 134-143, 1998. Google ScholarDigital Library
- {14} T. R. Puzak. Analysis of cache replacement algorithms. PhD thesis, Univ. of Mass., ECE Dept., Amherst, MA., 1985. Google ScholarDigital Library
- {15} A. Seznec. A case for two-way skewed-associative caches. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 169-178, 1993. Google ScholarDigital Library
- {16} A. J. Smith. Sequentiality and prefetching in database systems. ACM Transaction on Database Systems, 3(3):223-247, September 1978. Google ScholarDigital Library
- {17} A. J. Smith. Cache memories. Computing Surveys, 14(4), 1982. Google ScholarDigital Library
- {18} D. Weiss, J. J. Wuu, and V. Chin. The on-chip 3-mb subarray-based third-level cache on an itanium microprocessor. In IEEE journal of solid state circuits, pages 1523-1529, Nov. 2002.Google Scholar
- {19} S. J. E. Wilton and N. P. Jouppi. Cacti: an enhanced cache access and cycle time model. IEEE Journal of Solid-State Circuits, 31:677-688, May 1996.Google ScholarCross Ref
Index Terms
- The V-Way Cache: Demand Based Associativity via Global Replacement
Recommendations
The V-Way Cache: Demand Based Associativity via Global Replacement
ISCA '05: Proceedings of the 32nd annual international symposium on Computer ArchitectureAs processor speeds increase and memory latency becomes more critical, intelligent design and management of secondary caches becomes increasingly important. The efficiency of current set-associative caches is reduced because programs exhibit a non-...
Heterogeneous way-size cache
ICS '06: Proceedings of the 20th annual international conference on SupercomputingSet-associative cache architectures are commonly used. These caches consist of a number of ways, each of the same size. We have observed that the different ways have very different utilization, which motivates the design of caches with heterogeneous way ...
Way-tagged cache: an energy-efficient L2 cache architecture under write-through policy
ISLPED '09: Proceedings of the 2009 ACM/IEEE international symposium on Low power electronics and designWrite-through policy employed in many high-performance microprocessors provides good tolerance to soft errors in cache systems. However, it also incurs large energy overhead due to the increased accesses to caches at the lower level (e.g., the L2 cache) ...
Comments