Control flow optimization for supercomputer scalar processing

ABSTRACT

Control intensive scalar programs pose a very different challenge to highly pipelined supercomputers than vectorizable numeric applications. Function call/return and branch instructions disrupt the flow of instructions through the pipeline, degrading the utilization of the pipelined datapaths. This paper describes control flow optimization for scalar processing using an optimizing compiler. To obtain program control flow information, a system independent profiler has been integrated into the IMPACT-I C compiler. The control flow information obtained is converted into a weighted control graph. Based on the weighted control graph, function inline expansion, multi-way branch layout, and software branch prediction can be implemented. Using better compiler technology results in a very low cost hardware control unit (architecture) for high performance scalar processors.

REFERENCES

• 1: P.M. Kogge, The Architecture of Pipelined Computers, pp. 237-243, McGraw-Hill, 1981.
• 2: Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
• 3: R.M. Stallman, Internals of GNU CC, Free Software Foundation, Inc., 1988.
• 4: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.222-232, June 17-22, 1984, Montreal, Canada
• 5: C.A. Huson, An In-line Subroutine Expander for Parafrase, M.S. Thesis, University of Illinois at Urbana-Champaign, 1982.
• 6: R. Allen , S. Johnson, Compiling C for vectorization, parallelization, and inline expansion, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.241-249, June 20-24, 1988, Atlanta, Georgia, United States
• 7: D.A. Patterson and C. H. Sequin, "A VLSI RISC," IEEE Computer, pp. 8 - 21, September, 1982.
• 8: 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]
• 9: 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
• 10: 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
• 11: 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.
• 12: 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
• 13: Wen-Mei William Hwu, Hpsm: exploiting concurrency to achieve high performance in a single-chip microarchitecture, 1987
• 14: 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]
• 15: J.K.F. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design," IEEE Computer, January 1984.
• 16: 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
• 17: 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]
• 18: 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]
• 19: Shebanow, M.C. and Part, Y.N., "Autocorrelafion Branch Prediction," in preparation.
• 20: 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
• 21: 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
• 22: J.L. Hennessy, N. louppi, F. Baskett, and J. Gill, "MIPS: A VLSI Processor Architecture," Proceedings of the CMU Conference on VLSi Systems and Computations, October 1981.
• 23: J.S. Birnbaum and W. S. Worley, "Beyond RISC: High Precision Architecture," Spring COMPCON, p. 40, 1986.
• 24: 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]
• 25: 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]
• 26: Gerry Kane, MIPS R2000 RiSC ARCHITECTURE, Prentice Hall, Englewood Cliffs, NJ 07632, 1987.
• 27: 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]
• 28: P. P. Chang , W.-W. Hwu, Inline function expansion for compiling C programs, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.246-257, June 19-23, 1989, Portland, Oregon, United States
• 29: 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
• 30: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 31: J.A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, vol. vol. c-30, no.7, pp. 478- 490, IEEE, July 1981.
• 32: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

  C. Computer Systems Organization

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Design, Languages, Management, Measurement, Performance, Theory