Research Of Parallel ATPG Algorithm And Prototype System Design

Test is an indispensable task of VLSI circuits design. With the increased complexity ofVLSI circuits, time overhead of ATPG has become a bottleneck of design. Parallel processing isa very cost-effective alternative fOr speeding up it. The content of this thesis just is parallelATPG algorithLms and it prototyPe system fOr non-scan synchIonous sequential circuits.At present, the portability of ATPG algorithm is the key of blocking its commercialization.So, we first propose a para11el ATPG prototype system framework based on message passingsystem PVM. Because of better portability of PVM, all distributed parallel algorithms based on itcould avoid repeated development.Test generation (TG) and fault simulation (FS) are two interrelated paIts of ATPG Due toaiming different task, they have different inherent parallelism. For FS, we research somemethods to speed up sequential FS algorithms. We first propose and implement a sequentialword-level pattern parallel FS algorithrn fOr synchIonous sequential circuits. Differing fromother similar algorithIns, it utilizes the relative independence of every fault test sequencegenerated by the G-F two-value TG algorithm, pwtitions and dynamically mounts test pattem,avoids redundant simulation fOr added synchLronous sequence, and gets better results. We alsodevelop a new word-level fault parallel FS algorithIn fOr synchronous sequential circuits. Itsinnovation is to extend existed fanout-free region pwtitioning methods of combinational circuitsto synchIonous sequentia1 circuits, and combines fanout source fault simulation and critical pathtracing. Experimental resu1ts reveal that the efficiency of it is better than that of genericword-level fault parallel FS algorithms. Based on a sequential word-level fault parallel FSalgorithm, we develop a multi-processor fault parallel FS algorithIn and a multi-processor patternparallel FS algorithIn. According to experimental results, the speedups of the latter are higherthan those of the fOrmef, the perfOrmance of the former accords with that of current foreignsimilar algorithm.For TQ we research fault parallel, search-space parallel and circuit parallel TG aPproaches.By combining static and dynamic panitioning methods, we first implemellt a fault parallel TGalgorithm with better effect. Secondly, we utilize fault sensitization mode partitioning to developa search-space parallel TG algorithm. Compared with the foreign similar algorithIns, itsadvantages are easy to implement, flexible control, less synchronous cost and better speedup. Asemphasis, we propose a new backward width-flrst search circuit partitioning method withflip-flop as core for synchronous sequential circuits. And then based on it, we develop a newcircuit parallel TG algorithm. It can greatly decrease memory overhead of VLSI ATPG while getmoderate speedup.For ATPG we consider that loosely couPled mode between TG and FS is more propitious to$III N.research and develop parallel ATPG algorithms than tightly coupled mode. It is able to combine several parallel strategies quickly and parallelize newest TG and FS algorithms. In this thesis, we adopt loosely coupled mode, develop a series of effective parallel ATPG algorithms based on sequential G-F two-value TG algorithm and HOPE FS algorithm.Finally, we analyse the performance of loosely coupled mode parallel ATPG algorithms. The analyses reveal that, compared with traditional tightly coupled mode parallel ATPG algorithms, loosely coupled mode parallel ATPG algorithms can reduce time and memory overhead in theory.