Branch folding in the CRISP microprocessor: reducing branch delay to zero

ABSTRACT

A new method of implementing branch instructions is presented. This technique has been implemented in the CRISP Microprocessor. With a combination of hardware and software techniques the execution time cost for many branches can be effectively reduced to zero. Branches are folded into other instructions, making their execution as separate instructions unnecessary. Branch Folding can reduce the apparent number of instructions needed to execute a program by the number of branches in that program, as well as reducing or eliminating pipeline breakage. Statistics are presented demonstrating the effectiveness of Branch Folding and associated techniques used in the CRISP Microprocessor.

REFERENCES

• 1: A.D. Berenbaum, B. W. Colbry, D. R. Ditzel, R. D. Freeman, H. R. McLellan, K. J. O'Connor, and M. Shoji, "A Pipelined 32b Microprocessor with 13Kb of Cache Memory," Proceedings of the 1987 International Solid State Circuits Conference, pp. 34-35 (February, 1987).
• 2: D. R. Ditzel , H. R. McLellan , A. D. Berenbaum, The hardware architecture of the CRISP microprocessor, Proceedings of the 14th annual international symposium on Computer architecture, p.309-319, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30385]
• 3: D. Morris and R. N. Ibbet, The MU5 Computer System, Springer-Verlag (1979), p. 59.
• 4: Douglas W. Clark , Henry M. Levy, Measurement and analysis of instruction use in the VAX-11/780, Proceedings of the 9th annual symposium on Computer Architecture, p.9-17, April 26-29, 1982, Austin, Texas, United States
• 5: Cheryl A. Wiecek, A case study of VAX-11 instruction set usage for compiler execution, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.177-184, March 01-03, 1982, Palo Alto, California, United States
• 6: Leonard Jay Shustek, Analysis and performance of computer instruction sets., 1978
• 7: Werner Buchholz, Planning a computer system: Project Stretch, McGraw-Hill, Inc., Hightstown, NJ, 1962
• 8: George Radin, The 801 minicomputer, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.39-47, March 01-03, 1982, Palo Alto, California, United States
• 9: David A. Patterson , Carlo H. Sequin, RISC I: A Reduced Instruction Set VLSI Computer, Proceedings of the 8th annual symposium on Computer Architecture, p.443-457, May 12-14, 1981, Minneapolis, Minnesota, United States
• 10: J. L. Hennessy, N. Jouppi, F. Baskett, and J. Gill, "MIPS: A VLSI Processor Architecture," Proceedings of the CMU Conference on VLSI Systems and Computations (October 1981).
• 11: J. Moussouris, L. Crudele, D. Freitas, C. Hansen, E. Hudson, R. March, S. Przybylski, T. Riordan, C. Rowan, and D. Van't Hof, "A CMOS RISC Processor with Integrated System Functions," Spring COMPCON 1986, p. 126.
• 12: J. S. Birnbaum and W. S. Worley, "Beyond RISC: High- Precision Architecture," Spring COMPCON 1986, p. 40.
• 13: 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
• 14: R. W. Holgate and R. N. Ibbet, "An Analysis of Instruction-Fetching Strategies in Pipelined Computers," IEEE Transactions on Computers C-29(4), pp. 325-329 (April 1980).
• 15: D. Morris and R. N. Ibbet, The MU5 Computer System, Springer-Verlag (1979).
• 16: D. W. Anderson, "The System/360 Model 91: Machine Philosophy and Instruction Handling," IBM Journal of Research and Development 11(8), pp. 8-24 (January 1967).
• 17: W. D. Connors, "The IBM 3033: An Inside Look," Datamation, pp. 198-218 (May 1979).
• 18: H. Schorr, "Design Principles for a High-Performance System," Proceedings of the Symposium on Computers and Automata XXI, pp. 165-192 (April, 1971).
• 19: Robert G. Wedig , Marc A. Rose, The reduction of branch instruction execution overhead using structured control flow, Proceedings of the 11th annual international symposium on Computer architecture, p.119-125, January 1984
• 20: J. K. F. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design," Computer 17(1) (January, 1984).
• 21: A. D. Berenbaum, D. R. Ditzel, and H. R. McLellan, "Introduction to the CRISP Instruction Set Architecture," Proceedings of the 1987 Spring COMPCON, pp. 86-90 (February, 1987).
• 22: Manolis G. H. Katevenis, Reduced instruction set computer architectures for VLSI, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 23: Robert D. Russell, The PDP-11: A case study of how not to design condition codes, Proceedings of the 5th annual symposium on Computer architecture, p.190-194, April 03-05, 1978 [doi>10.1145/800094.803047]
• 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
• 25: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 26: J. K. F. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design," Computer 17(1) (January, 1984).
• 27: S. Bandyopadhyay, V. Begwani, and R. Murray, "Compiling for the CRISP Microprocessor," Proceedings of the Spring 1987 COMPCON, pp. 96-100 (February, 1987).
• 28: J. L. Hennessy and T. R. Gross, "Optimizing Branch Delays," Computer Systems Lab Technical Report, Stanford University (1981).
• 29: Peter M. Kogge, The Architecture of Pipelined Computers, McGraw-Hill (1981), pp. 237-243.
• 30: Hubert Rae McLellan, Jr., "Instruction Prefetch Strategies in a Pipelined Processor," Master of Science Thesis, Massachusetts Institute of Technology (February 1983).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Microprocessors

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design