We propose a method to estimate fault efficiency of test patterns for path delay faults. In path delay fault testing, fault coverage of test patterns is usually very low, because circuits have not only a lot of paths but also a lot of untestable paths. Although fault efficiency would be better metric to evaluate test patterns rather than fault coverage, it is too difficult to compute it exactly, if we do not compute the total number of untestable paths exactly. The proposed method samples a part of paths after untestable path analysis, and estimate fault efficiency based on the percentage of untestable paths in the sample paths. Through our experimental results, we show that the proposed method can accurately estimate fault efficiency of test patterns in a reasonable time. Also, since the accuracy of fault efficiency estimated with the proposed method depends on how to sample the paths, we look into the influence of path sampling methods to the accuracy in the experiments.

The multichannel switch is an architecture widely used for ATM (Asynchronous Transfer Mode). It is known that the fault tolerant characteristic can be incorporated in into the multichannel crossbar switching fabric. For example, if a link belonging to a multichannel group fails, the remaining links can assume responsibility for some of the traffic on the failed link. On the other hand, if a fault occurs in a switching element, it can lead to erroneous routing and sequencing in the multichannel switch. We investigate several fault localization algorithms in multichannel crossbar ATM switches with a view to early fault recovery. The optimal algorithm gives the best performance in terms of time to localization but is computationally complex, which makes it difficult to operate in real time. We develop an online algorithm which is computationally more efficient than the optimal one. We evaluate its performance through simulation. The simulation results show that the performance of the online algorithm is only slightly suboptimal for both random and bursty traffic. There are cases where the proposed online algorithm cannot pinpoint down to a single fault. We explain the causes and enumerate those cases. Finally, a fault recovery algorithm is described which utilizes the information provided by the fault localization algorithm. The fault recovery algorithm adds extra rows and columns to allow cells to detour the faulty element.

Zero-suppressed BDDs (ZBDDs) have been used in the nonenumerative path delay fault (PDF) grading of VLSI circuits. One basic and one cut-based grading algorithm are proposed to grade circuits with polynomial and exponential number of PDFs, respectively. In this article, we present a new ZBDD-based basic PDF grading algorithm to enable grading of some circuits with exponential number of PDFs without using the cut-based algorithm. The algorithm overcomes the memory overflow problems by dynamically pruning the ZBDD at run-time. This new algorithm may give exact or pessimistic coverage depending on the statuses of the pruned nodes. Furthermore, we re-assess the performance of the static variable ordering heuristics in ZBDDs for PDF coverage calculation. The proposed algorithm combined with the efficient static variable ordering heuristics can avoid ZBDD size explosion in many circuits. Experimental results for ISCAS85 benchmarks show that the proposed algorithm efficiently grades circuits.

A rotator graph was proposed as a topology for interconnection networks of parallel computers, and it is promising because of its small diameter and small degree. However, a rotator graph is a directed graph that sometimes behaves harmfully when it is applied to actual problems. A bi-rotator graph is obtained by making each edge of a rotator graph bi-directional. In a bi-rotator graph, average distance is improved against a rotator graph with the same number of nodes. In this paper, we give an algorithm for the container problem in bi-rotator graphs with its evaluation results. The solution achieves some fault tolerance such as file distribution based information dispersal technique. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into two cases according to the position of the destination node. The time complexity of the algorithm and the maximum length of paths obtained are estimated to be O(n3) and 4n-5, respectively. Average performance of the algorithm is also evaluated by computer experiments.

According to the proliferation of ubiquitous computing, various products which contain large-size embedded software have been developed. One of most typical features of embedded software is concurrency of software and hardware factors. That is, software has connected deeply into hardware devices. The existence of various hardware make quality assurance of embedded software more difficult. In order to assure quality of embedded software more effectively, this paper discusses features of embedded software and an effective method for quality assurance for embedded software. In this paper, we first analyze a failure distribution of embedded software and discuss the effects of hardware devices on quality of embedded software. Currently, in order to reduce hardware related faults, huge effort for testing with large number of test items is required. Thus, one of the most important issues for quality assurance of embedded software is how to reduce the cost and effort of software testing. Next, focusing on hardware constraints as well as software specifications in embedded software, we propose an evaluation metrics for determinating important functions for quality of embedded software. Furthermore, by referring to the metrics, undesirable behaviors of important functions are identified as root nodes of fault tree analysis. From the result of case study applying the proposed method to actual project data, we confirmed that test items considering the property of embedded software are constructed. We also confirmed that the constructed test items are appropriate to detect hardware related faults in embedded systems.

To guarantee the high reliability of video services, video servers usually adopt parity-encoding techniques in which data blocks and their associated parity blocks form a parity group. For real-time video service, all the blocks in a parity group are prefetched in order to cope with a possible disk failure, thereby incurring a buffering overhead. In this paper, we propose a new scheme called Round-level Parity Grouping (RPG) to reduce the buffer overhead while restoring VBR video streams in the presence of a faulty disk. RPG allows variable parity group sizes so that the exact amount of data is retrieved during each round. Based on RPG, we have developed a storage allocation algorithm for effective buffer management. Experimental results show that our proposed scheme reduces the buffer requirement by 20% to 25%.

Built-in self-test (BIST) hardware is included today in many chips. This hardware is used to test the chip's functional circuits. Since this BIST hardware is manufactured using the same technology as the functional circuits themselves, it is possible for it to be faulty. It is important, therefore, to assess the impact of this unreliable BIST on the product defect level after test. Williams and Brown's formula, relating the product defect level as a function of the manufacturing yield and fault coverage, is re-examined in this paper. In particular, special attention is given to the influence of an unreliable BIST on this relationship. We show that when the BIST hardware is used to screen the functional product, an unreliable BIST circuitry tends, in many cases, to reduce the effective fault coverage and increase the corresponding product defect level. The BIST unreliability impact is assessed for both early life phase, and product maturity phase.

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate a self-stabilizing distributed approximation for the minimum k-dominating set (KDS) problem in general networks. The minimum KDS problem is a generalization of the well-known dominating set problem in graph theory. For a graph G = (V,E), a set Dk V is a KDS of G if and only if each vertex not in Dk is adjacent to at least k vertices in Dk. The approximation ratio of our algorithm is , where Δ is the maximum degree of G, in the networks of which the minimum degree is more than or equal to k.

This paper presents a novel approach to improving the IDDQ-based diagnosability of a CMOS circuit by dividing the circuit into independent partitions and using a separate power supply for each partition. This technique makes it possible to implement multiple IDDQ measurement points, resulting in improved IDDQ-based diagnosability. The paper formalizes the problem of partitioning a circuit for this purpose and proposes optimal and heuristic based solutions. The effectiveness of the proposed approach is demonstrated through experimental results.

A diagnosis technique is presented to locate at least one fault in a scan chain with multiple timing faults. This diagnosis technique applies Single Excitation (SE) patterns of which only one bit can be flipped even in the presence of multiple faults. By applying the SE patterns, the problem of simulations with unknown values is eliminated. The diagnosis result is therefore deterministic, not probabilistic. Experiments on the ISCAS benchmark circuits show that the average diagnosis resolution is less than ten scan cells.

This paper proves that for every positive integers n,k and any positive number ε, we can explicitly construct a DAG G with n+O(k1+ε) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n,k and any positive number ε, we can explicitly construct a graph H with n+O(k2+ε) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.

This paper proposes an efficient methodology of delay fault testing of processor cores using their instruction sets. These test vectors can be applied in the functional mode of operation, hence, self-testing of processor core becomes possible for path delay fault testing. The proposed approach uses a graph theoretic model (represented as an Instruction Execution Graph) of the datapath and a finite state machine model of the controller for the elimination of functionally untestable paths at the early stage without looking into the circuit details and extraction of constraints for the paths that can potentially be tested. Parwan and DLX processors are used to demonstrate the effectiveness of our method.

The Mobius cube MQn proposed by Cull et al. is an alternative to the popular hypercube network. Recently, MQn was shown to be pancyclic, i.e., cycles of any lengths at least four can be embedded into it. Due to the importance of the fault tolerance in the parallel processing area, in this paper, we study an injured MQn with mixed node and link faults. We show that it is (n - 2)-fault-tolerant pancyclic for n 3, that is, an injured n-dimensional MQn is still pancyclic with up to (n - 2) faults. Furthermore, our result is optimal.

Δ-Timed Atomic Broadcast is the broadcast ensuring that all correct processes deliver the same messages in the same order, and that delivery latency of any message broadcast by any correct process is some predetermined time Δ or less. In this paper, we propose a Δ-timed atomic broadcast algorithm in a synchronous system where communication delay is bounded by a known constant d and processes suffer both crash faults and timing faults. The proposed algorithm can tolerate fc crash faults and ft timing faults as long as at least ft + 1 processes are correct, and its maximum delivery latency Δ is (2f' + 7)d where f' is the actual number of (crash or timing) faulty processes. That is, the algorithm attains the early-delivery in the sense that its delivery latency depends on the actual number of faults rather than the maximum number of faults that the algorithm can tolerate. Moreover, the algorithm has a distinct advantage of guaranteeing that timing-faulty processes also deliver the same messages in the same order as the correct processes (Uniformity). We also investigate the maximum number of faulty processes that can be tolerated. We show that no Δ-timed atomic broadcast algorithm can tolerate ft timing faults, if at most ft processes are correct. The impossibility result implies that the proposed algorithm achieves the maximum fault-resilience with respect to the number of faulty processes.

We describe a new inconsistent case which is susceptible to occur while producing consistent answer set using prioritized default logic. We define new semantics for prioritized default logic in order to solve this problem. There is a sign difference between General and Extended logic programs. Extended logic programs are formulated using classical negation, For this reason, an inconsistent answer set can sometimes be produced. For the most part, default reasoning semantics successfully resolved this problem, but a conflict could still arise in one particular case. The purpose of this paper is to present this eventuality, and revise the semantics of default logic in order to give an answer to this problem.

In this paper, usage of undefined states on a State Transition Graph (STG) is addressed to obtain high fault coverage, in the area of Synthesis For Testability (SFT) of synchronous sequential circuits. Basically, a given STG could be modified by adding undefined states and distinguishable transitions so that each state might be included in one strongly-connected component as much as possible. Such modification decreases the number of redundant faults caused by the existence of unreachable states on an STG. For the modification, we propose two algorithms for both incompletely-specified STGs and completely-specified STGs, respectively. In case of incompletely-specified STGs, undefined states are added using unspecified transitions of defined states. In case of completely-specified STGs, undefined states are added by changing transitions specified on an STG while preserving state equivalence. Experimental results with MCNC benchmarks show that the number of redundant faults of gate-level circuits synthesized by our modified STGs are reduced, resulting in high fault coverage as well as short test generation time

This paper presents a non-scan design scheme to enhance delay fault testability of controllers. In this scheme, we utilize a given state transition graph (STG) to test delay faults in its synthesized controller. The original behavior of the STG is used during test application. For faults that cannot be detected by using the original behavior, we design an extra logic, called an invalid test state and transition generator, to make those faults detectable. Our scheme allows achieving short test application time and at-speed testing. We show the effectiveness of our method by experiments.

A large memory is typically designed with multiple identical memory blocks for reducing delay and power. The circuit verification of individual memory blocks can be effectively handled by the Symbolic Trajectory Evaluation (STE) approach. However, if multiple memory blocks are integrated into a single system, the STE approach cannot verify it economically. This paper introduces algorithms for verifying block-level connectivity of memories. The verification time of a large memory can be reduced drastically by using bottom-up verification scheme. That is, a memory block is first verified thoroughly, and then only the interconnection between memory blocks of the large memory needs to be verified. The proposed verification algorithms require (3n+2(log2n+1)+3log2m) Read/Write operations for a 2nm-bit memory, where n and m are the address width and data width, respectively. Also, the algorithms can verify 100% of the inter-port and intra-port signal misplaced faults of the address, data input, and data output ports.

Replication to mask the effects of failures is a basic technique for improving reliability of a file system. Consistency control protocols are implemented to ensure the consistency among these replicas. The native token-based mechanism which merely sequences the distributed requests suffered from the poor system utilization due to the lack of dependence checking between writes and management of out-of-ordered requests. Hence, in this paper, by utilizing the idempotent property of NFS and executing ahead most of independent WRITE requests, the new consistency control scheme is proposed to improve the performance of operations and failure recovery. Finally, a numeric case shows the efficiency of the new scheme.

We present a built-in self-reconfiguring system for a mesh-connected processor array where faulty processor elements are compensated for by spare processing elements located in one row and one column. It has advantages in that the number of spare processing elements is small and additional control circuits and networks for changing interconnections of processing elements is so simple that hardware overhead for reconfiguration is also small. First, to indicate the motivation to the proposed reconfiguration scheme, we briefly describe other schemes with the same number of spares as that of the proposed scheme where faulty processing elements are replaced using straight shifts toward spares, and compare their reconfiguration probabilities to each other. Then, we show that a variant of the proposed scheme has the highest probability. Next, we present a built-in self-reconfiguring system for the scheme and formally prove that it works correctly. It can automatically replace faulty processors by spare processors on detecting faults of processors.