Sentinel scheduling: a model for compiler-controlled speculative execution

ABSTRACT

Speculative execution is an important source of parallelism for VLIW and superscalar processors. A serious challenge with compiler-controlled speculative execution is to efficiently handle exceptions for speculative instructions. In this article, a set of architectural features and compile-time scheduling support collectively referred to as sentinel scheduling is introduced. Sentinel scheduling provides an effective framework for both compiler-controlled speculative execution and exception handling. All program exceptions are accurately detected and reported in a timely manner with sentinel scheduling. Recovery from exceptions is also ensured with the model. Experimental results show the effectiveness of sentinel scheduling for exploiting instruction-level parallelism and overhead associated with exception handling.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
• 3: P. P. Chang , W. W. Hwu, Trace selection for compiling large C application programs to microcode, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.21-29, November 28-December 02, 1988, San Diego, California, United States
• 4: 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
• 5: 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
• 6: Kemal Ebcioğlu, A compilation technique for software pipelining of loops with conditional jumps, Proceedings of the 20th annual workshop on Microprogramming, p.69-79, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255317]
• 7: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 8: FISHER, J.A. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30 (July) 478-490.
• 9: FREUDENBERGER, S., AND RUTTENBERG, J. 1991. Phase ordering of register allocation and instruction scheduling. In Code Generation--Concepts, Tolls, Teehmques., Springer, New York, 146 170.
• 10: J. R. Goodman , W.-C. Hsu, Code scheduling and register allocation in large basic blocks, Proceedings of the 2nd international conference on Supercomputing, p.442-452, June 1988, St. Malo, France [doi>10.1145/55364.55407]
• 11: HEWLETT-PACKARD Co. 1990. PA-RISC 1.1 Archztecture and Instruction Set Reference Manual. Hewlerr-Packard Co., Cupertino, Calif.
• 12: P. Y T Hsu , E. S. Davidson, Highly concurrent scalar processing, Proceedings of the 13th annual international symposium on Computer architecture, p.386-395, June 02-05, 1986, Tokyo, Japan
• 13: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 14: JOHNSON, W. M. 1991 Superscalar Mwroprocessor Destgn. Prentice-Hall, Englewood Cliffs, N.J.
• 15: KANE, G. 1987. MIPS R2000 RISC Architecture. Prentice-Hall, Englewood Cliffs, N.J.
• 16: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 17: Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu , B. Ramakrishna Rau , Michael S. Schlansker, Sentinel scheduling for VLIW and superscalar processors, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.238-247, October 12-15, 1992, Boston, Massachusetts, United States
• 18: 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
• 19: 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]
• 20: 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]
• 21: Michael D. Smith , Mark Horowitz , Monica S. Lam, Efficient superscalar performance through boosting, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.248-259, October 12-15, 1992, Boston, Massachusetts, United States
• 22: Michael D. Smith , Monica S. Lam , Mark A. Horowitz, Boosting beyond static scheduling in a superscalar processor, Proceedings of the 17th annual international symposium on Computer Architecture, p.344-354, May 28-31, 1990, Seattle, Washington, United States
• 23: P. Tirumalai , M. Lee , M. Schlansker, Parallelization of loops with exits on pipelined architectures, Proceedings of the 1990 conference on Supercomputing, p.200-212, October 1990, New York, New York, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Associative memories

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces; System architectures; Instruction set design (e.g., RISC, CISC, VLIW)
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: Pipeline processors**

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization; Code generation

General Terms:
Design, Experimentation, Performance

Keywords:
VlIW processor, exception detection, exception recovery, instruction scheduling, instruction-level parallelism, speculative execution, superscalar processor