Unleashing Parallelism With Minimal Test Inflation in Multi-Threaded Test Pattern Generation

Shared-memory systems enable parallel computing for the automatic test pattern generation (ATPG). Although the existing techniques for parallel ATPG reach near-linear speedup, test inflation becomes a common problem in its practicality. Therefore, this paper proposes a multi-threaded test pattern generation called MT-TPG that can suppress test inflation and accelerate fault processing, simultaneously, to retain high parallelism. For suppressing test inflation, hard-fault shuffling (HFS) and concurrent-fault interruption (CFI) are involved to avoid repeated detection of the same fault among different threads. For accelerating fault processing, the potentially-droppable-fault removal (PDFR) and single-pattern parallel-fault simulation (SPPFSim) collectively drop not-yet-detected faults as early as possible for shortening the overall execution time of ATPG. According to our experimental results, the HFS and CFI can successfully suppress test inflation to < 4% on 17 benchmark circuits; PDFR and SPPFSim can achieve 13.7X speedup using 16 threads on average. As a result, MT-TPG is proven effective at unleashing parallelism with minimal test inflation on shared-memory systems.