XOR-basierte Logiksynthese

| Beteiligte Mitarbeiter | Projektbeschreibung | Software | Publikationen |

Logiksynthese und Verifikation sind zentrale Komponenten des computerunterstützten Schaltkreisentwurfs. Bedingt durch technologische Entwicklungen insbesondere im FPGA-Bereich haben Schaltkreise, die unter zusätzlicher Verwendung von EXORs aufgebaut werden, auch praktisch an Bedeutung gewonnen. Parallel dazu sind Datenstrukturen für Boolesche Funktionen durch den Einsatz von EXOR-basierten Zerlegungen weiter verbessert worden. Das Logiksynthese-Teilgebiet des Projektes wird im folgenden genauer erläutert:

Die Logiksynthese befaßt sich mit allen Aufgaben und Problemen, die es im Zusammenhang mit der bzgl. verschiedenartiger Kostenfunktionen möglichst optimalen Realisierung kombinatorischer und sequentieller Logik zu bewältigen gibt.

"Klassische" Logiksynthese liefert ausgehend von einer Anfangsbeschreibung eine optimierte zweistufige oder mehrstufige Darstellung des Schaltkreises, die auf der Verwendung von logischen Grundgattern AND, OR, NOT basiert. Optimierungskriterium ist dabei in der Regel die belegte Fläche. Die durch technologische Fortschritte gegebenen Möglichkeiten haben auch die Anforderungen an die Logiksynthese wesentlich verschärft: Zum einen lassen sich immer komplexere Funktionen auf einem Chip realisieren, und diese sollen natürlich auch von dem Logiksynthese-Werkzeug bearbeitet werden können. Zum anderen haben sich die Optimierungsziele verändert und vervielfältigt. Neben Fläche sind Zeitverhalten, Leistungsverbrauch und Testbarkeitseigenschaften als Optimierungskriterien von zunehmender Bedeutung.

Als ein wichtiges Beispiel seien hier auf Field Programmable Gate Arrays (FPGAs) basierende Technologien erwähnt, bei denen EXOR-Gatter als Grundgatter mit den gleichen Verzögerungszeiten wie die Standardgatter angesehen werden können. Dies ist ein Grund, warum Logiksynthese, die die Integration von EXOR-Gattern zum Ziel hat, theoretisch wie praktisch neu an Bedeutung und Interesse gewonnen hat. Weiter kann zumindest für zweistufige Realisierungen von bestimmten Schaltkreisklassen gezeigt werden, daß AND/EXOR eine kompaktere Darstellung zuläßt als sie bei der Verwendung von AND/OR möglich ist. Darüberhinaus haben zweistufige AND/EXOR-basierte Realisierungen (unter bestimmten zusätzlichen Bedingungen) gute Testbarkeitseigenschaften. Auf der anderen Seite stehen aber trotz dieser Vorteile bisher so gut wie keine Werkzeuge zur Verfügung, die eine Logiksynthese unter Einbeziehung von EXORs für Schaltkreise mit "vielen" Inputs ähnlich effizient wie bei der AND/OR-basierten Synthese ermöglichen. Die bekannten Algorithmen arbeiten nur für eine kleine Zahl von Inputs und sind in der Regel auf zweistufige Darstellungen beschränkt.

Schon die klassische Logiksynthese erfordert die Lösung von i.a. NP-vollständigen Problemen. Bei den oben erläuterten, gestiegenen Anforderungen bezüglich Qualität und Quantität kommt der Effizienz der Datenstrukturen und Grundoperationen zur Darstellung und Manipulation der behandelten Objekte besondere Bedeutung zu. Hier erfreuen sich Ordered Binary Decision Diagrams (OBDDs) zur Repräsentation Boolescher Funktionen ständig wachsender Aufmerksamkeit. Sie konnten bei der computerunterstützten Logiksynthese mit großem Erfolg eingesetzt werden. Vorteile sind Eindeutigkeit der Repräsentation und effiziente Realisierung der Grundoperationen, wie z.B. Äquivalenztest, Tautologietest, Boolesches AND (OR, ...) von zwei OBDDs. Diese Vorteile werden erkauft mit der Gefahr, daß die Größe der Repräsentation exponentiell in der Anzahl der verwendeten Variablen ist. Dies ist z.B. bei Multiplizierern immer der Fall. Eine "Explosion" der OBDDs kann man in vielen praktischen Fällen dadurch verhindern, daß man OBDD-Algorithmen sehr sorgfältig und problemangepaßt entwirft und auch dynamisch versucht, die Repräsentationsgröße zu reduzieren. Eine andere Möglichkeit besteht darin, nach alternativen Darstellungen zu suchen. Hier gibt es verschiedene Ansätze, die man grob in folgende Richtungen einteilen kann: einmal wird versucht, die strukturellen Eigenschaften zu lockern (z.B. Übergang von Ordered zu Free BDDs); zum anderen werden neben der Shannon-Zerlegung, die zur BDD-Repräsentation führt, andere Zerlegungen untersucht. In diesem Zusammenhang sind EXOR-basierte Zerlegungen betrachtet worden. Sie haben schließlich zur Einführung der Ordered Kronecker Functional Decision Diagrams (OKFDDs) geführt. EXOR-basierte Zerlegungen korrespondieren in natürlicher Weise zu Synthesemethoden, die EXORs als Grundgatter zulassen.

Auch wenn die Logiksynthese die Integration mehrerer Optimierungsziele wie Zeitverhalten oder Testbarkeit erlaubt, kann es trotzdem notwendig sein, im Rahmen einer Nachbearbeitung gezielt Verbesserungen herbeizuführen. Als bekanntes Beispiel sei hier die Möglichkeit testbarkeitserhaltender Transformationen, die einerseits die Testbarkeit bewahren und andererseits die Fläche reduzieren, erwähnt. Ansätze, dieses Konzept auch in Richtung anderer Optimierungsziele weiter auszubauen, sind an mehreren Stellen unabhängig voneinander zu beobachten.

Ausgehend von den bereits erzielten Ergebnissen werden im Bereich der Logiksynthese folgende Schwerpunkte gesetzt:

Verwendung von EXOR als Grundgatter (neben AND, OR, NOT) bei der (zwei- und mehrstufigen) Schaltkreissynthese unter Beachtung der Optimierungsziele Zeit, Fläche und Testbarkeit

Qualitätsverbesserung von synthetisierten Schaltkreisen durch Anwendung von lokalen Transformationen während und nach der Synthese

Zur Darstellung und Manipulation von Booleschen Funktionen werden in modernen Werkzeugen des Schaltkreisentwurfs Decision Diagrams eingesetzt. Es hat sich gezeigt, daß die Klasse der Ordered Kronecker Functional Decision Diagrams (OKFDDs) besonders effizient ist.

Das Software-Paket PUMA zur Verwaltung von OKFDDs wurde bereits vor Beginn des Projektes entwickelt und wird heute vielfach verwendet. Dazu gehören nicht nur Anwendungen aus dem Bereich des Projektes und des eigenen Lehrstuhls. Auch Forschungsgruppen an anderen Universitäten und aus der Industrie setzten PUMA bereits ein.

PUMA ist frei verfügbar und kann über FTP von dem Server ftp.informatik.uni-freiburg.de in dem Verzeichniss pub/puma, oder direkt über die WWW-Seite mit der Dokumentation von PUMA bezogen werden.