In this paper, we discuss problems in design and fault masking of multiple-valued cellular arrays where basic cells having simple switch functions are arranged iteratively. The stuck-at faults of switch cells are assumed to be fault models. First, we introduce a universal single-level array and derive the ratio of the number of single faults whose influence can be masked to the total number of single faults. Next, we propose a universal two-level array that outputs correct values even if single faults occur in it and derive the ratio of the number of double faults whose influence can be masked compared to the total number of double faults. By evaluating the universal single-level array and the universal two-level array from the viewpoints of design and fault masking, we show that the latter is superior to the former. Finally, we compare our universal two-level array with formerly presented arrays in order to demonstrate the advantages of our universal two-level array.

Synthesis tools are now extensively used in the VLSI circuit design process. They allow a much higher design productivity, but the designer often does not directly control the circuit structure. Thus, when circuits are dedicated to dependable applications, designers have difficulties in implementing manually the devices needed to obtain fault detection or tolerance capabilities. The ASYL-SdF System has been developed over the last few years in order to avoid this break in the design flow, and to facilitate the designer's work when dependability is targeted. This paper gives an overview of the resulting tool, its synthesis flow for fault detection and fault tolerance in Finite State Machines, its limitations and the current developments. Actual circuit implementation results are given in terms of area overheads, expected reliability and experimental fault detection coverage.

Multistage Interconnection Networks (MIN) with multiple outlets are networks which can support higher bandwidth than those of nonblocking networks by passing multiple packets to the same destination. Fault recovery mechanisms are proposed for two of such networks (TBSF/PBSF) with the best use of their inherent fault tolerant capability. With these mechanisms, on-the-fly fault recovery is possible for multiple faults on switching elements. For the link fault, the networks are reconfigured after fault diagnosis, and the network is available with some performance degradation. The bandwidth degradation under multiple faults on link/element is analyzed with both theoretical models and simulation. Through the analysis, F-PBSF shows high fault tolerance under high traffic load and low reliability by using 3 or more banyan networks.

Various reconfiguration schemes against faults of mesh-connected processor arrays have been proposed. As one of them, the mesh-connected processor arrays model based on single-track switches was proposed in [1]. The model has an advantage of its inherent simplicity of the routing hardware. Furthermore, the 2 track switch model [2] and the multiple track switch model [3] were proposed to enhance yields and reliabilities of arrays. However, in these models, Simplicity of the routing hardware is somewhat lost because multiple tracks are used for each row and column. In this paper, we present a builtin self-reconstruction approach for mesh-connected processor arrays which are partitioned into sub-arrays each using single-track switches. Spare PEs which are located on the boundaries of the sub-arrays compensate faulty PEs in these sub-arrays. First, we formulate a reconfigulation algorithm for partitioned mesh-arrays using a Hopfield-type neural network, and then its performance for reconfigulation in terms of survival rates and reliabilities of arrays and processing time are investigated by computer simulations. From the results, we can see that high reliabilites are achieved while processing time is a little and hardware overhead (links and switches) required for reconstruction is as same as that for the track switch model. Next, we present a hardware implementation of the neural algorithm so that a built-in self-reconfigurable scheme may be realized.

This paper proposes new algorithms for diagnosing (detection, identification and location) baseline multistage interconnection networks (MIN) as one of the basic units in a massively parallel system. This is accomplished in the presence of single and multiple faults under a new fault model. This model referred to as the geometric fault model, considers defective crossing connections which are located between adjacent stages, internally to the MIN (therefore, a fault corresponds to a physical bridge fault between two connections). It is shown that this type of fault affects the correct geometry of the network, thus requiring a different testing approach than previous methods. Initially, an algorithm which detects the presence of bridge faults (both in the single and multiple fault cases), is presented. For a single bridge fault, the proposed algorithm locates the fault except in an unique pathological case under which it is logically impossible to differentiate between two equivalent locations of the fault (however, the switching element affected by this fault is uniquely located). The proposed algorithm requires log2 N test vectors to diagnose the MIN as fault free (where N is the number of input lines to the MIN). For fully diagnosing a single bridge fault, this algorithm requires at most 2 log2 N tests and terminates when multiple bridge faults are detected. Subsequently, an algorithm which locates all bridge faults is given. The number of required test vectors is O(N). Fault location of each bridge fault is accomplished in terms of the two lines in the bridge and the numbers of the stages between which it occurs. Illustrative examples are given.

Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number Δ(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate Δ(t, H) for the hypercube and torus, which are well-known as important interconnection networks for multiprocessor systems. If we denote the hypercube and the square torus on N vertices by QN and DN respectively, we show, among others, that Δ(t, QN) = O(tN log(log N/t + log 2e)) for any t and N (t 2), and Δ(1, DN) = N/2 for N even.

In this paper, we study the following node-to-node and node-to-set routing problems in r-dimensional torus Trn with r 2 and n 4 nodes in each dimension: given at most 2r - 1 faulty nodes and non-faulty nodes s and t in Trn, find a fault-free path s t; and given at most 2r - k faulty nodes and non-faulty nodes s and t1,..., tk in Trn, find k fault-free node-disjoint paths s ti, 1 i k. We give an O(r2) time algorithm which finds a fault-free path s t of length at most d(Trn) + 1 for the node-to-node routing, where d(Trn) is the diameter of Trn. For node-to-set routing, we show an O(r3) time algorithm which finds k fault-free node-disjoint paths s ti, 1 i k, of length at most d(Trn) + 1. The upper bounds on the length of the found paths are optimal. From this, Rabin diameter of Trn is d(Trn) + 1.

The order of faults which are targeted for test-pattern generation affects both of the processing time for test generation and the number of generated test-patterns. This order is referred to as a test generation schedule. In this paper, we consider the effect of scheduling in test generation. We formulate the test generation scheduling problem which minimizes the cost of testing. We propose schedulings based on test-pattern generation time, dominating probability and dominated probability, and analyze the effect of these schedulings. In the analysis, we show that the total test-pattern generation time and the total number of test-patterns can be reduced by the scheduling according to the descending order of dominating probability prior to the ascending order of test-pattern generation. This is confirmed by the experiments using ISCAS'85 benchmark circuits. Further, in the experiments, we consider eight schedulings, and show that the scheduling according to the ascending order of dominated probability is the most effective of them.

A system based on application of Fuzzy Cognitive Map (FCM) to perform on-line fault diagnosis is presented. The diagnostic part of the system is composed of two diagnostic schemes. The first one (basic diagnostic algorithm) can be considered as a simple transition of Shiozaki's signed directed graph approach to FCM framework. The second one is an extended version of the basic diagnostic algorithm where an important concept, the temporal associative memories (TAM) recall of FCM, is adopted. In on-line application, self-generated fault FCM model generates predicted pattern sequence through the TAM recall process, which is compared with observed pattern sequence to declare the origin of fault. As the resultant diagnosis scheme takes short computation time, it can be used for on-line fault diagnosis of large and complex processes, and even for incipient fault diagnosis. In practical case, since real observed pattern sequence may be different from predicted one through the TAM recall owing to propagation delay between process variables, the time indexed fault FCM model incorporating delay time is proposed. The utility of the proposed system is illustrated in fault diagnosis of a tank-pipe system.

In this paper, we give an algorithm which, given a set F of at most n-k faulty nodes, and two sets S={s1, , sk} and T = {t1,, tk}, 1kn, of non-faulty nodes in n-dimensional hypercubes Hn, finds k fault-tree node disjoint paths sitje, where (j1, , Jk) is a permutation of (1, , k), of length at most n + k in O(kn log k) time. The result of this paper implies that n disjoint paths of length at most 2n for set-to-set node disjoint path problem in Hn can be found in O(n2 log n) time.

A directed graph G = (V,E) is called the n-rotator graph if V = {a1a2an|a1a2an is a permutation of 1,2,,n} and E = {(a1a2an,b1b2bn)| for some 2 i n, b1b2bn = a2aia1ai+1an}. We show that for any pair of distinct nodes in the n-rotator graph, we can construct n - 1 disjoint paths, each length < 2n, connecting the two nodes. We propose a nonadaptive fault-tolerant file transmission algorithm which uses these disjoint paths. Then the probabilistic analysis of its reliability is given.

In this paper, we give an algorithm which, given a set F of at most (n - 1) - k faulty nodes, and two sets S = {s1,..., sk} and T = {t1,..., tk}, 1 k n - 1, of nonfaulty nodes in n-dimensional star graphs Gn, finds k fault-free node disjoint paths si tji, where (j1,..., jk) is a permutation of (1,..., k), of length at most d(Gn) + 5 in O(kn) optimal time, where d(Gn) = 3(n-1)/2 is the diameter of Gn.

In this paper we analyze the reliability of a simple broadcasting scheme for hypercubes (HCCAST) with random faults. We prove that HCCAST (n) (HCCAST for the n-dimensional hypercube) can tolerate Θ(2n/n) random faulty nodes with a very high probability although it can tolerate only n - 1 faulty nodes in the worst case. By showing that most of the f-fault configurations of the n dimensional hypercube cannot make HCCAST (n) fail unless f is too large, we illustrate that hypercubes are inherently strong enough for tolerating random faults. For a realistic n, the reliability of HCCAST (n) is much better than that of the broadcasting algorithm described in [6] although the latter can asymptotically tolerate faulty links of a constant fraction of all the links. Finally, we compare the fault-tolerant performance of the two broadcasting schemes for n = 15, 16, 17, 18, 19, 20, and we find that for those practical valuse, HCCAST (n) is very reliable.

In order to ensure the reliability and safety of equipment installed in process lines, it is important that maintenance and management should make efficient use of machine diagnosis techniques. Machine diagnosis by means of acoustic signals has hitherto been beset with difficulty, but there is now a strong demand that new acoustic type diagnosis equipment (utilizing acoustic signals) be developed. In response to this demand, the authors recently conducted research on diagnosis of machine faults by means of the processing of acoustic signals. In this research they were able to develop new acoustic type machine diagnosis techniques, and, using these techniques, to develop acoustic diagnosis equipment for practical use.

CAMs (Content Addressable Memories) are functional memories which have functions such as word-parallel equivalence search, bilateral 1-bit data shifting between consecutive words, and word-parallel writing. Since CAMs can be integrated because of their regular structure, massively parallel CAM functions can be executed. Taking advantage of CAMs, Ishiura and Yajima have proposed a parallel fault simulation algorithm using a CAM. This algorithm, however, requires a large amount of CAM storage to simulate large-scale circuits. In this paper, we propose a new massively parallel fault simulation algorithm requiring less CAM storage, and compare it with Ishiura and Yajima's algorithm. Experimental results of the algorithm on CHARGE --the CAM-based hardware engine developed in our laboratory--are also reported.

A new high-performance fault-tolerant ATM switching network is proposed. This network contains the baseline network and has many redundant switching elements to enhance the fault tolerance and throughput of the conventional multistage interconnection networks. The presented routing algorithm is very simple and can support a very huge number of paths between each input-output pair. The paths can be used to route cells when internal cell contentions occur in switching elements. The redundant switching elements at the last stage offer two access points to the output ports to resolve the output conflict. Performance analysis and simulation results show that this network has better maximum throughput even for faulty conditions. Among various networks, it has the largest number of redundant paths, and the greatest unit node contribution and unit edge contribution.

An automatic transistor-level performance fault tracing method is proposed which is applicable to the case where only CAD layout data is available in the CAD-linked electron beam test system. The technique uses an integrated algorithm that combines a previously proposed transistor-level fault tracing algorithm and a successive circuit extraction from CAD layout data. An expansion of the algorithm to the fault tracing in a combined focused ion beam and electron beam test system which enables us to measure signals on the interconnections in the lower layers is also described. An application of the technique to a CMOS model layout with about 100 transistors shows its validity.

We present basic strategies for memory-restricted forgetting mechanisms of cases and propose a forgetting strategy which is a combination of the basic strategies. The effectivness of the proposed strategy for improving the performance of case-based reasoning systems is demonstrated through simulations in the electric power systems.

The integration of both real-time systems and fault-tolerant systems has been emerged as one of the greatest challenges of this decade. It is called a responsive system, which has the objective to optimeze both timeliness and reliability. The performance measure in responsive systems is responsiveness that tells how probable a system executes correctly on time with faults occurred. While there have been some achievements in communication protocols and specification, we believe that scheduling problems in responsive systems are not understood deeply and sufficiently, yet. In this paper, we discuss the scheduling problem in responsive systems. At first, we investigate the issues in the scheduling and propose the precise definition of the responsiveness. We also suggest a scheduling algorithm called Responsive Earliest Deadline First (REDF) for preemptive aperiodic tasks in a uniprocessor system. We show that REDF is optimal to obtain the maximum responsiveness, and the time complexity is analyzed to be (N 2N). By illustrating a contradictory example, it is shown that REDF can be enhanced if a constraint on tasks is released.

We study all-to-all broadcasting in hypercubes with randomly distributed Byzantine faults. We construct an efficient broadcasting scheme BC1-n-cube running on the n-dimensional hypercube (n-cube for short) in 2n rounds, where for communication by each node of the n-cube, only one of its links is used in each round. The scheme BC1-n-cube can tolerate (n-1)/2 Byzantine faults of nodes and/or links in the worst case. If there are exactly f Byzantine faulty nodes randomly distributed in the n-cabe, BC1-n-cube succeeds with a probability higher than 1(64nf/2n) n/2. In other words, if 1/(64nk) of all the nodes(i.e., 2n/(64nk) nodes) fail in Byzantine manner randomly in the n-cube, then the scheme succeeds with a probability higher than 1kn/2. We also consider the case where all nodes are faultless but links may fail randomly in the n-cube. Broadcasting by BC1-n-cube is successful with a probability hig her than 1kn/2 provided that not more than 1/(64(n1)k) of all the links in the n-cube fail in Byzantine manner randomly. For the case where only links may fail, we give another broadcasting scheme BC2-n-cube which runs in 2n2 rounds. Broadcasting by BC2-n-cube is successful with a high probability if the number of Byzantine faulty links randomly distributed in the n-cube is not more than a constant fraction of the total number of links. That is, it succeeds with a probability higher than 1nkn/2 if 1/(48k) of all the links in the n-cube fail randomly in Byzantine manner.