Tolerating data access latency with register preloading

ABSTRACT

By exploiting fine grain parallelism, superscalar processors can potentially increase the performance of future supercomputers. However, supercomputers typically have a long access delay to their first level memory which can severely restrict the performance of superscalar processors. Compilers attempt to move load instructions far enough ahead to hide this latency. However, conventional movement of load instructions is limited by data dependence analysis. This paper introduces a simple hardware scheme, referred to as preload register update, to allow the compiler to move load instructions even in the presence of inconclusive data dependence analysis results. Preload register update keeps the load destination registers coherent when load instructions are moved past store instructions that reference the same location. With this addition, superscalar processors can more effectively tolerate longer data access latencies.

REFERENCES

• 1: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Nancy J. Warter , Wen-mei W. Hwu, IMPACT: an architectural framework for multiple-instruction-issue processors, Proceedings of the 18th annual international symposium on Computer architecture, p.266-275, May 27-30, 1991, Toronto, Ontario, Canada
• 2: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
• 3: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 4: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 5: Zhiyuan Li , Pen-Chung Yew , Chuag-Qi Zhu, Data dependence analysis on multi-dimensional array references, Proceedings of the 3rd international conference on Supercomputing, p.215-224, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318813]
• 6: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 7: V. A. Guarna Jr., "Analysis of C programs for parallelization in the presence of pointers," Master's thesis, Center for Supercomputing Research and Development, University of Illinois, Urbana-Champaign, Illinois, 1987.
• 8: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
• 9: Pohua P. Chang , William Y. Chen , Scott A. Mahlke , Wen-mei W. Hwu, Comparing static and dynamic code scheduling for multiple-instruction-issue processors, Proceedings of the 24th annual international symposium on Microarchitecture, p.25-33, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123471]
• 10: P. G. Emma, J. W. Knight, III, J. H. Pomerene, R. N. Rechtschaffen, and F. J. Sparacio, "Posting out-ofsequence fetches," Feb. 1991. United States Patent No. 4991090.
• 11: H. Dietz , C. H. Chi, CRegs: a new kind of memory for referencing arrays and pointers, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.360-367, November 12-17, 1988, Orlando, Florida, United States
• 12: Ben Heggy , Mary Lou Soffa, Architectural support for register allocation in the presence of aliasing, Proceedings of the 1990 conference on Supercomputing, p.730-739, October 1990, New York, New York, United States
• 13: Alexandru Nicolau, Run-time disambiguation: coping with statically unpredictable dependencies, IEEE Transactions on Computers, v.38 n.5, p.633-678, May 1989
• 14: S. A. Mahlke, W. Y. Chen, W. W. Hwu, B. R. Rau, and M. S. Schlansker, "Sentinel scheduling for VLIW and superscalar processors," tech. rep., Center for Reliable and High-Performance Computing, University of illinois, Urbana, IL, Dec. 1991.
• 15: H. S. Warren, Jr., Instruction scheduling for the IBM RISC System/6000 processor, IBM Journal of Research and Development, v.34 n.1, p.85-92, Jan. 1990
• 16: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 17: Gerry Kane, MIPS RISC architecture, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 18: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

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

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Design, Experimentation, Performance

Keywords:
VLIW/superscalar processor, data dependence analysis, load latency, register file, register preload