More Web Proxy on the site http://driver.im/

article

Open access

Unified control flow and data dependence traces

Authors:

Sriraman Tallam,

Rajiv GuptaAuthors Info & Claims

ACM Transactions on Architecture and Code Optimization (TACO), Volume 4, Issue 3

Pages 19 - es

https://doi.org/10.1145/1275937.1275943

Published: 01 September 2007 Publication History

Abstract

We describe the design, generation, and compression of the extended whole program path (eWPP), representation that not only captures the control flow history of a program execution but also its data dependence history. This representation is motivated by the observation that, typically, a significant fraction of data dependence history can be recovered from the control flow trace. To capture the remainder of the data dependence history, we introduce disambiguation checks in the program whose control flow signatures capture the results of the checks. The resulting extended control flow trace enables the recovery of otherwise irrecoverable data dependences. The code for the checks is designed to minimize the increase in program execution time and the extended control flow trace size when compared to directly collecting control flow and address traces. Our experiments show that compressed eWPPs are only one-quarter of the size of combined compressed control flow and address traces. However, their collection incurs a 5× increase in runtime overhead relative to the overhead required for directly collecting the control flow and address traces, respectively.

References

[1]

Agrawal, H. and Horgan, J. 1990. Dynamic program slicing. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. 246--256.

Digital Library

[2]

Agrawal, H., DeMillo, R., and Spafford, E. 1993. Debugging with dynamic slicing and backtracking. Software Practice and Experience 23, 6, 589--616.

Digital Library

[3]

Ammons, G. and Larus, J.R. 1998. Improving data flow analysis with path profiles. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. 72--84.

Digital Library

[4]

Ball, T. and Larus, J.R. 1996. Efficient path profiling. In Proceedings of the IEEE/ACM International Symposium on Microarchitecture. IEEE/ACM, New York. 46--57.

Digital Library

[5]

Bodik, R., Gupta, R., and Soffa, M.L. 1998. Complete removal of redundant expressions. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. 1--14.

Digital Library

[6]

Burtscher, M. 2004. VPC3: A fast and effective trace-compression algorithm. In Proceedings of the SIGMETRICS Conference. ACM, New York. 167--176.

Digital Library

[7]

Burtscher, M. and Jeeradit, M. 2003. Compressing extended program traces using value predictors. In Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques. IEEE, Los Alamitos, CA. 159--169.

Digital Library

[8]

Chen, T., Lin, J., Dai, X., Hsu, W.-C., and Yew, P.-C. 2004. Data Dependence Profiling for Speculative Optimization. In Proceedings of the 13th International Conference on Compiler Construction. 57--72.

[9]

Gupta, R., Berson, D., and Fang, J.Z. 1998. Path profile guided partial redundancy elimination using speculation. In Proceedings of the IEEE International Conference on Computer Languages. IEEE, Los Alamitos, CA. 230--239.

Digital Library

[10]

Jacobson, Q., Rotenberg, E., and Smith, J.E. 1997. Path-based next trace prediction. In Proceedings of the 30th IEEE/ACM International Symposium on Microarchitecture. IEEE/ACM, New York. 14--23.

Digital Library

[11]

Kamkar, M. 1993. Interprocedural dynamic slicing with applications to debugging and testing. PhD Thesis, Linkoping University, Sweden.

[12]

Korel, B. and Laski, J. 1988. Dynamic program slicing. Information Processing Letters 29, 3, 155--163.

Digital Library

[13]

Korel, B. and Rilling, J. 1997. Application of dynamic slicing in program debugging. In Proceedings of the Automated and Algorithmic Debugging. 43--59.

[14]

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

Digital Library

[15]

Liao, S. W., Wang, P. H., Wang, H., Shen, J. P., Hoflehner, G., Lavery, D. M., and Zhang, X. 2002. Post-Pass Binary Adaptation for Software Speculative Precomputation. In ACM SIGPLAN Conference on Programming Language Design and Implementation. 117--128.

Digital Library

[16]

Lin, J., Chen, T., Hsu, W.C., Yew, P.C., Ju, R.D.C., Ngai, T.F., and Chan, S. 2003. A Compiler Framework for Speculative Analysis and Optimizations. In ACM SIGPLAN Conference on Programming Language Design and Implementation. 289--299.

Digital Library

[17]

Lin, J., Hsu, W.C., Yew, P.C., Ju, R.D.C., Ngai, T.F. 2004. A Compiler Framework for Recovery Code Generation in General Speculative Optimizations. In 14th International Conference on Parallel Architectures and Compilation Techniques. 17--28.

Digital Library

[18]

Nevil-Manning, C.G. and Witten, I.H. 1997. Linear-time, incremental hierarchy inference for compression. In Proceedings of the Data Compression Conference. IEEE-CS, Los Alamitos, CA. 3--11.

Digital Library

[19]

Sazeides, Y. 2003. Instruction-isomorphism in program execution. In Proceedings of the Value Prediction Workshop.

[20]

Tallam, S., Gupta, R., and Zhang, X. 2005. Extended Whole Program Paths. In 14th International Conference on Parallel Architectures and Compilation Techniques. 17--26.

Digital Library

[21]

Weiser, M. 1982. Program slicing. IEEE Transactions on Software Engineering SE-10, 4, 352--357.

[22]

Young, C. and Smith, M.D. 1998. Better global scheduling using path profiles. In Proceedings of the IEEE/ACM International Symposium on Microarchitecture. IEEE/ACM, New York. 115--123.

Digital Library

[23]

Zhang, X. and Gupta, R. 2004. Cost effective dynamic program slicing. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. 94--106.

Digital Library

[24]

Zhang, X., He, H., Gupta, N. and Gupta, R. 2005. Experimental Evaluation of using Dynamic Slices for Fault Location. In SIGSOFT-SIGPLAN Sixth International Symposium on Automated and Analysis-Driven Debugging. ACM, New York. 33--42.

Digital Library

[25]

Zhang, X., Gupta, N. and Gupta, R. 2006. Pruning Dynamic Slices with Confidence. In ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. 169--180.

Digital Library

[26]

Zhang, Y. and Gupta, R. 2001. Timestamped whole program path representation and its applications. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. 180--190.

Digital Library

[27]

Zhao, Q., Sim, J.E., Wong, W.F., and Rudolph, L. 2006. DEP: detailed execution profile. In 15th International Conference on Parallel Architectures and Compilation Techniques. 154--163.

Digital Library

[28]

Zilles, C.B. and Sohi, G. 2000. Understanding the backward slices of performance degrading instructions. In Proceedings of the IEEE/ACM 27th International Symposium on Computer Architecture. IEEE/ACM, New York. 172--181.

Digital Library

Cited By

Xu ZChon YSu YTan ZApostolakis SCampanoni SAugust D(2024)PROMPT: A Fast and Extensible Memory Profiling FrameworkProceedings of the ACM on Programming Languages10.1145/36498278:OOPSLA1(449-473)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649827
Avalos Baddouh CKhairy MGreen RPayer MRogers T(2021)Principal Kernel Analysis: A Tractable Methodology to Simulate Scaled GPU WorkloadsMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480100(724-737)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480100
Sharma SDagenais M(2016)Hardware-assisted instruction profiling and latency detectionThe Journal of Engineering10.1049/joe.2016.01272016:10(367-376)Online publication date: 1-Oct-2016
https://doi.org/10.1049/joe.2016.0127
Show More Cited By

Index Terms

Unified control flow and data dependence traces
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Process validation
        Traceability
      2. Software defect analysis
        Software testing and debugging

Recommendations

The design and evaluation of path matching schemes on compressed control flow traces

A control flow trace captures the complete sequence of dynamically executed basic blocks and function calls. It is usually of very large size and therefore commonly stored in compressed format. On the other hand, control flow traces are frequently ...
Conversion of control dependence to data dependence
POPL '83: Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

Program analysis methods, especially those which support automatic vectorization, are based on the concept of interstatement dependence where a dependence holds between two statements when one of the statements computes values needed by the other. ...
Computation of interprocedural control dependence
ISSTA '98: Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis

Program dependence information is useful for a variety of software testing and maintenance tasks. Properly defined, control and data dependencies can be used to identify semantic dependencies. To function effectively on whole programs, tools that ...

Reviews

Reviewer: Vladimir Stantchev

The extended whole program path (eWPP) representation is described in this paper. It captures both control flow history and data dependence history of program execution. The objective is to capture data dependence history that cannot be recovered from the control trace. For this, the authors use disambiguation checks. The approach is described clearly and thoroughly with test data. A positive result is the reduced size (one-fourth) of eWPP, as compared to combined compressed control flow and address traces. The runtime overhead (five times) for their collection makes the approach not universally applicable?keeping in mind that this is an already optimized solution (for example, the authors use binary search instead of linear search). The use of tools, such as Phoenix CF, can automate instrumentation code insertion. Overall, there is no clear statement of benefits from the approach. Specifically, what is the trade-off between smaller size versus high-runtime overhead__?__ 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

cover image ACM Transactions on Architecture and Code Optimization

ACM Transactions on Architecture and Code Optimization Volume 4, Issue 3

September 2007

191 pages

ISSN:1544-3566

EISSN:1544-3973

DOI:10.1145/1275937

Issue’s Table of Contents

Copyright © 2007 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2007

Published in TACO Volume 4, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
888
Total Downloads

Downloads (Last 12 months)86
Downloads (Last 6 weeks)14

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xu ZChon YSu YTan ZApostolakis SCampanoni SAugust D(2024)PROMPT: A Fast and Extensible Memory Profiling FrameworkProceedings of the ACM on Programming Languages10.1145/36498278:OOPSLA1(449-473)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649827
Avalos Baddouh CKhairy MGreen RPayer MRogers T(2021)Principal Kernel Analysis: A Tractable Methodology to Simulate Scaled GPU WorkloadsMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480100(724-737)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480100
Sharma SDagenais M(2016)Hardware-assisted instruction profiling and latency detectionThe Journal of Engineering10.1049/joe.2016.01272016:10(367-376)Online publication date: 1-Oct-2016
https://doi.org/10.1049/joe.2016.0127
Railing BHein EConte T(2015)ContechACM Transactions on Architecture and Code Optimization10.1145/277689312:2(1-24)Online publication date: 8-Jul-2015
https://dl.acm.org/doi/10.1145/2776893
Clapp LAnand SAiken AYoung MXie T(2015)Modelgen: mining explicit information flow specifications from concrete executionsProceedings of the 2015 International Symposium on Software Testing and Analysis10.1145/2771783.2771810(129-140)Online publication date: 13-Jul-2015
https://dl.acm.org/doi/10.1145/2771783.2771810
Cai HSantelices R(2015)TRACERJD: Generic trace-based dynamic dependence analysis with fine-grained logging2015 IEEE 22nd International Conference on Software Analysis, Evolution, and Reengineering (SANER)10.1109/SANER.2015.7081862(489-493)Online publication date: Mar-2015
https://doi.org/10.1109/SANER.2015.7081862
Holewinski JRamamurthi RRavishankar MFauzia NPouchet LRountev ASadayappan P(2012)Dynamic trace-based analysis of vectorization potential of applicationsACM SIGPLAN Notices10.1145/2345156.225410847:6(371-382)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2345156.2254108
Yu HLi ZHeimdahl MSu Z(2012)Multi-slicing: a compiler-supported parallel approach to data dependence profilingProceedings of the 2012 International Symposium on Software Testing and Analysis10.1145/2338965.2336756(23-33)Online publication date: 15-Jul-2012
https://dl.acm.org/doi/10.1145/2338965.2336756
Yu HLi ZBanerjee UGallivan KBilardi GKatevenis M(2012)Fast loop-level data dependence profilingProceedings of the 26th ACM international conference on Supercomputing10.1145/2304576.2304584(37-46)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1145/2304576.2304584
Holewinski JRamamurthi RRavishankar MFauzia NPouchet LRountev ASadayappan PVitek JLin HTip F(2012)Dynamic trace-based analysis of vectorization potential of applicationsProceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2254064.2254108(371-382)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2254064.2254108
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents