Instruction fetch unit for parallel execution of branch instructions

ABSTRACT

A mechanism to reduce the cost of branches in pipelined processors is presented. This technique is implemented by means of a non-conventional cache (branch target cache) and an early branch detection circuit. Branches are executed by the instruction fetch unit (IFU) in parallel with the other instructions. In this way, the execution time cost for many branches can be effectively reduced to zero. In order to obtain the IFU design parameters, the mechanism is evaluated by means of an analytical model. Simulation results show the effectiveness of this technique.

REFERENCES

• 1: Thomas R. Gross , John L. Hennessy, Optimizing delayed branches, Proceedings of the 15th annual workshop on Microprogramming, p.114-120, October 05-07, 1982, Palo Alto, California, United States
• 2: Manolis G. H. Katevenis, Reduced instruction set computer architectures for VLSI, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 3: John L. Hennessy , Norman Jouppi , Forest Baskett , John Gill, MIPS: a VLSI processor architecture, Stanford University, Stanford, CA, 1981
• 4: M.J. Mahonet al. Hewlett-Packard Precision architecture: the processor. Hewlett-Packard Journal, 37, August i986, pp. 4-22.
• 5: P. Chow , M. Horowitz, Architectural tradeoffs in the design of MIPS-X, Proceedings of the 14th annual international symposium on Computer architecture, p.300-308, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30384]
• 6: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• 7: J. A. DeRosa , H. M. Levy, An evaluation of branch architectures, Proceedings of the 14th annual international symposium on Computer architecture, p.10-16, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30352]
• 8: M. Troianietal. The VAX 8600 I Box: A Pipelined Implementation of the VAX Architecture. Digital Technical Journal, inaugural issue, pp. 24-42.
• 9: D.W. Anderson, F. Sparacio and R. Tomasulo. The IBM System/360 Model 91: Machine Philosophy and Instruction Handling. IBM Journal of Research and Development, Vol. 11, No. 1, January 1967, pp. 8-24.
• 10: D. Morris and R.N. Ibbet. The MU5 Computer System. Springer-Verlag, 1979.
• 11: J.K.F. Lee and A.J. Smith. Branch Prediction Strategies and Branch Target Bt~ffer Design. Computer Magazine, January 1984, pp. 6-22.
• 12: A. Basu. Impact of Prediction Accuracy on the Performance of a Pipeline Comp. EURO87, pp. 832-835.
• 13: A. R. Pleszkun , J. R. Goodman , W. C. Hsu , R. T. Joersz , G. Bier , P. Woest , P. B. Schechter, WISQ: a restartable architecture using queues, Proceedings of the 14th annual international symposium on Computer architecture, p.290-299, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30383]
• 14: D. R. Ditzel , H. R. McLellan, Branch folding in the CRISP microprocessor: reducing branch delay to zero, Proceedings of the 14th annual international symposium on Computer architecture, p.2-8, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30351]
• 15: J. Cortadella and T. Jov~ Designing a Branch Target Buffer for Executing Branches with Zero Time Cost in a RISC Processor. Microprocessing and Microprogramming, Vol.24, n 1-5, 1988, pp. 573-580.
• 16: A. Gonz~lez, J.M. Llaberla, J. Cortadella. A Mechanism for Reducing the Cost of Branches in RISC architectures. Microprocessing and Microprogramming, Vol.24, n 1-5, 1988, pp. 565-572.
• 17: Advanced Micro Devices. AM 29000 Streamlined Instruction Processor. Publication 09075, February 1987, pp. 49-54.
• 18: Mark Hill , Susan Eggers , Jim Larus , George Taylor , Glenn Adams , B. K. Bose , Garth Gibson , Paul Hansen , Jon Keller , Shing Kong , Corinna Lee , Daebum Lee , Joan Pendleton , Scott Ritchie , David Wood , Ben Zorn , Paul Hilfinger , Dave Hodges , Randy Katz , John Ousterhout , Dave Patterson, Design decisions in SPUR, Computer, v.19 n.11, p.8-22, Nov. 1986 [doi>10.1109/MC.1986.1663096]
• 19: B.Case, S.Gupta and T. Olson. Microprocessor Benchmarks Start with Software Simulation that Models the Work Environment. Electronic Design, May 1987.
• 20: A. Olive, V. Vifials and C. Rodriguez. Identifying l~nfiuencing Factors on Branch Target Cache Memory Performance. MINI and Microcomputers and their Application, San Feliu, Spain, 1988, pp. 364-367.
• 21: J. Cortadella, J.M. Llaberfa and A. Gonzalez. Keeping Control Transfer Instructions out of the Pipeline in Architectures without condition code. Research Report 1987, RR87/ll. Facultad de Inform(~tica. Universidad Polit~cnica de Catalufia.
• 22: A. Gonz~lez. Instruction Unit for Parallel Execution of Branch {nstructions Ph.D. Thesis. Facultad de Inform~tica. Universidad Polit~cnica de Catalufia.
• 23: J.Cortadella and J.M.Llaberia. A Low Cost Evaluation Methodology for New architectures. Int. Syrup. on Applied Informatics, Grindelwald. Feb. 1987
• 24: John Hennessy , Norman Jouppi , Forest Baskett , Thomas Gross , John Gill, Hardware/software tradeoffs for increased performance, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.2-11, March 01-03, 1982, Palo Alto, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Experimentation, Measurement, Performance, Reliability, Theory

Keywords:
branch instructions, control dependencies, instruction cache memory, pipelined processors, zero time cost branches