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

Article

Wish Branches: Combining Conditional Branching and Predication for Adaptive Predicated Execution

Authors:

Yale N. PattAuthors Info & Claims

MICRO 38: Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture

Pages 43 - 54

https://doi.org/10.1109/MICRO.2005.38

Published: 12 November 2005 Publication History

Publisher Site Get Access

Abstract

Predicated execution has been used to reduce the number of branch mispredictions by eliminating hard-to-predict branches. However, the additional instruction overhead and additional data dependencies due to predicated execution sometimes offset the performance advantage of having fewer mispredictions. We propose a mechanism in which the compiler generates code that can be executed either as predicated code or non-predicated code (i.e., code with normal conditional branches). The hardware decides whether the predicated code or the non-predicated code is executed based on a run-time confidence estimation of the branch's prediction. The code generated by the compiler is the same as predicated code, except the predicated conditional branches are NOT removed - they are left intact in the program code. These conditional branches are called wish branches. The goal of wish branches is to use predicated execution for hard-to-predict dynamic branches and branch prediction for easy-to-predict dynamic branches, thereby obtaining the best of both worlds. We also introduce a class of wish branches, called wish loops, which utilize predication to reduce the misprediction penalty for hard-to-predict backward (loop) branches. We describe the semantics, types, and operation of wish branches along with the software and hardware support required to generate and utilize them. Our results show that wish branches decrease the average execution time of a subset of SPEC INT 2000 benchmarks by 14.2% compared to traditional conditional branches and by 13.3% compared to the best-performing predicated code binary.

References

[1]

{1} J. R. Allen, K. Kennedy, C. Porterfield, and J. Warren. Conversion of control dependence to data dependence. In POPL-10, 1983.

Digital Library

[2]

{2} D. Anderson, F. Sparacio, and R. Tomasulo. The IBM system/360 model 91: Machine philosophy and instruction-handling. IBM Journal of Research and Development, 11(1):8- 24, Jan. 1967.

Digital Library

[3]

{3} P.-Y. Chang, E. Hao, T.-Y. Yeh, and Y. N. Patt. Using predicated execution to improve the performance of a dynamically-scheduled machine with speculative execution. In PACT-1995, 1995.

Digital Library

[4]

{4} C.-Y. Cher and T. N. Vijaykumar. Skipper: a microarchitecture for exploiting control-flow independence. In MICRO-34, 2001.

Digital Library

[5]

{5} Y. Choi, A. Knies, L. Gerke, and T.-F. Ngai. The impact of if-conversion and branch prediction on program execution on the Intel Itanium processor. In MICRO-34, 2001.

Digital Library

[6]

{6} Y. Chou, J. Fung, and J. P. Shen. Reducing branch misprediction penalties via dynamic control independence detection. In ICS-99, 1999.

Digital Library

[7]

{7} W. Chuang and B. Calder. Predicate prediction for efficient out-of-order execution. In ICS-03, 2003.

Digital Library

[8]

{8} Compaq Computer Corporation. Alpha 21264 Microprocessor Hardware Reference Manual, 1999.

[9]

{9} A. Darsch and A. Seznec. IATO, The IAOO Toolkit. IRISA. http://www.irisa.fr/caps/projects/ArchiCompil/iato/.

[10]

{10} M. R. de Alba and D. R. Kaeli. Runtime predictability of loops. In IEEE 4th Annual Workshop on Workload Characterization, 2001.

Digital Library

[11]

{11} T. Heil and J. E. Smith. Selective dual path execution. Technical report, University of Wisconsin-Madison, Nov. 1996.

[12]

{12} Intel Corporation. IA-64 Intel Itanium Architecture Software Developer's Manual Volume 3: Instruction Set Reference, 2002.

[13]

{13} E. Jacobsen, E. Rotenberg, and J. E. Smith. Assigning confidence to conditional branch predictions. In MICRO-29, 1996.

Digital Library

[14]

{14} A. Klauser, T. Austin, D. Grunwald, and B. Calder. Dynamic hammock predication for non-predicated instruction set architectures. In PACT-1998, 1998.

Digital Library

[15]

{15} A. Klauser, A. Paithankar, and D. Grunwald. Selective eager execution on the polypath architecture. In ISCA-25, 1998.

Digital Library

[16]

{16} A. KleinOsowski and D. J. Lilja. Minnespec: A new SPEC benchmark workload for simulation-based computer architecture research. Computer Architecture Letters, 1, June 2002.

Digital Library

[17]

{17} Y. Liu, Z. Zhang, R. Qiao, and R. Ju. A region-based compilation infrastructure. In INTERACT-7, 2003.

Digital Library

[18]

{18} C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: Building customized program analysis tools with dynamic instrumentation. In PLDI, 2005.

Digital Library

[19]

{19} S. A. Mahlke, R. E. Hank, R. A. Bringmann, J. C. Gyllenhaal, D. M. Gallagher, and W. W. Hwu. Characterizing the impact of predicated execution on branch prediction. In MICRO-27, 1994.

Digital Library

[20]

{20} S. Mantripragada and A. Nicolau. Using profiling to reduce branch misprediction costs on a dynamically scheduled processor. In ICS-2000, 2000.

Digital Library

[21]

{21} S. McFarling. Combining branch predictors. Technical Report TN-36, Digital Western Research Laboratory, June 1993.

[22]

{22} ORC. Open research compiler for Itanium processor family. http://ipf-orc.sourceforge.net/.

[23]

{23} D. N. Pnevmatikatos and G. S. Sohi. Guarded execution and dynamic branch prediction in dynamic ILP processors. In ISCA-21, 1994.

Digital Library

[24]

{24} B. R. Rau, D. W. L. Yen, W. Yen, and R. A. Towle. The Cydra 5 departmental supercomputer. IEEE Computer, 22:12-35, Jan. 1989.

Digital Library

[25]

{25} E. M. Riseman and C. C. Foster. The inhibition of potential parallelism by conditional jumps. IEEE Transactions on Computers , C-21(12):1405-1411, 1972.

Digital Library

[26]

{26} E. Rotenberg, Q. Jacobson, and J. E. Smith. A study of control independence in superscalar processors. In HPCA-5, 1999.

Digital Library

[27]

{27} T. Sherwood and B. Calder. Loop termination prediction. In HiPC-3, 2000.

[28]

{28} E. Sprangle and Y. Patt. Facilitating superscalar processing via a combined static/dynamic register renaming scheme. In MICRO-27, 1994.

Digital Library

[29]

{29} G. S. Tyson. The effects of predication on branch prediction. In MICRO-27, 1994.

Digital Library

[30]

{30} A. Uht and V. Sindagi. Disjoint eager execution: An optimal form of speculative execution. In ISCA-22, 1995.

[31]

{31} P. H. Wang, H. Wang, R. M. Kling, K. Ramakrishnan, and J. P. Shen. Register renaming and scheduling for dynamic execution of predicated code. In HPCA-7, 2001.

Digital Library

[32]

{32} T.-Y. Yeh and Y. N. Patt. Alternative implementations of two-level adaptive branch prediction. In ISCA-19, 1992.

Digital Library

Cited By

Chauhan AGaur JSperber ZSala FRappoport LYoaz ASubramoney SMartínez JDuato JEeckhout L(2020)Auto-predication of critical branchesProceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture10.1109/ISCA45697.2020.00019(92-104)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1109/ISCA45697.2020.00019
Adileh ALilja DEeckhout LOskin MInoue K(2018)Architectural support for probabilistic branchesProceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2018.00018(108-120)Online publication date: 20-Oct-2018
https://dl.acm.org/doi/10.1109/MICRO.2018.00018
McFarlin DZilles C(2015)Branch vanguardACM SIGARCH Computer Architecture News10.1145/2872887.275040043:3S(323-335)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2872887.2750400
Show More Cited By

Index Terms

Wish Branches: Combining Conditional Branching and Predication for Adaptive Predicated Execution
1. Computer systems organization
  1. Architectures
    1. Serial architectures
      1. Pipeline computing
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Wish Branches: Enabling Adaptive and Aggressive Predicated Execution

The goal of wish branches is to use predicated execution for hard-to-predict dynamic branches, and branch prediction for easy-to-predict dynamic branches, thereby obtaining the best of both worlds. Wish loops, one class of wish branches, use predication ...
Long-latency branches: how much do they matter?

Dynamic branch prediction plays a key role in delivering high performance in the modern microprocessors. The cycles between the prediction of a branch and its execution constitute the branch misprediction penalty because a misprediction can be detected ...
Exploiting instruction level parallelism in the presence of conditional branches

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MICRO 38: Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture

November 2005

350 pages

ISBN:0769524400

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Computer Society

United States

Publication History

Published: 12 November 2005

Check for updates

Qualifiers

Article

Conference

Micro-38

Sponsor:

SIGMICRO

Micro-38: The 38th Annual IEEE/ACM International Symposium on Microarchitecture

November 12 - 16, 2005

Barcelona, Spain

Acceptance Rates

MICRO 38 Paper Acceptance Rate 29 of 147 submissions, 20%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
57
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chauhan AGaur JSperber ZSala FRappoport LYoaz ASubramoney SMartínez JDuato JEeckhout L(2020)Auto-predication of critical branchesProceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture10.1109/ISCA45697.2020.00019(92-104)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1109/ISCA45697.2020.00019
Adileh ALilja DEeckhout LOskin MInoue K(2018)Architectural support for probabilistic branchesProceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2018.00018(108-120)Online publication date: 20-Oct-2018
https://dl.acm.org/doi/10.1109/MICRO.2018.00018
McFarlin DZilles C(2015)Branch vanguardACM SIGARCH Computer Architecture News10.1145/2872887.275040043:3S(323-335)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2872887.2750400
McFarlin DZilles CPrvulovic M(2015)Bungee jumpsProceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830781(370-382)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830781
McFarlin DZilles CMarr DAlbonesi D(2015)Branch vanguardProceedings of the 42nd Annual International Symposium on Computer Architecture10.1145/2749469.2750400(323-335)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2749469.2750400
Prémillieu NSeznec A(2014)Efficient Out-of-Order Execution of Guarded ISAsACM Transactions on Architecture and Code Optimization10.1145/267703711:4(1-21)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.1145/2677037
Sheikh RTuck JRotenberg E(2012)Control-Flow DecouplingProceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2012.38(329-340)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1109/MICRO.2012.38
Hilton ARoth A(2007)GingerACM SIGARCH Computer Architecture News10.1145/1273440.125071635:2(436-447)Online publication date: 9-Jun-2007
https://dl.acm.org/doi/10.1145/1273440.1250716
Hilton ARoth ATullsen DCalder B(2007)GingerProceedings of the 34th annual international symposium on Computer architecture10.1145/1250662.1250716(436-447)Online publication date: 9-Jun-2007
https://dl.acm.org/doi/10.1145/1250662.1250716
Santana ORamirez AValero M(2007)Enlarging Instruction StreamsIEEE Transactions on Computers10.1109/TC.2007.7074256:10(1342-1357)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1109/TC.2007.70742
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