07 GowherMalik MOS AK

Slide1: 

Professor Vladimir I. HAHANOV Doctor of Sciences (Engineering), IEEE member Chief-Editor of Journals“Radioelectronics & Informatics” “Automated Control Systems & Devices”, Gowher Malik : Student of Masters Program ‘Computer Systems and Networks’ at’ Kharkov National University of RadioElectronics’. It consists of two institutes and 7 faculties, 8000 students, 100 professors and doctors of science, 400 PhD and professor assistants, more than 900 computers in laboratories. 14, Lenin Avenue, Kharkov, 61166, Ukraine Phone (+380)-572-70 21 326, E-mail:Hahanov@kture.kharkov.ua Scientific space: Digital Systems Testing and Testable Design, Fault Simulation and Test Generation for RTL-Systems .

Slide2: 

Actuality of digital systems testing For multi-million gate ASICs, reusable Intellectual Property (IP), and System-on-Chip (SoC) designs, verification consumes 70% of the design effort. The number of verification engineers is usually twice the number of RTL designers. The testbenches code makes up to 80 % of the total design code volume. [Bergeron Janick. Writing testbenches: functional verification of HDL models.– Boston: Kluwer Academic Publishers.– 2001.– 354 c.]

Slide3: 

Aldec: Active HDL, Riviera Cadence: Verifault Altera: MAX+PLUS II Xilinx: Foundation 2.1 Synopsys: FPGA Express Synthesis, BSD Compiler, TetraMAX Actel: ActelDeskTop Synplicity: VeriBest, Synplify Asset: ScanWorks boundary scan (IEEE 1149.1) system (Test Development Station, Programming Station, Manufacturing Station, Diagnostic& Repair Station) Virage Logic: Embed-It!, Architect, Integrator, Automated Characterization (automated memory development tools) Logic Vision: Embedded Test, ET Verify, LV TestStation Mentor Graphics: FlexTest, QuickFault Syntest: TurboBIST-Memory, TurboBist–LogicTurboFault, TurboFault, SynTest Simucad: Verilog HDL Logic Simulation, HyperFault Fault Simulation (logic simulation, fault simulation) Corporations – Leaders in Design and Test area

Slide4: 

Properties of well known Test Systems

Slide5: 

References [1] Hahanov V.I., Babich À.V., Hyduke S.M., Test Generation and Fault Simulation Methods on the Basis of Cubic Algebra for Digital Devices, Proc. Euromicro Symposium on Digital Systems Design, Warsaw, Poland, 2001, 228-235. [2] Semenetz. V., Hahanova I., Hahanov V. Digital systems design using VHDL.- Kharkov.- KNURE.- 2003.- 492 p. [3] Bondarenko M., Krivoulya G., Ryabtcev V., Fradkov S., Hahanov V. Design and testing of computer systems and networks.- Kiev: NMCVO. 2000.- 306 p. [4] Levendel Y.H., Menon P.R., Comparison of fault simulation methods – Treatment of unknown signal values, Journal of Digital Systems. Vol. 4, 1980, 443-459. [5] Abramovici M., Breuer M.A. and Friedman A.D., Digital System Testing and Testable Design.- Computer Science Press, 1998. [6] Ubar R. ,The analysis of diagnostic tests for combinational digital circuits by fault back tracing methods.- Moscow.- Automatica and Telemechanica.- No 8.- 1977. [7] Hahanov V.I., Technical diagnosis for devices of personal conputers.- Kiev: IZMN, 1997) [8] Nierman T.M., Cheng W.–T., Patel J.H. PROOFS: A Fast, Memory Efficient Sequential Circuit Fault Simulator // IEEE Transaction on CAD. – 1992. – vol.11, no. 2. – P. 198–207. [9] Sudhakar M. Reddy, Irith Pomeranz, Xijiang Lin, Nadir Z. Basturkmen. New Procedures for Identifying Undetectable and Redundant Faults In Synchronous Sequential Circuits // 17th IEEE VLSI Test Simposium. – 1999. – P. 476–480. [10] Ruifeng Guo, Irith Pomeranz, Sudhakar M. Reddy. A Fault Simulation Based Test Pattern Generator for Synchronous Sequential Circuits//17th IEEE VLSI Test Simposium.–1999.–P.456–460.

Slide6: 

Purpose is to develop high performance fault simulation method for test generation system of complex digital devices described in HDL. Problems are: 1. Investigation of design and test world market. 2. Developing deductive theory of fault simulation for RTL described digital systems. 3. Developing deductive-parallel fault analysis model. 4. Creation of back traced deductive-parallel fault analysis method. 5. Developing deductive model of circuit structure analysis. 6. Creation of internal circuit model for fault simulation. 7. Developing topological deductive-parallel fault simulation. 8. Program applications of developed methods and models. 9. Integrating fault simulation program with ATPG SIGETEST. 10. Testing and verification implemented methods, models and program. Outlines: Purpose & Problems

Circuit structure analysis: 

Circuit structure analysis Searching the reconvergent fan outs for purpose of its deductive-parallel fault simulation. Transforming reconvergent fan out lines into pseudo primary outputs. Representation of circuits model as tree like structure for back-traced fault simulation.

Slide8: 

Model transformation: Circuit – Graph – OR-circuit It is needed for theoretical proof of deductive model consistency for reconvergent fan-out searching. 2) The current equipotential line of fault free circuit becomes vertex of the oriented graph. 3) The vertex model becomes a logical element OR, where the number of inputs is equal to input edges of the current vertex.

Structure analysis OR-circuit graph modelSearching of reconvergent fan-outs: 

Structure analysis OR-circuit graph model Searching of reconvergent fan-outs Model image-object relation for adjacent vertices in graph Analyzing OR-circuit graph model Deductive (Set Theory) Deductive-parallel (Boolean Theory)

Slide10: 

Deductive searching sample of reconvergent fan-outs in oriented graph (Vj – list of predecessors, Vi – list of reconvergent fan out)

Slide11: 

Flip-flop structure and its graph model that is used for RFO searching Definition: for the synchronous circuits containing FF feedbacks, the loop line is RFO, if this one consists of more then one outgoing arcs and has the nearest line of convergence which doesn’t belong to this feedback loop. Boolean Normal Form: S2_tmp0=C_tmp0*Q3_tmp0(t-1); Q2_tmp0(t)=!S2_tmp0+(D_tmp0*Q2_tmp0(t-1)); R3_tmp0=!(D_tmp0*Q2_tmp0(t-1)); Q3_tmp0(t)=!C_tmp0+(R3_tmp0*Q3_tmp0(t-1)); Q(t,0)=!Q3_tmp0(t)+(Q2_tmp0(t)*Q(t-1)).

Slide12: 

Set theory model of fault transportation Operates test-vector, multi-valued cubic coverage, output fault list n – number of cubes; m – number of input lines; k – number of output lines; Sr – fault list on output r of multi output primitive; Sj – input fault list of primitive Tj (Tr) – value of test-vector coordinate; Cij (Cir) – input (output) coordinate value of cubic coverage; The most universal and basic formula of fault transportation

Slide13: 

Boolean model of deductive-parallel fault analysis by truth table Operates test-vector, cubic coverage, deductive truth table or deductive function

Universal deductive models of fault transportation for exhaustive test applied on AND-, OR-primitives: 

Universal deductive models of fault transportation for exhaustive test applied on AND-, OR-primitives

Universal deductive parallel simulator(may be used as embedded accelerator)transport fault vectors through AND-, OR-primitive under any applied binary input vector: 

Universal deductive parallel simulator (may be used as embedded accelerator) transport fault vectors through AND-, OR-primitive under any applied binary input vector X1, X2 -vector variables; x1, x2 – Boolean variables; input AND/OR- primitive mode Table of two test-vector evaluation for parallel simulation

Slide16: 

The limitations of deductive functions creation Statement 1. Deductive function for binary vector has not inversion on any primitive outputs. Statement 2. Deductive function for binary vector can have inversion on primitive inputs. Statement 3. Deductive function for binary vector can’t have inversion on all primitive inputs.

Transformations of good primitives into deductive ones under applied binary vectors: 

Transformations of good primitives into deductive ones under applied binary vectors

Reconfiguration of good model into deductive-parallel one: 

Reconfiguration of good model into deductive-parallel one Input test-vector T=11111110001 and good device model create deductive circuit for simulating fault-vector containing in fault matrix

Slide19: 

Back-traced fault simulation strategy: reconvergent fan-out searching; fault-free simulation of test-vector; separation of tree-like structure; fault simulation of reconvergent fan-outs; back-traced superposition of tree-like parts; forming of general detected fault vector. Computing complexity (n – number of line or gates, W – length of computer word):

Slide20: 

Back-traced fault simulation procedure – superposition of detectable fault vectors of primitives for tree-like structure In the table sign (.) equals to sign empty set. The condition of superposition is not empty set intersection on connected line j.

Interpretative model of fault-free and fault analysis: 

Interpretative model of fault-free and fault analysis Formulas of interpretative model evaluation for (1 - fault free simulation, 2 - fault simulation) Truth table of fault-free simulation Internal model of Fault-free simulation Internal model of fault simulation

Developing topologic deductive-parallel fault simulation.Incorrectness of two structure fault simulation using single path activation: 1) pseudo detectable a-fault, 2) undetectable b-fault How to delete such incorrectness? – To simulate RFO and TLS separately and to simplify back-traced superposition.: 

Developing topologic deductive-parallel fault simulation. Incorrectness of two structure fault simulation using single path activation: 1) pseudo detectable a-fault, 2) undetectable b-fault How to delete such incorrectness? – To simulate RFO and TLS separately and to simplify back-traced superposition.

The basis of topologic simulation: 

The basis of topologic simulation 1) Inversion input of deductive element AND forbids fault activation path for all predecessor lines of the mentioned input. 2) All inputs of deductive primitive AND are defined as inverted if primitive have more than one uncomplemented input. 3) Deductive primitive AND activate all predecessor lines faults only on uncomplemented input that must be only one. 4) Deductive primitive OR can’t contain inverted inputs. 5) Reconvergent fan out line is signed as inversion if its fault don’t detect on test-vector. 6) The input or output lines with inversion are interruption condition of fault back tracing trough considered branch of tree like structure. 7) Detected fault of reconvergent fan outs signed by bold point is considered like primary output foe executing fault back tracing. 8) Interpretation of topologic simulation result: equipotent line’s faults that aren’t signed as inversion on deductive model are detected.

Developing topologic deductive-parallel fault simulation: 

Developing topologic deductive-parallel fault simulation 1) Fault-free circuit structure 2) Fault-free simulation of test-vector 3) Deductive model and reconvergent fan-out fault simulation 4) Topological back-traced fault simulation

Developing topologic deductive-parallel fault simulation.Interpretation of result: The faults of lines having inversion sign aren’t detected. : 

Developing topologic deductive-parallel fault simulation. Interpretation of result: The faults of lines having inversion sign aren’t detected. 1) The faults of lines 7, 8 and 11 are detected. 2) The faults of lines 10 and 11 are detected – it have not inversion sign.

Slide26: 

The strategy of developed methods applying for test quality evaluation (RFO – reconvergent fan-out, TLS – tree like structure) Computing complexity of fault simulation approaches: B - number of not equivalent faults; G – number of gates; W – length of computer word; a – number of activated gates; k – number of reconvergent fan-outs; n – number of lines; p – superposition time; t – parallel operation time. Parallel Deductive Deductive-Parallel Back-traced Deductive-Parallel Topologic Deductive-Parallel

Slide27: 

SIGETEST contains: Translator from HDL to internal data structure Set of test generators (deterministic, pseudo-random, genetic) Set of fault simulators Test bench translator The problem solved: Test quality evaluation Fault table creation for errors diagnosis Test set minimization Test pattern generation

Slide28: 

IEEE Language Standard support by SIGETEST The purpose is to make test generation and fault simulation system as invariant towards mentioned hardware description languages. The languages VHDL, EDIF, Netlist and XILINX library of RTL elements are supported. The compilers from System C, Verilog, VHDL and EDIF languages to internal data structure formats are developing.

Slide29: 

Speed testing of fault simulation methods Comparison of 2 methods for circuits, including 1000 – 8000 gates. Deductive method Deductive-parallel method Number of gates in the circuit Simulation time

Slide30: 

Speed testing of fault simulation methods Processing time of 1 gate for circuits, including 1000 – 8000 gates. Deductive method Deductive-parallel method

Slide31: 

Speed testing of fault simulation methods Circuits are 17 – 7552 gates Deductive-parallel method BDP method Number of gates in the circuit Gate processing time (in microseconds)

Slide32: 

Comparison of fault simulation systems speed Nemesis, BDP-, DP-method, Turbo-tester. Circuits are 432 – 7552 gates Nem BDP DP TT

Slide33: 

SIGETEST: fault simulation speed testing Circuits are 6288 – 40 000 gates Topological Deductive parallel

Slide34: 

SIGETEST: fault simulation speed testing Circuits are 1000 – 100 000 gates Topological Deductive parallel

SIGETEST – SImulation and GEneration of TEST: 

SIGETEST – SImulation and GEneration of TEST Was rewarded with Intel diploma in CAD systems competition, 2003 Universal model of digital systems deductive-parallel analysis Sufficient simulation speed-up due to the back-traced superposition Deductive model of reconvergent fan-out searching Method of topologic fault simulation for tree-like structure Technical solutions for embedded fault simulators The further SIGETEST development: Structural analysis improvement for simulation speed-up Analysis of false fault compensation for flip-flops and latches Theoretical proof of superposition correctness for flip-flop structure Structural analysis for asynchronous circuits Development of compilers from HDL languages Development of hardware accelerators for fault simulation speed-up

Slide36: 

Thank YOU for your attention!