research-article

A real-time program trace compressor utilizing double move-to-front method

Authors:

Vladimir Uzelac,

Aleksandar MilenkovicAuthors Info & Claims

DAC '09: Proceedings of the 46th Annual Design Automation Conference

Pages 738 - 743

https://doi.org/10.1145/1629911.1630102

Published: 26 July 2009 Publication History

Get Access

Abstract

This paper introduces a new unobtrusive and cost-effective method for the capture and compression of program execution traces in real-time, which is based on a double move-to-front transformation. We explore its effectiveness and describe a cost-effective hardware implementation. The proposed trace compressor requires only 0.12 bits per instruction of trace port bandwidth, at the cost of 25K gates.

References

[1]

ARM, "Embedded Trace Macrocell Architecture Specification," http://infocenter.arm.com.

Google Scholar

[2]

Altera, "Nios II Processor Reference Handbook," http://www.altera.com.

Google Scholar

[3]

Xilinx, "MicroBlaze Processor Reference Guide Embedded Development Kit EDK 10.1i," http://www.xilinx.com.

Google Scholar

[4]

"Lauterbach GmbH," http://www.lauterbach.com.

Google Scholar

[5]

C.-F. Kao, et al., "A Hardware Approach to Real-Time Program Trace Compression for Embedded Processors," IEEE Transactions on Circuits and Systems, vol. 54, pp. 530--543, 2007.

Crossref

Google Scholar

[6]

M.-C. Hsieh and C.-T. Huang, "An embedded infrastructure of debug and trace interface for the DSP platform," in 45th ACM Design Automation Conference, 2008.

Digital Library

Google Scholar

[7]

M. Milenkovic, et al., "Algorithms and Hardware Structures for Unobtrusive Real-Time Compression of Instruction and Data Address Traces" Data Compression Conference, pp. 283--292, 2007

Digital Library

Google Scholar

[8]

M. R. Guthaus, et al., "MiBench: A free, commercially representative embedded benchmark suite," in Proceedings of the IEEE 4th Workshop on Workload Characterization, 2001.

Digital Library

Google Scholar

[9]

T. Austin, et al., "SimpleScalar: An Infrastructure for Computer System Modeling," Computer, vol. 35, pp. 59--67, 2002.

Digital Library

Google Scholar

[10]

B. Jon Louis, et al., "A locally adaptive data compression scheme," Commun. ACM, vol. 29, pp. 320--330, 1986.

Digital Library

Google Scholar

[11]

M. Burrows and D. J. Wheeler, "A block-sorting lossless data compression algorithm," Digital SRC Research Report 1994.

Google Scholar

[12]

K. Pagiamtzis and A. Sheikholeslami, "Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey," IEEE Journal of Solid-State Circuits, vol. 41, 2006.

Crossref

Google Scholar

Cited By

View all

Ponugoti MMilenkovic A(2019)Enabling On-the-Fly Hardware Tracing of Data Reads in MulticoresACM Transactions on Embedded Computing Systems10.1145/332264218:4(1-27)Online publication date: 10-Jun-2019
https://dl.acm.org/doi/10.1145/3322642
Choi JKim BKim HLee H(2019)A High-Throughput Hardware Accelerator for Lossless Compression of a DDR4 Command TraceIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2018.286966327:1(92-102)Online publication date: Jan-2019
https://doi.org/10.1109/TVLSI.2018.2869663
Ponugoti MTewar AMilenkovi A(2016)On-the-fly load data value tracing in multicoresProceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems10.1145/2968455.2968507(1-10)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1145/2968455.2968507
Show More Cited By

Index Terms

A real-time program trace compressor utilizing double move-to-front method

Recommendations

Real-time unobtrusive program execution trace compression using branch predictor events
CASES '10: Proceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems

Unobtrusive capturing of program execution traces in real-time is crucial in debugging cyber-physical systems. However, tracing even limited program segments is often cost-prohibitive, requiring wide trace ports and large on-chip trace buffers. This ...
A Trace-Capable Instruction Cache for Cost-Efficient Real-Time Program Trace Compression in SoC

This paper presents a novel approach to make the on-chip instruction cache of a SoC to function simultaneously as a regular instruction cache and a real-time program trace compressor, named trace-capable cache (TC-cache). It is accomplished by ...
Hardware-based data value and address trace filtering techniques
CASES '10: Proceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems

Capturing program and data traces during program execution unobtrusively in real-time is crucial in debugging and testing of cyber-physical systems. However, tracing a complete program unobtrusively is often cost-prohibitive, requiring large on-chip ...

Reviews

Reviewer: T.H. Tse

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. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '09: Proceedings of the 46th Annual Design Automation Conference

July 2009

994 pages

ISBN:9781605584973

DOI:10.1145/1629911

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DAC '09

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC '09: The 46th Annual Design Automation Conference 2009

July 26 - 31, 2009

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
147
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ponugoti MMilenkovic A(2019)Enabling On-the-Fly Hardware Tracing of Data Reads in MulticoresACM Transactions on Embedded Computing Systems10.1145/332264218:4(1-27)Online publication date: 10-Jun-2019
https://dl.acm.org/doi/10.1145/3322642
Choi JKim BKim HLee H(2019)A High-Throughput Hardware Accelerator for Lossless Compression of a DDR4 Command TraceIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2018.286966327:1(92-102)Online publication date: Jan-2019
https://doi.org/10.1109/TVLSI.2018.2869663
Ponugoti MTewar AMilenkovi A(2016)On-the-fly load data value tracing in multicoresProceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems10.1145/2968455.2968507(1-10)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1145/2968455.2968507
Ponugoti MMilenkovic A(2016)Exploiting cache coherence for effective on-the-fly data tracing in multicores2016 IEEE 34th International Conference on Computer Design (ICCD)10.1109/ICCD.2016.7753295(312-319)Online publication date: Oct-2016
https://doi.org/10.1109/ICCD.2016.7753295
Mihajlović BŽilić ŽGross W(2015)Architecture-Aware Real-Time Compression of Execution TracesACM Transactions on Embedded Computing Systems10.1145/276644914:4(1-24)Online publication date: 9-Sep-2015
https://dl.acm.org/doi/10.1145/2766449
Irrgang KPreusser T(2015)An LZ77-style bit-level compression for trace data compaction2015 25th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2015.7294006(1-4)Online publication date: Sep-2015
https://doi.org/10.1109/FPL.2015.7294006
Uzelac VMilenkovic AMilenkovic MBurtscher M(2014)Using Branch Predictors and Variable Encoding for On-the-Fly Program TracingIEEE Transactions on Computers10.1109/TC.2012.26763:4(1008-1020)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1109/TC.2012.267
(2013)BibliographyMulticore Technology10.1201/b15268-20(409-450)Online publication date: 18-Jul-2013
https://doi.org/10.1201/b15268-20
Uzelac VMilenković A(2013)Hardware-Based Load Value Trace Filtering for On-the-Fly DebuggingACM Transactions on Embedded Computing Systems10.1145/2465787.246579912:2s(1-18)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1145/2465787.2465799
Mihajlović BŽilić ŽAtienza DXie YAyala JStevens K(2011)Real-time address trace compression for emulated and real system-on-chip processor core debuggingProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973075(331-336)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.1145/1973009.1973075
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Real-time unobtrusive program execution trace compression using branch predictor events

A Trace-Capable Instruction Cache for Cost-Efficient Real-Time Program Trace Compression in SoC

Hardware-based data value and address trace filtering techniques

Reviews

Access critical reviews of Computing literature here