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

Article

Free access

Analysis techniques for predicated code

Authors:

Richard Johnson,

Michael SchlanskerAuthors Info & Claims

MICRO 29: Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture

Pages 100 - 113

Published: 02 December 1996 Publication History

Abstract

Predicated execution offers new approaches to exploiting instruction-level parallelism (ILP), but it also presents new challenges for compiler analysis and optimization. In predicated code, each operation is guarded by a boolean operand whose run-time value determines whether the operation is executed or nullified. While research has shown the utility of predication in enhancing ILP, there has been little discussion of the difficulties surrounding compiler support for predicated execution. Conventional program analysis tools (e.g. data flow analysis) assume that operations execute unconditionally within each basic block and thus make incorrect assumptions about the run-rime behavior of predicated code. These tools can be modified to be correct without requiring predicate analysis, but this yields overly-conservative results in crucial areas such as scheduling and register allocation. To generate high-quality code for machines offering predicated execution, a compiler must incorporate information about relations between predicates into its analysis. We present new techniques for analyzing predicated code. Operations which compute predicates are analyzed to determine relations between predicate values. These relations are captured in a graph-based data structure, which supports efficient manipulation of boolean expression representing facts about predicated code. This approach forms the basis for predicate-sensitive data flow analysis. Conventional data flow algorithms can be systematically upgraded to be predicate sensitive by incorporating information about predicates. Predicate-sensitive data flow analysis yields significantly more accurate results than conventional data flow analysis when applied to predicated code.

References

[1]

A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principle& Techniques, and Tools. Addison-Wesley, Reading, MA, 1986.

Digital Library

[2]

J. R. Allen, K. Kennedy, C. Portfield, and J. Warren. Conversion of control dependence to data dependence. In Conference Record of the lOth Annual ACM Symposium on Principles of Programming Languages, pages 177-189, Austin, Texas, Jan. 24-26, 1983.

Digital Library

[3]

G. J. Chaitin. Register allocation and spilling via graph coloring. In Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, pages 98-105, Boston, Massachusetts, June 23-25, 1982. Published as ACM SIGPLAN Notices 17(6).

Digital Library

[4]

J. C. Dehnert, P. Y.-T Hsu, and J. P. Bratt. Overlapped loop support in the Cydra 5. in Third International Conference on Architectural Support for Programming Languages and Operating Systems, pages 26-38, Boston, Massachusetts, Apr. 3-6, 1989.

Digital Library

[5]

J. C. Dehnert and R. A. Towle. Compiling for the Cydra 5. iEEE Computer, 7(1/2): 181-227, 1993.

Digital Library

[6]

A. E. Eichenberger and E. S. Davidson. Register allocation for predicated code. In Proceedings of the 28th Annual International Symposium on Microarchitecture, pages 180-191, Ann Arbor, Michigan, Nov. 29-Dec. 1, 1995.

Digital Library

[7]

D. M. Gillies, D. R. Ju, R. Johnson, and M. Schlansker. Global predicate analysis and its application to register allocation. In Proceedings of the 28th Annual International Symposium on Microarchitecture, Paris, France, Dec. 2-4, 1996.

Digital Library

[8]

Hewlett-Packard Company. PA-RISC 1.1 Architecture and Instruction Set Reference Manual. Prentice-Hall, second edition, 1992.

[9]

P. Y. T Hsu and E. S. Davidson. Highly concurrent scalar processing. In Proceedings of the 13th Annual International Symposium on Computer Architecture, pages 386- 395, Tokyo, Japan, June 2-5, 1986.

Digital Library

[10]

V. Kathail, M. Schlansker, and B. Rau. HPL PlayDoh architecture specification: Version 1.0. Technical Report HPL-93- 80, Hewlett-Packard Laboratories, Feb. 1993.

[11]

D. C. Lin. Compiler support for predicated execution in superscalar processors. Master's thesis, University of Illinois at Urbana-Champaign, 1990.

[12]

S. A. Mahlke, R. E. Hank, R. A. Bringmann, J. C. Gyllenhaal, D. M. Gallagher, and W. Hwu. Characterizing the impact of predicated execution on branch predication. In Proceedings of the 27th Annual International Symposium on Microarchitecture, pages 217-227, San Jose, California, Nov. 30--Dec. 2, 1994.

Digital Library

[13]

S. A. Mahlke, D. C. Lin, W. Y. Chen, R. E. Hank, and R. A. Bringmann. Effective compiler support for predicated execution using the hyperblock. In Proceedings of the 25th Annual International Symposium on Microarchitecture, pages 45-54, Portland, Oregon, Dec. 1-4, 1992.

Digital Library

[14]

J. C. H. Park and M. Schlansker. On predicated execution. Technical Report HPL-91-58, Hewlett-Packard Software and Systems Laboratory, May 1991.

[15]

B. Rau, D. Yen, W. Yen, and R. Towle. The Cydra 5 departmental supercomputer: Design philosophies, decisions, and trade-offs. IEEE Computer, 22(1 ): 12-35, Jan. 1989.

Digital Library

[16]

M. Schlansker and V. Kathail. Critical path reduction for scalar programs. In Proceedings of the 28th Annual International Symposium on Microarchitecture, pages 57-69, Ann Arbor, Michigan, Nov. 29-Dec. 1, 1995.

Digital Library

[17]

G. S. Tyson. The effects of predicated execution on branch prediction. In Proceedings of the 27th Annual International Symposium on Microarchitecture, pages 196-206, San Jose, California, Nov. 30-Dec. 2, 1994.

Digital Library

[18]

N.J. Wafter, S. A. Mahlke, W. W. Hwu, and B. R. Rau. Reverse if-conversion, in Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 290-299, Albuquerque, New Mexico, June 23-25, 1993.

Digital Library

Cited By

Nicolau ALi GVeidenbaum AKejariwal AGschwind MNicolau ASalapura VMoreira J(2009)Synchronization optimizations for efficient execution on multi-coresProceedings of the 23rd international conference on Supercomputing10.1145/1542275.1542303(169-180)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542275.1542303
Snavely NDebray SAndrews G(2005)Unpredication, Unscheduling, UnspeculationIEEE Transactions on Software Engineering10.1109/TSE.2005.2731:2(99-115)Online publication date: 1-Feb-2005
https://dl.acm.org/doi/10.1109/TSE.2005.27
Smelyanskiy MMahlke SDavidson E(2004)Probabilistic Predicate-Aware Modulo SchedulingProceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization10.5555/977395.977658Online publication date: 20-Mar-2004
https://dl.acm.org/doi/10.5555/977395.977658
Show More Cited By

Index Terms

Analysis techniques for predicated code

Recommendations

Partial dead code elimination on predicated code regions

This paper presents the design, implementation and experimental evaluation of a practical region-based partial dead code elimination (PDE) algorithm on predicated code in the Open Research Compiler framework. Existing PDE algorithms are not applicable ...
An evaluation of speculative instruction execution on simultaneous multithreaded processors

Modern superscalar processors rely heavily on speculative execution for performance. For example, our measurements show that on a 6-issue superscalar, 93% of committed instructions for SPECINT95 are speculative. Without speculation, processor resources ...
Predicated switching - optimizing speculation on EPIC machines

Explicitly parallel instruction computing (EPIC) processors are a very attractive platform for many of today's multimedia and communications applications. In particular, clustered EPIC machines can take aggressive advantage of the available instruction-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MICRO 29: Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture

December 1996

359 pages

ISBN:0818676418

Chairmen:
Stephen Melvin
Zytek Communications Corp.
,
Steve Beaty
Hewlett-Packard Corp.

Copyright © Copyright (c) 1996 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
IEEE-CS\TCMM: TC on Microprocessors & Microcomputers

Publisher

IEEE Computer Society

United States

Publication History

Published: 02 December 1996

Check for updates

Author Tags

Qualifiers

Article

Conference

MICRO96

Sponsor:

SIGMICRO
IEEE-CS\TCMM

MICRO96: 29th Annual International Symposium on Microarchitecture

December 2 - 4, 1996

Paris, France

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
615
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nicolau ALi GVeidenbaum AKejariwal AGschwind MNicolau ASalapura VMoreira J(2009)Synchronization optimizations for efficient execution on multi-coresProceedings of the 23rd international conference on Supercomputing10.1145/1542275.1542303(169-180)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542275.1542303
Snavely NDebray SAndrews G(2005)Unpredication, Unscheduling, UnspeculationIEEE Transactions on Software Engineering10.1109/TSE.2005.2731:2(99-115)Online publication date: 1-Feb-2005
https://dl.acm.org/doi/10.1109/TSE.2005.27
Smelyanskiy MMahlke SDavidson E(2004)Probabilistic Predicate-Aware Modulo SchedulingProceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization10.5555/977395.977658Online publication date: 20-Mar-2004
https://dl.acm.org/doi/10.5555/977395.977658
Wu CLian RZhang JJu RChan SLiu LFeng XZhang Z(2004)An overview of the open research compilerProceedings of the 17th international conference on Languages and Compilers for High Performance Computing10.1007/11532378_3(17-31)Online publication date: 22-Sep-2004
https://dl.acm.org/doi/10.1007/11532378_3
Smelyanskiy MMahlke SDavidson ELee HJohnson RConte THwu W(2003)Predicate-aware schedulingProceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization10.5555/776261.776280(169-178)Online publication date: 23-Mar-2003
https://dl.acm.org/doi/10.5555/776261.776280
Collard JLavery DJohnson RConte THwu W(2003)Optimizations to prevent cache penalties for the Intel® Itanium® 2 ProcessorProceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization10.5555/776261.776273(105-114)Online publication date: 23-Mar-2003
https://dl.acm.org/doi/10.5555/776261.776273
Chidester MGeorge ARadlinski M(2003)Multiple-path execution for chip multiprocessorsJournal of Systems Architecture: the EUROMICRO Journal10.1016/S1383-7621(03)00042-049:1-2(33-52)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1016/S1383-7621%2803%2900042-0
Ashmawy AIsmail HFahmy A(2002)Hybrid Predication Model for Instruction Level ParallelismProceedings of the 16th International Parallel and Distributed Processing Symposium10.5555/645610.662037Online publication date: 15-Apr-2002
https://dl.acm.org/doi/10.5555/645610.662037
Carter LCalder BEbcioglu KPingali KNicolau A(2002)Using predicate path information in hardware to determine true dependencesProceedings of the 16th international conference on Supercomputing10.1145/514191.514224(230-240)Online publication date: 22-Jun-2002
https://dl.acm.org/doi/10.1145/514191.514224
Choi YKnies AGerke LNgai TPatt YFisher JFaraboschi PSkadron K(2001)The impact of if-conversion and branch prediction on program execution on the Intel® Itanium™ processorProceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture10.5555/563998.564023(182-191)Online publication date: 1-Dec-2001
https://dl.acm.org/doi/10.5555/563998.564023
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 Publication

Media

Figures

Other

Tables

View Table of Contents