Checkpoint repair for out-of-order execution machines

ABSTRACT

Out-of-order execution and branch prediction are two mechanisms that can be used profitably in the design of Supercomputers to increase performance. Unfortunately this means there must be some kind of repair mechanism, since situations do occur that require the computing engine to repair to a known previous state. One way to handle this is by checkpoint repair. In this paper we derive several properties of checkpoint repair mechanisms. In addition, we provide algorithms for performing checkpoint repair that incur very little overhead in time and modest cost in hardware. We also note that our algorithms require no additional complexity or time for use with write back cache memory systems than they do with write through cache memory systems, contrary to statements made by previous researchers.

REFERENCES

• 1: 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
• 2: W. Hwu , Y. N. Patt, HPSm, a high performance restricted data flow architecture having minimal functionality, Proceedings of the 13th annual international symposium on Computer architecture, p.297-306, June 02-05, 1986, Tokyo, Japan
• 3: J. K. L. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design," IEEE Computer, vol. 17, no. 1, Jan. 1984.
• 4: Robert M. Keller, Look-Ahead Processors, ACM Computing Surveys (CSUR), v.7 n.4, p.177-195, Dec. 1975 [doi>10.1145/356654.356657]
• 5: James E. Smith , Andrew R. Pleszkun, Implementation of precise interrupts in pipelined processors, Proceedings of the 12th annual international symposium on Computer architecture, p.36-44, June 17-19, 1985, Boston, Massachusetts, United States
• 6: D.W. Anderson, F. J. Sparacio, F. J. Tomasulo, "The IBM System/360 Model 91: Machine Philosophy and Instruction Handling", IBM Journal of Research and Development, vol. 11, No.1, pp. 8-24, 1967.
• 7: R.M. Tomasulo, "An Efficient Algorithm for Exploiting Multiple Arithmetic Units," IBM Journal of Research and Development, vol.11, no. 1, pp.25-33, Jan. 1967.
• 8: J. E. Thornton, Design of a Computer—The Control Data 6600, Scott Foresman & Co, 1970
• 9: S. Weiss and J. E. Smith, "Instruction Issue Logic in Pipelined Supercomputers," IEEE Trans. on Computers, pp. 1013-1022. vol. c-33, No. 11, Nov. 1984.
• 10: DEC, VAX Architeeture Handbook, 1981.
• 11: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• 12: A. J. Smith, "Cache Memories," Computing Surveys, vol.14, No. 8, pp. 478-580, September 1986.
• 13: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 14: W. W. Hwu and Y. N. Patt, "Design Choices for the HPSm Microprocessor Chip," Proeeedings of the 20th Annual HICSS, pp. 329-336, Jan. 1987.
• 15: W. W. Hwu and Y. N. Patt, "Checkpoint Repair for High Performance Out-of-order Execution Machines," internal report.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

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

General Terms:
Algorithms, Design