Forward semantic: a compiler-assisted instruction fetch method for heavily pipelined processors

ABSTRACT

A new instruction fetch method, forward semantic, is offered to enable the deeply pipelined processors to fetch one useful instruction every cycle. Forward semantic is an improved alternative to the delayed branching (with or without squashing), with five major advantages. Fist, no restriction is imposed on the type of instructions filling the branch slots, which allows a large number of slots to be filled. Second, no modification to the offsets and displacements is necessary when an instruction is copied to fill a branch slot, which simplifies the linker implementation. Third, an interrupted program can resume execution with a single program counter, eliminating the need for reloading the instruction pipeline before resuming execution. Fourth, programs compiled with N slots can execute on pipelines requiring K (K ≤ N) slots, which makes family architecture compatibility possible . Lastly, the filling of branch slots is totally transparent to code compaction and software interlocking schemes. These advantages combine to provide an efficient instruction fetch mechanism and to eliminate artificial penalties on branch cost. At the cost of 11% static code expansion, forward semantic achieves an instruction fetch cost of 1.2 cycles for pipelines requiring 10 slots for each taken branch. This level of instruction fetch efficiency has never been achieved before with conventional instruction fetch methods. The branch cost is dictated by the accuracy of the compile-time branch prediction rather than artificial limitations, such as data dependencies, which prevent the slots from being filled. These results are measured from the execution of real UNIX and CAD programs with complex control structures.

REFERENCES

• 1: P. M. Kogge, The Architecture of Pipelined Computers, pp. 237-243, McGraw-Hill, 1981.
• 2: 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
• 3: J. K. F. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design,' IEEE Computer, January 1984.
• 4: J. A. DeRosa and H. M. Levy, "An Evaluation of Branch Architectures,' Proceedings of the 15th International Symposium on Computer Architecture, Honolulu, Hawaii, May 30 -June 2,1988.
• 5: 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
• 6: 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]
• 7: W. W. Hwu , T. M. Conte , P. P. Chang, Comparing software and hardware schemes for reducing the cost of branches, Proceedings of the 16th annual international symposium on Computer architecture, p.224-233, April 1989, Jerusalem, Israel
• 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: D. A. Patterson and C. H. Sequin, "A VLSI RISC,' IEEE Computer, pp. 8 - 21, September, 1982.
• 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. S. Bimbaum and W. S. Worley, "Beyond RISC: High Precision Architecture,' Spring COMPCON, p. 40.1986.
• 12: 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
• 13: 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]
• 14: 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]
• 15: G. Kane, MIPS R2000 RISC Architecture, Prentice Hall, Englewood Cliffs, NJ, 1987.
• 16: Charles Melear, The Design of the 88000 RISC Family, IEEE Micro, v.9 n.2, p.26-38, March 1989 [doi>10.1109/40.24848]
• 17: 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
• 18: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• 19: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 20: S. Weiss and J. E. Smith, "Instruction Issue Logic in Pipelined Supercomputers," IEEE Transactions on Computers, vol. C-33, pp. 1013--1022, IEEE, November 1984.
• 21: Y. N. Patt , W. M. Hwu , M. Shebanow, HPS, a new microarchitecture: rationale and introduction, Proceedings of the 18th annual workshop on Microprogramming, p.103-108, December 03-06, 1985, Pacific Grove, California, United States
• 22: Wen-Mei William Hwu, Hpsm: exploiting concurrency to achieve high performance in a single-chip microarchitecture, 1987
• 23: R D Acosta , J Kjelstrup , H C Torng, An instruction issuing approach to enhancing performance in multiple functinal unit processors, IEEE Transactions on Computers, v.35 n.9, p.815-828, Sept. 1986 [doi>10.1109/TC.1986.1676841]
• 24: R. M. Tomasulo, "An Efficient Algorithm for Exploiting Multiple Arithmetic Units," IBM Journal of Research and Development, vol. 11, pp. 25-33, January 1967.
• 25: W.-M. W. Hwu , Y. N. Patt, Checkpoint repair for high-performance out-of-order execution machines, IEEE Transactions on Computers, v.36 n.12, p.1496-1514, Dec. 1987 [doi>10.1109/TC.1987.5009500]
• 26: P. P. Chang , W. W. Hwu, Trace selection for compiling large C application programs to microcode, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.21-29, November 28-December 02, 1988, San Diego, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Styles (e.g., parallel, pipeline, special-purpose)

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation

General Terms:
Algorithms, Design