Register requirements of pipelined processors

ABSTRACT

To enable concurrent instruction execution, scientific computers generally rely on pipelining, which combines with faster system clocks to achieve greater throughput. Each concurrently executing instruction requires buffer space, usually implemented as a register, to receive its result. This paper focuses on the issue of how many registers are required to achieve optimal performance in pipelined scientific computers. Four machine models are considered: single, double, and triple issue scalar machines, and vector machines with various register lengths. A model is presented that accurately relates the register requirements for optimum performance cyclically scheduled loops with tree-dependence graphs to the degree of function unit pipelining, the instruction issue bandwidth, and code properties. A method for finding upper and lower bounds on the minimum register requirements is also presented. The result of this work is a theory for assessing register requirements that can be used to reveal fundamental differences among machines within a space of architectural and implementation design choices. Some experimental data is also provided to support the theory.

REFERENCES

• 1: M. J. Flynn, "Very High-Speed Computing Systems," Proc. IEEB, vol. 54, pp. 1901-1909, December 1966.
• 2: Robert P. Colwell , Robert P. Nix , John J. O'Donnell , David B. Papworth , Paul K. Rodman, A VLIW architecture for a trace scheduling compiler, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.180-192, October 1987, Palo Alto, California, United States
• 3: B. J. Smith, "Architecture and Applications of the HEP Multiprocessor Computer System," Real Time Signal Procesing IV, vol. 298, August 1981.
• 4: 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
• 5: D. W. Anderson, F. J. Sparacio, and R. M. Tomasulo, "IBM System/360 Model 91: Machine Philosophy and Instruction Handling," IBM Journal of Research and Development, pp. 8-24, January 1967.
• 6: William Mangione-Smith , Santosh G. Abraham , Edward S. Davidson, Vector register design for polycyclic vector scheduling, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.154-163, April 08-11, 1991, Santa Clara, California, United States
• 7: P Y Hsu, Highly concurrent scalar processing, University of Illinois, Department of Computer Science, Urbana, IL, 1986
• 8: Roy F. Touzeau, A Fortran compiler for the FPS-164 scientific computer, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.48-57, June 17-22, 1984, Montreal, Canada
• 9: 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
• 10: B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, Proceedings of the 9th annual symposium on Computer Architecture, p.131-139, April 26-29, 1982, Austin, Texas, United States
• 11: B. Ramakrishna Rau , David W. L. Yen , Wei Yen , Ross A. Towie, The Cydra 5 Departmental Supercomputer: Design Philosophies, Decisions, and Trade-Offs, Computer, v.22 n.1, p.12-26, 28-30, 32-35, January 1989 [doi>10.1109/2.19820]
• 12: Christine Eisenbeis , W. Jalby , Alain Lichnewsky, Compile time optimization of memory and register usage on the Cray 2, Selected papers of the second workshop on Languages and compilers for parallel computing, p.230-253, May 1990, Urbana, Illinois, United States
• 13: Monica Sin-Ling Lam, A systolic array optimizing compiler, 1987
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: James E. Smith, Decoupled access/execute computer architectures, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.289-308, Nov. 1984 [doi>10.1145/357401.357403]
• 16: William Mangione-Smith , Santosh G. Abraham , Edward S. Davidson, A Performance Comparison of the IBM RS/6000 and the Astronautics ZS-1, Computer, v.24 n.1, p.39-46, January 1991 [doi>10.1109/2.67192]
• 17: William Henry Mangione-Smith, Performance bounds and buffer space requirements for concurrent processors, University of Michigan, Ann Arbor, MI, 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

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

General Terms:
Experimentation, Measurement, Performance