| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
The VPC Trace-Compression Algorithms
November 2005 (vol. 54 no. 11)
pp. 1329-1344
Execution traces, such as are used to study and analyze program behavior, are often so large that they need to be stored in compressed form. This paper describes the design and implementation of four value prediction-based compression (VPC) algorithms for traces that record the PC as well as other information about executed instructions. VPC1 directly compresses traces using value predictors, VPC2 adds a second compression stage, and VPC3 utilizes value predictors to convert traces into streams that can be compressed better and more quickly than the original traces. VPC4 introduces further algorithmic enhancements and is automatically synthesized. Of the 55 SPECcpu2000 traces we evaluate, VPC4 compresses 36 better, decompresses 26 faster, and compresses 53 faster than BZIP2, MACHE, PDATS II, SBC, and SEQUITUR. It delivers the highest geometric-mean compression rate, decompression speed, and compression speed because of the predictors' simplicity and their ability to exploit local value locality. Most other compression algorithms can only exploit global value locality.
[1] 1329 J. Ahola, “Compressing Address Traces with RECET,” Proc. 2001 IEEE Int'l Workshop Workload Characterization, pp. 120-126, Dec. 2001.[2] R. Brown, K. Driesen, D. Eng, L. Hendren, J. Jorgensen, C. Verbrugge, and Q. Wang, “STEP: A Framework for the Efficient Encoding of General Trace Data,” Proc. Workshop Program Analysis for Software Tools and Eng., pp. 27-34, Nov. 2002.[3] M. Burrows and D.J. Wheeler, “A Block-Sorting Lossless Data Compression Algorithm,” Digital SRC Research Report 124, May 1994.[4] M. Burtscher, “VPC3: A Fast and Effective Trace-Compression Algorithm,” Proc. Joint Int'l Conf. Measurement and Modeling of Computer Systems, pp. 167-176, June 2004.[5] M. Burtscher and M. Jeeradit, “Compressing Extended Program Traces Using Value Predictors,” Proc. Int'l Conf. Parallel Architectures and Compilation Techniques, pp. 159-169, Sept. 2003.[6] M. Burtscher and N.B. Sam, “Automatic Generation of High-Performance Trace Compressors,” Proc. 2005 Int'l Symp. Code Generation and Optimization, pp. 229-240, Mar. 2005.[7] M. Burtscher and B.G. Zorn, “Exploring Last $n$ Value Prediction,” Proc. Int'l Conf. Parallel Architectures and Compilation Techniques, pp. 66-76, Oct. 1999.[8] M. Burtscher and B.G. Zorn, “Hybrid Load-Value Predictors,” IEEE Trans. Computers, vol. 51, no. 7, pp. 759-774, July 2002.[9] I.K. Chen, J.T. Coffey, and T.N. Mudge, “Analysis of Branch Prediction via Data Compression,” Proc. Seventh Int'l Conf. Architectural Support for Programming Languages and Operating Systems, pp. 128-137, Oct. 1996.[10] E.N. Elnozahy, “Address Trace Compression through Loop Detection and Reduction,” Proc. Int'l Conf. Measurement and Modeling of Computer Systems, pp. 214-215, May 1999.[11] A. Eustace and A. Srivastava, “ATOM: A Flexible Interface for Building High Performance Program Analysis Tools,” WRL Technical Note TN-44, Digital Western Research Laboratory, Palo Alto, Calif., July 1994.[12] E. Federovsky, M. Feder, and S. Weiss, “Branch Prediction Based on Universal Data Compression Algorithms,” Proc. 25th Int'l Symp. Computer Architecture, pp. 62-72, June 1998.[13] F. Gabbay, “Speculative Execution Based on Value Prediction,” Electrical Eng. Dept. Technical Report #1080, Technion-Israel Inst. of Tech nology, Nov. 1996.[14] B. Goeman, H. Vandierendonck, and K. Bosschere, “Differential FCM: Increasing Value Prediction Accuracy by Improving Table Usage Efficiency,” Proc. Seventh Int'l Symp. High Performance Computer Architecture, pp. 207-216, Jan. 2001.[15] O. Hammami, “Taking into Account Access Pattern Irregularity when Compressing Address Traces,” Proc. Southeastcon, pp. 74-77, Mar. 1995.[16] A. Hamou-Lhadj and T.C. Lethbridge, “Compression Techniques to Simplify the Analysis of Large Execution Traces,” Proc. 10th Int'l Workshop Program Comprehension, pp. 159-168, June 2002.[17] http://sequence.rutgers.edu/sequitursequitur.cc , 2005.[18] http://sources.redhat.combzip2/, 2005.[19] http:/www.cygwin.com/, 2005.[20] http://www.ece.uah.edu/lacasa/sbcsbc.html , 2005.[21] http:/www.gzip.org/, 2005.[22] http://www.spec.org/osgcpu2000/, 2005.[23] E.E. Johnson, “PDATS II: Improved Compression of Address Traces,” Proc. Int'l Performance, Computing, and Comm. Conf., pp. 72-78, Feb. 1999.[24] E.E. Johnson and J. Ha, “PDATS: Lossless Address Trace Compression for Reducing File Size and Access Time,” Proc. IEEE Int'l Phoenix Conf. Computers and Comm., pp. 213-219, Apr. 1994.[25] E.E. Johnson, J. Ha, and M.B. Zaidi, “Lossless Trace Compression,” IEEE Trans. Computers, vol. 50, no. 2, pp. 158-173, Feb. 2001.[26] R.E. Kessler, E.J. McLellan, and D.A. Webb, “The Alpha 21264 Microprocessor Architecture,” Proc. Int'l Conf. Computer Design, pp. 90-95, Oct. 1998.[27] D.E. Knuth, “Dynamic Huffman Coding,” J. Algorithms, vol. 6, pp. 163-180, 1985.[28] J.R. Larus, “Abstract Execution: A Technique for Efficiently Tracing Programs,” Software-Practice and Experience, vol. 20, no. 12, pp. 1241-1258, Dec. 1990.[29] J.R. Larus, “Whole Program Paths,” Proc. Conf. Programming Language Design and Implementation, pp. 259-269, May 1999.[30] M.H. Lipasti and J.P. Shen, “Exceeding the Dataflow Limit via Value Prediction,” Proc. 29th Int'l Symp. Microarchitecture, pp. 226-237, Dec. 1996.[31] M.H. Lipasti, C.B. Wilkerson, and J.P. Shen, “Value Locality and Load Value Prediction,” Proc. Seventh Int'l Conf. Architectural Support for Programming Languages and Operating Systems, pp. 138-147, Oct. 1996.[32] Y. Luo and L.K. John, “Locality-Based Online Trace Compression,” IEEE Trans. Computers, vol. 53, no. 6, pp. 723-731, June 2004.[33] A. Milenkovic and M. Milenkovic, “Stream-Based Trace Compression,” Computer Architecture Letters, vol. 2, Sept. 2003.[34] A. Milenkovic and M. Milenkovic, “Exploiting Streams in Instruction and Data Address Trace Compression,” Proc. Sixth Ann. Workshop Workload Characterization, pp. 99-107, Oct. 2003.[35] C.G. Nevill-Manning and I.H. Witten, “Linear-Time, Incremental Hierarchy Interference for Compression,” Proc. Data Compression Conf., pp. 3-11, Mar. 1997.[36] C.G. Nevill-Manning and I.H. Witten, “Identifying Hierarchical Structure in Sequences: A Linear-Time Algorithm,” J. Artificial Intelligence Research, vol. 7, pp. 67-82, Sept. 1997.[37] C.G. Nevill-Manning and I.H. Witten, “Compression and Explanation Using Hierarchical Grammars,” The Computer J., vol. 40, pp. 103-116, 1997.[38] A.R. Pleszkun, “Techniques for Compressing Program Address Traces,” Proc. 27th Ann. IEEE/ACM Int'l Symp. Microarchitecture, pp. 32-40, Nov. 1994.[39] G. Reinman and B. Calder, “Predictive Techniques for Aggressive Load Speculation,” Proc. 31st Int'l Symp. Microarchitecture, pp. 127-137, Dec. 1998.[40] B. Rychlik, J.W. Faistl, B.P. Krug, and J.P. Shen, “Efficacy and Performance Impact of Value Prediction,” Proc. Int'l Conf. Parallel Architectures and Compilation Techniques, pp. 148-154, Oct. 1998.[41] A.D. Samples, “Mache: No-Loss Trace Compaction,” Proc. Int'l Conf. Measurement and Modeling of Computer Systems, vol. 17, no. 1, pp. 89-97, Apr. 1989.[42] Y. Sazeides and J.E. Smith, “Implementations of Context Based Value Predictors,” Technical Report ECE-97-8, Univ. of Wisconsin-Madison, Dec. 1997.[43] Y. Sazeides and J.E. Smith, “The Predictability of Data Values,” Proc. 30th Int'l Symp. Microarchitecture, pp. 248-258, Dec. 1997.[44] A. Srivastava and A. Eustace, “ATOM: A System for Building Customized Program Analysis Tools,” Proc. Conf. Programming Language Design and Implementation, pp. 196-205, June 1994.[45] D. Tullsen and J. Seng, “Storageless Value Prediction Using Prior Register Values,” Proc. 26th Int'l Symp. Computer Architecture, pp. 270-279, May 1999.[46] J.S. Vitter, “Design and Analysis of Dynamic Huffman Codes,” J. ACM, vol. 34, no. 4, pp. 825-845, Oct. 1987.[47] K. Wang and M. Franklin, “Highly Accurate Data Value Prediction Using Hybrid Predictors,” Proc. 30th Int'l Symp. Microarchitecture, pp. 281-290, Dec. 1997.[48] T.A. Welch, “A Technique for High-Performance Data Compression,” Computer, pp. 8-19, June 1984.[49] Y. Zhang and R. Gupta, “Timestamped Whole Program Path Representation and Its Applications,” Proc. Conf. Programming Language Design and Implementation, pp. 180-190, June 2001.[50] J. Ziv and A. Lempel, “A Universal Algorithm for Data Compression,” IEEE Trans. Information Theory, vol. 23, no. 3, pp. 337-343, May 1977.
Index Terms:
Index Terms- Data compaction and compression, performance analysis and design aids.
Citation:
Martin Burtscher, Ilya Ganusov, Sandra J. Jackson, Jian Ke, Paruj Ratanaworabhan, Nana B. Sam, "The VPC Trace-Compression Algorithms," IEEE Transactions on Computers, vol. 54, no. 11, pp. 1329-1344, Nov. 2005, doi:10.1109/TC.2005.186
