An evaluation of branch architectures

ABSTRACT

Branch instructions form a significant fraction of executed instructions, and their design is thus a crucial component of any architecture. This paper examines three alternatives in the design of branch instructions: delayed vs. non-delayed branches, one- vs. two-instruction branches, and the use or non-use of condition codes. Simulation and analytical techniques are used to provide quantitative comparisons between these choices.

REFERENCES

• 1: 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
• 2: Control Data Corporation. CDC CYBER 170 Computer Systems, CDC CYBER 180 Computer Systems Virtual State: Volume II, Instruction Descriptions, Programming Information, Hardware Reference Manual. Control Data Corporation, St. Paul, Minnesota, 1984.
• 3: David Cutler. Digital Equipment Corporation, July 1985. Personal Communication.
• 4: John DeRosa. An Architectural Analysis of Branch Instructions. Master's thesis, Department of Computer Science, University of Washington, July 1986. Technical Report 86-07-06.
• 5: Digital Equipment Corporation. Decsystem10 System Reference Manual. Digital Equipment Corporation, Maynard, Massachusetts. 1975.
• 6: Joel S. Emer , Douglas W. Clark, A Characterization of Processor Performance in the vax-11/780, Proceedings of the 11th annual international symposium on Computer architecture, p.301-310, January 1984
• 7: Thomas Gross. Analysis of delayed branches. August 1984. Unpublished.
• 8: Thomas Karl Richard Gross, Code optimization of pipeline constraints, 1983
• 9: 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
• 10: John L. Hennessy , Norman Jouppi , Forest Baskett , John Gill, MIPS: a VLSI processor architecture, Stanford University, Stanford, CA, 1981
• 11: 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
• 12: John L. Hennessy , Norman Jouppi , Steven Przybylski , Christopher Rowen , Thomas Gross, Design of a high performance VLSI processor, Stanford University, Stanford, CA, 1983
• 13: John L. Hennessy. VLSI processor architecture. IEEE Transactions on Computers, C-33(12):1221-1246, December 1984.
• 14: H J Hindin, IBM RISC workstation features 40-bit virtual addressing, Computer Design, v.25 n.4, p.28-30, Feb. 15, 1986
• 15: IBM Corporation. IBM RT PC Hardware Technical Reference, Volume 1. IBM, September 1986. SV21-8024.
• 16: Intel Corporation. iAPX 432 GDP Architecture Reference Manual. Intel Corporation, Santa Clara, California, 1981. Order no. 171860-001.
• 17: Manolis G. H. Katevenis, Reduced instruction set computer architectures for VLSI, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 18: Donald E. Knuth. An empirical study of FORTRAN programs. Software - Practice and Experience, 1:105-133, 1971.
• 19: Peter Kogge. The Architecture of Pipelined Computers. McGraw-Hill Book Company, 1981.
• 20: Johnny K. F. Lee and Alan Jay Smith. Branch prediction strategies and branch target buffer design. IEEB Computer, 6-22, January 1984.
• 21: Michael J. Mahon, Ruby Bel-Loh Lee, Terrence C. Miller, Jerome C. Huck, and William R. Bryg. Hewlett-Packard Precision architecture: the processor. Hewlett-Packard Journal, 37(8):4-22, August 1986.
• 22: R. E. Matick and D. T. Ling. Architecture implications in the design of microprocessors. IBM Systems Journal, 23(3):264-280, 1984.
• 23: 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
• 24: David A. Patterson , David R. Ditzel, The case for the reduced instruction set computer, ACM SIGARCH Computer Architecture News, v.8 n.6, p.25-33, October 1980 [doi>10.1145/641914.641917]
• 25: 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
• 26: Bernard L. Peuto , Leonard J. Shustek, An instruction timing model of CPU performance, Proceedings of the 4th annual symposium on Computer architecture, p.165-178, March 23-25, 1977
• 27: Steven A. Przybylski , Thomas R. Gross , John L. Hennessy , Norman P. Jouppi , Christopher Rowen, Organization and VLSI implementation of MIPS, Advances in VLSI and Computer Systems, v.1 n.2, p.170-208, Fall 1984
• 28: 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
• 29: Ramakrishna B. Rau , George E. Rossmann, The effect of instruction fetch strategies upon the performance of pipelined instruction units, Proceedings of the 4th annual symposium on Computer architecture, p.80-89, March 23-25, 1977
• 30: 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]
• 31: Leonard Jay Shustek. Analysis and Performance of Computer Instruction Sets. PhD thesis, Stanford University, January 1978.
• 32: 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
• 33: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

General Terms:
Design, Measurement, Performance