Instruction trace compression for rapid instruction cache simulation

ABSTRACT

Modern Application Specific Instruction Set Processors (ASIPs) have customizable caches, where the size, associativity and line size can all be customized to suit a particular application. To find the best cache size suited for a particular embedded system, the application(s) is/are executed, traces obtained, and caches simulated. Typically, program trace files can range from a few megabytes to several gigabytes. Simulation of cache performance using large program trace files is a time consuming process. In this paper, a novel instruction cache simulation methodology that can operate directly on a compressed program trace file without the need for decompression is presented. This feature allowed our simulation methodology to have an average speed up of 9.67 times compared to the existing state of the art tool (Dinero IV cache simulator), for a range of applications from the Mediabench suite.

REFERENCES

• 1: Xtensa Processor, http://www.tensilica.com.
• 2: Seagate Technology, http://www.seagate.com/docs/pdf/marketing/po-db35.pdf
• 3: Haris Lekatsas , Jörg Henkel , Wayne Wolf, Code compression for low power embedded system design, Proceedings of the 37th conference on Design automation, p.294-299, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337423]
• 4: J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Trans. on Information Theory, v. 23, pp. 337 -- 343, May 1977.
• 5: J. Ziv and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding," IEEE Trans. on Information Theory, v. 24, n. 5, Sept. 1978.
• 6: T. A. Welch, "A Technique for High-Performance Data Compression," Computer, v. 17, n. 6, June 1984, pp. 8 -- 19.
• 7: Andrew R. Pleszkun, Techniques for compressing program address traces, Proceedings of the 27th annual international symposium on Microarchitecture, p.32-39, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192728]
• 8: E. E. Johnson and J. Ha, "PDATS: Lossless address space compression for reducing file size and access time," IEEE International Phoenix Conference on Computers and Communication, 1994.
• 9: Eric E. Johnson , Jiheng Ha , M. Baqar Zaidi, Lossless Trace Compression, IEEE Transactions on Computers, v.50 n.2, p.158-173, February 2001 [doi>10.1109/12.908991]
• 10: C. G. Nevill-Manning and I. H. Witten, "Identifying Hierarchical Structure in Sequences: A linear-time algorithm," JAIR," pp. 67--82, 1997.
• 11: Scott F. Kaplan , Yannis Smaragdakis , Paul R. Wilson, Flexible reference trace reduction for VM simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.1, p.1-38, January 2003 [doi>10.1145/778553.778554]
• 12: A. Milenkovic and M. Milenkovic, "Exploiting Streams in Instruction and Data Address Trace Compression," IEEE WWC, pp. 99--107, 2003.
• 13: Martin Burtscher, VPC3: a fast and effective trace-compression algorithm, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 14: Yue Luo , Lizy Kurian John, Locality-Based Online Trace Compression, IEEE Transactions on Computers, v.53 n.6, p.723-731, June 2004 [doi>10.1109/TC.2004.12]
• 15: Xiangyu Zhang , Rajiv Gupta, Whole Execution Traces, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.105-116, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.37]
• 16: Xiangyu Zhang , Rajiv Gupta, Whole execution traces and their applications, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.3, p.301-334, September 2005 [doi>10.1145/1089008.1089012]
• 17: 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
• 18: J. Edler and M. D. Hill, "Dinero IV Trace-Driven Uniprocessor Cache Simulator," http://www.cs.wisc.edu/~markhill/DineroIV/.
• 19: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263657]
• 20: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 21: Andhi Janapsatya , Aleksandar Ignjatović , Sri Parameswaran, Finding optimal L1 cache configuration for embedded systems, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118482]
• 22: Arijit Ghosh , Tony Givargis, Analytical Design Space Exploration of Caches for Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10650, March 03-07, 2003