CAD Tool for Test Generation in Distributed Computing Environment

Abstract

The work done here is inspired by the emergence of high performance, massively parallel computers and distributed computing environments, which demands the development of new parallel and distributed algoritms to take advantage of these technologies. Many complex problems can be solved efficiently by massive parallelism. On the other hand, Advancements in integrated circuit (1C) technology have made it possible to fabricate digital circuits with a very large number of devices on a single chip. IC technology namely, Very Large Scale Integration (VLSI) involves the fabrication of millions of components and interconnections on a chip. The main advantages of VLSI are reduced system cost, improved performance, and high reliability. These advantages would be lost until the chips are economically tested. The availability of affordable parallel machines and distributed network of idle workstations in most of the design and test environments has prompted us for the development of efficient parallel and distributed algorithms for the compute-intensive test generation problem. Test generation is known to be hard i.e. NP-complete problem. While the test generation for purely combinational circuit is challanging due to the high circuit complexity of VLSI circuits, thus, there exists a critical need to develop efficient test generation algorithms that can handle VLSI chips at a resonable computing cost and provide high fault coverage. , Literature review of the existing approaches for test generation has been done. The approaches have been classified into conventional and unconventional ones. The conventional test generation approaches for combinational circuits are reviewed. The most successful combinational test generation algorithms are found to be mainly based upon two steps: First, create a change at the fault-site and second, search for consistent value on all signal lines in the circuit such that the fault-effect is successfully propagated to at least one of its primary output (PO). This is called the Path Sensitization approach. Most of the work done by researchers is on Stuck-at fault models; we found that 95% fault coverage was through stuck-at fault models. Then no body took concentration on rest 5% fault. That faults was due to delay, memory, register problems. But with in change in time, researchers took these 5% faults i.e. Delay Faults under consideration. They added lot of research on this area. These delays are not due to logical problem of input-output but due to presence of hazards (static as well as dynamic hazards), delay defects like . GOS defects • Resistive shorting defects between nodes and to the supply rails etc. Due to pressence of these delay faults, there was always performance degradation. Researchers proposed different-2 techniques, approaches methods to solve these delay faults. These delay faults are categorised as Path, Gate, Transition, Line, Segment, and Functional delays. In this thesis we are focussing on Path delay faults. Various approaches, methods used to solve path delay fault problem are described fully in literature review. We are using here, Algebra for test generation of these delay faults. In this thesis, we are focussing on ten-valued logic for robust tests and three-valued logic for non-robust tests. From the earlier research as mentioned in literature, by using sequential algorithm for path delay faults, we are not gaining efficient results. CPU utlization and memory consumption is coming high. To cop this problem, several parallelization techniques for test generation problem have been investigated in the past. These techniques have been tried to parallelize some of the portions of the conventional uniprocessor algorithms and execute them in parallel. Although these techniques have shown some promising results, but much work remains in this direction since no effective parallel or distributed system has yet been found. The thesis addresses to develop efficient parallel and distributed algorithms for the test generation problem. The scope of this work is limited only to combinational circuits. Here in this thesis, we develop a parallel algorithm for test generation of path delay faults using IO-valued logic for robust tests and 3-valued logic for non-robust tests using master-slave approach in parallel and distributed environment (PVM) on LINUX platform. We have successfully tested the prototype of the proposed solution for different ISCAS'85 benchmark circuits as well as some example circuits. The experimental results are encouraging. The plots of computational time vs number of processors, speedup vs.number of processors and the computation time vs. no. of tested paths are shown. Average CPU time is coming low and memory utlization is less, speed-up is increasing as the no. of processors increases. These results clearly demonstrate the effectiveness of the proposed algorithm.