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

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

Embed Size (px)

Citation preview

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

P. Tafertshofer, A. Ganz, M. Henftling

SAT-basiertes ATPGim

ImplikationsgraphenVortragender: Piet Engelke

Page 2: P. Tafertshofer, A. Ganz, M. Henftling SAT-basiertes ATPG im Implikationsgraphen Vortragender: 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

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

I Einführung

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

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

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

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

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

Implikation am AND Gatter

XX

0

X0

0

=>

11

X

11

1

=>

X0

X

X0

X

=>

1)

2)

3)

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

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

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

II Konstruktion des Implikations-

graphen(IG)

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

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

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

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.*

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

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 ****

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

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:

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

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

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

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

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

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

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

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)* * *

=>

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

III Operationenim Implikations-

graphen

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

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

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

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

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

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

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

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

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

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*)

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

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

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

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*

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

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

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

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.

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

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

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

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.

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

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

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

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

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

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

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

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

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

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* ^*^

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

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.

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

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.

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

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

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

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

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

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

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

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

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

IV Ergebnisse

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

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.

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

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)

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

[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