Reducing cache misses by application-specific re-configurable indexing

ABSTRACT

The predictability of memory access patterns in embedded systems can be successfully exploited to devise effective application-specific cache optimizations. In this work, we propose an improved indexing scheme for direct-mapped caches, which drastically reduces the number of conflict misses by using application-specific information; the scheme is based on the selection of a subset of the address bits. With respect to similar approaches, our solution has two main strengths. First, it models the misses analytically by building a miss equation, and exploits a symbolic algorithm to compute the exact optimum solution (i.e., the subset of address bits to be used as cache index that minimizes conflict misses). Second, we designed a re-configurable bit selector, which can be programmed at run-time to fit the optimal cache indexing to a given application. Results show an average reduction of conflict misses of 24%, measured over a set of standard benchmarks, and for different cache configurations.

REFERENCES

• 1: [1] A. Macil, L. Benini, M. Poncino, Memory Design Techniques for Low-Energy Embedded Systems, Kluwer Academic Publishers, 2002.
• 2: [2] W. Wolf, M. Kandemir, "Memory System Optimization of Embedded Software," Proceedings of the IEEE, Vol. 91, No. 1, pp. 165-182, January 2003.
• 3: R. J. Enbody , H. C. Du, Dynamic hashing schemes, ACM Computing Surveys (CSUR), v.20 n.2, p.850-113, June 1988 [doi>10.1145/46157.330532]
• 4: Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States [doi>10.1145/360128.360153]
• 5: Peter Petrov , Alex Orailğlu, Towards effective embedded processors in codesigns: customizable partitioned caches, Proceedings of the ninth international symposium on Hardware/software codesign, p.79-84, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371687]
• 6: Tony Givargis, Improved indexing for cache miss reduction in embedded systems, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776052]
• 7: [7] J. M. Frailong, W. Jalby, J. Lenfant, "XOR-Schemes: A Flexible Data Organization in Parallel Memories," ICPP'85: International Conference on Parallel Processing, pp. 276-283, Aug. 1985.
• 8: B. Ramakrishna Rau, Pseudo-randomly interleaved memory, Proceedings of the 18th annual international symposium on Computer architecture, p.74-83, May 27-30, 1991, Toronto, Ontario, Canada
• 9: Nigel Topham , Antonio González, Randomized Cache Placement for Eliminating Conflicts, IEEE Transactions on Computers, v.48 n.2, p.185-192, February 1999 [doi>10.1109/12.752660]
• 10: Ching-Long Su , Chin-Chi Teng , Alvin M. Despain, A Study of Cache Hashing Functions for Symbolic Applications in Micro-Parallel Processors, Proceedings of the 1994 International Conference on Parallel and Distributed Systems, p.530-537, December 19-21, 1994
• 11: André Seznec, A case for two-way skewed-associative caches, Proceedings of the 20th annual international symposium on Computer architecture, p.169-178, May 16-19, 1993, San Diego, California, United States
• 12: Anant Agarwal , Stephen D. Pudar, Column-associative caches: a technique for reducing the miss rate of direct-mapped caches, Proceedings of the 20th annual international symposium on Computer architecture, p.179-190, May 16-19, 1993, San Diego, California, United States
• 13: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 14: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 15: R. I. Bahar , E. A. Frohm , C. M. Gaona , G. D. Hachtel , E. Macii , A. Pardo , F. Somenzi, Algebric Decision Diagrams and Their Applications, Formal Methods in System Design, v.10 n.2-3, p.171-206, April -May 1997 [doi>10.1023/A:1008699807402]
• 16: [16] J. M. Rabaey, A. Chandrakasan, B. Nikoli¿ Digital Integrated Circuits, Second Edition, Prentice-Hall, 2002.
• 17: [17] M. D. Hill, J. Elder, DineroIV Trace-Driven Uniprocessor Cache Simulator, www.cs.wisc.edu/markhill/DineroIV, 1998.
• 18: Afzal Malik , Bill Moyer , Dan Cermak, A low power unified cache architecture providing power and performance flexibility (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.241-243, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344610]
• 19: [19] T. Givargis, F. Vahid, "Platune: A Tuning Framework for System-on-a-Chip Platforms," IEEE Transactions on Computer Aided Design, Vol. 21, No. 11, Nov. 2002.
• 20: [20] New Mexico State University TraceBase, tracebase.nmsu.edu.