容错计算英文版课件：lec06-testing

1、Fault-Tolerant ComputingDealing with Low-Level ImpairmentsOct. 20061Fault TestingAbout This PresentationEditionReleasedRevisedRevisedFirstOct. 2006This presentation has been prepared for the graduate course ECE 257A (Fault-Tolerant Computing) by Behrooz Parhami, Professor of Electrical and Computer

2、Engineering at University of California, Santa Barbara. The material contained herein can be used freely in classroom teaching or any other educational setting. Unauthorized uses are prohibited. Behrooz ParhamiOct. 20062Fault TestingFault TestingOct. 20063Fault TestingThe good news is that the tests

3、 dont show any other problemsOct. 20064Fault TestingMultilevel ModelComponentLogicServiceResultInformationSystemLegend:ToleranceEntryTodayNext lectureOct. 20065Fault TestingOverview of Fault TestingFAULT TESTING(Engineering, Manufacturing, Maintenance)Correctdesign?Correctimplementation?CorrectOpera

4、tion?Oct. 20066Fault TestingRequirements and Setup for TestingReference valueTest patternsourceCircuit under test(CUT)ComparatorPass/FailTestability requires controllability and observability (redundancy may reduce testability if we are not careful; e.g., TMR)Reference value can come from a “gold” v

5、ersion or from a tableTest patterns may be randomly generated, come from a preset list, or be selected according to previous test outcomesTest results may be compressed into a “signature” before comparingTest application may be off-line or on-line (concurrent)Easier to test if direct access to some

6、inner points is possibleOct. 20067Fault TestingImportance and Limitations of Testing“Trying to improve software quality by increasing the amount of testing is like trying to lose weight by weighing yourself more often.”Steve C. McConnell“Program testing can be used to show the presence of bugs, but

7、never to show their absence!” Edsger W. DijkstraTest coverage may be well below 100% (model inaccuracies and impossibility of dealing with all combinations of the modeled faults)Important to detect faults as early as possibleApproximate cost of catching a fault at various levels Component $1 Board $

8、10 System $100 Field $1000Oct. 20068Fault TestingFault Models at Different Abstraction LevelsFault model is an abstract specification of the types of deviations in logic values that one expects in the circuit under testCan be specified at various levels: transistor, gate, function, systemTransistor-

9、level faults Caused by defects, shorts/opens, electromigration, transients, . . . May lead to high current, incorrect output, intermediate voltage, . . . Modeled as stuck-on/off, bridging, delay, coupling, crosstalk faults Quickly become intractable because of the large model spaceFunction-level fau

10、lts Selected in an ad hoc manner based on the function of a block (decoder, ALU, memory)System-level faults (malfunctions, in our terminology) Will discuss later in section dealing with mid-level impairmentsOct. 20069Fault TestingGate- or Logic-Level Fault ModelsMost popular models (due to their acc

11、uracy and relative tractability)Line stuck faults Stuck-at-0 (s-a-0) Stuck-at-1 (s-a-1)Line open faults Often can be modeled as s-a-0 or s-a-1Delay faults (less tractable than the previous fault types) Signals experience unusual delaysABCSKs-a-0Line bridging faults Unintended connection (wired OR/AN

12、D)Short(OR)OpenOther faults Coupling, crosstalkOct. 200610Fault TestingPath Sensitization and D-AlgorithmThe main idea behind test design: control the faulty point from inputs and propagate its behavior to some outputExample: s-a-0 faultTest must force the line to 1This method is formalized in the D

13、-algorithmABCSKs-a-01/0111/001/0Two possible tests(A, B, C) = (0 1 1) or (1 0 1)Forward trace(sensitization)Backward traceD-calculus1/0 on the diagram above is represented as D0/1 is represented as DEncounters difficulties with XOR gates (PODEM algorithm fixes this)Oct. 200611Fault TestingSelection

14、of a Minimal Test SetEach input pattern detects a subset of all possible faults of interest (according to our fault model)ABCSKE F G H J L N M P R Q Choosing a minimal test set is a covering problemABCPQs-a-0 s-a-1 s-a-0 s-a-1000- - x011x -x -101? ? ?111? ? ?Equivalent faults: e.g.,P s-a-0 L s-a-0 Q

15、 s-a-0Q s-a-1 R s-a-1 K s-a-1Oct. 200612Fault TestingCapabilities and Complexity of D-AlgorithmReconvergent fan-out Consider the s input s-a-0PODEM solves the problem by setting y to 011D1 DD z s y xWorst-case complexity of D-algorithm is exponential in circuit size Must consider all path combinatio

16、ns XOR gates cause the behavior to approach the worst case Average case is much better; quadraticPODEM: Path-oriented decision making Developed by Goel in 1981 Also exponential, but in the number of circuit inputs, not its sizeSimple path sensitization does not allow us to propagate the fault to the

17、 primary output zOct. 200613Fault TestingBoolean DifferenceK = f(A, B, C) = AB BC CAdK/dB= f(A, 0, C) f(A, 1, C)= CA (A C) = A CABCSKE F G H J L N M P R Q s-a-0K = PC ABdK/dP= AB (C AB) = C(AB)Tests that detect P s-a-0 are solutions to the equation P dK/dP = 1(A B) C(AB) = 1 C = 1, A BTests that det

18、ect P s-a-1 are solutions to the equation P dK/dP = 1(A B) C(AB) = 1 C = 1, A = B = 0Oct. 200614Fault TestingComplexity of Fault TestingThe satisfiability problem (SAT) Decision problem: Is a Boolean expression satisfiable? (i.e., can we assign values to the variables to make the result 1?)Theorem (

19、Cook, 1971): SAT is NP-completeIn fact, even restricted versions of SAT remain NP-completeAccording to the Boolean difference formulation, test generation can be converted to SAT (find the solutions to P dK/dP = 1)To prove the NP-completeness of test generation, we need to show that SAT (or some oth

20、er NP-complete problem) can be converted to test generationFor a simple proof, see Fuji85, pp. 113-114Oct. 200615Fault TestingDesign for Testability: CombinationalIncrease controllability and observability via the insertion of degating mechanisms and control pointsDesign for dual-mode operation Norm

21、al mode Test modeDegateControl/ObserveABMuxesPartitioneddesignABNormal modeABTest modefor AOct. 200616Fault TestingDesign for Testability: SequentialIncrease controllability and observability via provision of mechanisms to set and observe internal flip-flopsScan design Shift desired states into FF S

22、hift out FF states to observeCombinational logic.FFFF.Mode controlCombinational logic.FFFF.Partial scan design:Mitigates the excessive overhead of a full scan designOct. 200617Fault TestingBoundary Scan for Board-Level TestingAllows us to apply arbitrary inputs to circuit parts whose inputs would ot

23、herwise not be externally accessibleBoundary scan elements of multiple parts are cascaded together into a scan pathAny digital circuitScan inScan outTest clockMode selectFrom: /pdfs/boundaryscan_tutorial.pdf Parallel outParallel inOct. 200618Fault TestingBasic Boundary Scan CellFrom: /pdfs/boundarys

24、can_tutorial.pdf Oct. 200619Fault TestingBuilt-in Self-Test (BIST)Reference valueTest patternsourceCircuit under test(CUT)ComparisonPass/FailTest patterns may be generated (pseudo)randomly e.g., via LFSRsDecision may be based on compressed test resultsOrdinary testingTest patterngenerationCircuit un

25、der test(CUT)DecisionPass/FailBuilt-in self-testingOct. 200620Fault TestingQuantifying Testability: ControllabilityN(0) = 7N(1) = 1CTF = 0.25Controllability transfer factorCTF = 1 N(0) N(1)N(0) + N(1)N(0) = 1N(1) = 7CTF = 0.25Coutput = (Si Cinput i / k) CTF1.00.30.5 0.15A line with very low controllability is a good place for test point insertion 0Control p