Architectural support for the efficient generation of code for horizontal architectures

Abstract

Horizontal architectures, such as the CDC Advanced Flexible Processor [I] and the FPS APi20-B [2}, consist 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 have been developed to perform high speed scientific computations at a modest cost: Figure 1 displays those characteristics of horizontal architectures that are germane to the issues discussed in this paper. The simultaneous requirements of high performance and low cost lead to an architecture consisting of multiple pipelined processing elements (PEs) such as adders and multipliers, a memory (which for scheduling purposes may be viewed as yet another PE with two operations: a READ and a WRITE), and an interconnect which ties them all together. The interconnect allows the result of one operation to be directly routed to another PE as one of the inputs for an operation that is to be performed there. The required memory bandwidth is reduced since temporary values need not be written to and read from the memory. The final aspect of horizontal processors that is of interest is that their program memories emit wide instructions which synchronously specify the actions of the multiple and possibly dissimilar PEs. The program memory is sequenced by a conventional sequencer that assumes sequential flow of control unless a branch is explicitly specified.

As a consequence of the simplicity of such an architecture, it is inexpensive relative to the potential performance of the multiple pipelined PEs. However, 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 expensiw3 project. The polycyclic architecture [3- 6] is a horizontal architecture with architectural support for the scheduling task. The cause of the complexity involved in scheduling conventional horizontal processors and the manner in which the polycyclic architecture addresses this issue are outlined in this paper.

References

1. 1 CDC Advanced Flexible Processor Microcode Cross Assembler (MICA) Reference Manual, Control Data Corp., Publication No. 77900500, Apr. 1980.
2. 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. 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. 4 B.R. Rau and C.D. Glaeser, "Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing", Proc. 14th Annual Workshop on Microprogramming, pp. 183-198, Oct. 1981.
5. 5 B.R. Rau, R.L. Picard, C.D. Glaeser and E.M. Greenawalt, "The polycyclic architecture: a statically scheduled data flow architecture", Computer (to appear).
6. 6 B.R. Rau, C.D. Glaeser and E.M. Greenawalt, "Efficient code generation for horizontal architectures; compiler techniques and architectural support", (submitted for publication).
7. 7 J.H. Patel, "Processor-memory interconnections for multiprocessors", Proc. 6th Annual Symposium on Computer Architecture, pp. 168-177, April 1979.
8. 8 A.V. Aho and J.D. Ullman, Principles of Compiler Design, Addison-Wesley, New York, 1977.
9. 9 W.A. Wulf, et al., The Design of an Optimizing Compiler, Elsevier, New York, 1975.
10. 10 F.L. Bauer and J. Eichel (Eds.), Compiler Construction, An Advanced Course, Springer-Verlag, New York, 1976.
11. 11 D. Landskov, S. Davidson and B. Shriver, "Local microcode compaction techniques", Computing Surveys, Vol.11, No. 3, pp. 261-294, Sep. 1980.
12. 12 M.J. Gonzalez, "Deterministic processor scheduling", Computing Surveys, Vol. 9, No. 3, pp. 173-204, Sep. 1977.
13. 13 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.

Index Terms

• Computer systems organization

  • Architectures

    • Serial architectures

      • Pipeline computing

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Source code generation