Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
A real-time program trace compressor utilizing double move-to-front method
Uzelac V., Milenkovic A.  DAC 2009 (Proc. of the 46th Annual Design Automation Conference, San Francisco, California, Jul 26-31, 2009)738-743.2009.Type:Proceedings
Date Reviewed: Jan 15 2010

The move-to-front (MTF) transform is a standard data compression technique that reduces the entropy of data streams. After a symbol has been processed, it is moved to the top of the history table, which ensures that frequently used symbols are encoded using fewer bits.

Uzelac and Milenkovic propose using the MTF transform to perform program tracing by enhancing the technique to two levels--the double move-to-front (DMTF) method. As the paper states, “consider the following repeating stream pattern {ABAC}.” {ABAC} may be encoded as a pattern of {1212} at the first-level MTF, and then encoded as a pattern of {1111} at the second-level MTF. This way, “the MTF transformation lowers the number of frequent symbols.” The authors further extend the method by using last-value predictors and adaptive zero-length counters.

The trace compressor with the best performance configuration achieves a compression ratio between 83:1 and 29389:1; “the average weighted compression ratio is 268:1.” The resulting code requires 0.001 to 0.39 bits per instruction, with an average of 0.12 bits per instruction. The estimated complexity of the best performing configuration is equivalent to 25,000 logic gates.

This well-written paper proposes an innovative technique. Unfortunately, the authors fail to compare the performance of the proposed technique to that of other program trace compressors. Also, since DMTF is an enhancement of the MTF transform in data compression, the paper should have evaluated the method in relation to other data compression techniques.

Reviewer:  T.H. Tse Review #: CR137634 (1008-0794)
Bookmark and Share
Design Aids (B.7.2 )
Testing And Debugging (D.2.5 )
Coding And Information Theory (E.4 )
Would you recommend this review?
Other reviews under "Design Aids": Date
Transaction management in the design environment
Katz R.  New applications of data bases (, Cambridge, UK,2731984. Type: Proceedings
Oct 1 1985
Application of a transformational software development methodology to VLSI design
Mostow J., Balzer B. Journal of Systems and Software 4(1): 51-61, 1984. Type: Article
Jan 1 1985
Design automation: automated full-custom VLSI layout using the ULYSSES design environment
Bushnell M., Academic Press Prof., Inc., San Diego, CA, 1988. Type: Book (9789780121484002)
May 1 1989

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy