A Case for Compressing Traces with BDDs [abstract] (IEEE Xplore, PDF, Google Tech Talk)
Graham D. Price and Manish Vachharajani
IEEE Computer Architecture Letters (CAL), Volume 5, Number 2, December 2006.
Instruction-level traces are widely used for program and hardware
analysis. However, program traces for just a few seconds of execution
are enormous, up to several terabytes in size, uncompressed.
Specialized compression can shrink traces to a few gigabytes, but
trace analyzers typically stream the the decompressed trace
through the analysis engine. Thus, the complexity of analysis depends
on the decompressed trace size (even though the decompressed trace is
never stored to disk). This makes many global or interactive analyses
infeasible.
This paper presents a method to compress program traces using
binary decision diagrams (BDDs). BDDs intrinsically support
operations common to many desirable program analyses and these
analyses operate directly on the BDD. Thus, they are often polynomial
in the size of the compressed representation. The paper
presents mechanisms to represent a variety of trace data using BDDs
and shows that BDDs can store, in 1 GB of RAM, the entire
data-dependence graph of traces with over 1 billion instructions.
This allows rapid computation of global analyses such as
heap-object liveness and dynamic slicing.