Arithmetic program paths

ABSTRACT

We present Arithmetic Program Paths, a novel, efficient way to compress program control-flow traces that reduces program bit traces to less than a fifth of their original size while being fast and memory efficient. In addition, our method supports online, selective tracing and compression of individual conditionals, trading off memory usage and compression rate. We achieve these properties by recording only the directions taken by conditional statements during program execution, and using arithmetic coding for compression. We provide the arithmetic coder with a probability distribution for each conditional that we obtain using branch prediction techniques. We implemented the technique and experimented on several SPEC 2000 programs. Our method matches the compression rate of state-of-the-art tools while being an order of magnitude faster.

REFERENCES

• 1: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 2: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 3: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 4: 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
• 5: Martin Burtscher , Metha Jeeradit, Compressing Extended Program Traces Using Value Predictors, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.159, September 27-October 01, 2003
• 6: John G. Cleary and Ian H. Witten. A comparison of enumerative and adaptive codes. IEEE Transactions on Information Theory, 30(2):306--315, March 1984.
• 7: Evelyn Duesterwald , Vasanth Bala, Software profiling for hot path prediction: less is more, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.202-211, November 2000, Cambridge, Massachusetts, United States
• 8: Rajiv Gupta , Mary Lou Soffa, Hybrid slicing: an approach for refining static slices using dynamic information, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.29-40, October 12-15, 1995, Washington, D.C., United States
• 9: Pascal Van Hentenryck, Incremental constraint satisfaction in logic programming, Logic programming, MIT Press, Cambridge, MA, 1990
• 10: D.A. Huffman. A method for the construction of minimum redundancy codes. In Proceedings of IRE, volume 40, pages 1098--1101, 1952.
• 11: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Interprocedural conditional branch elimination, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.146-158, June 16-18, 1997, Las Vegas, Nevada, United States
• 12: G. G. Langdon. Introduction to arithmetic coding. IBM Journal of Research and Development, 1984.
• 13: J. R. Larus, Abstract execution: a technique for efficiently tracing programs, Software—Practice & Experience, v.20 n.12, p.1241-1258, Dec. 1990 [doi>10.1002/spe.4380201205]
• 14: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 15: Zhijian Lu , John Lach , Mircea R. Stan , Kevin Skadron, Alloyed branch history: combining global and local branch history for robust performance, International Journal of Parallel Programming, v.31 n.2, p.137-177, April 2003 [doi>10.1023/A:1022669325321]
• 16: Scott McFarling. Combining branch predictors. Technical Note TN-36, Digital Equipment Corporation Western Research Laboratory (WRL), June 1993.
• 17: David Melski and Thomas Reps. Interprocedural path profiling. Technical Report CS-TR-1998-1382, University of Wisconsin, Madison, September 1998.
• 18: A. Moffat , R. Neal, Arithmetic coding revisited, Proceedings of the Conference on Data Compression, p.202, March 28-30, 1995
• 19: Ravi Nair. Branch behavior on the IBM RS/6000. Technical Report 17859, IBM Thomas J. Watson Research Center, 1992.
• 20: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 21: Craig G. Nevill-Manning , Ian H. Witten, Linear-Time, Incremental Hierarchy Inference for Compression, Proceedings of the Conference on Data Compression, p.3, March 25-27, 1997
• 22: Richard Clark Pasco, Source coding algorithms for fast data compression., 1976
• 23: 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]
• 24: Steven P. Reiss, Trace-Based Debugging, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.305-314, May 03-05, 1993
• 25: Steven P. Reiss , Manos Renieris, Encoding program executions, Proceedings of the 23rd International Conference on Software Engineering, p.221-230, May 12-19, 2001, Toronto, Ontario, Canada
• 26: J.J. Risannen. Arithmetic codings as number representations. In Acta Polytech. Scand. Math., 1979.
• 27: Claude E. Shannon. A mathematical theory of communication. Technical report, Bell Systems Technical Journal, 1948.
• 28: John Paul Shen and Mikko H. Lipasti. Modern Processor Design: Fundamentals of Superscalar Processors. McGraw-Hill, 2005.
• 29: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 30: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 31: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 32: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States
• 33: Youtao Zhang , Rajiv Gupta, Timestamped whole program path representation and its applications, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.180-190, June 2001, Snowbird, Utah, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Experimentation, Measurement, Performance

Keywords:
arithmetic coding, bit-tracing, branch prediction