Failure-tolerant parallel programming and its supporting system architecture

ABSTRACT

The state-of-art in software validation as well as the continuing growth of the size and complexity of software subsystems, makes extra costs paid for software error tolerance more than justified. A program in which software redundancy is incorporated i.e. a program in which procedures for run-time validation and recovery are explicitly specified, is generally called a failure-tolerant program. One problem in failure-tolerant programming, which could be particularly serious in real-time computing environments, is the program execution time increased due to incorporation of validation and recovery procedures. This paper introduces an approach to the solution, called the failure-tolerant parallel programming. The essence of this approach is to maximally overlap main-stream computation with redundant computation oriented for validation and recovery. Subsequently, a model system architecture tailored for efficient execution of failure-tolerant parallel programs is described. It is of highly general and modular nature and contains a novel memory subsystem named the duplex memory. Directions of further researches on program structuring and expansion of the model architecture are also indicated.

REFERENCES

• 1: A. Avizienis , G. C. Gilley , F. P. Mathur , D. A. Rennels , J. A. Rohr , D. K. Rubin, The STAR (Self-Testing And Repairing) Computer: An Investigation of the Theory and Practice of Fault-Tolerant Computer Design, IEEE Transactions on Computers, v.20 n.11, p.1312-1321, November 1971 [doi>10.1109/T-C.1971.223133]
• 2: Robert S. Boyer , Bernard Elspas , Karl N. Levitt, SELECT—a formal system for testing and debugging programs by symbolic execution, Proceedings of the international conference on Reliable software, p.234-245, April 21-23, 1975, Los Angeles, California
• 3: W. C. Carter , W. G. Bouricius, A Survey of Fault Tolerant Computer Architecture and its Evaluation, Computer, v.4 n.1, p.9-16, January 1971 [doi>10.1109/C-M.1971.216739]
• 4: Chandy, K. M. and C. V. Ramamoorthy, "Rollback and Recovery Strategies for Computer Programs," IEEE Trans, on Comp., February 1972, pp. 137--146.
• 5: Chandy, K. M. et al., "Analytic Models for Rollback and Recovery Strategies in Data Base Systems," IEEE Trans, on Software Engr., March 1975, pp. 100--110.
• 6: K. M. Chandy, A Survey of Analytic Models of Rollback and Recovery Stratergies, Computer, v.8 n.5, p.40-47, May 1975 [doi>10.1109/C-M.1975.218955]
• 7: Chang, H. Y. et al., Fault Diagnosis of Digital Systems, Wiley-Interscience, 1970.
• 8: Connet, J. R. et al., "Software Defenses in Real-Time Control Systems," Digest of the 1972 Int'l Symp. on Fault-Tolerant Computing, pp. 94--99.
• 9: Melvin E. Conway, A multiprocessor system design, Proceedings of the November 12-14, 1963, fall joint computer conference, November 12-14, 1963, Las Vegas, Nevada [doi>10.1145/1463822.1463838]
• 10: Dijkstra, E. W., "Structured Programming," in J. N. Buxton and B. Randell (eds.), Software Engineering Techniques, report on a Conf. sponsored by the NATO Science Committee, Rome, Italy, 1969, pp. 84--88.
• 11: Elemendorf, W. R., "Fault-Tolerant Programming," Digest of the 1972 Int'l Symp. on Fault-Tolerant Computing, pp. 79--83.
• 12: Bernard Elspas , Karl N. Levitt , Richard J. Waldinger , Abraham Waksman, An Assessment of Techniques for Proving Program Correctness, ACM Computing Surveys (CSUR), v.4 n.2, p.97-147, June 1972 [doi>10.1145/356599.356602]
• 13: Hetzel, W. C. (ed), Program Test Methods, Prentice-Hall, 1973.
• 14: James J. Horning , Hugh C. Lauer , P. M. Melliar-Smith , Brian Randell, A program structure for error detection and recovery, Operating Systems, Proceedings of an International Symposium, p.171-187, April 23-25, 1974
• 15: Kennedy, P. J. and T. M. Quinn, "Recovery Strategies in the No. 2 Electronic Switching System," Digest of the 1972 Int'l Symp. on Fault-Tolerant Computing, pp. 165--169.
• 16: James C. King, A new approach to program testing, Proceedings of the international conference on Reliable software, p.228-233, April 21-23, 1975, Los Angeles, California
• 17: Kopetz, H., "Software Redundancy in Real-Time Systems," Proc. IFIP Congress 1974, pp. 182--186.
• 18: Pierce, W. H., Failure-Tolerant Computer Design, Academic Press, 1965.
• 19: Henry Pikner, Programmed restarts, Proceedings of the 1971 26th annual conference, p.13-27, January 1971 [doi>10.1145/800184.810469]
• 20: C. V. Ramamoorthy , R. C. Cheugn , K. H. Kim, Reliability and Integrity of Large Computer Programs, GFK-GI-GMR Fachtagung Prozessrechner 1974, p.86-162, June 10-11, 1974
• 21: Ramamoorthy, C. V. and K. H. Kim, "Software Monitors Aiding Systematic Testing and their Optimal Placement," Proc. 1st Nat'l Conf. on Software Engr., pp. 21--26.
• 22: Randell, B., "System Structure for Software Fault Tolerance," IEEE Trans. on Software Engr., June 1975, pp. 220--232.
• 23: Rohr, J. A., "STAREX-Self-Repair Routines: Software Recovery in the JPL-STAR Computer," Digest of the 1973 Int'l Symp. on Fault-Tolerant Computing, pp. 11--16.
• 24: John Allen Rohr, System software for a fault-tolerant digital computer, University of Illinois at Urbana-Champaign, Champaign, IL, 1973
• 25: Short, R. A., "The Attainment of Reliable Digital Systems Through the Use of Redundancy---A Survey," IEEE Comp. Group News, March 1968, pp. 2--17.
• 26: Von Neumann, J., "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components," in Automata Studies, Annals of Math. No. 34, Princeton Univ. Press, 1956, pp. 43--98.
• 27: S. S. Yau , R. C. Cheung, Design of self-checking software, Proceedings of the international conference on Reliable software, p.450-455, April 21-23, 1975, Los Angeles, California