P. Tafertshofer, A. Ganz, M. Henftling SAT-basiertes ATPG im Implikationsgraphen Vortragender: Piet...

P. Tafertshofer, A. Ganz, M. Henftling

SAT-basiertes ATPGim

ImplikationsgraphenVortragender: Piet Engelke

Inhaltsübersicht

I Einführung• Testmustergenerierung• Motivation

II Konstruktion des Implikationsgraphen

III Operationen im Implikationsgraphen• direkte Implikation• indirekte Implikation• Justifikation• Propagation

IV Ergebnisse / Zusammenfassung

I Einführung

Testmustergenerierung

.

.

.

.

.

.

primäre Eingänge

primäre Ausgänge

Fehlerort

• Justifikation: finde Belegung an den primären Eingängendie internes Signal auf bestimmten Wert setzt

• Propagation: Signaländerung an internem Signal zu den primären Ausgängen “transportieren”(Sensibilisierung + Justifikation)

• Implikation: weise unbestimmten Ein- Ausgängen eines GattersWerte zu, die sich aus der aktuellen Belegungzwingend ergeben

Testmustergenerierung

.

.

.

.

.

.

primäre Eingänge

primäre Ausgänge

Fehlerort

• Justifikation: finde Belegung an den primären Eingängendie internes Signal auf bestimmten Wert setzt

• Propagation: Signaländerung an internem Signal zu den primären Ausgängen “transportieren”(Sensibilisierung + Justifikation)

• Implikation: weise unbestimmten Ein- Ausgängen eines GattersWerte zu, die sich aus der aktuellen Belegungzwingend ergeben

Implikation am AND Gatter

XX

0

X0

0

=>

11

X

11

1

=>

X0

X

X0

X

=>

1)

2)

3)

Motivation

strukturbasiert: • Netzliste getrennt von Modulbibliothek• komplizierte Algorithmen• nicht erweiterbar

SAT basiert: • Schaltkreis dargestellt als Klauselmenge• sehr flexibel und effizient• keine topologischen Informationen

=> Topologie, Effizienz und Flexibilität

II Konstruktion des Implikations-

graphen(IG)

Erzeugung des IG

benötigt werden:

• Art und Kodierung der Logik

• Wahrheitstabellen der verwendeten Gatter

• Netzliste des Schaltkreises

Ablauf:

1a) Kodierung und Optimierung der Wahrheitstabellen

1b) Extraktion der Klauselmenge

1c) Konvertierung in Subgraphen

2a) personalisieren der Subgraphen

2b) Subgraphen zu einem IG verbinden

Kodierung der Logik

x L3 Kodierung Interpretationcx c*

x

0 0 1 Signal x = 01 1 0X 0 0

1 1 Konflikt bei Signal x

Signal x = 1Signal x = unbekannt

verwendete Logik : L3 = {0, 1, X}

Definition - Konflikt:

Eine Wertzuweisung heißt konfliktfrei gdw.:

für alle Signalvariablen cx cx 0 gilt.*

Kodierung und OptimierungWahrheitstab.

a b c0 0 00 1 01 0 01 1 10 X 01 X XX 0 0X 1 XX X X

kodierte Tabelleca c*

a cb c*b cc c*

c0 1 0 1 0 10 1 1 0 0 11 0 0 1 0 11 0 1 0 1 00 1 0 0 0 11 0 0 0 0 00 0 0 1 0 10 0 1 0 0 00 0 0 0 0 0

1 1 - - - -- - 1 1 - -

ca c*a cb c*

b cc c*c

- 1 - - - 1- - - 1 - 11 - 1 - 1 -

optimierte Tabelle

• nur konfliktfreie Belegungen gehen bei der Optimierung ein

• Konflikte müssen von den Algorithmen abgefangen werden

=> charakteristische Funktion eines AND Gatters als KNF

(ca cc) (cb cc) (ca cb cc) 1 ****

Konvertierung in Subgraphen (1)

x y z (x y z) (x z y) (y z x)

z

z

y x

yx

x y (x y) (y x) x

x y

y

es gelten folgende Umformungen:

Aufteilung von Klauseln

• Klauseln mit mehr als drei Variablen werden in Systeme aus binären und ternären Klauseln gewandelt

• führe zusätzliche Variable v ein:

(w x y z) (w x v) (y z v) v {0,1}

• es gilt (sei x eine Variablenbelegung):

=> der Existenzquantor kann ignoriert werden

[f(x) g(x, z)] f(x) g(x, z) x z x, z

Konvertierung in Subgraphen (2)

strukturelle Informationenf = Vorwärtskante: Kante vom Ein- zum Ausgang des Gattersb = Rückwärtskante: Kante vom Aus- zum Eingang des Gatterso = sonstige Kante

(ca cc) (cb cc) (ca cb cc) 1 ****

**mit cx cx und cx cx

cc

cb

ca

*cc

*ca

*cb

b

b

f

f

f

o

of

b

f

b

ac

b

IG formal

Implikationsgraph: GI = (VI, EI)• Menge der Knoten VI = VIS VI

VIS die SignalknotenVI die - Knoten

• Menge der Kanten EI = Ef Eb Eo Ef VorwärtskantenEb RückwärtskantenEo sonstige Kanten

• GB = (VI, Ef) Graph der Rückwärtskanten• GF = (VI, Eb) Graph der Vorwärtskanten

Beispiel für einen IGcf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

b b

f

f f

f f

b b

f

f f

bbbb

f

f f

ff

b bbb

ff

a

bd

f

ec

(cd cf) (ce cf) (cd ce cf) | f = AND(d, e) * * * *

(ca cd) (cb cd) (ca cb cd) | d = OR(a, b)* **

(cb ce) (cc ce) (cb cc ce) 1| e = OR(b, c)* * *

=>

III Operationenim Implikations-

graphen

Ausgehend von einer Menge VI VSvon markierten Knotenwerden alle Nachfolger vj markiert wenn:

1) Knoten vj ein - Knoten ist und all seine Vorgänger markiert sind

2) Knoten vj ein Signalknoten ist und mindestens einer seiner Vorgänger markiert ist

So lange fortfahren bis keine Markierungen mehr möglich sind.

Alle durch diese Regel markierten Knoten zusammen, repräsentieren die Belegung die aus Vimpliziert werden kann.

Eine Implikation ist nur dann möglich, wenn sie keine Konfliktehervorruft.

direkte Implikation - Regel

Die direkte Implikation

a = X

b = 1d = X

f = X

e = Xc = X

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

b b

f

f f

f f

b b

f

f f

bbbb

f

f f

ff

b bbb

ff

es gelte b = 1

propagiere alle Implikationen der aktuellen Belegung durchden Schaltkreis

Beispiel zur direkten Implikation

a = X

b = 1d = 1

f = X

e = 1c = X

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

b b

f

f f

f f

b b

f

f f

bbbb

f

f f

ff

b bbb

ff

Nachfolger eines - Knotens markieren, wenn beide Vorgänger passiert wurden

Beispiel zur direkten Implikation

a = X

b = 1d = 1

f =1

e = 1c = X

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

b b

f

f f

f f

b b

f

f f

bbbb

f

f f

ff

b bbb

ff

direkte Implikation:cb cf

die Implikation stoppt, wenn keine Markierungen mehr möglich sind

Die indirekte Implikation im IG

ca cb*ca *cb

cx

*cx

• werden in der Preprocessing - Phase entdeckt und dem

Graphen als Kante hinzugefügt

• Identifikation durch direkte Implikation und anschließender Kontraposition: ca cb (cb

* ca*)

Sei cx der ursprünglich markierte Knoten. Aus einer rekonvergenten

Struktur (cx, cy) im IG folgt nur dann eine indirekte Implikation,

wenn:

• cx ein Fanoutknoten im IG ist

• cy über einen - Knoten markiert wurde dessen Vorgänger

beide nach Implikation über disjunkte Pfade markiert worden

sind

indirekte Implikation - Regel

Beispiel zur indirekten Implikation

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

b b

f

f f

f f

b b

f

f f

bbbb

f

f f

ff

b bbb

ff

direkte Implikation:cb cf

indirekte Implikation:cf

* cb*

Justifikation im IG (1)

Wert an internen Signalen soll durch Zuweisungen an primären

Eingängen eingestellt werden

• Objective: Werteinstellungsziel für eine internes Signal

Ablauf des Verfahrens:

1. Wahl des Objectives

2. Backtracing: versuche Belegung an den primären Eingängen

zu finden, die das Objective einstellen

3. Implikation: prüfe ob die gewählte Belegung das Objective

wirklich erfüllt

Justifikation im IG (2)

Definition - unjustifizierte Klauseln:

Eine Klausel C = c1 c2 ... cn heißt unjustifiziert, gdw. alle

Literale c1, c2,..., cn nicht erfüllt sind und mindestens ein

Komplement ci* eines Literales ci Eins ist.

Definition - Justifikation einer Klausel:

Seien c1, c2,..., cm unspezifizierte Literale in einer unjustifizierten

Klausel C = c1 c2 ... cm und seien V1, V2,..., Vm

Wertzuweisungen. Dann wird die Menge konfliktfreier

Zuweisungen J = {c1= V1, c2= V2, ... cm= Vm} eine Justifikation der

Klausel C genannt, wenn die Wertzuweisungen in J die Klausel C

erfüllen.

Justifikation im IG (3)

cz

*cy*cx

cy cx

*cz

=> Justifikation besteht aus genau zwei Elementen J = {{cx= 1}, {cz= 1}}

x y z (x y z) (x z y) (y z x)

• Objective entspricht unjustifizierter Klausel

• nur ternäre Klauseln können unjustifiziert sein

Backtracing - Regel

Das Objective oi sei bereits zum Konten vi V vorangetrieben worden. sucs(vi) Vs und suc(vi) Vbezeichnen die nachfolgenden Signal bzw. - Knoten in GB. Dann wird das Objective oi zu den folgenden Knoten getrieben:

• allen Signalknoten vj sucs(vi).

• einem - Knoten vj suc(vi) der entsprechen eines Kontrollierbarkeitsmaßes gewählt wird. Knoten vj, die einen Signalknoten cx als Nachfolger haben, dessen zugehöriger Komplementknoten cx

* markiert ist, werden nicht gewählt.

Diese Regel wird solange angewandt, bis keine Propagationvon Objectives mehr möglich ist, d.h. alle Objectives einen PI erreicht haben.

Beispiel zur Justifikationcf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

1 2

2332

f = 0 soll justifiziert werdenes gelte bereits e = 1

a = X

b = Xd = X

f = 0

e = 1c = X

!

nur die Rückwärtskanten werden verwendet Backtracing mit “depth - first” Strategie

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

1 2

2332

a = X

b = X(d = 0)

f = 0

e = 1c = X

!

Wahl eines - Knotens nach vorberechnetem Testbarkeitsmaß

Beispiel zur Justifikation

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

1 2

2332

(a = 0)

(b = 0)(d = 0)

f = 0

e = 1c = X

!

über direkte Übergänge erreichte Nachfolger werden immer gewähltBacktracing stoppt, da die primären Eingänge erreicht wurden

Beispiel zur Justifikation

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

1 2

2332

a = 0

b = 0d = 0

f = 0

e = 1c = X

Implikation der Eingangsbelegungdie Justifikation wird für alle Objectives durchgeführt

cf* erfolgreich justifiziert

Beispiel zur Justifikation

PropagationKodierung

x L9 gut fehlerhaftcx cx

* ´c`x ´c`x*

0 0 1 0 11 1 0 1 0X 0 0 0 0D 1 0 0 1/D 0 1 1 0G0 0 1 0 0G1 1 0 0 0F0 0 0 0 1F1 0 0 1 0

• Kodierung von Unterschieden macht Übergang von L3 zu L9

notwendig

• split-circuit Modell

=> Verdopplung des L3 Graphen

(= zwei disjunkte, isomorphe Graphen)

• im Fehlergraphen werden alle Knoten mit einem ‘^’ kenntlich gemacht

• Konflikt liegt vor, wenn gilt:

(cx cx) = 1 oder(cx cx) = 1* ^*^

Propagation - Regel (1)Das Ausgangssignal sI sei beobachtbar an Signal si, d.h. (si = D) (si = /D), bzw. (ci ci

*) (ci* ´c`i) 1. sucs(vi) Vs

g und suc (vi) V g

bezeichnen alle nachfolgenden Signal bzw. - Knoten eines Knotens vi

in GF g =(V

g , EF g). Signal sI wird an einem nachfolgenden Signal sj

beobachtbar gemacht, durch:• Wahl eines Knotens vj sucs(ci) suc (ci) entsprechend eines vor-

berechneten Beobachtbarkeitsmaßes.Knoten vj = cj sucs(ci), deren zugehöriger Komplementknoten cj

*

markiert ist und Knoten vj suc(ci) , die einen Signalknoten cx zum

Nachfolger haben, dessen zugehöriger Komplementknoten cx* markiert

ist, werden nicht gewählt.

wenn vj sucs(ci), d.h. vj bezeichnet einen Signalknoten cj, so markiere

seinen zugehörigen Komplementknoten ´cj`* in G f.

wenn vj suc (ci), so markiere seinen nachfolgenden Signalknoten ck

und dessen zugehörigen Komplementknoten ´ck`* in G f.

Propagation - Regel (2)

(Fortsetzung)• Implikation ausgehend von allen markierten Knoten in G, wodurch die

sensibilisierenden Zuweisungen eingefügt werden. Wenn dieImplikationen zu einem Konflikt führen, werden alle Zuweisungenrückgängig gemacht und ein anderer Knoten vj sucs(ci) suc (ci)

wird gewählt. Führen alle Knoten vj zu einem Konflikt so erfolgt ein

Backtracking zur letzten Entscheidung.

Diese Regel wird solange angewendet, bis ein PO erreicht wurde oder alle aus vj sucs(ci) suc (ci) gewählten Knoten zu einem Konflikt

führen.

Beispiel zur Propagation

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

gut fehlerhafta = 1

b = Dd = 1

f = X

e = Xc = X

ca^

cf *cf

cd ce

cb cc *cc *cb *ca

*ce *cd

^

^ ^

^ ^ ^ ^

^ ^ ^ ^

propagiere Unterschied b = D, es gelte a = 1die Vorwärtskanten leiten die Propagation (depth first - Strategie)

1

3

1

Beispiel zur Propagation

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

gut fehlerhafta = 1

b = Dd = 1

f = X

e = X/0c = X

ca^

cf *cf

cd ce

cb cc *cc *cb *ca

*ce *cd

^

^ ^

^ ^ ^ ^

^ ^ ^ ^

wähle Knoten ce nach vorberechnetem Beobachtbarkeitsmaß => Komplementknoten im Fehlergraphen wird markiert

Beispiel zur Propagation

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

gut fehlerhafta = 1

b = Dd = 1

f = D

e = F0c = X

ca^

cf *cf

cd ce

cb cc *cc *cb *ca

*ce *cd

^

^ ^

^ ^ ^ ^

^ ^ ^ ^

wähle und markiere Knoten cf (nach Beobachtbarkeitsmaß)=> Komplementknoten im Fehlergraphen wird markiertein “primärer” Ausgang wurde erreicht

Beispiel zur Propagation

cf *cf

cd ce

ca cb cc *cc *cb *ca

*ce *cd

gut fehlerhafta = 1

b = Dd = 1

f = D

e = Dc = 0

ca^

cf *cf

cd ce

cb cc *cc *cb *ca

*ce *cd

^

^ ^

^ ^ ^ ^

^ ^ ^ ^

führe Implikation durchkonfliktfreie Belegungen werden zwischen den Graphen ausgetauscht

IV Ergebnisse

Experimentelle ErgebnisseTEGUS (Zeit in [s]) CGRASP (Zeit in [s]) TIP (Zeit in [s])

SK total SAT KNF total SAT KNF total ATPG IGc432 2,05 0,53 1,48 3,70 1,48 2,21 0,07 0,05 0,02c499 5,44 1,27 4,08 5,56 20,6 3,49 0,17 0,17 0,00c880 2,16 0,41 1,69 5,48 2,13 3,34 0,07 0,07 0,00c1355 11,73 2,49 9,12 31,98 12,90 19,08 0,82 0,82 0,00c1908 18,75 3,77 14,82 41,79 22,95 18,84 1,67 1,62 0,05c2670 27,88 8,65 18,83 32,93 23,38 9,55 1,57 1,52 0,05c3540 94,94 37,47 57,06 102,53 57,14 45,39 6,55 6,27 0,28c5315 48,90 7,94 40,28 77,26 54,85 22,41 5,32 5,29 0,03c6288 473,61 244,02 228,87 566,82 319,37 247,44 39,44 39,40 0,03c7552 104,93 20,63 83,16 214,04 169,48 44,55 13,94 13,91 0,03s1269 5,21 0,95 4,16 0,25 0,25 0,00s3271 9,55 1,34 7,92 1,00 0,98 0,02s4863 63,61 18,47 44,68 6,60 6,49 0,12s5378 25,84 3,08 22,16 2,80 2,77 0,03s9234 215,05 134,63 79,41 19,21 17,84 1,37s13207 137,01 10,51 124,63 33,31 33,23 0,08s15850 282,60 32,62 247,63 28,33 28,20 0,13s35932 749,79 10,05 732,84 238,55 238,35 0,20s38417 1035,19 42,88 984,26 175,10 174,80 0,30s38584 920,57 20,73 892,09 341,08 340,81 0,27

geo. Mittel 51,40 36,97 4,79

stuck-at ATPG ohne Fehlersimulation

TEGUS : P.Stephan, R.K. Brayton und A.L. SangiovanniVincentelli ; 1996.CGRASP : L.G. e Silva, L.M. Silveira und J. Marques-Silva; 1999.

Zusammenfassung• KNF mit der Toplogie in einer Datenstruktur vereint

• einfach aufgebauter, flexibler Graph Der Graph besteht aus nur zwei Knotentypen und erlaubtdie Aufnahme zusätzlicher Kanten (indirekte Implikationen).

• kompakte Darstellung des Schaltkreises Die Größe des Graphen ist linear in der Anzahl der Schaltkreismodule.

• effizientAlle vorgestellten Operationen sind als Graphenalgorithmen

implementiert.

• strukturbasierte Algorithmen und Heuristiken sind übertragbar (vgl. beispielsweise Backtracing)

[1] P. Tafertshofer, A. Ganz und M. Henftling : “A SAT - Based Implication Engine“, Tech. Rep. TUM-LRE-97-2, Technical University of Munich, April 1997.

[2] P. Tafertshofer und A. Ganz : ”SAT Based ATPG Using Fast Justifcation and Propagation in the Implication Graph”, ICCAD 1999.

[3] M. Abramovici, M.A. Breuer und A.D. Friedman : “Digital Systems Testing and Testable Design”, Computer Science Press, 1990.

[4] L.G. e Silva, L.M. Silveira und J. Marques-Silva : “Algorithms for solving boolean satisfiability in combinational circuits”, in Design Automation Conference and Test in Europe (DATE), S. 526-530, 1999.

[5] S. Russell, P. Norvig : “Artificial Intelligence - A Modern Approach”, Prentice Hall Int’l Editions, S. 77f, 1995.

Literaturverzeichnis