Techniques for compressing program address traces

ABSTRACT

In this paper a technique for generating consistent, reproducible traces with about an order of magnitude better compression than standard general-purpose compression programs is described. With this approach, the trace is read once, an intermediate form is generated and then read as the input to the second pass over the address stream. No program source code is required, and this technique will work on address streams that include OS calls. As a result of the way the address trace is encoded and processed, representing each reference requires only a fraction of a bit, between 0.00114 to 0.878 bits per reference. For example, the roughly 1.6 billion references generated by the xlisp benchmark from the SPEC92 suite can be stored using only about 48.6 million bytes. Depending on the benchmarks, more or less bits per references may be needed.

REFERENCES

• AgSH86: A. Agarwal , R. L. Sites , M. Horowitz, ATUM: a new technique for capturing address traces using microcode, Proceedings of the 13th annual international symposium on Computer architecture, p.119-127, June 02-05, 1986, Tokyo, Japan
• BePF91: Jeffrey C. Becker , Arvin Park , Matthew Farrens, An analysis of the information content of address reference streams, Proceedings of the 24th annual international symposium on Microarchitecture, p.19-24, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123470]
• Beck93: Jeffrey Chaim Becker, Increasing VLSI chip address and data I/O pin bandwidth through compression, University of California at Davis, Davis, CA, 1993
• Hamm77: D. W. Hammerstrom, Analysis of Memory Referencing Behavior, Ph.D. Thesis, Department of Electrical Engineering, University of Illinois at Urbana-Champaign, Champaign, Illinois, (1977).
• HaDa77: D. W. Hammerstrom , E. S. Davidson, Information content of CPU memory referencing behavior, Proceedings of the 4th annual symposium on Computer architecture, p.184-192, March 23-25, 1977
• KeHW94: R. E. Kessler , M. D. Hill , D. A. Wood, A Comparison of Trace-Sampling Techniques for Multi-Megabyte Caches, IEEE Transactions on Computers, v.43 n.6, p.664-675, June 1994 [doi>10.1109/12.286300]
• LaPI88: S. Laha , J. H. Patel , R. K. Iyer, Accurate Low-Cost Methods for Performance Evaluation of Cache Memory Systems, IEEE Transactions on Computers, v.37 n.11, p.1325-1336, November 1988 [doi>10.1109/12.8699]
• Laru93: Computer Staff, Efficient program tracing, Computer, v.26 n.5, p.52-61, May 1993 [doi>10.1109/2.211900]
• SrWa94: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• Welc84: T.A. Welch, "A Technique for High Performance Data Compression", IEEE Computer, voi. t7, no. 6 (June 1984), pp. 8-19.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

General Terms:
Design, Performance, Theory

Keywords:
compression, trace generation