Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2000-03-22
2004-02-10
Iqbal, Nadeem (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S026000, C714S046000, C714S057000
Reexamination Certificate
active
06691249
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to monitoring, detecting, and isolating failures in a system, and in particular to tools applied for analyzing the system.
“To diagnose” means to determine why a malfunctioning device is behaving incorrectly. More formally, to diagnose is to select a subset of a predetermined set of causes responsible for the incorrect behavior. A diagnosis must both explain the incorrect behavior and optimize some objective function, such as probability of correctness or cost of incorrect diagnosis. The need to diagnose is a common reason to measure or to test.
The diagnosis of an engineered device for the purpose of repair or process improvement shall now be regarded. This is in contrast to, say, a distributed computer system containing software objects that may be created or destroyed at any time. It is assumed that the device consists of a finite number of replaceable components. Failures of the device are caused only by having one or more bad components. What shall be called herein “diagnosis” is often called “fault identification”. When presented with a failed device, a technician or a computer program (sometimes called a “test executive”) will run one or more tests. A technician familiar with the internal workings of a failing device must interpret the test results to identify the bad components.
Expert systems have been used for diagnosing computer failures, as described e.g. by J. A. Kavicky and G. D. Kraft in “An expert system for diagnosing and maintaining the AT&T 3B4000 computer: an architectural description”, ACM, 1989. Analysis of data from on-bus diagnosis hardware is described in Fitzgerald, G. L., “Enhance computer fault isolation with a history memory,” IEEE, 1980. Fault-tolerant computers have for many years been built with redundant processing and memory elements, data pathways, and built-in monitoring capabilities for determining when to switch off a failing unit and switch to a good, redundant unit (cf. e.g. U.S. Pat. No. 5,099,485).
Prior diagnostic systems for determining likely failed components in a system under test (SUT) include model-based diagnostic systems. A model-based diagnostic system may be defined as a diagnostic system that renders conclusions about the state of the SUT using actual SUT responses from applied tests and an appropriate model of correct or incorrect SUT behavior as inputs to the diagnostic system. Such a diagnostic system is usually based upon computer-generated models of the SUT and its components and the diagnostic process.
Model-based diagnostic systems are known e.g. from W. Hamscher, L. Console, J. de Kleer, in ‘
Readings in system model
-
based diagnosis
’, Morgan Kauffman, 1992. A test-based system model is used by the Hewlett-Packard HP Fault Detective (HPFD) and described in
HP Fault Detective User's Guide
, Hewlett-Packard Co., 1996.
U.S. Pat. No. 5,808,919 (Preist et al.) discloses a model-based diagnostic system, based on functional tests, in which the modeling burden is greatly reduced. The model disclosed in Preist et al. employs a list of functional tests, a list of components exercised by each functional test along with the degree to which each component is exercised by each functional test, and the historical or estimated a priori failure rate for individual components.
U.S. Pat. No. 5,922,079 (Booth et al.) discloses an automated analysis and troubleshooting system that identifies potential problems with the test suite (ability of the model to detect and discriminate among potential faults), and also identifies probable modeling errors based on incorrect diagnoses.
EP-A-887733 (Kanevsky et al.) discloses a model-based diagnostic system that provides automated tools that enable a selection of one or more next tests to apply to a device under test from among the tests not yet applied based upon a manageable model of the device under test.
In the above three model-based diagnostic systems, a diagnostic engine combines the system-model-based and probabilistic approaches to diagnostics. It takes the results of a suite of tests and computes—based on the system model of the SUT—the most likely to be failed components.
The diagnostic engine can be used with applications where a failing device is to be debugged using a pre-determined set of test and measurement equipment to perform tests from a pre-designed set of tests. Using test results received from actual tests executed on the SUT and the system model determined for the SUT, the diagnostic engine computes a list of fault candidates for the components of the SUT. Starting, e.g., from a priori (that is, formed or conceived beforehand) failure probabilities of the components, these probabilities may then be weighted with the model information accordingly if a test passes or fails. At least one test has to fail, otherwise the SUT is assumed to be good.
An embedded processor is a microprocessor or other digital computing circuit that is severely limited in computing power and/or memory size because it is embedded (i.e., built in to) another product. Examples of products typically containing embedded processors include automobiles, trucks, major home appliances, and server class computers (that often contain an embedded maintenance processor in addition to the Central Processing Unit(s)). Embedded processors typically have available several orders of magnitude less memory and an order of magnitude or two less computing power than a desktop personal computer. For example, a megabyte of memory would be a large amount for a home appliance. It is desirable to enable. such an embedded processor in such a product to diagnose failures of the product. A diagnosis engine providing such a capability shall be called an embedded diagnosis engine.
It is possible to perform probabilistic diagnosis by various heuristic methods, as applied by the aforementioned HP Fault Detective product or U.S. Pat. No. 5,808,919 (Preist et al.). Heuristics by nature trade off some accuracy for reduced computation time. However, the HP Fault Detective typically requires 4 to 8 megabytes of memory. This is can be a prohibitive amount for an embedded diagnosis engine.
Another method for solving the problem is Monte Carlo simulation. Although the Monte Carlo simulation method can be made arbitrarily accurate (by increasing the number of simulations), the simulation results must be stored in a database that the diagnosis engine later reads. It has been shown that, even when stored in a space-efficient binary format, this database requires 2-6 megabytes for typical applications. This is too much for an embedded application and would be a burden on a distributed application where the database might have to be uploaded on a computer network for each diagnosis.
A common way of building a probabilistic diagnostic system is to use a Bayesian network (cf. Finn V. Jensen: “Bayesian Networks”, Springer Verlag, 1997). A Bayesian network is a directed acyclic graph. Each node in the graph represents a random variable. An edge in the graph represents a probabilistic dependence between two random variables. A source (a node with no in-edges) is independent of all the other random variables and is tagged with its a priori probability. A non-source node is tagged with tables that give probabilities for the value of the node's random variable conditioned on all of the random variables upon which it is dependent.
The computation on Bayesian networks of most use in diagnosis is called belief revision. Suppose values of some of the random variables (in the context of herein, the results of some tests) are observed. A belief revision algorithm computes the most likely probabilities for all the unobserved random variables given the observed ones. Belief revision is NP-hard (cf. M. R. Garey and D. S. Johnson: “Computers and Intractability:
A guide to the theory of NP-completeness”, W.H. Freeman and Co., 1979), and so all known algorithms have a worst-case computation time exponential in the number of random variables in the graph.
Bayesian networks used for diagnosis are
Barford Lee A.
Smith David R.
Agilent Technologie,s Inc.
Bonura Timothy M
Iqbal Nadeem
LandOfFree
Probabilistic diagnosis, in particular for embedded and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Probabilistic diagnosis, in particular for embedded and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic diagnosis, in particular for embedded and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3321524