Integration von SAT Checker und BDDs für den kombinatorischen Äquivalenzvergleich

SAT-Engines-Seminar

WS 2000/01

Asmir Hadzidedic

Paper

„ Integrating a Boolean Satisfiability Checker and BDDs

for Combinational Equivalence Checking „

Aarti Gupta

Pranav Ashar

CCRL, NEC USA

Princeton, NJ

1997

Übersicht

Einführung Ausnutzung interner Korrespondenzen Kombination von BDDs mit der ATPG basierten Methoden Integration von SAT und BDD

- Aufzählung von BDD Würfel

- Aufzählung von SAT Lösungen

* Konsistenz Methode

* Early Bounding Experimentelle Ergebnisse Iteratives SAT+BDD Verfahren

Einführung(1)

Äquivalenztest für die kombinatorischen Schaltkreise ist ein wichtiges Problem bei dem Entwurf von digitalen Systemen.

Äquivalenztest:

Realisieren zwei vorgegebene kombinatorische Schaltkreise eigentlich die gleiche Funktion?

Historisch, haben sich zwei unterschiedliche Vorgehensweisen zu diesem Problem durchgesetzt:

- Methoden, die auf Funktionen basieren,

- Methoden, die auf ATPG (Automatic Test Pattern Generation) basieren.

Einführung(2)

Funktionen-basierte Methoden versuchen die gesamte Schaltkreisfunktionalität in eine einzelne kanonische Darstellung umzuwandeln.

Äquivalenzvergleich der möglicherweise unterschiedlichen Schaltkreisstrukturen reduziert sich auf dem viel einfacheren Problem des Vergleiches der kanonischen Darstellungen.

Benutzung von Reduced Ordered Binary Decision Diagrams (ROBDD) Mit ROBDD ist ein Vergleich in konstanter Zeit möglich. Nachteile von ROBDD:

- Für bestimmte allgemein verwendete Funktionen ist die BDD Größe exponentiell . ( Bsp. Multiplizierer )

- Schlecht für die Random Logik.

Einführung(3)

Die ATPG basierten Methoden arbeiten direkt auf der Schaltkreisstruktur.

Konstruktion eines „Miter“ Schalkreises:

Einführung(4)

Äquivalenznachweis erfolgt durch den Nachweis der redundanten Fehler s-a-0 (Stuck at 0) am Miter-Ausgang.

Die ATPG basierte Methoden können größere Schaltkreise als Funktionen basierte Methoden auffassen, wenn die Schaltkreise strukturell ähnlich sind.

Keine dieser Methoden genügt allein, um heutige Äquivalenzprobleme von Schaltkreisen effizient zu lösen.

Zwei neue Methoden sind vorgeschlagen worden, um die Nachteile der ATPG basierten und der BDDs basierten Methoden zu verbessern.

Ausnutzung interner Korrespondenzen(1)

Diese Methode versucht, Korrespondenz zwischen internen Knotenpunkten des Schaltkreises auszunutzen.

Das Ziel ist die Überprüfung des Verifizierungsproblems zu vereinfachen.

Berman schlug vor, die Simulation auszunutzen, um die Paare des möglicherweise gleichwertigen internen Signals zu kennzeichnen.

Gleichwertigkeit der Korrespondenzpaare wurde mit einem ATPG basierten Checker durchgeführt.

In der Praxis hat diese Methode gute Ergebnisse erbracht, sogar für die Schaltkreise, die sich strukturell deutlich unterscheiden.

Ausnutzung interner Korrespondenzen(2)

Beispiel:

Kombination von BDDs mit der ATPG basierten Methoden(1)

Diese Methode baut vom Output zu den Inputs einen, so groß wie möglich, BDD auf. Der Teil des „Miter“ Schaltkreises wird „Fanout-Partition“ genannt. Der Rest des „Miter“ Schaltkreises wird „Fanin-Partition“ genannt.

Kombination von BDDs mit der ATPG basierten Methoden(2)

Die ATPG basierte Methoden werden verwendet, um die Vektoren an der Grenze zwischen der „Fanout-“ und der „Fanin-Partition“ zu überprüfen.

Jeder Vektor, für den es eine Belegung der Inputvariablen gibt, muß noch gegen BDD überprüft werden, um sicherzugehen, daß am Output von „Miter“-Schaltkreis eine " 1" ausgegeben wird.

Oder: jeder Vektor aus der ON-Menge von BDD muß überprüft werden, ob es eine Belegung der Inputvariablen gibt, die für den Vektor verantwortlich ist.

Der erste Vorschlag dieser Methode stammt von Berman (1989).

Kombination von BDDs mit der ATPG basierten Methoden(3)

Die Ausnutzung interner Korrespondenzen kann zusätzlich benutzt werden, um die Größe der „Fanout-Partition“ zu erhöhen. Damit wird die Suche nach den erfüllenden Vektoren in der „Fanin-Partition“ vereinfacht.

Eine explizite Aufzählung der erfüllenden Vektoren bzw. der ON-Menge des BDD ist selbst für eine gemäßigte Größe schwer durchführbar.

Das gilt auch,wenn man eine Würfeldarstellung statt der Minterme nimmt.

Integration von SAT und BDD (1)

SAT: Sei gegeben eine Boolesche Formel in KNF. Finde eine Belegung der

Booleschen Variablen, so daß das Ergebnis der Formel wahr ist. Typische SAT-Algorithmen verwenden bei der Suche nach Belegungen

systematisches Backtracking. Jeder Schritt von Backtracking besteht aus zwei Teilschritte:

1. Branching: Auswahl einer Variable und setzen ihres Wertes 2. Bounding: Aktualisieren die KNF-Formel mit dem Wert der Variable

bis ein Fixpunkt erreicht ist. Wenn Schritt 2. zu einen Widerspruch führt, kann die Suche gestoppt werden

und die Prozedur kann einen Schritt zurückgehen.

Integration von SAT und BDD (2)

„Fanout-Partition“ wird mit BDD und „Fanin-Partition“ mit SAT Klauseln aufgefaßt.

Ziel ist es, zu bestimmen, ob der Miter Ausgang jemals „1“ annehmen kann. Eine Lösung besteht darin, daß eine erfüllende Belegung der SAT-Klauseln durch die Primarinputs existiert, und diese Belegung bzw. Teilbelegung auch Element der ON-Mende des BDDs ist.

Das heißt, wir suchen nach einem nicht leeren Durchschnitt zwischen der SAT Lösung und der BDD-ON-Menge.

Man beachte, daß BDD und die SAT Klauseln jene Variablen teilen, die die Knotenpunkte auf der Grenze der beiden Partitionen darstellen. Diese Variablen werden „Cutset“-Variablen genannt.

Aufzählung von BDD Würfel

Jeder „erfüllende“ Würfel des BDDs wird aufgezählt. Jeder dieser Würfel kann zum SAT Checker in Form von 1-Klausel

angeschlossen werden, die zu dem Rest des Schaltkreises hinzugefügt werden können.

Das SAT Problem wird unabhängig für jeden Würfel gelöst. Falls für irgendeines dieser Probleme eine Lösung gefunden wird, ist diese Lösung bereits ein Gegenbeispiel für das Äquivalenzproblem.

Nachteile:

- Die Zahl von BDD Würfeln kann groß sein, und

- SAT Checker wiederholt die Arbeit für ähnliche Würfel.

Aufzählung von SAT Lösungen

Anstatt, die Elemente der BDD-ON-Menge aufzuzählen, sollen die SAT Lösungen aufgezählt und überprüft werden, ob sie der BDD-ON-Menge angehören.

Nachteil: - SAT Lösungen aufzuzählen ist kostspieliger als die BDD-ON-

Menge aufzuzählen. Vorteile: - SAT Lösungen können implizit aufgezählt werden, indem man

„Backtracking“ verwendet, und - Überprüfung, ob eine gegebene Belegung der BDD-ON-Menge angehört, ist ein lineares Zeitproblem, im Vergleich zu dem Lösen eines SAT Problems für jeden Würfel (ein NP-hartes Problem).

Die Konsistenz Methode

Der SAT Checker wird gestartet; aber immer, wenn er mit einer Lösung endet, prüfen wir, ob die Belegung von der Cutset-Variablen zu der BDD-ON-Menge gehört.

Falls ja, dann ist das ein Gegenbeispiel für den Äquivalenzvergleich. Fall nein, dann überspringen wir die letzte Belegung in SAT Branch-und-Bound Prozedur und suchen wir nach der nächsten SAT Lösung

Dies wird die Konsistenz Methode genannt, da jede SAT Lösung auf Zugehörigkeit zur BDD-ON-Menge überprüft wird.

Nachteil:

- Die Zahl von „Backtracks“ wird nicht verringert und dadurch wird

das Lösen des SAT Problems in keiner Hinsicht vereinfacht.

Early Bounding (1)

Idee: Immer, wenn eine Cutset-Variable in die SAT Branch-und-Bounding

Prozedur genommen wird, können wir überprüfen, ob die bisherige unvollständige Zuweisung, einschließlich der neuesten Zuweisung zur Cutset-Variable, einen nicht leeren Durchschnitt mit der BDD-ON-Menge hat.

Folgerung: Wenn ja, dann müssen wir den Rest der Variablen wie üblich überprüfen. Wenn nein, dann können wir die Teillösung der SAT Prozedur sofort

durchstreichen, die bis zu diesem Schritt erreicht werden konnte. Vorteil: Der Bounding-Schritt kann für die Cutset-Variable früher abgebrochen

werden, und das Ausbreiten kann dadurch verhindert werden.

Early Bounding (2)

Algorithmus: sat_bound ( sat ,lit, bdd ) { if ( lit_is_a_cutset_variable ( lit ) ) { new_bdd = project_variable_in_bdd ( bdd, lit ); if ( bdd_equal ( new_bdd, Zero_bdd ) ) return failure; else bdd = new_bdd; } /* rest of the procedure is unchanged */ }

Early Bounding (3)

sat_branch ( sat,bdd ) {

lit = find_next_lit ( sat ) ; /* find the next literal to bound */

if ( lit == NIL ) return success; /* SAT solution is found */

old_bdd = bdd;

if ( sat_bound ( sat,lit,bdd ) && sat_branch ( sat,bdd ) ) return success;

undo_lit_assignment ( sat ) ; /* previous branch failed:backtrack */

bdd = old_bdd;

if ( sat_bound ( sat,neg(lit),bdd ) && sat_branch ( sat,bdd ) ) return success;

return failure;

}

Early Bounding (4)

Immer wenn eine Variable Cutset-Variable ist, projizieren wir sie in der sat_bound Prozedur in BDD mit der project_variable_in_bdd Prozedur.

Die Prozedur project_variable_in_bdd verwendet entweder die bdd_substitute oder die bdd_cofactoroperation Prozedur, die in den Standard-BDD-Paketen vorhanden sind.

Wenn das resultierende BDD dem Zero_bdd gleich ist, haben wir einen leeren Durchschnitt, und wir geben „Fehler“ zurück. D.h. diese SAT Lösung bzw. Teillösung ist nicht in der ON-Menge von BDD enthalten.

Andernfalls wird das projizierte BDD auf die Aufrufprozedur geführt.

Early Bounding (5)

In der sat_branch Prozedur suchen wir zunächst nach dem nächsten Literal; und wir prüfen, ob wir schon eine vollständige Lösung haben.

Wenn dieses Literal eine Cutset-Variable ist, die nicht zu einem Zero_bdd führt, und wir besitzen eine vollständige Lösung, die dieses Literal enthält, dann beenden wir die Prozedur mit Erfolg. D.h. die entsprechenden Schaltkreise sind nicht äquivalent.

Wenn dieser Fall nicht auftritt, dann wird die SAT Lösung bezüglich des Literals zurückgesetzt und die oben drei genannten Bedingungen werden auch für den negierten Literale geprüft.

Falls die beiden Fälle mit nicht negiertem und negiertem Literal nicht auftreten, dann haben die SAT Lösungsmenge und BDD-ON-Menge einen leeren Durchschnitt.

Spezielle BDD Operationen (1)

Erfahrung hat gezeigt, daß die Nutzung der Standard BDD Operationen die SAT Prozedur für große BDDs beträchtlich verlangsamt.

Hier:

Sobald die Miter BDD Partition erstellt ist, wird nicht das volle Set von Programmen eines BDD-Manipulationspakets für die restliche Arbeit angefordert.

Denn: nur zwei Operationen sind eigentlich erforderlich:

- Projektion einer Variable in ein BDD, und

- Prüfung, ob resultierendes BDD gleich Zero_bdd ist. Jede Operation wird beim Bounding der Cutset-Variablen einmal

verwendet.

Spezielle BDD Operationen (2)

Mit den Standard BDD Paketen ist die Laufzeit im Worst Case zur Größe des BDD proportional; und mit den speziellen BDD Operationen ist die Laufzeit konstant.

Es wird eine einfach verkettete Liste verwendet, um die Zuweisung von Cutset-Variable zu verfolgen. Das Projizieren einer Variable wird einfach durch Setzen ihres Wertes bewerkstelligt, was eine konstante Zeitoperation ist.

Die Überprüfung gegen ein Zero_bdd setzt voraus, daß BDD durchquert wird. Wenn irgendein Pfad zu einem One_bdd gefunden wird, wird die Suche abgebrochen, und das BDD ist dem Zero_bdd nicht gleich. Im Worst Case ist die benötigte Zeit proportional zu der BDD Größe.

Ohne die Gesamtkomplexität zu beeinflussen, beseitigen diese speziellen Operationen so kostspielige Cachezugriffe und die Wartung der Knotentabelle, was eigentlich die Laufzeit verringert.

Analyse (1)

Methoden:

- Benutzung von BDDs für die Reduzierung des SAT Problems bezüglich der Anzahl der Backtracks,

- Vermeiden der expliziten Aufzählung der BDD Würfel,

- “Early Bounding” während der SAT Prozedur,

- Benutzung von speziellen BDD Operationen zur Verbesserung der Laufzeit.

Analyse (2)

Umgebung:

- SUN ULTRA WORKSTATION mit 128 MB Arbeitsspeicher,

- SIS mit einem SAT Checker, der in der Literatur als TEGUS oder als CMU BDD Paket benannt wird,

- Benchmark von ISCAS-Gruppe mit dem Schaltkreis C6288,

- Bei BDD ist eine Knotenbegrenzung auf 500 K eingebaut,

- Eine Zeitschranke ist auch vorhanden ( 30 bzw. 3 Stunden ) .

SAT+BDDs vs SAT (1)

SAT+BDDs vs. SAT (2)

T ist eine Zeitschranke von 30 Stunden für alle Ausgänge. Für die ersten acht Ausgänge wurde SAT+BDD Checker nicht

aufgerufen, da das Miter BDD selbst die Konstante „0“ geliefert hat. SAT hat nur bis zum 13. Ausgang die Zeitschranke eingehalten. Für die Ausgänge, die verifiziert werden konnten, wurde ein Faktor

(Verhältnis zwischen 9. Und 6. Spalte) bis zu 27 erzielt.

(siehe die letzte Spalte in der Tabelle 1.) Für das Experiment wurde bei den SAT+BDD Verfahren das „Early

Bounding“ benutzt. (vgl. 5. und 8. Spalte in Tabelle 1.)

Vorteile durch die Aufzählung der SAT Lösungen (1)

Vorteile durch die Aufzählung der SAT Lösungen (2)

T ist eine Zeitschranke von 3 Stunden. Die Spalte 5. enthält die Anzahl der BDD-Würfel, die überprüft werden

müssen, und die Spalte 6. die entsprechende Zeit. Für den 9. Ausgang ist die BDD-Würfel-Aufzählungsmethode nicht beendet. Dies liegt an der großen Zahl von 1250 Millionen Würfeln, die unabhängig aufgezählt und überprüft werden müssen. Demgegenüber konnte die SAT Lösung Aufzählungsmethode bis zum 14. Ausgang durchgeführt werden.

Beim Vergleich zwischen „Early Bounding“- und „Konsistenz“-Methoden wurde ein Faktor bezüglich der Anzahl von Backtracks von bis zu 34 erzielt.

Vorteile durch die Aufzählung der SAT Lösungen (3)

Die Spalte 8. Stellt die Zeit dar, die mit den speziellen BDD Operationen erreicht wurde und die Spalte 11. die Zeit, die mit denStandard-BDD-Operationen erreicht wurde.

Innerhalb der festgesetzten Grenzzeit wurde eine Verringerung der Laufzeit bis zu 65% erreicht.

Falls man die BDD und die SAT Partitionen vergrößert, kann man auch größere Gewinne erwarten.

Iteratives SAT+BDD Verfahren

Die SAT+BDD Äquivalenztechnik kann einen Kern aus einer Iterativen Methode haben:

1. Suchen nach Kandidaten für die äquivalenten Paare im Miter Schaltkreis

2. Versuche, die Äquivalenz jedes Paares zu überprüfen

3. Ersetze die Knoten, wenn ein zu ihnen äquivalentes Paar gefunden wurde

Im Schritt 1. wird die randomisierte Mustersimulation von einer Liste der Kandidaten für die Äquivalenzpaare verwendet.

Im Schritt 2. wird die SAT+BDD Methode verwendet. In der Wirklichkeit kann man hier alleine SAT Verfahren verwenden.

Zusammenfassung

Einführung Ausnutzung interner Korrespondenzen Kombination von BDDs mit der ATPG basierten Methoden Integration von SAT und BDD

- Aufzählung von BDD Würfel ( nicht effizient )

- Aufzählung von SAT Lösungen

* Konsistenz Methode ( nicht effizient )

* Early Bounding Experimentelle Ergebnisse Iteratives SAT+BDD Verfahren