ECE 269 VLSI System Testing Krish Chakrabarty Testability Measures ECE 269 Krish Chakrabarty 1 Testability Measures Origins Controllability and observability SCOAP measures Sources of correlation error Combinational circuit example Sequential circuit example Test vector length prediction High level testability measures Summary ECE 269 Krish Chakrabarty 2 1 Purpose Need approximate measure of Difficulty of setting internal circuit lines to 0 or 1 by setting primary circuit inputs Difficulty of observing internal circuit lines by observing primary outputs Uses Analysis of difficulty of testing internal circuit parts redesign or add special test hardware Guidance for algorithms computing test patterns avoid using hard to control lines Estimation of fault coverage Estimation of test vector length ECE 269 Krish Chakrabarty 3 Origins Origins Control theory Rutman 1972 First definition of controllability Goldstein 1979 SCOAP First definition of observability First elegant formulation First efficient algorithm to compute controllability and observability Parker McCluskey 1975 Definition of probabilistic controllability Brglez 1984 COP 1st probabilistic measures Seth Pan Agrawal 1985 PREDICT 1st exact probabilistic measures ECE 269 Krish Chakrabarty 4 2 Testability Analysis Involves circuit topological analysis but no test vectors and no search algorithm Static analysis Linear computational complexity Otherwise is pointless might as well use automatic test pattern generation and calculate Exact fault coverage Exact test vectors ECE 269 Krish Chakrabarty 5 Types of Measures SCOAP Sandia Controllability and Observability Analysis Program Combinational measures CC0 Difficulty of setting circuit line to logic 0 CC1 Difficulty of setting circuit line to logic 1 CO Difficulty of observing a circuit line Sequential measures analogous SC0 SC1 SO ECE 269 Krish Chakrabarty 6 3 Range of SCOAP Measures Controllabilities 1 easiest to infinity hardest Observabilities 0 easiest to infinity hardest Combinational measures Roughly proportional to circuit lines that must be set to control or observe given line Sequential measures Roughly proportional to times a flip flop must be clocked to control or observe given line ECE 269 Krish Chakrabarty 7 Goldstein s Goldstein s SCOAP SCOAP Measures Measures AND gate O P 0 controllability output controllability min input controllabilities 1 AND gate O P 1 controllability output controllability S input controllabilities 1 XOR gate O P controllability output controllability min controllabilities of each input set 1 Fanout Stem observability S or min some or all fanout branch observabilities ECE 269 Krish Chakrabarty 8 4 Controllability Controllability Examples Examples ECE 269 Krish Chakrabarty 9 More More Controllability Controllability Examples Examples ECE 269 Krish Chakrabarty 10 5 Observability Observability Examples Examples To observe a gate input Observe output and make other input values non controlling ECE 269 Krish Chakrabarty 11 More More Observability Observability Examples Examples To observe a fanout stem Observe it through branch with best observability ECE 269 Krish Chakrabarty 12 6 Error Error Due Due to to Stems Stems Reconverging Reconverging Fanouts Fanouts SCOAP measures wrongly assume that controlling or observing x y z are independent events CC0 x CC0 y CC0 z correlate CC1 x CC1 y CC1 z correlate CO x CO y CO z correlate x y z Krish Chakrabarty ECE 269 13 Correlation Error Example Exact computation of measures is NP Complete and impractical Italicized green measures show correct values SCOAP measures are in red or bold CC0 CC1 CO 1 1 6 1 1 5 1 1 5 1 1 4 6 6 6 2 3 4 x 2 3 4 5 4 6 y 2 3 4 2 3 4 6 2 0 4 2 0 z 1 1 6 1 1 5 ECE 269 Krish Chakrabarty 14 7 Sequential Circuit Example ECE 269 Krish Chakrabarty 15 Levelization Algorithm 6 1 Label each gate with max of logic levels from primary inputs or with max of logic levels from primary output Assign level 0 to all primary inputs PIs For each PI fanout Label that line with the PI level number Queue logic gate driven by that fanout While queue is not empty Dequeue next logic gate If all gate inputs have level s label the gate with the maximum of them 1 Else requeue the gate ECE 269 Krish Chakrabarty 16 8 Controllability Through Level 0 Circled numbers give level number CC0 CC1 ECE 269 Krish Chakrabarty 17 Controllability Through Level 2 ECE 269 Krish Chakrabarty 18 9 Final Combinational Controllability ECE 269 Krish Chakrabarty 19 Combinational Observability for Level 1 Number in square box is level from primary outputs POs CC0 CC1 CO ECE 269 Krish Chakrabarty 20 10 Combinational Observabilities for Level 2 ECE 269 Krish Chakrabarty 21 Final Combinational Observabilities ECE 269 Krish Chakrabarty 22 11 Sequential Measure Differences Combinational Increment CC0 CC1 CO whenever you pass through a gate either forwards or backwards Sequential Increment SC0 SC1 SO only when you pass through a flip flop either forwards or backwards to Q Q D C SET or RESET Both Must iterate on feedback loops until controllabilities stabilize See details in the text ECE 269 Krish Chakrabarty 23 Summary Summary Testability approximately measures Difficulty of setting circuit lines to 0 or 1 Difficulty of observing internal circuit lines Uses Analysis of difficulty of testing internal circuit parts Redesign circuit hardware or add special test hardware where measures show bad controllability or observability Guidance for algorithms computing test patterns avoid using hard to control lines Estimation of fault coverage 3 5 error Estimation of test vector length ECE 269 Krish Chakrabarty 24 12