SAT-based ATPG using multilevel compatible don't-cares
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
In a typical IC design flow, circuits are optimized using multilevel don't cares. The computed don't cares are discarded before Technology Mapping or Automatic Test Pattern Generation (ATPG). In this paper, we present two combinational ATPG algorithms for combinational designs. These algorithms utilize the multilevel don't cares that are computed for the design during technology independent logic optimization. They are based on Boolean Satisfiability (SAT), and utilize the single stuck-at fault model. Both algorithms make use of the Compatible Observability Don't Cares (CODCs) associated with nodes of the circuit, to speed up the ATPG process. For large circuits, both algorithms make use of approximate CODCs (ACODCs), which we can compute efficiently. Our first technique speeds up fault propagation by modifying the active clauses in the transitive fanout (TFO) of the fault site. In our second technique, we define new j - active variables for specific nodes in the transitive fanin (TFI) of the fault site. Using these j-active variables we write additional clauses to speed up fault justification. Experimental results demonstrate that the combination of these techniques (when using CODCs) results in an average reduction of 45% in ATPG runtimes. When ACODCs are used, a speed-up of about 30% is obtained in the ATPG run-times for large designs. We compare our method against a commercial structural ATPG tool as well. Our method is slower for small designs, but for large designs, we obtain a 31% average speedup over the commercial tool.
