Compressing address trace data for cache simulations

Summary form only given. Our new approach of storing address traces, the RPS format (recovered program structure), is based on two ideas: first, the structure of the underlying program is reconstructed from the address trace, and second, the output is decomposed in multiple files such that gzip can take advantage of repeated input patterns. In the first step, the control flow of the program is determined by identifying the basic blocks, i.e., the straight segments of code with no jumps in and out. Then, the invocation sequence of basic blocks is written to a file, which can be compressed by a factor of more than 35, since gzip can easily detect patterns in it. The basic block data contains information on the length of a basic block and on the position of load and store instructions among all instructions. Their addresses are stored in separate files. In the second step, the load and store references are partitioned in global, local and unassigned variable classes. Global variables have the same value for all invocations of a basic block, local variables can be represented as base + offset, where offset is a constant and base only changes between invocations of a basic block. All other variables are “unassigned” and their addresses are stored in separate files as a difference to the previous value