Application-specific reconfigurable XOR-indexing to eliminate cache conflict misses

ABSTRACT

Embedded systems allow application-specific optimizations to improve the power/performance trade-off. In this paper, we show how application-specific hashing of the address can eliminate a large number of conflict misses in caches. We consider XOR-functions: each set index bit is computed as the XOR of a subset of the address bits.Previous work has considered simpler bit-selecting functions. Compared to such work, the contributions of this paper are two-fold. Firstly, we present a heuristic algorithm to construct application-specific XOR-functions. Secondly, in order to adapt the hashing to the application, we show that a reconfigurable XOR-function selector is inherently less complex than a reconfigurable selector for bit-selecting functions. This is possible by placing restrictions on the allowed XOR-functions.Our evaluation shows a reduction of cache misses for standard benchmarks averaging between 30% and 60%, depending on the cache size.

REFERENCES

• 1: S. G. Abraham and H. Agusleo. Reduction of cache interference misses through selective bit-permutation mapping. Technical Report CSE-TR-205-94, The University of Michigan, 1994.
• 2: François Bodin , André Seznec, Skewed Associativity Improves Program Performance and Enhances Predictability, IEEE Transactions on Computers, v.46 n.5, p.530-544, May 1997 [doi>10.1109/12.589219]
• 3: J. M. Frailong, W. Jalby, and J. Lenfant. XOR-schemes: A flexible data organization in parallel memories. In Proceedings of the 1985 International Conference on Parallel Processing, pages 276--283, Aug. 1985.
• 4: 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]
• 5: Antonio González , Mateo Valero , Nigel Topham , Joan M. Parcerisa, Eliminating cache conflict misses through XOR-based placement functions, Proceedings of the 11th international conference on Supercomputing, p.76-83, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263599]
• 6: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop on, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 7: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 8: K. Patel , E. Macii , L. Benini , M. Poncino, Reducing cache misses by application-specific re-configurable indexing, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.125-130, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382556]
• 9: 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
• 10: M. Schlansker, R. Shaw, and S. Sivaramakrishnan. Randomization and associativity in the design of placement-insensitive caches. Technical Report HPL-93-41, HP Laboratories, June 1993.
• 11: J. Scott, L. Lee, J. Arends, and B. Moyer. Designing the low-power M Core architecture. In Proceedings of the IEEE Power Driven Microarchitecture Workshop, pages 145--150, June 1998.
• 12: 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]
• 13: H. Vandierendonck. Avoiding Mapping Conflicts in Microprocessors. PhD thesis, Ghent University, 2004.
• 14: Hans Vandierendonck , Koen De Bosschere, XOR-Based Hash Functions, IEEE Transactions on Computers, v.54 n.7, p.800-812, July 2005 [doi>10.1109/TC.2005.122]