Research On The Critical Path Tracing Method

Testing is an important and necessary part for research and development of very large scale integration(VLSI). With the rapid development of VLSI, the scale and density of circuits increase quickly. It makes VLSI testing more difficult. The consequence is that the cost of testing a chip has become the fundamental part of the overall cost of the chip. To decrease testing cost, highly efficient testing methods are pressingly needed.Two main aspects in VLSI testing, fault simulation and test generation, are researched in this dissertation. Based on the method of critical path tracing, a set of effective strategies and accelerated techniques, and two algorithms, one for fault simulation and another for test generation, are proposed.In fault simulation, the most difficult problem — fanout stem fault simulation is coped with. To speed up fault simulation, static analysis and dynamic calculations are all considered. In static analysis on circuit structure, as little time as possible is spent in obtaining as more information as possible about the feature of circuits. In the process of fault simulation, a set of dynamic accelerated techniques are used to reduce a lot of repeated and useless calculations. The close combination of dynamic calculations with the results from static analysis makes the roles of all the accelerated techniques be brought into full play. By using these techniques, the number of the stems needed to perform explicit fault simulation and the number of active events in fault effect propagation are greatly decreased, the regions of explicit fault simulation and the regions of critical path tracing are reduced, too, and fault effect propagation can be finished as early as possible. All of these results lead to the acceleration of fault simulation. ISCAS'85 10 benchmark combinational circuits are experimented. The accelerated parallel pattern critical path tracing(APPCPT) algorithm, based on the static and dynamic accelerated techniques, obtains high performance for both small and large numbers of test patterns. Especially with the increase of circuit gates, its effectiveness improves rapidly.In test generation, three key problems are considered in particular. First, in general strategies of the algorithm, four search strategies are put forward to simplify the computing complexity, to increase the ability of a test detecting new faults, and to raise fault coverage of a test set. Second, to speed up the determination of stem criticality and to increase new critical paths as more as possible without adding the computing complexity, several effective methods are presented. Third, in the process of test generation, a set of dynamic accelerated techniques are proposed to reduce the number of backtracks, to avoid a lot of repeated and useless calculations, and to enhance the ability of a test detecting more faults. The algorithm of critical path tracing test generation (CPTTG), presented in this dissertation, obtains higher fault coverage, smaller test set and shorter CPU time for ISCAS'85 10 benchmark combinational circuits.