ABSTRACT
This paper describes split-stream dictionary (SSD) compression, a new technique for transforming programs into a compact, interpretable form. We define a compressed program as interpretable when it can be decompressed at basic-block granularity with reasonable efficiency. The granularity requirement enables interpreters or just-in-time (JIT) translators to decompress basic blocks incrementally during program execution. Our previous approach to interpretable compression, the Byte-coded RISC (BRISC) program format [1], achieved unprecedented decompression speed in excess of 5 megabytes per second on a 450MHz Pentium II while compressing benchmark programs to an average of three-fifths the size of their optimized x86 representation. SSD compression combines the key idea behind BRISC with new observations about instruction re-use frequencies to yield four advantages over BRISC and other competing techniques. First, SSD is simple, requiring only a few pages of code for an effective implementation. Second, SSD compresses programs more effectively than any interpretable program compression scheme known to us. For example, SSD compressed a set of programs including the spec95 benchmarks and Microsoft Word97 to less than half the size, on average, of their optimized x86 representation. Third, SSD exceeds BRISC's decompression and JIT translation rates by over 50%. Finally, SSD's two-phased approach to JIT translation enables a virtual machine to provide graceful degradation of program execution time in the face of increasing RAM constraints. For example, using SSD, we ran Word97 using a JIT-translation buffer one-third the size of Word97's optimized x86 code, yet incurred only 27% execution time overhead.
- 1.J. Ernst, W. Evans, C. Fraser, S. Lucco, and T. Proebsting, "Code compression," PLDI '97:358-365, 6/97. Google ScholarDigital Library
- 2.http ://www'palm'c~m/h~me'htmlGoogle Scholar
- 3.J. Kahn, R.H. Katz, K.Pister, "MOBICOM challenges: mobile networking for 'Smart Dust'," ACM MOBICOM Conference, Seattle, WA, 8/99. Google ScholarDigital Library
- 4.J. Hennessy and D. Patterson, Computer Architecture: A Quantitative Approach, Addison-Wesley, ISBN 1-55860- 329-8. Google ScholarDigital Library
- 5.Intel Corp., Pentium Processor User's Manual Volume 3: Architecture and Programming Manual, Intel Literature Sales, ISBN 1-55512-195-0.Google Scholar
- 6.http://developer.intel.com/design/ia64/microarch_ovw/index. htm.Google Scholar
- 7.S. Furber, ARM System Architecture, Addison-Wesley, ISBN 0-201-40352-8. Google ScholarDigital Library
- 8.S. Lucco, O. Sharp, and R. Wahbe, "Omniware: a universal substrate for web programming," in Fourth International World Wide Web Conference, Boston, Massachusetts, 12/95. http ://www.w3.org/Conferences/WWW4/Papers/165/.Google Scholar
- 9.A. Adl-Tabatabai, G. Langdale, S. Lucco, and R. Wahbe, "Efficient and language-independent mobile programs," PLDI '96:127-136, 6/96. Google ScholarDigital Library
- 10.A. Lempel and J. Ziv, "On the complexity of finite sequences," IEEE Transactions on Information Theory 22(1):75-81, 1/76. Google ScholarDigital Library
- 11.J. Ziv and A. Lempel, "Compression of individual sequences via variable-rate coding," IEEE Transactions on Information Theory 24(5):530-536, 9/78. Google ScholarDigital Library
- 12.C. Fraser, "Automatic inference of models for statistical code compression," PLDI '99:242-246, 5/99. Google ScholarDigital Library
- 13.K. Arnold and J. Gosling, The Java Programming Language, Addison-Wesley, ISBN 0-201-63455-4. Google ScholarDigital Library
- 14.W. Pugh, "Compressing java class files," PLDI '99:247-258, 5/99. Google ScholarDigital Library
- 15."Architecture Neutral Distribution Format: a white paper," Open Software Foundation, 11/90.Google Scholar
- 16.T. Kistler and M. Franz, "Slim binaries," Communications of the ACM, 40(12):87-94, 12/97. Google ScholarDigital Library
- 17.M. Franz, "Adaptive compression of syntax trees and iterative dynamic code optimization: Two basic technologies for mobile-object systems," TR 97-04, Dept. of Information and Computer Science, University of California, Irvine, 2/97.Google Scholar
- 18.I. Witten, R. Neal, and J. Cleary, "Arithmetic coding for data compression," Communications of the ACM 30(6):520- 540, 6/87. Google ScholarDigital Library
- 19.T. Yu, "Data compression for PC software distribution," Software-Practice & Experience 26(11): 1181-1195, 11/96. Google ScholarDigital Library
- 20.R. Jones and R. Lins, Garbage Collection: Algorithms for Automatic Dynamic Memory Management, Wiley, ISBN 0- 471-94148-4. Google ScholarDigital Library
Index Terms
- Split-stream dictionary program compression
Recommendations
Split-stream dictionary program compression
This paper describes split-stream dictionary (SSD) compression, a new technique for transforming programs into a compact, interpretable form. We define a compressed program as interpretable when it can be decompressed at basic-block granularity with ...
Lossless compression of VLSI layout image data
We present a novel lossless compression algorithm called Context Copy Combinatorial Code (C4), which integrates the advantages of two very disparate compression techniques: context-based modeling and Lempel-Ziv (LZ) style copying. While the algorithm ...
FPGA bitstream compression and decompression using LZ and golomb coding (abstract only)
FPGA '13: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arraysIn this paper we propose an optimized bitstream compression algorithm based on LZ and a novel architecture of decompressor, the proposed algorithm improves the Compression Ratio by fully utilizing the regularity of configuration bits of CLB (...
Comments