Article

Arithmetic program paths

Authors:

Manos Renieris,

Shashank Ramaprasad,

Steven P. ReissAuthors Info & Claims

ESEC/FSE-13: Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering

Pages 90 - 98

https://doi.org/10.1145/1081706.1081721

Published: 01 September 2005 Publication History

Abstract

We present Arithmetic Program Paths, a novel, efficient way to compress program control-flow traces that reduces program bit traces to less than a fifth of their original size while being fast and memory efficient. In addition, our method supports online, selective tracing and compression of individual conditionals, trading off memory usage and compression rate. We achieve these properties by recording only the directions taken by conditional statements during program execution, and using arithmetic coding for compression. We provide the arithmetic coder with a probability distribution for each conditional that we obtain using branch prediction techniques. We implemented the technique and experimented on several SPEC 2000 programs. Our method matches the compression rate of state-of-the-art tools while being an order of magnitude faster.

References

[1]

Hiralal Agrawal and Joseph R. Horgan. Dynamic program slicing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, 1990.

Digital Library

[2]

Glenn Ammons, Rastislav Bodik, and James Larus. Mining specifications. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2002.

Digital Library

[3]

Thomas Ball and James R. Larus. Efficient path profiling. In Proceedings of the 29th Annual International Symposium on Microarchitecture, pages 46--57, 1996.

Digital Library

[4]

M. Burtscher. Vpc3: A fast and effective trace-compression algorithm. In Joint International Conference on Measurement and Modeling of Computer Systems, pages 167--176, June 2004.

Digital Library

[5]

M. Burtscher and M. Jeeradit. Compressing extended program traces using value predictors. International Conference on Parallel Architectures and Compilation Techniques, pages 159--169, 2003.

Digital Library

[6]

John G. Cleary and Ian H. Witten. A comparison of enumerative and adaptive codes. IEEE Transactions on Information Theory, 30(2):306--315, March 1984.

Digital Library

[7]

Evelyn Duesterwald and Vasanth Bala. Software profiling for hot path prediction: Less is more. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, 2000.

Digital Library

[8]

Rajiv Gupta, Mary Lou Soffa, and John Howard. Hybrid slicing: Integrating dynamic information with static analysis. In Proceedings of the ACM SIGSOFT International Symposium on the Foundations of Software Engineering, October 1995.

Digital Library

[9]

Pascal Van Hentenryck. Incremental Constraint Satisfaction in Logic Programming. In Seventh International Conference on Logic Programming, Jerusalem, Israel, June 1990.

Digital Library

[10]

D.A. Huffman. A method for the construction of minimum redundancy codes. In Proceedings of IRE, volume 40, pages 1098--1101, 1952.

[11]

Rastislav Bodík, Rajiv Gupta, and Mary Lou Soffa. Interprocedural conditional branch elimination. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, 1997.

Digital Library

[12]

G. G. Langdon. Introduction to arithmetic coding. IBM Journal of Research and Development, 1984.

Digital Library

[13]

J. Larus. Abstract execution: a technique for efficiently tracing programs. Software -- Practice& Experience, 20, 1990.

Digital Library

[14]

James R. Larus. Whole program paths. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 259--269, 1999.

Digital Library

[15]

Zhijian Lu, John Lach, Mircea R. Stan, and Kevin Skadron. Alloyed branch history: Combining global and local branch history for robust performance. International Journal of Parallel Programming, 31(2):137--177, April 2003.

Digital Library

[16]

Scott McFarling. Combining branch predictors. Technical Note TN-36, Digital Equipment Corporation Western Research Laboratory (WRL), June 1993.

[17]

David Melski and Thomas Reps. Interprocedural path profiling. Technical Report CS-TR-1998-1382, University of Wisconsin, Madison, September 1998.

[18]

A. Moffat, R. Neal, and I.H. Witten. Arithmetic coding revisited. In IEEE Data Compression Conference, pages 202--211, 1995.

Digital Library

[19]

Ravi Nair. Branch behavior on the IBM RS/6000. Technical Report 17859, IBM Thomas J. Watson Research Center, 1992.

[20]

George C. Necula, Scott McPeak, S.P. Rahul, and Westley Weimer. CIL: Intermediate language and tools for analysis and transformation of C programs. In International Conference on Compiler Construction, April 2002.

Digital Library

[21]

Craig G. Nevill-Manning and Ian H. Witten. Linear-time, incremental hierarchy inference for compression. In DCC: Data Compression Conference. IEEE Computer Society TCC, 1997.

Digital Library

[22]

R. Pasco. Source Coding Algorithms for fast data compression. PhD thesis, Dept. of EE, Stanford University, Stanford, CA, 1976.

Digital Library

[23]

Andrew Pleszkun. Techniques for compressing program address traces. XXVII Annual IEEE/ACM Symposium on Microarchitecture, pages 32--40, 1994.

Digital Library

[24]

Steven P. Reiss. Trace-based debugging. In Peter Fritzon, editor, Automated and Algorithmic Debugging, First International Workshop, AADEBUG'93, volume 749 of Lecture Notes in Computer Science, pages 305--314. Springer, 3-5 May 1993.

Digital Library

[25]

Steven P. Reiss and Manos Renieris. Encoding program executions. In Proceedings of the 23rd International Conference on Software Engineering, pages 221--230, 2003.

Digital Library

[26]

J.J. Risannen. Arithmetic codings as number representations. In Acta Polytech. Scand. Math., 1979.

[27]

Claude E. Shannon. A mathematical theory of communication. Technical report, Bell Systems Technical Journal, 1948.

[28]

John Paul Shen and Mikko H. Lipasti. Modern Processor Design: Fundamentals of Superscalar Processors. McGraw-Hill, 2005.

[29]

James E. Smith. A study of branch prediction strategies. In ISCA '81: Proceedings of the 8th annual symposium on Computer Architecture, pages 135--148. IEEE Computer Society Press, 1981.

Digital Library

[30]

Bjarne Steensgaard. Points-to analysis in almost linear time. In Symposium on Principles of Programming Languages, pages 32--41, 1996.

Digital Library

[31]

I.H. Witten, R. Neal, and J. Cleary. Arithmetic coding for data compression. Comm. of the ACM, pages 520--540, 1987.

Digital Library

[32]

Tse-Yu Yeh and Yale N. Patt. A comparison of dynamic branch predictors that use two levels of branch history. In ISCA, pages 257--266, 1993.

Digital Library

[33]

Y. Zhang and R. Gupta. Timestamped whole program paths. Conference on Programming Language Design and Implementation, 2001.

Digital Library

Cited By

Zhang MMathur UViswanathan MSpinellis DGousios GChechik MDi Penta M(2021)Checking LTL[F,G,X] on compressed traces in polynomial timeProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468557(131-143)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468557
Ming JWu DWang JXiao GLiu PLo DApel SKhurshid S(2016)StraightTaint: decoupled offline symbolic taint analysisProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970299(308-319)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970299
Yang CWu SChan W(2016)Hierarchical Program PathsACM Transactions on Software Engineering and Methodology10.1145/296309425:3(1-44)Online publication date: 22-Aug-2016
https://dl.acm.org/doi/10.1145/2963094
Show More Cited By

Index Terms

Arithmetic program paths
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout
        Data compression
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Process validation
        Traceability

Recommendations

Arithmetic program paths

We present Arithmetic Program Paths, a novel, efficient way to compress program control-flow traces that reduces program bit traces to less than a fifth of their original size while being fast and memory efficient. In addition, our method supports ...
Design of high peformance arithmetic encode for CABAC in H.264/AVC
MINO'09: Proceedings of the 8th WSEAS international conference on Microelectronics, nanoelectronics, optoelectronics

CABAC is one of the entropy coding technologies applied to a main profile of H.264/AVC. The subject of concern for performance enhancements of CABAC improves irregular renormalization and bit output of arithmetic coder. This paper proposes an efficient ...
Optimization of Arithmetic Coding for JPEG2000

Embedded block coding with optimized truncation (EBCOT) employed in the JPEG2000 standard accounts for the majority of the processing time, because the EBCOT is full of bit operations that cannot be implemented efficiently in software. The block coder ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE-13: Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering

September 2005

402 pages

ISBN:1595930140

DOI:10.1145/1081706

General Chair:
Michel Wermelinger
The Open University, UK
,
Program Chair:
Harald C. Gall
University of Zurich, Switzerland

ACM SIGSOFT Software Engineering Notes Volume 30, Issue 5
September 2005
462 pages
ISSN:0163-5948
DOI:10.1145/1095430
Issue’s Table of Contents

Copyright © 2005 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ESEC/FSE05

Sponsor:

ESEC/FSE05: Joint 10th European Software Engineering Conference 2005

September 5 - 9, 2005

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
386
Total Downloads

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

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang MMathur UViswanathan MSpinellis DGousios GChechik MDi Penta M(2021)Checking LTL[F,G,X] on compressed traces in polynomial timeProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468557(131-143)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468557
Ming JWu DWang JXiao GLiu PLo DApel SKhurshid S(2016)StraightTaint: decoupled offline symbolic taint analysisProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970299(308-319)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970299
Yang CWu SChan W(2016)Hierarchical Program PathsACM Transactions on Software Engineering and Methodology10.1145/296309425:3(1-44)Online publication date: 22-Aug-2016
https://dl.acm.org/doi/10.1145/2963094
Ming JWu D(2016)BinCFP: Efficient Multi-threaded Binary Code Control Flow Profiling2016 IEEE 16th International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM.2016.21(61-66)Online publication date: Oct-2016
https://doi.org/10.1109/SCAM.2016.21
Ming JWu DXiao GWang JLiu P(2015)TaintPipeProceedings of the 24th USENIX Conference on Security Symposium10.5555/2831143.2831148(65-80)Online publication date: 12-Aug-2015
https://dl.acm.org/doi/10.5555/2831143.2831148
Miranskyy AMadhavji NGittens MDavison MWilding MGodwin DTaylor CNg JCouturier CVigder MChechik M(2008)SIFTProceedings of the 2008 conference of the center for advanced studies on collaborative research: meeting of minds10.1145/1463788.1463817(274-288)Online publication date: 27-Oct-2008
https://dl.acm.org/doi/10.1145/1463788.1463817
Miranskyy AMadhavji NGittens MDavison MWilding MGodwin DCrnkovic IBertolino A(2007)An iterative, multi-level, and scalable approach to comparing execution tracesThe 6th Joint Meeting on European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering: companion papers10.1145/1295014.1295035(537-540)Online publication date: 3-Sep-2007
https://dl.acm.org/doi/10.1145/1295014.1295035
Miranskyy AMadhavji NGittens MDavison MWilding MGodwin DCrnkovic IBertolino A(2007)An iterative, multi-level, and scalable approach to comparing execution tracesProceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering10.1145/1287624.1287704(537-540)Online publication date: 7-Sep-2007
https://dl.acm.org/doi/10.1145/1287624.1287704
Ming JWu DWang JXiao GLiu PLo DApel SKhurshid S(2016)StraightTaint: decoupled offline symbolic taint analysisProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970299(308-319)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970299
Zhao QSim JWong WRudolph LAltman ESkadron KZorn B(2006)DEPProceedings of the 15th international conference on Parallel architectures and compilation techniques10.1145/1152154.1152180(154-163)Online publication date: 16-Sep-2006
https://dl.acm.org/doi/10.1145/1152154.1152180

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents