Tradeoffs in system level diagnosis of multiprocessor systems

ABSTRACT

The development of LSI technology makes it possible to partition a system into replaceable modules, and the advent of low-cost microprocessors makes possible networks of hundreds (or more) of interconnected modules. The problem of repairing such a system is becoming a matter of major importance in digital systems.

In this paper a new procedure for defining an optimal design with respect to cost of repair for a system consisting of replaceable modules (processors) is introduced. Also the tradeoff between the number of repetitions of the diagnostic test (speed of diagnosis), the number of testing links in the system (complexity), and the number of replaced fault-free modules (accuracy) is considered.

In an early paper, Preparata, Metze, and Chien⁴ formulated a model of system level diagnosis and defined two types of diagnosability measures, i.e. one-step t-fault diagnosability, and sequential t-fault diagnosability. They proved that D_δt is one-step t-fault diagnosable and single loop connection is sequentially t-fault diagnosable. Friedman¹² later generalized this measure to one-step t-out-of-S (t/S) diagnosability, in which t faults are diagnosed to within S ≥ t modules. This introduces the possibility of inexact diagnosis---i.e. such that some fault-free modules may have to be replaced in order to repair a system in one step.

So far most of the results that are available are only for single-loop or D_δt design, and the results for a system in between these two extreme cases are not available. A D_δt system needs more testing links and a single-loop system needs more steps in order to be repaired. In this paper we have defined a design in between D_δt and single-loop systems; also the tradeoff between the number of repetitions of the diagnostic test (speed of diagnosis), the number of testing links (complexity), and the number of replaced fault-free modules (accuracy) is considered, and the optimal design with respect to cost of repair is defined.

REFERENCES

• 1: R. E. Forbes , D. H. Rutherford , C. B. Stieglitz , L. H. Tung, A self-diagnosable computer, Proceedings of the November 30--December 1, 1965, fall joint computer conference, part I, November 30-December 01, 1965, Las Vegas, Nevada [doi>10.1145/1463891.1464010]
• 2: Agnew, P. W., D. H. Rutherford, R. J. Suhocki, C. M. Yen, and D. E. Muller. "An Architectural Study for a Self-Repairing Computer." U.S. Space Systems Division, Final Tech. Doc. Rept. SSD-TR-65-159, AD47976, November 1965.
• 3: C. V. Ramamoorthy, A structural theory of machine diagnosis, Proceedings of the April 18-20, 1967, spring joint computer conference, April 18-20, 1967, Atlantic City, New Jersey [doi>10.1145/1465482.1465603]
• 4: Preparata, F. P., G. Metze, and R. T. Chien. "On the Connection Assignment Problem of Diagnosable System." IEEE Transactions on Electronic Computers, EC-16, (1967), pp. 848--854.
• 5: Preparata, F. P. "Some Results on Sequentially Diagnosable Systems." Proceedings Hawaii International Conference System Science, University of Hawaii Press, 1968, pp. 623--626.
• 6: Seshagiri, N. "Completely Self-Diagnosable Digital System." International Journal of Systems Science, 1 (1971), pp. 235--246.
• 7: S. L. Hakimi , A. T. Amin, Characterization of Connection Assignment of Diagnosable Systems, IEEE Transactions on Computers, v.23 n.1, p.86-88, January 1974 [doi>10.1109/T-C.1974.223782]
• 8: C. R. Kime, An Analysis Model for Digital System Diagnosis, IEEE Transactions on Computers, v.19 n.11, p.1063-1073, November 1970 [doi>10.1109/T-C.1970.222833]
• 9: J. D. Russell , C. R. Kime, System Fault Diagnosis: Masking, Exposure, and Diagnosability Without Repair, IEEE Transactions on Computers, v.24 n.12, p.1155-1161, December 1975 [doi>10.1109/T-C.1975.224158]
• 10: J. D. Russell , C. R. Kime, System Fault Diagnosis: Closure and Diagnosability with Repair, IEEE Transactions on Computers, v.24 n.11, p.1078-1089, November 1975 [doi>10.1109/T-C.1975.224136]
• 11: Adham, M., and A. D. Friedman. "Digital System Fault Diagnosis." Journal of Design Automation and Fault-Tolerant Computing, 1 (1977), pp. 115--132.
• 12: Friedman, A. D. "A New Measure of Digital System Fault Diagnosis." Digest 1975 International Symposium Fault-Tolerant Computing. IEEE Computer Society Publications, 1975, pp. 167--170.
• 13: Karunanithi, S., and A. D. Friedman. "System Diagnosis with t/S Diagnosability." Digest 1977 International Symposium Fault-Tolerant Computing. IEEE Computer Society Publications, 1977, pp. 65--71.
• 14: Kavianpour, A., and A. D. Friedman. "Design of Easily Diagnosable System." Third USA-JAPAN Computer Conference, 1978, San Francisco.
• 15: Kavianpour, A. "Diagnosis of Digital System using t/S Measure." Doctoral dissertation, University of Southern California, Los Angeles, June 1978.
• 16: Kavianpour, A., and A. D. Friedman. "Different Diagnostic Models for Multiprocessor System." 8th World Computer Congress, IFIP, October 1980.