Upload
odilia-nestle
View
109
Download
2
Embed Size (px)
Citation preview
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