History cache: hardware support for reverse execution

ABSTRACT

Reverse execution provides access to old states of an executing process. An application of reverse execution can be found in program debugging. When an error is detected, its cause is often hidden in the history of the process. In such situations, it is important to be able to recover and examine past states of the process. Numerous other applications of reverse execution are found in programming environments, in fault-tolerant computing and in speculative computation.Since processes are in general irreversible, the history must be saved in order to provide reverse execution. The main problem in dealing with the history is the amount of data generated. This paper describes a new approach to reverse execution based on a history cache which compacts the history. The performance of the history cache is measured on a simulator. The history cache can compact the history by more than an order of magnitude. Efficient support for reverse execution enables many new techniques such as a generic undo operation, a real-time checkpoint, and fast backtracking.

REFERENCES

• 1: James E. Archer, Jr. , Richard Conway , Fred B. Schneider, User Recovery and Reversal in Interactive Systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.1, p.1-19, Jan. 1984 [doi>10.1145/357233.357234]
• 2: [2] R. M. Balzer. EXDAMS - EXtendable Debugging and Monitoring System. In AFIPS Conference Proceeedings, Vol. 34, pages 567-580. SJCC, 1969.
• 3: James R. Bitner , Edward M. Reingold, Backtrack programming techniques, Communications of the ACM, v.18 n.11, p.651-656, Nov. 1975 [doi>10.1145/361219.361224]
• 4: T. A. Cargill , B. N. Locanthi, Cheap hardware support for software debugging and profiling, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.82-83, October 1987, Palo Alto, California, United States
• 5: [5] K. M. Chandy and C. V. Ramamoorthy. Rollback and recovery strategies for computer programs. IEEE Transactions on Computers, 21(6):546-556, June 1972.
• 6: Stuart I. Feldman , Channing B. Brown, IGOR: a system for program debugging via reversible execution, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.112-123, May 05-06, 1988, Madison, Wisconsin, United States
• 7: [7] A. M. Feridun and K. G. Shin. A fault-tolerant multiprocessor system with rollback recovery capabilities. In Proc. 2nd Int. Conf. Distributed Comput. Sys., pages 283-298. IEEE, 1981.
• 8: Christopher W. Fraser, A retargetable compiler for ANSI C, ACM SIGPLAN Notices, v.26 n.10, p.29-43, Oct. 1991 [doi>10.1145/122616.122621]
• 9: Richard M. Fujimoto , Jya-Jang Tsai , Ganesh C. Gopalakrishnan, Design and Evaluation of the Rollback Chip: Special Purpose Hardware for Time Warp, IEEE Transactions on Computers, v.41 n.1, p.68-82, January 1992 [doi>10.1109/12.123382]
• 10: Jan Heering , Paul Klint, Towards monolingual programming environments, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.183-213, April 1985 [doi>10.1145/3318.3321]
• 11: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 12: W.-M. W. Hwu , Y. N. Patt, Checkpoint repair for high-performance out-of-order execution machines, IEEE Transactions on Computers, v.36 n.12, p.1496-1514, Dec. 1987 [doi>10.1109/TC.1987.5009500]
• 13: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 14: [14] P. A. Lee, N. Ghani, and K. Heron. A recovery cache for the PDP-11. IEEE Transactions on Computers, 29(6):546-549, June 1980.
• 15: [15] Y.-H. Lee and K. G. Shin. Design and evaluation of a fault-tolerant multiprocessor using hardware recovery blocks. IEEE Transactions on Computers , 33(2):113-124, February 1984.
• 16: George B. Leeman, Jr., A formal approach to undo operations in programming languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.50-87, Jan. 1986 [doi>10.1145/5001.5005]
• 17: K. Li , J. F. Naughton , J. S. Plank, Real-time, concurrent checkpoint for parallel programs, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.79-88, March 14-16, 1990, Seattle, Washington, United States
• 18: Henry Lieberman, Reversible Object-Oriented Interpreters, Proceedings of the European Conference on Object-Oriented Programming, p.11-19, June 15-17, 1987
• 19: J. M. Mellor-Crummey , T. J. LeBlanc, A software instruction counter, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.78-86, April 03-06, 1989, Boston, Massachusetts, United States
• 20: T. G. Moher, PROVIDE: A Process Visualization and Debugging Environment, IEEE Transactions on Software Engineering, v.14 n.6, p.849-857, June 1988 [doi>10.1109/32.6163]
• 21: Douglas Z. Pan , Mark A. Linton, Supporting reverse execution for parallel programs, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.124-129, May 05-06, 1988, Madison, Wisconsin, United States
• 22: Bernard L. Peuto , Leonard J. Shustek, An instruction timing model of CPU performance, Proceedings of the 4th annual symposium on Computer architecture, p.165-178, March 23-25, 1977
• 23: James E. Smith , Andrew R. Pleszkun, Implementing Precise Interrupts in Pipelined Processors, IEEE Transactions on Computers, v.37 n.5, p.562-573, May 1988 [doi>10.1109/12.4607]
• 24: Rok Sosic , Robert R. Johnson, The many faces of introspection, The University of Utah, 1992
• 25: R. Sosic , J. Gu, Efficient Local Search with Conflict Minimization: A Case Study of the n-Queens Problem, IEEE Transactions on Knowledge and Data Engineering, v.6 n.5, p.661-668, October 1994 [doi>10.1109/69.317698]
• 26: [26] L. Sterling and E. Shapiro. The Art of Prolog. MIT Press, Cambridge, MA, 1986.
• 27: Tim Teitelbaum , Thomas Reps, The Cornell program synthesizer: a syntax-directed programming environment, Communications of the ACM, v.24 n.9, p.563-573, Sept. 1981 [doi>10.1145/358746.358755]
• 28: Andrew P. Tolmach , Andrew W. Appel, Debugging standard ML without reverse engineering, Proceedings of the 1990 ACM conference on LISP and functional programming, p.1-12, June 27-29, 1990, Nice, France [doi>10.1145/91556.91564]
• 29: P. R. Wilson , T. G. Moher, Demonic memory for process histories, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.330-343, June 19-23, 1989, Portland, Oregon, United States
• 30: M. V. Zelkowitz, Reversible execution, Communications of the ACM, v.16 n.9, p.566, Sept. 1973 [doi>10.1145/362342.362360]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  C. Computer Systems Organization

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

General Terms:
Design, Measurement, Performance, Standardization, Theory