VPC3: A High-Performance Trace Compression Utility
Contact
Prof.
Martin Burtscher
Computer
Systems Laboratory
School of
Electrical and Computer Engineering
Cornell
University, Ithaca, NY 14853
E-mail:
burtscher @ csl.cornell.edu
Web: http://www.csl.cornell.edu/~burtscher/
Overview
In 2003, we introduced VPC1 and VPC2, two trace compression algorithms that are based on value predictors. Both algorithms are quite effective on extended traces (i.e., traces that capture PCs plus other information) but suffer from a relatively slow decompression speed.
VPC3 fixes this shortcoming. It employs a brand new compression algorithm that compresses and decompresses extended program traces faster than other algorithms while at the same time achieving a much higher compression rate.
The key idea behind VPC3 is to use value predictors to expose and enhance the patterns in the traces. It does this by splitting the original trace into four streams (subtraces). Bzip2 is then used to compress the four streams.
Downloading
and Using VPC3
The Source Code of VPC3 and a Sample Trace are available for download and use under these Software License Terms and Conditions. The provided code compresses and decompresses traces that consist of a 4-byte header (which has to spell “vpc3” in ASCII) followed by one or more trace entries, each of which comprises a 4-byte PC field and an 8-byte extended data (ED) field.
4-byte
header; 4-byte PC1, 8-byte ED1; 4-byte PC2, 8-byte ED2; …
Sample Results
The table below shows the geometric-mean compression rate, compression time, and decompression time of three popular compression algorithms as well as VPC3. The traces we used for this study were taken from the SPECcpu2000 benchmark programs and capture the PC and the effective address of all load and store instructions that miss in a simulated 16kB, direct-mapped, 64-byte line, write-allocate L1 data cache.
|
|
gzip |
bzip2 |
sequitur |
vpc3 |
|
compression rate |
7.0 |
11.5 |
21.0 |
38.2 |
|
compression time (min) |
12.1 |
7.6 |
7.0 |
2.1 |
|
decompression time (min) |
0.23 |
1.30 |
0.80 |
0.76 |
VPC3’s Operation
Below is a simple example illustrating how VPC3 compresses each PC and extended data (ED) value from the uncompressed trace. For simplicity, the specific internals of each of the predictors have been left out. Note that the numbers next to the arrows represent bus widths and not PC or ED values. VPC3 converts a trace into four output streams, each of which is then compressed with bzip2. The four compressed streams can optionally be concatenated into one file.
Let us assume that the current PC value in the trace is 1024 and the corresponding ED value is 16. The four predictors VPC3 uses to predict PCs make their predictions and compare them to the actual PC. In our example, predictor1’s prediction of 1024 matches the current PC value. The selector then writes that predictor’s identification code (1) to the first stream.
Then the current PC value is used to index into the ED predictors. Each predictor outputs its current prediction and compares it to the true current ED value. Of the ten predictors VPC3 uses to predict ED values, predictor10’s prediction of 16 is a match. The selector writes the corresponding predictor code (10) to the third stream.
Finally, all the predictors are updated with the true PC or ED value before moving on to the next PC/ED pair in the trace.
Let us assume the next PC/ED pair in the trace is 8200/385. Again, the four PC predictors output four predictions. However, for this PC none of the predictors produces a match. The selector thus writes a special code (0) to the first stream to flag the value as unpredictable, and the unpredictable PC value (8200) is written to the second stream.
Once more, the current PC value is used to index into the ED predictors. This time none of the ED predictors produces a correct prediction. Hence, the selector writes a special code (0) to the third stream, indicating an unpredictable value, and the actual ED value (385) is recorded in the fourth stream.
Then, all the predictors are updated appropriately before moving on to the next PC/ED pair in the trace.
Related
Publications
M. Burtscher. “VPC3: A Fast and Effective Trace-Compression Algorithm.” Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’04). June 2004. [abstract] [pdf]
M. Burtscher and M. Jeeradit. “Compressing Extended Program Traces Using Value Predictors.” 12th International Conference on Parallel Architectures and Compilation Techniques (PACT’03), pp. 159-169. September 2003. [abstract] [pdf]
Compression
Links
MACHE: a trace-compression utility that exploits the locality of memory references
PDATS2: a compression algorithm for traces that is based on storing only the differences between successive memory references
SEQUITUR: a trace-compression algorithm that builds a context-free grammar and allows the extraction of interesting information from the compressed trace without the need for decompression
SBC: a stream-based compression algorithm for program traces
GZIP: a general-purpose compression utility found on most UNIX systems
BZIP2: a general-purpose compressor providing better but slower compression than gzip
LZOP: a general-purpose compression utility providing very high compression and decompression speeds
General FAQ on compression
Acknowledgment
This work was supported in part by the National Science Foundation under Grants No. 0208567 and 0312966.
Page maintained by Martin Burtscher, Nana B. Sam, Ilya Ganusov, Sandra J. Jackson, Paruj Ratanaworabhan, and Jian Ke.
Last update: 17 June 2004