Efficient code generation for horizontal architectures: Compiler techniques and architectural support

ABSTRACT

A horizontal architecture consists of a number of resources that can operate in parallel, each of which is controlled by a field in the wide instruction word. Such architectures offer the potential for high performance scientific computing at a modest cost. If this potential performance is to be realized, the multiple resources of a horizontal processor must be scheduled effectively. The scheduling task for conventional horizontal processors is quite complex and the construction of highly optimizing compilers for them is a difficult and expensive project. The polycyclic architecture is a horizontal architecture with architectural support for the scheduling task. The complexity of scheduling conventional horizontal processors and the ease of scheduling polycyclic processors is demonstrated by means of an example.

REFERENCES

• 1: CDC Advanced Flexible Processor Microcode Cross Assembler (MICA) Reference Manual, Control Data Corp., Publication No. 77900500, Apr. 1980.
• 2: A. E. Charlesworth, "An approach to scientific array processing: the architectural design of the AP-120B/FPS-164 family," Computer, Vol. 14, No. 9, pp. 18-27, Sep. 1981.
• 3: B. R. Rau, P. J. Kuekes and C. D. Glaeser, "A statically scheduled VLSI interconnect for parallel processors," Proc. CMU Conference on VLSI Systems and Computations, Carnegie-Mellon Univ., Pittsburgh, Pennsylvania, pp. 389-395, Oct. 1981.
• 4: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 5: B. R. Rau, R. L. Picard, C. D. Glaeser and E. M. Greenawalt, "The polycyclic architecture: a statically scheduled dataflow architecture," Computer (to appear).
• 6: Janak H. Patel, Processor-memory interconnections for multiprocessors, Proceedings of the 6th annual symposium on Computer architecture, p.168-177, April 23-25, 1979 [doi>10.1145/800090.802906]
• 7: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 8: P. Brinch Hansen, "The programming language Concurrent Pascal," IEEE Trans. Soft. Eng., Vol. 1, No. 2, pp. 199-207, June 1975.
• 9: The Cray-1S Series of Computers, Cray Research Inc., Pub. No. 2240008C, 1979.
• 10: Special issue on Data Flow Systems, Computer, Vol. 15, No. 2, Feb. 1982.
• 11: 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]
• 12: W. H. Kohler "A preliminary evaluation of the critical path method for scheduling tasks on multiprocessor systems," IEEE Trans. on Computers, Vol. C-24, No. 12, pp. 1235-1238, Dec. 1975.
• 13: Mario J. Gonzalez, Jr., Deterministic Processor Scheduling, ACM Computing Surveys (CSUR), v.9 n.3, p.173-204, Sept. 1977 [doi>10.1145/356698.356700]
• 14: E. J. McCluskey, Theory and Design of Switching Circuits, McGraw-Hill, New York, 1965.
• 15: T. Agerwala, "Microprogram optimization: a survey," IEEE Trans. on Computers, Vol. C-25, No. 10, pp. 962-973, Oct. 1976.
• 16: W. J. Karplus and D. Cohen, "Architectural and software issues in the design and application of peripheral array processors," Computer, Vol. 14, No. 9, pp. 11-17, Sep. 1981.
• 17: Danny Cohen, A methodology for programming a pipeline array processor, Proceedings of the 11th annual workshop on Microprogramming, p.82-89, November 19-22, 1978, Pacific Grove, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design