Compressing Variable-length Instruction Traces

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Trace-driven simulation is a widely used technique to study computer architecture systems and to evaluate micro architecture features. A trace may contain execution information for billions or even trillions of instructions and storing these traces is a challenge itself. In this paper we describe VITC, a one-pass trace compression tool based in streams. VITC is based on SBC and compresses traces by exploiting the natural instruction and data redundancy in instruction streams. The VITC is capable of compressing traces of variable-length instructions, such as x86 instruction traces, and produces compressed files 87 times smaller than gzip and 47 times smaller than bzip2. The compressed traces produced by VITC are, on average, 1200 times smaller than the original ones. © 2012 IEEE.103109Brazilian Computer Society (SBC),CAPES,FAPERJ,Cons. Nac. Desenvolv. Cient. Tecnol. (CNPq),Ministerio da Ciencia, Tecnologia e InovacaoConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Burtscher, M., Vpc3: A fast and effective trace-compression algorithm (2004) SIGMETRICS Perform. Eval. Rev., 32, pp. 167-176Burtscher, M., Sam, N.B., Automatic generation of high-performance trace compressors (2005) Proceedings of the International Symposium on Code Generation and Optimization, pp. 229-240Edler, J., Hill, M.D., Dinero Iv Trace-driven Uniprocessor Cache Simulator, , http://www.cs.wisc.edu/~markhill/DineroIV/, Acessado em 27/08/2012Henning, J.L., Spec cpu2006 benchmark descriptions (2006) SIGARCH Comput. Archit. News, 34, pp. 1-17Johnson, E.E., Ha, J., Zaidi, M.B., Lossless trace compression (2001) IEEE Trans. Comput., 50, pp. 158-173Larus, J.R., Whole program paths (1999) SIGPLAN Not., 34, pp. 259-269Lawton, K.P., Bochs: A portable pc emulator for unix/x (1996) Linux J., 7, p. 1996Luo, Y., John, L.K., Locality-based online trace compression (2004) IEEE Trans. Comput., 53, pp. 723-731Milenković, A., Milenković, M., Exploiting streams in instruction and data address trace compression (2003) Proceedings of IEEE 6th Annual Workshop on Workload Characterization, pp. 99-107Milenković, A., Milenković, M., An efficient single-pass trace compression technique utilizing instruction streams (2007) ACM Trans. Model. Comput. Simul., 17Nevill-Manning, C.G., Witten, I.H., Linear-time, incremental hierarchy inference for compression (1997) Proceedings of Data Compression Conference, pp. 3-11Samples, A.D., Mache: No-loss trace compaction (1989) SIGMETRICS Perform. Eval. Rev., 17, pp. 89-97Uhlig, R.A., Trace-driven memory simulation: A survey (2004) ACM Computing Surveys, 29, pp. 128-170Zhang, Y., Gupta, R., Timestamped whole program path representation and its applications (2001) Proceedings of ACM SIGPLAN Conf. on Programming Language Design and Implementation, pp. 180-190Ziv, J., Lempel, A., A universal algorithm for sequential data compression (1977) IEEE Transactions on Information Theory, 23, pp. 337-34