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

research-article

On-the-fly detection of precise loop nests across procedures on a dynamic binary translation system

Authors:

Yasushi Inoguchi,

Tadao NakamuraAuthors Info & Claims

CF '11: Proceedings of the 8th ACM International Conference on Computing Frontiers

Article No.: 25, Pages 1 - 10

https://doi.org/10.1145/2016604.2016634

Published: 03 May 2011 Publication History

Abstract

Loop structures in programs have been regarded as a primary source of finding parallelism from sequential codes. In this paper, we present a new technique that dynamically detects precise loop structures with their inter-procedural nests on a dynamic binary translation system. Using precompiled application binary code as an input, our mechanism generates the simple but precise markers when they are loaded from their binary code image, and at runtime monitors loop structures with inter-procedural nesting on the fly using Loop-Call Context Graph. We implement our mechanism and evaluate it using SPEC CPU benchmark suite. The results show that our mechanism reveals precise loop structures with interprocedural loop nesting successfully. The results also show that ours can reduce overheads for loop analysis compared with the existing ones. These indicate that our mechanism can be applied to runtime optimization and parallelization as well as hints for performance tuning.

References

[1]

A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley, 2006.

Digital Library

[2]

G. Ammons, T. Ball, and J. R. Larus. Exploiting hardware performance counters with flow and context sensitive profiling. In Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, pages 85--96, 1997.

Digital Library

[3]

K. Beyls and E. H. D'Hollander. Refactoring for data locality. Computer, 42(2):62--71, 2009.

Digital Library

[4]

E. Borin and Y. Wu. Characterization of DBT overhead. In Proceedings of the 2009 IEEE International Symposium on Workload Characterization (IISWC), pages 178--187, 2009.

Digital Library

[5]

E. Borin, Y. Wu, C. Wang, W. Liu, M. Breternitz, Jr., S. Hu, E. Natanzon, S. Rotem, and R. Rosner. TAO: two-level atomicity for dynamic binary optimizations. In Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization, pages 12--21, 2010.

Digital Library

[6]

M. Chen and K. Olukotun. TEST: a tracer for extracting speculative threads. In Proceedings of the international symposium on Code generation and optimization, pages 301--312, 2003.

Digital Library

[7]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009.

Digital Library

[8]

E. Duesterwald and V. Bala. Software profiling for hot path prediction: less is more. In Proceedings of the Symposium. on Architectural Support for Programming Languages and. Operating Systems, pages 202--211, 2000.

Digital Library

[9]

M. Hall, J. Chame, C. Chen, J. Shin, G. Rudy, and M. M. Khan. Loop transformation recipes for code generation and auto-tuning. The 22nd International Workshop on Languages and Compilers for Parallel Computing, LCPC 2009, Lecture Notes in Computer Science, 2010.

Digital Library

[10]

P. Havlak. Nesting of reducible and irreducible loops. ACM Trans. Program. Lang. Syst., 19(4):557--567, 1997.

Digital Library

[11]

J. Lau, E. Perelman, and B. Calder. Selecting software phase markers with code structure analysis. In Proceedings of the International Symposium on Code Generation and Optimization, pages 135--146, 2006.

Digital Library

[12]

C.-K. Luk et al. Pin: building customized program analysis tools with dynamic instrumentation. In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, pages 190--200, 2005.

Digital Library

[13]

T. Moseley et al. Identifying potential parallelism via loop-centric profiling. In Proceedings of the 4th international conference on Computing frontiers, pages 143--152, 2007.

Digital Library

[14]

S. Rul, H. Vandierendonck, and K. De Bosschere. Towards automatic program partitioning. In Proceedings of the 6th ACM conference on Computing frontiers, pages 89--98, 2009.

Digital Library

[15]

Y. Sato, K. Suzuki, and T. Nakamura. Run-time detection mechanism of nested call-loop structure to monitor the actual execution of codes. In Proceedings of First International Workshop on Software Technologies for Future Dependable Distributed Systems, pages 184--188, 2009.

Digital Library

[16]

N. R. Tallent, J. M. Mellor-Crummey, and M. W. Fagan. Binary analysis for measurement and attribution of program performance. In Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, pages 441--452, 2009.

Digital Library

[17]

J. Tubella and A. González. Control speculation in multithreaded processors through dynamic loop detection. In Proceedings of the 4th International Symposium on High-Performance Computer Architecture, page 14, 1998.

Digital Library

[18]

S. Wang, X. Dai, K. S. Yellajyosula, A. Zhai, and P.-C. Yew. Loop selection for thread-level speculation. In Workshops on Languages and Compilers for Parallel Computing (LCPC 2005), 2005.

Digital Library

[19]

Y. Wu, M. Breternitz, and T. Devor. Continuous trip count profiling for loop optimizations in two-phase dynamic binary translators. In Proceedings of eighth Annual Workshop on Interaction between Compilers and Computer Architectures (INTERACT'04), pages 3--12, 2004.

Cited By

Mosaner RLeopoldseder DRigger MSchatz RMössenböck HHosking AFinocchi I(2019)Supporting on-stack replacement in unstructured languages by loop reconstruction and extractionProceedings of the 16th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3357390.3361030(1-13)Online publication date: 21-Oct-2019
https://dl.acm.org/doi/10.1145/3357390.3361030
Gruber FSelva MSampaio DGuillon CMoynault APouchet LRastello FHollingsworth JKeidar I(2019)Data-flow/dependence profiling for structured transformationsProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295737(173-185)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295737
Endo TMidorikawa HSato Y(2018)Software Technology That Deals with Deeper Memory Hierarchy in Post-petascale EraAdvanced Software Technologies for Post-Peta Scale Computing10.1007/978-981-13-1924-2_12(227-248)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-981-13-1924-2_12
Show More Cited By

Index Terms

On-the-fly detection of precise loop nests across procedures on a dynamic binary translation system
1. Hardware
  1. Communication hardware, interfaces and storage

Recommendations

Tiling imperfectly-nested loop nests
SC '00: Proceedings of the 2000 ACM/IEEE conference on Supercomputing

Tiling is one of the more important transformations for enhancing loca lity of reference in programs. Intuitively, tiling a set of loops achieves the effect of interleaving iterations of these loops. Tiling of perfectly-nested loop nests (which are loop ...
Synthesizing Transformations for Locality Enhancement of Imperfectly-Nested Loop Nests

Linear loop transformations and tiling are known to be very effective for enhancing locality of reference in perfectly-nested loops. However, they cannot be applied directly to imperfectly-nested loops. Some compilers attempt to convert imperfectly-...
Locality Enhancement Of Imperfectly-nested Loop Nests

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '11: Proceedings of the 8th ACM International Conference on Computing Frontiers

May 2011

268 pages

ISBN:9781450306980

DOI:10.1145/2016604

General Chair:
Calin Cascaval
Qualcomm Research
,
Program Chairs:
Pedro Trancoso
University of Cyprus, CY
,
Viktor Prasanna
University of Southern California

Copyright © 2011 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

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 May 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CF'11

Sponsor:

SIGMICRO

CF'11: Computing Frontiers Conference

May 3 - 5, 2011

Ischia, Italy

Acceptance Rates

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
299
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mosaner RLeopoldseder DRigger MSchatz RMössenböck HHosking AFinocchi I(2019)Supporting on-stack replacement in unstructured languages by loop reconstruction and extractionProceedings of the 16th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3357390.3361030(1-13)Online publication date: 21-Oct-2019
https://dl.acm.org/doi/10.1145/3357390.3361030
Gruber FSelva MSampaio DGuillon CMoynault APouchet LRastello FHollingsworth JKeidar I(2019)Data-flow/dependence profiling for structured transformationsProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295737(173-185)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295737
Endo TMidorikawa HSato Y(2018)Software Technology That Deals with Deeper Memory Hierarchy in Post-petascale EraAdvanced Software Technologies for Post-Peta Scale Computing10.1007/978-981-13-1924-2_12(227-248)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-981-13-1924-2_12
d'Antras AGorgovan CGarside JGoodacre JLuján M(2017)HyperMAMBO-X64ACM SIGPLAN Notices10.1145/3140607.305075652:7(228-241)Online publication date: 8-Apr-2017
https://dl.acm.org/doi/10.1145/3140607.3050756
Chiang TLiu CYeh CTu CHung SGrygiel KCerny TKim SWang W(2017)Program Analysis with a Loop-Function-based Tracing Tool on Virtual PlatformsProceedings of the International Conference on Research in Adaptive and Convergent Systems10.1145/3129676.3129683(255-260)Online publication date: 20-Sep-2017
https://dl.acm.org/doi/10.1145/3129676.3129683
d'Antras AGorgovan CGarside JGoodacre JLuján M(2017)HyperMAMBO-X64Proceedings of the 13th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments10.1145/3050748.3050756(228-241)Online publication date: 8-Apr-2017
https://dl.acm.org/doi/10.1145/3050748.3050756
Kim CKim JKang JLee JKim H(2017)Context-Aware Memory Profiling for Speculative Parallelism2017 IEEE 24th International Conference on High Performance Computing (HiPC)10.1109/HiPC.2017.00045(328-337)Online publication date: Dec-2017
https://doi.org/10.1109/HiPC.2017.00045
Sehatbakhsh NNazari AZajic APrvulovic MHsu WYang CLipasti MLee H(2016)Spectral profilingThe 49th Annual IEEE/ACM International Symposium on Microarchitecture10.5555/3195638.3195710(1-11)Online publication date: 15-Oct-2016
https://dl.acm.org/doi/10.5555/3195638.3195710
Gorgovan Cd'Antras ALuján M(2016)MAMBOACM Transactions on Architecture and Code Optimization10.1145/289645113:1(1-26)Online publication date: 5-Apr-2016
https://dl.acm.org/doi/10.1145/2896451
d'Antras AGorgovan CGarside JLuján M(2016)Optimizing Indirect Branches in Dynamic Binary TranslatorsACM Transactions on Architecture and Code Optimization10.1145/286657313:1(1-25)Online publication date: 5-Apr-2016
https://dl.acm.org/doi/10.1145/2866573
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.

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