Lossless Trace Compression

The tremendous storage space required for a useful data base of program traces has prompted a search for trace reduction techniques. In this paper we discuss a range of information-lossless ad-dress and instruction trace compression schemes that can reduce both storage space and access time by an order of magnitude or more, without discarding either references or inter-reference timing in-formation from the original trace. The PDATS family of trace compression techniques achieves trace coding densities of about six references per byte. This family of techniques is now in use as the standard in the NMSU TraceBase, an extensive trace archive that has been established for use by the international research and teaching community. Index Terms: Trace reduction, trace compression, lossless coding, trace-driven simulation. 1