Article

Free access

Optimizing delayed branches

Authors:

Thomas R. Gross,

John L. HennessyAuthors Info & Claims

MICRO 15: Proceedings of the 15th annual workshop on Microprogramming

Pages 114 - 120

Published: 05 October 1982 Publication History

PDF eReader

Abstract

Delayed branches are commonly found in micro-architectures. A compiler or assembler can exploit delayed branches. This is achieved by moving code from one of several points to the positions following the branch instruction. We present several strategies for moving code to utilize the branch delay, and discuss the requirements and benefits of these strategies. An algorithm for processing branch delays has been implemented and we give empirical results. The performance data show that a reasonable percentage of these delays can be avoided.

References

[1]

Wulf, W.A., "Compilers and Computer Architecture," Computer, Vol. 14, No. 7, July 1981, pp. 41-48.

Digital Library

Google Scholar

[2]

McClure, R.M., "Parallelism in Microprogrammed Controls," in Intl. Advanced Summer Institute on Microprogramming, Boulaye, G. and Mermet, J., eds., Hermann, Paris, 1972, pp. 307-328.

Google Scholar

[3]

Agrawala, A.K. and Rauscher, T.G., Foundations of Microprogramming Academic Press, New York, 1976, ACM Monograph Series

Google Scholar

[4]

Fisher, J.A., "2N-way Jump Microinstruction Hardware and an Effective Instruction Binding Method," Proceedings: The 13th Annual Microprogramming Workshop Micro 13, ACM, SIGMICRO, 1980, pp. 64-75.

Digital Library

Google Scholar

[5]

Patterson, D.A. and Sequin C.H., "RISC-I: A Reduced Instruction Set VLSI Computer," Proc. of the Eighth Annual Symposium on Computer Architecture, Minneapolis, Minn., May 1981,.

Digital Library

Google Scholar

[6]

Hennessy, J.,Jouppi, N., Przybylski, S., Rowen, C., Gross, T., Baskett, F., and Gill, J., "MIPS: A Microprocessor Architecture," Proceedings of Micro-15, IEEE, October 1982,.

Digital Library

Google Scholar

[7]

Radin, G., "The 801 Minicomputer," Proc. SIGARCH/SIGPLAN Symposium on Architectural Support for Programming Languages and Operating Systems, ACM, Palo Alto, March 1982, pp. 39-47.

Digital Library

Google Scholar

[8]

Shustek, L.J., Analysis and Performance of Computer Instruction Sets, PhD dissertation, Stanford University, May 1977, Also published as SLAC Report 205.

Digital Library

Google Scholar

[9]

Riseman, E.M. and Foster, C.C., "The Inhibition of Potential Parallelism by Conditional Jumps," Trans. on Computer, Vol. C-21, No. 12, Dec 1972, pp. 1405-1411.

Google Scholar

[10]

Hennessy, J.L. and Gross, T.R., "Code Generation and Reorganization in the Presence of Pipeline Constraints," Proc. Ninth POPL Conference, ACM, January 1982,.

Digital Library

Google Scholar

[11]

Hennessy, J.L., Jouppi, N., Baskett, F., and Gill, J, "MIPS: A VLSI Processor Architecture," Proc. CMU Conference on VLSI Systems and Computations, Computer Science Press, October 1981,.

Crossref

Google Scholar

[12]

Baskett, F., "Puzzle: an informal compute bound benchmark", Widely circulated and run.

Google Scholar

Cited By

View all

Takano S(2017)Performance Scalability of Adaptive Processor ArchitectureACM Transactions on Reconfigurable Technology and Systems10.1145/300790210:2(1-22)Online publication date: 11-Apr-2017
https://dl.acm.org/doi/10.1145/3007902
Aa TMei BDe Sutter BKim TSainrat PLumetta SNavarro N(2007)A backtracking instruction scheduler using predicate-based code hoisting to fill delay slotsProceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems10.1145/1289881.1289921(229-237)Online publication date: 30-Sep-2007
https://dl.acm.org/doi/10.1145/1289881.1289921
Yeh TPatt Y(1998)Alternative implementations of two-level adaptive branch prediction25 years of the international symposia on Computer architecture (selected papers)10.1145/285930.286004(451-461)Online publication date: 1-Aug-1998
https://dl.acm.org/doi/10.1145/285930.286004
Show More Cited By

Index Terms

Optimizing delayed branches
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Very long instruction word
    2. Serial architectures
      1. Complex instruction set computing
      2. Reduced instruction set computing
2. Hardware
  1. Electronic design automation
    1. Logic synthesis
      1. Circuit optimization

Recommendations

Optimizing delayed branches

Delayed branches are commonly found in micro-architectures. A compiler or assembler can exploit delayed branches. This is achieved by moving code from one of several points to the positions following the branch instruction. We present several strategies ...
Formal Verification of Pipelined Microprocessors with Delayed Branches
ISQED '06: Proceedings of the 7th International Symposium on Quality Electronic Design

Presented is an approach for formal verification of pipelined microprocessors with delayed branches, i.e., branch instructions whose immediately following instruction is always executed regardless of whether the branch is taken. Delayed branches are ...
Optimizing Indirect Branches in Dynamic Binary Translators

Dynamic binary translation is a technology for transparently translating and modifying a program at the machine code level as it is running. A significant factor in the performance of a dynamic binary translator is its handling of indirect branches. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MICRO 15: Proceedings of the 15th annual workshop on Microprogramming

October 1982

201 pages

ACM SIGMICRO Newsletter Volume 13, Issue 4
Dec. 1982
169 pages
ISSN:1050-916X
DOI:10.1145/1014194
Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 05 October 1982

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

96
Total Citations
View Citations
1,205
Total Downloads

Downloads (Last 12 months)423
Downloads (Last 6 weeks)38

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Takano S(2017)Performance Scalability of Adaptive Processor ArchitectureACM Transactions on Reconfigurable Technology and Systems10.1145/300790210:2(1-22)Online publication date: 11-Apr-2017
https://dl.acm.org/doi/10.1145/3007902
Aa TMei BDe Sutter BKim TSainrat PLumetta SNavarro N(2007)A backtracking instruction scheduler using predicate-based code hoisting to fill delay slotsProceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems10.1145/1289881.1289921(229-237)Online publication date: 30-Sep-2007
https://dl.acm.org/doi/10.1145/1289881.1289921
Yeh TPatt Y(1998)Alternative implementations of two-level adaptive branch prediction25 years of the international symposia on Computer architecture (selected papers)10.1145/285930.286004(451-461)Online publication date: 1-Aug-1998
https://dl.acm.org/doi/10.1145/285930.286004
Dubey PAdams GFlynn M(1995)Evaluating Performance Tradeoffs Between Fine-Grained and Coarse-Grained AlternativesIEEE Transactions on Parallel and Distributed Systems10.1109/71.3634146:1(17-27)Online publication date: 1-Jan-1995
https://dl.acm.org/doi/10.1109/71.363414
Drach NSeznec AWolfe AMangione-Smith W(1993)MIDEEProceedings of the 26th annual international symposium on Microarchitecture10.5555/255235.255286(193-201)Online publication date: 1-Dec-1993
https://dl.acm.org/doi/10.5555/255235.255286
Perleberg CSmith A(1993)Branch Target Buffer Design and OptimizationIEEE Transactions on Computers10.1109/12.21468742:4(396-412)Online publication date: 1-Apr-1993
https://dl.acm.org/doi/10.1109/12.214687
Gonzalez ALlaberia J(1993)Reducing Branch Delay to Zero in Pipelined ProcessorsIEEE Transactions on Computers10.1109/12.21017942:3(363-371)Online publication date: 1-Mar-1993
https://dl.acm.org/doi/10.1109/12.210179
Yeh TPatt YHwu W(1992)A comprehensive instruction fetch mechanism for a processor supporting speculative executionProceedings of the 25th annual international symposium on Microarchitecture10.5555/144953.145016(129-139)Online publication date: 10-Dec-1992
https://dl.acm.org/doi/10.5555/144953.145016
Yeh TPatt Y(1992)Alternative implementations of two-level adaptive branch predictionACM SIGARCH Computer Architecture News10.1145/146628.13970920:2(124-134)Online publication date: 1-Apr-1992
https://dl.acm.org/doi/10.1145/146628.139709
Yeh TPatt Y(1992)A comprehensive instruction fetch mechanism for a processor supporting speculative executionACM SIGMICRO Newsletter10.1145/144965.14501623:1-2(129-139)Online publication date: 10-Dec-1992
https://dl.acm.org/doi/10.1145/144965.145016
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Optimizing delayed branches

Formal Verification of Pipelined Microprocessors with Delayed Branches

Optimizing Indirect Branches in Dynamic Binary Translators