No abstract available.

A distributed algorithm is described for detecting and diagnosing faulty processors in an arbitrary network. Fault free processors perform simple periodic tests on one another; when a fault is detected or a newly repaired processor joins the network, this new information is disseminated in parallel throughout the network. It is formally proven that the algorithm is correct, and it is also shown that the algorithm is optimal in terms of the time required for all of the fault free processors in the network to learn of a new event. Simulation results are given for arbitrary network topologies.>

In an approach recently proposed for the yield enhancement of programmable gate arrays (PGA's), an initial placement of a circuit is first obtained using a standard technique such as simulated annealing on a defect-free PGA. In the next step, this placement is reconfigured so that the circuit is mapped onto the defect-free portion of a defective PGA chip with the same architecture. We first formulate the reconfiguration aspect of this approach as a problem of shifting pebbles on a graph. We present efficient reconfiguration algorithms for this pebble shift problem. Using these algorithms as heuristics, we develop a yield enhancement system not only for PGA's, but also for programmable Wafer Scare Integrated (WSI) processor arrays. We evaluate the heuristic algorithms using the measures of routability and total wire length of the reconfigured placement of the circuit. Based on this evaluation, we establish proper reconfiguration strategies.>

The diagnosability and diagnosis problems for a model introduced by J. Maeng and M. Malek (1981) of a self-diagnosable multiprocessor system where processors compare the results of tasks performed by other processors in the system are analyzed. A set of criteria is given for determining whether the faulty processors in the system can be diagnosed on the basis of the comparisons, and a polynomial-time algorithm is presented to identify the faulty units of such a system on the basis of the comparison results when the system is known to be diagnosable.>

Automatic generation of conformance test sequences for communication protocols by means of unique input/output (UIO) sequences is addressed. It is shown that if multiple minimum-length UIO sequences are computed for each state of the finite-state-machine (FSM) specification, then the length of the resulting test sequence is significantly reduced without an appreciable increase in the time needed to compute the sequence. An algorithm for assignment of the multiple UIO sequences is given. This algorithm, which is based on network flow, is polynomial in the number of states and transitions of the FSM and is effective in reducing the overall length of the test sequence.>

The problem of determining whether a redundant random-access memory (RRAM) containing faulty memory cells can be repaired with spare rows and columns is discussed. The approach is to increase the number of working RRAMs manufactured per unit time, rather than per wafer, by presenting a computationally efficient algorithm for detecting unrepairability, a computationally efficient algorithm for optimal repair for special patterns of faulty memory cells and online algorithms that can find an optimal repair or else detect unrepairability during memory testing, aborting unnecessary testing. Experimental validation of the approach is given that is based on industrial device fabrication data.>

A method for generating test sequences for checking the conformance of a protocol implementation to its specification is described. A rural Chinese postman tour problem algorithm is used to determine a minimum-cost tour of the transition graph of a finite-state machine. It is shown that, when the unique input/output sequence (UIO) is used in place of the more cumbersome distinguishing sequence, both the controllability and observability problems of the protocol testing problem are addressed, providing an efficient method for computing a test sequence for protocol conformance testing.>

The four major methods of conformance test generation reported in the literature are reviewed: transition tours; distinguishing sequences; characterizing sequences; and unique input/output sequences. These methods are used to test the control portion of a protocol specification. The conformance testing concepts developed in the standards world are summarized. Their relationship with the four formal methods is discussed.>

Programmable gate arrays (PGAs) offer a convenient means of prototyping complex logic. An approach is presented for enhancing the yield of PGAs through defect tolerance. This serves two purposes: to make the product economical, as well as to help reduce the turnaround time. The approach is based on using programmable interconnect to test the logic in the PGA and to use adaptive customization to avoid the defective portions. The ideas are illustrated through the use of a novel PGA architecture. Heuristics for adaptive customization of the PGAs are given and their effectiveness is studied through yield analysis. The results of the study for a sample circuit are included.>

A test sequence is given for the test access port (TAP) controller portion of the boundary-scan architecture proposed by the Joint Test Action Group (JTAG) and IEEE Working Group P1149.1 as an industry-standard design-for-testability technique. The resulting test sequence, generated by using a technique based on Rural Chinese Postman tours and unique input/output sequences, is of minimum cost (time) and rigorously tests the specified functional behavior of the controller. The test sequence can be used for detecting design faults for conformance testing or for detecting manufacture-time/run-time defects/faults.>

A technique for detecting and diagnosing faults at the processor level in a multiprocessor system is described. A process is assigned whenever possible to two processors: the processor to which it would normally be assigned (primarily) and an additional processor that would otherwise be idle (secondary). Two strategies are described and analyzed: one that is preemptive and another that is nonpreemptive. It is shown that, for moderately loaded systems, a sufficient percentage of processes can be performed redundantly using the system's spare capacity to provide a basis for fault detection and diagnosis with virtually no degradation of response time. A multiprocessor that uses the approach for detecting faults at the processor loads is described.>

A description is given of an experience in estimating fault coverage of a test sequence designed to test the control portion of a protocol. The control portion of this protocol is modeled as a finite-state machine. This study uses Monte Carlo simulation and introduces a novel notion of machine equivalence. An algorithm given checks for this notion of machine equivalence.>

A technique is described for detecting and diagnosing faults at the processor level in a multiprocessor system. In this method, a process is assigned whenever possible to two processors: the processor that it would normally be assigned to (primary) and an additional processor which would otherwise be idle (secondary). Two strategies will be described and analyzed: one which is preemptive and another which is non-preemptive. It is shown that for moderately loaded systems, a sufficient percentage of processes can be performed redundantly using the system's spare capacity to provide a basis for fault detection and diagnosis with virtually no degradation of response time.

In this correspondence a system-level, comparison-based strategy for identifying faulty processors in a multiprocessor system is described. Unlike other strategies which have been proposed in the literature, the comparison approach is more efficient and relies on more realistic assumptions about the system under consideration. The new strategy is shown to correctly identify the set of faulty processors with a remarkably high probability, making it an attractive and viable addition or alternative to present fault diagnosis techniques.

An O(n3) algorithm is given for determining the most likely set of faulty processors in a class of systems introduced by Maheshwari and Hakimi[6], known as probabilistically diagnosable systems. The technique uses the a priori probability of failure of each unit combined with the results of tests which the processors administer to one another to perform diagnosis. The algorithm uses well-known results on network flow and minimum weight vertex cover sets.

In the literature on diagnosable multiprocessor systems, regular testing structures which isolate up to t1 faulty processors to within a set of t1 processors have been studied. These structures are called D(n, t0, X) systems and are said to be t1/t1-diagnosable. In this correspondence, the problem of designing regular testing structures which isolate the largest number of faulty processors is shown to be equivalent to determining full-difference triangles. These triangles have been used to design error-correcting convolutional codes and transmission systems without third-order intermodulation interference, and have been studied extensively. Recognizing this relationship allows results from these areas to be applied directly to the design of diagnosable systems. A list of the best-known systems is given.

A novel procedure presented here generates test sequences for checking the conformity of protocol implementations to their specifications. The test sequences generated by this procedure only detect the presence of many faults, but they do not locate the faults. It can always detect the problem in an implementation with a single fault.

In this paper, a new class of diagnosable systems, called tp-self-implicating systems, which is a special case of the well-known tp-diagnosable systems introduced by Preparata et al. [1], is described. If there are no more than tp faulty units and the faults are assumed to be permanent, then the faulty units in a tp-self-implicating system can always be identified using at least one of two straight forward criteria associated with test outcomes. In each case, the given faulty unit in effect implicates itself as faulty. Necessary and sufficient conditions are given on the structures of PMC models for self-implication. Finally, an algorithm for identifying the set of faulty units in a tp-self-implicating system is given which is linear in the number of tests in the system, rendering it more efficient than the most efficient known algorithm for the general class of tp-diagnosable systems.

Consider a system composed of n independent processors, each of which tests a subset of the others. It is assumed that at most tp of these processors are permanently faulty and that the outcome of a test is reliable if and only if the processor which performed the test is fault free. Such a system is said to be tp-diagnosable if, given any complete collection of test results, the set of faulty processors can be uniquely identified. In this paper, it is shown that tp-diagnosable systems, due to their robust interconnection structure, possess heretofore unknown graph theoretic properties relative to vertex cover sets and maximum matchings. An 0(n2.5) algorithm is given which exploits these properties to identify the set of faulty processors in a tp-diagnosable system. The algorithm is shown to be correct, complete, not based on any conjecture, and superior to any other known fault identification algorithm for the general class of tp-diagnosable systems.

For hybrid fault situations (that is, bounded combinations of permanent and intermittent faults) in a classical PMC diagnosable system [1], the identification of faulty units has heretofore required that testing be patiently and perhaps unrealistically repeated until the test results obtained are consistent with permanent fault situations. As a consequence, intermediate test results go unused. Moreover, the occurrence of test results consistent with permanent fault situations will, in generaL, be a rare event.

Multiple-unit computer systems which are to be tolerant of intermittently faulty units or transiently upset units are considered in this paper. Designs for such systems, which exploit a new so-called greedy diagnosis theory, are developed. Using greedy diagnosis, assessments on the condition of a unit (intermittent-fault case) or the integrity of data (transient-upset case) can be made on the basis of syndromes formed from comparisons of the results of jobs performed by pairs of units. Greedy diagnosis avoids the requirement that for such syndromes to be useful, they must be interpretable from a permanent-fault/continuous-upset perspective.