A SAT based test generation method for delay fault testing of macro based circuits

Delay fault testing and at-speed testing are widely used to verify the timing of synchronous digital IC’s. The importance of these techniques is still growing because of the relevant IC’s parameters uncertainties which characterize the current technologies. In order to drive this process, several fault models and test generation techniques have been developed that target different trade-offs between accuracy and efficiency. The largest fraction of these approaches is based upon gate level descriptions of the circuit. In case the basic building blocks are more complex than logic gates and their implementation is not known, functional level approaches have been proposed. For instance, this is the case for look-up tables based Field Programmable Gate Arrays (FPGAs) and it may be a perspective for deep submicron circuits that exploit logic bricks as basic building blocks. This class of circuits has been referred to as macro or module based. In this context, the main activities performed during the tree years of my PhD are related to the timing failures problems in module-based CMOS VLSI circuits. The attention to module-based (or block-based) circuits follows the current VLSI physical design trends that attempt to limit the parametric failures due to the scaling of technology toward nanometric feature sizes. In such technologies, in fact, the traditional design paradigms that are based on small (i.e gate level) cells may produce high levels of variability, thus resulting in parametric defects. The use of highly regular cell structures, called logic bricks has been proposed to solve these problems thus increasing the yield of VLSI circuits. A brick comprises a logic function created from a small set of logic primitives that are mapped on to a micro-regular fabric. Such logic function is typically more complex that those implemented in traditional VLSI libraries. Field Programmable Gate Array (FPGA) technology also exploits a module based design approach. Unlike logic bricks, FPGAs are completely programmable, because they are based on look up tables (a n-bit LUT can accomplish every n-bit function), but the drawback is related to the implementation of the LUT, that is unknown to designer and not optimized for regularity. In this scenario, the delay fault testing became a big issue, since it is very difficult to study a circuit built using modules whose implementation in not known, either for technological and for intellectual property reasons. Moreover, the aggressive timing policies used in today’s ICs make the need for delay fault testing more relevant. The main PhD activity, that will be explained in detail in this thesis, is related to a new method that we propose to generate test vectors for path delay faults in circuits based on modules. In particular, we consider the single path delay fault model in combinational circuits or in (enhanced) full-scan ones that are composed of functional blocks whose implementation is not known. In such circuits a path fault is detected by suitable conditions so that a test pair is able to propagate a transition through the path under test, in order to detect a path delay fault. In order to identify such conditions, we introduced a new signal representation that enables the use of boolean differential calculus. Also, additional conditions to prevent invalidation of tests by hazards have been identified. We suppose that the dynamic behavior of the block is modeled using input delays such as in the timing arc delay model. We target simple combinational blocks such as logic bricks, that are expected to present up to 8-10 inputs and a low logic depth. The used method is scalable, to generate conditions for path delay fault tests also at gate level. In order to assess the feasibility of the proposed approach, I realized a software, written in C/C++, that permits to find out robust and non-robust test pairs, starting from the BLIF description of a module based circuit. Such a software uses a BDD description of the blocks’ functions on which we apply Boolean Differences to obtain local sensitization conditions at module level. Since there are circuits whose BDD structure may be very large and it may be inefficient (in some cases also infeasible) to treat it, we translate functions obtained at macros level to a CNF description. After that, a SAT solver generates the test pairs at circuit level starting from the conjunction of all the CNF functions. The software tool was used to verify the proposed approach on a set of benchmarks (both combinational or full-scan) from ITC’99 and ISCAS’85 sets. Such benchmarks allowed to show the feasibility of the proposed approach, although they are not fully representative of the target circuits for which the method was developed. Another significant work, carried out during my PhD period, also deal with testing of macro-based circuits, but it concerns specifically logic bricks. In particular, a method for high quality functional fault simulation and test generation for such circuits was conceived and a software tool that implements it was developed. For both the approaches, results showed the feasibility of them, but also highlighted possibilities to improve and extend the work done.