Über die multi-level Synthese von EXOR-Schaltkreisen

Diplomarbeit von Tonja Pfeiffer, Stefan Eckrich

Zusammenfassung:

In dieser Arbeit wurde ein neues Verfahren zur Synthese kombinatorischer Schaltkreise auf der Grundlage von OKFDDs vorgestellt. Die durch OKFDDs repräsentierten Funktionen wurden mit Hilfe von Abhängigkeitsmatrizen dargestellt. Die Definition der Abhängigkeiten verlangt eine neue kanonische Darstellung für OKFDDs, quasireduzierte und bezüglich einer BMM -- Reihenfolge partiell quasireduzierte OKFDDs. Deren Kanonizität wurde in dieser Arbeit nachgewiesen.

Die einzelnen Abhängigkeitsmatrizen werden mit Booleschen Matrix Multiplikationen verknüpft. Diese Boolschen Matrix Multiplikationen werden dann in Teilschaltkreise umgesetzt. Dabei hat die Reihefolge, in der die Booleschen Matrix Multiplikationen ausgeführt werden, Einfluss auf die Schaltkreisdimensionen.

Unser Verfahren zur Schalkreissynthese liefert ohne großen Mehraufwand für OBDDs Schaltkreise in Zwei -- Weg Logik. Für OKFDDs wurden Aussagen über die Funktionalität der zusätzlichen Ausgänge getroffen.

Praktische Untersuchungen ergaben, daß Schaltkreise mit geringer Tiefe, guter Testbarkeit und einem vertretbaren Zuwachs an Größe erzeugt werden können. Die erzeugten Schaltkreise wurden mit den von anderen Verfahren erzeugten Schaltkreisen verglichen. Sie sind etwas größer als die von SIS erzeugten Schaltkreise aber deutlich kleiner als die von ESPRESSO erzeugten Schaltkreise. Die Tiefe der erzeugten Schaltkreise ist sehr viel kleiner als die Tiefe der mit SIS erzeugten Schaltkreise, sie ist sogar etwas kleiner als die Tiefe der mit ESPRESSO erzeugten Schaltkreise. Die Testbarkeit der erzeugten Schaltkreise ist vergleichbar mit der Testbarkeit der von SIS erzeugten Schaltkreise.

Ein weiterer großer Vorteil ergibt sich durch die zugrundeliegende Datenstruktur, denn es konnte für alle Benchmark Schaltkreise ein OKFDD gefunden werden und daraus ein Schaltkreis synthetisiert werden. SIS und ESPRESSO führten für einige Benchmark Schaltkreise zu keinen Ergebnissen.

Aufgrund der bisherigen Untersuchungen lässt sich sagen, dass das vorgestellte Syntheseverfahren über Abhängigkeiten eine echte Alternative zu den bisher bekannten Verfahren darstellt.

Zukünftige Aufgaben bestehen darin, die praktischen Untersuchungen, welchen Einfluss die Reihenfolge der Booleschen Matrix Multiplikationen auf die zu erzeugenden Schaltkreise hat, weiterzuführen. Ausgangspunkt für diese Untersuchungen sollten quasireduzierte OKFDDs ohne Komplementmarken sein.

Inhaltsverzeichnis:

1.	Einleitung	1
2.	Boolesche Funktionen und Entscheidungsdiagramme	3
2.1	Einleitung	3
2.2	Grundlegende Definitionen	3
2.3	Abhängigkeiten und quasireduzierte OKFDDs	11
3.	Die Abhängigkeit zur terminalen Null	21
3.1	Die allgemeine T - Funktion	21
3.2	Die Q -Funktion	23
3.3	Nicht komplette OKFDDs	27
4.	OKFDD basierte Schaltkreissynthese	31
4.1	Die OKFDD - Darstellung über Abhängigkeiten	31
4.2	Beschreibung von Schaltkreisen	33
4.3	Verschiedene OKFDD - Schaltkreise	35
4.3.1	Von Abhängigkeiten zu Schaltkreisen	35
4.3.2	Die Knotenersetzung	37
4.3.3	Knotenersetzung und Abhängigkeit	38
4.3.4	Schaltkreise logarithmischer Tiefe	40
4.3.5	Oder und exklusiv-Oder Operation / Abhängikeit	42
4.4	Verbesserungen der Schaltkreissynthese	46
4.4.1	Levelübergreifende Kanten	46
4.4.2	Erkennung redundanter Gatter	50
4.5	Effizienz der Synthese	53
4.5.1	Komplementmarken entfernen	54
4.5.2	Vollständiges Quasireduzieren	55
4.5.3	Partielles Quasireduzieren	56
4.5.4	Die Erzeugung der Schaltkreisbeschreibungen	57
4.5.5	Die Gesamtlaufzeit	60
5	Die BMM - Reihenfolge	63
5.1	Speicherung einer BMM - Reihenfolge	64
5.2	Streng lineare BMM - Reihenfolge	65
5.3	Logarithmische Tiefe	66
5.4	Strategien zu besseren Freilosverteilungen	67
5.4.1	Die Matrixketten Multiplikation	67
5.4.2	Der Freilos Algorithmus	70
5.4.3	Zufällige Verteilung der Freilose	72
6.	Größe der Schaltkreise	75
6.1	Vollständige Schaltkreise	75
6.2	Reduzierte Schaltkreise	77
6.3	Beeinflussung von OKFDDs	79
6.4	Beeinflussung der Schaltkreisgröße	80
6.4.1	Gatteranzahl als Kostenmaß	81
6.4.2	Matrixbelegung als Kostenmaß	82
6.4.3	Probleme bei der Implementierung	83
7.	Datenstrukturen für OKFDDs und Schaltkreise	85
7.1	Eine Datenstruktur für OKFDDs	85
7.2	Eine Datenstruktur zur Schaltkreisbeschreibung	88
8.	Implementierung der Schaltkreissynthese	91
8.1	Systemkompatiblität	91
8.2	Implementierung der Datenstruktur zur Synthese in C++	92
8.3	Vorbereitungen	94
8.3.1	Entfernen der Komplementmarken	95
8.3.2	Quasireduzieren	97
8.4	Erzeugen von Schaltkreis - Beschreibungen	103
8.4.1	Parameter	104
8.4.2	Zellnamenskonventionen	108
8.4.3	Eine Klasse für Abhängigkeitsmatrizen	110
8.4.4	Primäre Abhängigkeitsmatrizen	111
8.4.5	Sekundäre Abhängigkeitsmatrizen	112
8.4.6	Terminale Abhängigkeitsmatrizen	114
8.4.7	Abschließende Optimierungen	115
8.5	Verifizieren der Korrektheit	116
8.5.1	Verifizieren der Vorbereitungen an den OKFDDs	117
8.5.2	Verifizieren der erzeugten Schaltkreise	117
8.6	Öffentliche Variablen und Funktionen	119
8.6.1	Elementvariablen der Klasse OKFDD_to_TC	119
8.6.2	Methoden der Klasse OKFDD_to_TC	123
8.6.3	Hilfsfunktionen und globale Konstrukte	129
8.6.4	Eine besondere Boolesche Matrixklasse	133
8.6.5	Eine Klasse ganzzahliger Matrizen	135
8.6.6	Die Klasse der Abhängigkeitsmatrizen	136
9.	Ein Synthesebeispiel	139
10.	Messergebnisse	147
10.1	Größenveränderung an OKFDDs und OBDDs	149
10.2	Belegung der Abhängigkeitsmatrizen	155
10.3	Vergleich der Synthesemethoden	158
10.3.1	Auswirkungen der BMM-Reihenfolgen	158
10.3.2	Vergleich zwischen OKFDD und OBDD	163
10.3.3	Logiktyp und Schaltkreisgröße	166
10.3.4	Vergleich mit anderen Synthesemethoden	169
10.4	Synthesezeiten	180
10.5	Gatteranzahl in vollständigen Schaltkreisen	184
10.6	Sifting nach geringsten BMM - Kosten	186
11.	Zusammenfassung	189
A.	Listing	191
A.1	Das Makefile	191
A.2	main.h	191
A.3	main.c	193
A.4	step.h	197
A.5	step.c	211
B.	Listing der Messprogramme	283
B.1	Größe der DDs	283
B.1.1	Absolute Knotenzahlen	283
B.1.2	Größenwachstum	285
B.2	Zeilenbelegung der Abhängigkeitsmatrizen	287
B.3	Vergleich OKFDDs und OBDDs	289
	Literaturverzeichnis	291