Optimization of horizontal microcode generation for loop structures

ABSTRACT

MIMOSA is an experimental software for the automatic generation and optimization of microcode for horizontal microprogrammed computers. Achieving peak performance on this class of machines depends heavily upon efficient use of low-level parallelism. MIMOSA takes advantage from high level dependence analysis done by a front-end vectorizer. It translates a FORTRAN loop into horizontal microcode, combining several techniques of optimization such as vectorization, pipeline scheduling, microcode compaction. This paper explains how these different tools are coupled together when applied to simple regular loops.

REFERENCES

• 1: CHAILLOUX, J. ,"Le_Lisp de I'INRIA, le Manuel de Reference", Deeembre 198~.
• 2: CRAY RESEARCH INC.,"Cray-XMP Computer Systems", Main Frame Reference, 1980
• 3: DAVIDSON E.S., ~The Design and Control of Pipelined Function Generators", Proc. 1971 Int. IEEE Conf. on Syst., Networks and Computera~ 1971.
• 4: Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.37-47, June 17-22, 1984, Montreal, Canada
• 5: Mahadevan Ganapathi , Charles N. Fischer, Affix grammar driven code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.560-599, Oct. 1985 [doi>10.1145/4472.4486]
• 6: HANEN C., "Optimizing Static Microprogrammable Pipelines: a Timed Petri Net Model", Proe of the ~nd International Conference on Supereomputing, Santa Clara, 1987.
• 7: KENNEDY, K., "Automatic Vectorization of Fortran Programs to Vector Form", Technical Report, Rive University, Houston, TX, October 1980.
• 8: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 9: KOGGE, P.M., "The Architecture of Pipelined Processors", McGraw-Hill, New York 1981.
• 10: David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980 [doi>10.1145/356819.356822]
• 11: LICtINEWSKY, A., LOYER, M., "Un Module Vectoriel Flottant sur SPS7. Pourquoi?", Bulletin de Liaison de Liaison de la Recherche en Informatique et en Automatique, no 112, 1987.
• 12: LICHNEWSKY A. AND T HOMASSET F., "Techniques de base pour l'exploitation automatique du parallelisme dans les programmes", Rapport de Recherche INRIA, N 460, 1985.
• 13: LICrtNEWSKV, A., THOMASSET, F., EISENBEIS, C., "Automatic Detection of Parallelism in Scientific Programs with Application to Array- Processors", Proe.of IBM Institute, North Holland, 1986.
• 14: MACKE, T., ttUSON, C., DAVIES, J., LEASURE, B., WOLFE, M., "The KAP/ST-100 : A Fortran Translator for the ST100 Attached Processor", International Conference on Parallel Processing 1986.
• 15: NICOLAU, A., "Uniform Parallelism Exploitation in Ordinary Programs", International Conference on Parallel Computing 1985.
• 16: B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, ACM SIGARCH Computer Architecture News, v.10 n.3, p.131-139, April 1982
• 17: SHAR, L.E., "Design and scheduling of statically configured pipelines", Stanford Univ., Technical Report n 4~, 1972.
• 18: Janak H. Patel , Edward S. Davidson, Improving the throughput of a pipeline by insertion of delays, Proceedings of the 3rd annual symposium on Computer architecture, p.159-164, January 19-21, 1976
• 19: STAR TECHNOLOGIES, INC. "ST100: The 100 Megaflops array processor", Hardware and Software Reference Manuals.
• 20: Roy F. Touzeau, A Fortran compiler for the FPS-164 scientific computer, ACM SIGPLAN Notices, v.19 n.6, p.48-57, June 1984

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Pipeline processors**
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Code generation

General Terms:
Design, Languages, Measurement, Performance