Testování sekvenčních obvodů Simulace poruch, minimalizace testu

Testování sekvenčních obvodů Simulace poruch, minimalizace testu Testování a spolehlivost ZS 2011/2012, 4. přednáška Ing. Petr Fišer, Ph.D. Katedra číslicového návrhu Fakulta informačních technologií ČVUT v Praze

MI-TSP-4, ČVUT FIT, © Petr Fišer, 2011

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

1

Testování sekvenčních obvodů Testování kombinačních obvodů 

Přivedu na PI takové hodnoty, které excitují a propagují poruchu



Test = ohodnocení PO



Složitost O(2n), n je počet PI

Testování sekvenčních obvodů 

Pojem stavu.



Stav = ohodnocení některých signálů



nestačí přivést příslušné hodnoty na PI, musím se nacházet ve správném stavu



Test = sekvence ohodnocení PI



Složitost nejméně O(2n+q), n je počet PI, q počet stavů



Výpočetně velice náročné, v praxi se používá jen pro velice malé obvody


2

Testování sekvenčních obvodů Možné přístupy: Funkcionální přístup - test automatu 

Testuji všechny přechody v přechodové tabulce

Strukturní přístup – „rozbalím“ sekvenční obvod 

Převedu na kombinační obvod složený z časových rámců sekvenčního obvodu

Přístupy založené na simulaci Různé avantgardní přístupy 

Genetické algoritmy

Použití DFT – obvod navrhuji tak, aby bylo možné oddělit kombinační část a registry 

„scan buňky“


3

Test automatu Princip:  

1.

Snažím se projít všechny přechody přechodové tabulky a ověřit správnost výsledku Na začátku musím obvod uvést do známého stavu Synchronizační sekvence (synchronizing sequence) Přivede automat z libovolného stavu do známého stavu

2.

Nastavovací sekvence (homing sequence) Přivede automat do daného stavu

3.

Rozlišovací sekvence (distinguishing sequence) Podle odezvy na PO zjistím, v jakém stavu se nacházím

4.

Převodní sekvence (transition sequence) Převádí automat z jednoho stavu do druhého


4

Test automatu Synchronizační sekvence (synchronizing sequence) Přivede automat z libovolného stavu do známého stavu Start: nevím (mohu se nacházet v libovolném stavu) Cíl: jednoznačný stav Jak: vytvářím strom, listy = jednoznačné stavy Nemusí vždy existovat


5

Test automatu Převodní sekvence (transition sequence) Převádí automat z jednoho stavu do druhého Daná popisem FSM – dle přechodové tabulky Nemusí vždy existovat


6

Test automatu Rozlišovací sekvence (distinguishing sequence) Podle odezvy na PO zjistím, v jakém stavu se nacházím Start: nevím (mohu se nacházet v libovolném stavu) Cíl: jednoznačná výstupní sekvence, identifikující daný stav Jak: vytvářím strom, listy = jednoznačné stavy Nemusí vždy existovat


7

Rozbalování časových rámců Princip:    

„rozbalím“ sekvenční obvod do časových rámců (timeframes) vznikne kombinační obvod aplikuji D-algoritmus Komb. PI PO nezasahuji do struktury obvod (rozbalení je jen myšlenkové) PPI

PPO DFF

PI

PO PI

PO PI Komb. obvod

Časový rámec 0 MI-TSP-4, ČVUT FIT, © Petr Fišer, 2011

Komb. obvod

Časový rámec 1

PO Komb. obvod

Časový rámec 2 8

Rozbalování časových rámců [Putzolu’71]

Algoritmus: 1. 2. 3. 4. 5.

6.

7.

Vyber poruchu Vytvořím kopii kombinační části pro časový rámec 0 (t = 0) Vygeneruji testovací vektor (např. pomocí D-algoritmu) Propaguje-li se porucha (D) na PO a je excitována, konec Propaguje-li se porucha pouze na PPO (vstupy DFF), vytvoř další kopii obvodu (časový rámec t + 1) Excituje-li se porucha z DFF, vytvoř předchozí časový rámec (t - 1) Jdi na 3


9

Rozbalování časových rámců Problém:  

Pětihodnotová D-logika neuvažuje opakovaný vliv poruchy (v různých časových rámcích) může nastat konflikt 



pětihodnotová logika je slabá (moc silné omezení)

algoritmus není úplný (ne vždy nalezne test, i když existuje)

Řešení:  

Devítihodnotová logika [Muth’76] 0, 1, X, 0/1, 1/0, 0/X, 1/X, X/0, X/1 (= bezporuchový / poruchový) 



Např. 1/0 = D

oproti 5-hodnotové logice zavedena X hodnota pro poruchový nebo bezporuchový obvod (jeden z nich)


10

Rozbalování časových rámců Shrnutí S použitím 9-hodnotové logiky je modifikovaný D-algoritmus úplný V průběhu algoritmu musím expandovat časové rámce dopředu i dozadu

 

může se zacyklit (ale lze detekovat)



Počet expandovaných časových rámců může být neúnosný





O(9#FF)

Složitost algoritmu: O(2#PI.9#FF)

 

použitelné jen pro obvody s malým počtem klopných obvodů


11

Metody založené na simulaci Vlastnosti      

Jednoduše implementovatelné Je možné použít i pro asynchronní obvody Malé pokrytí poruch Nelze identifikovat nedetekovatelné poruchy Těžko detekovatelné poruchy je těžké detekovat Test má daleko k minimalitě – silně redundantní testy


12

Generování testu pomocí genetických algoritmů Motivace   

Generování testu pro sekvenční obvody je velice obtížné Deterministicky špatně řešitelné ... vlastně nevím, jak na to 

zkusím to jinak

Princip Populace:  

Testovací vektor Sekvence testovacích vektorů

Fitness:  

Schopnost vektoru inicializovat nebo detekovat poruchu Pokrytí poruch

Operace:  

Křížení Mutace


13

Simulace poruch a.k.a. „poruchová simulace“, (fault simulation) = jaké poruchy jsou detekované daným testovacím vektorem? Je dáno: 

Obvod



Test (testovací vektor, sekvence vektorů)



Poruchový model

Výstup: 

Poruchový výstup



Detekované / nedetekované poruchy



Pokrytí poruch


14

Simulace poruch Praktické aplikace (kde se používá): 1.

Vyřazení detekovaných poruch ze seznamu poruch 



2.



po vygenerování testovacího vektoru odsimuluji, které poruchy detekuje



takto se implicitně řeší dominance

Viz ATPG algoritmus

Řízení generování testu 

3.

Jaké poruchy detekuje daný testovací vektor?

Viz předchozí

Slovník poruch 

Jaké poruše odpovídá jaká chybná odezva?


15

Simulace poruch n …… počet PI G …… počet hradel F …… počet poruch FF ...... počet klopných obvodů Kombinační ATPG: 

O(G  2n  F)

Sekvenční ATPG: 

O(G  2n  2FF  F)

Simulace poruch (pro jeden vektor): 



O(G  F)

Simulace se vyplatí!


16

Simulace poruch Základní strategie Základní triviální přístup (serial simulation) 

Podobné klasické logické simulaci



Pro daný testovací vektor simuluji bezporuchový obvod a obvod s poruchou

Paralelní simulace 

Využit paralelizmus na úrovni strojového slova

Deduktivní simulace 

Urychlující techniky, podobné učení v ATPG

Souběžná (concurrent) simulace


17

Sériová simulace poruch Triviální přístup, založený pouze na logické simulaci Princip: 

Odsimuluj bezporuchový obvod



Pro každou poruchu modifikuj obvod (injekce poruch) a odsimuluj



Porovnej poruchové odezvy s bezporuchovou

Plusy: 

Jednoduchá implementace, stačí použít obyčejný logický simulátor



Vždy mohu simulovat libovolnou poruchu pod daným poruchovým modelem

Mínusy: To nejpomalejší, co je


18

Paralelní simulace Založená na paralelizmu na úrovni strojového slova 

Vše, co provádím, jsou logické operace 

jde to snadno

Možnosti: 1. 2.

Simuluji více poruch najednou Simuluji více vektorů najednou


19

Paralelní simulace Simuluji více poruch najednou

1.



(Single Pattern Parallel Fault Propagation, SPPFP) [Seshu’65] Pro každý vektor simuluji w-1 poruch najednou (w je šířka strojového slova) 

teoreticky w-1  rychlejší, než sériová simulace (simuluji bezporuchový obvod + w-1 poruch najednou)


20

Paralelní simulace Simuluji více poruch najednou

1. 

Není možné simulaci včas zastavit 



Nevím, kde narazím na poruchu  musím simulovat až ke všem PO

Problém s vícehodnotovou logikou   

Každý signál může nabývat 3 hodnot (0, 1, X) 2 bity na signál při dnešních architekturách mohou nastat problémy s cache


21

Paralelní simulace Simuluji více vektorů najednou

2.

 

(Parallel Pattern Single Fault Propagation, PPSFP) [Waicukauski’86] Nejprve odsimuluji bezporuchový obvod Pak pro každou poruchu simuluji w vektorů najednou (w je šířka strojového slova) 

teoreticky w  rychlejší, než sériová simulace


22

Paralelní simulace Simuluji více vektorů najednou

2. 

Mohu zastavit simulaci, pokud se porucha nepropaguje 





Od bodu, kde se hodnoty bezporuchového a poruchového obvodu neliší, nemusím poruchu simulovat (pro žádný vektor) Jakmile zjistím, že se porucha nepropaguje na žádný PO (pro žádný vektor), mohu simulaci ukončit

Problém s vícehodnotovou logikou 

 

Každý signál může nabývat 3 hodnot (0, 1, X) 2 bity na signál při dnešních architekturách mohou nastat problémy s cache


23

Deduktivní simulace [Armstrong’72] Hlavní princip: V podstatě není poruchová simulace, spíše dedukce Simuluji pouze bezporuchový obvod 

... a simuluji všechny poruchy jedním průchodem

Každý signál má přiřazen seznam poruch, které se přes něj mohou propagovat / je možné je detekovat Seznam detekovaných poruch za každým hradlem se odvozuje ze „vstupních“ seznamů poruch a funkce (resp. monotonicity) hradla Seznam se dynamicky vytváří a aktualizuje 

při simulaci každého vektoru



může být neefektivní (zbytečné operace navíc)



seznam poruch se může během simulace dosti zvětšovat 

paměťově náročné


24

Deduktivní simulace Vytváření seznamu poruch  

Každý signál (výstup hradla z) má přiřazený seznam poruch Lz Budiž: 

 



I ...... množina všech vstupů hradla C ...... množina vstupů hradla, na nichž je řídící hodnota (např. 0 pro AND) val ...... hodnota výstupu, když na žádném vstupu není řídící hodnota

Pokud C =  (tj. na žádném vstupu není řídící hodnota): 𝐿𝑍 =

𝐿𝑖 ∪ 𝑧/𝑣𝑎𝑙 𝑖∈𝐼



Jinak: 𝐿𝑍 =

𝐿𝑖 − 𝑖∈𝐼


𝐿𝑖

∪ 𝑧/𝑣𝑎𝑙

𝑖∈𝐼−𝐶 25

Kompakce testu = už hotový test chci „zmenšit“ – zredukovat počet vektorů Jak? Některé vektory mohou „dominovat“ jiným 

Pro každý vektor zjistím „masku poruch“. Dominované vektory odstraním

Kombinace některých vektorů pokrývá všechny poruchy, které pokrývá jiný vektor  

problém unátního pokrytí (UCP) NP-těžké [Gary&Johnson]

Dospecifikování některých bitů neúplně určených vektorů     

bitům, které zůstaly neurčené, přiřadím hodnotu náhodně, deterministicky, aby pokrývaly co nejvíce poruch pak lze aplikovat dominance, atd. Takto lze vektory i spojit – statická kompakce ... ale také NP-těžké [Gary&Johnson]


26

Statická kompakce testu Princip:    

Vektory vygenerované ATPG obsahují DC (nespecifikované bity) Pospojuji vektory, kde to jde Neuvažuje se pokrytí poruch, pouze vektory NP-těžké 

používají se jednoduché heuristiky

Příklad:

01X 0X0 0X1 X01


010 001

27

Dynamická kompakce testu Princip:   

Vektory vygenerované ATPG obsahují DC (nespecifikované bity) Čím více DC ve vektoru, tím méně poruch pokrývá Dosazením konkrétních hodnot za X se snažím pokrýt co nejvíce dalších poruch  



poruchová simulace (oproti statické kompakci) opět NP-těžké

„Dynamická“ – protože se provádí již při vytváření testu, ne až na konci


28

Literatura G. R. Putzolu and T. P. Roth, "A Heuristic Algorithm for the Testing of Asynchronous Circuits", IEEE Trans. Computers, pp. 639-647, June 1971. P. Muth, "A Nine-Valued Circuit Model for Test Generation", IEEE Trans. Computers, pp. 630-636, June 1976. S. Seshu and D. N. Freeman, “On improved diagnosis program”, IEEE Trans. Electron. Comput, EC-14(1), 76-79, 1965 J.A. Waicukauski, E. Lindbloom, V.S. Iyengar, and B.K. Rosen, "Transition Fault Simulation by Parallel Pattern Single Fault Propagation", in Proc. ITC, 1986 V. D. Agrawal, K. T. Cheng, and P. Agrawal, "A Directed Search Method for Test Generation Using a Concurrent Simulator", IEEE Trans. CAD, pp. 131-138, Feb. 1989. P. Goel and B. C. Rosales, "Test generation and dynamic compaction of tests“, in Proc. 1979 Annu. Test Conf, Cherry Hill, NJ. D. B. Armstrong, “A Deductive Method for Simulating Faults in Logic Circuits,” IEEE Trans. on Computers, Vol. C21, No. 5, May 1972. E. G. Ulrich and T. Baker, "Concurrent simulation of nearly identical digital networks", Computer, vol. 7, pp.39 44 , 1974. W.T. Cheng and M.L. Yu., “Differential fault simulation - a fast method using minimal memory”. In Proceedings of the 26th ACM/IEEE Design Automation Conference (DAC '89). ACM, New York, NY, USA, 424-428. M. Abramovici, P. R. Menon, and D. T. Miller. “Critical path tracing - an alternative to fault simulation”. In Proceedings of the 20th Design Automation Conference (DAC '83). IEEE Press, Piscataway, NJ, USA, 214-220.


29

Testování sekvenčních obvodů Simulace poruch, minimalizace testu

Recommend Documents