Logiksynthese mit Funktionaler Dekomposition
| Beteiligte Mitarbeiter | Projektbeschreibung | Publikationen
|
| Lehrstuhl für Rechnerarchitektur | |
| Christoph Scholl, Prof. Dr. | |
Die grundsätzliche Aufgabe beim Entwurf einer Schaltung besteht darin, eine gegebene Schaltungsspezifikation in eine korrekte Schaltungsimplementierung umzusetzen. Ein Teilschritt in diesem Entwurfsablauf ist die Logiksynthese, die ausgehend von der Spezifikation, die der funktionale Entwurf liefert, eine geeignete Implementierung generiert. Ergebnis der Logiksynthese ist eine Netzlistenbeschreibung über einer bestimmten Menge von Grundzellen.
Der in diesem Projekt behandelte Themenkomplex ist im wesentlichen der kombinatorischen Logiksynthese zuzurechnen, d.h. der automatischen Synthese kombinatorischer Teilschaltungen (ohne speichernde Elemente).
Das hier betrachtete Verfahren zur mehrstufigen kombinatorischen Logiksynthese beruht auf der Durchführung rekursiver Zerlegungen der zu realisierenden Booleschen Schaltfunktion. Eine disjunkte Zerlegung einer Booleschen Funktion f mit den Eingangsvariablen x1, ..., xn ist eine Darstellung von folgender Form:
Die durch alpha und g angegebenen Blöcke werden dann rekursiv weiter zerlegt. Zur Reduzierung der Kosten der Realisierung sind Lösungen erstrebenswert, bei denen die Anzahl r von Zerlegungsfunktionen möglichst gering ist.
Ein Einsatzgebiet des angegebenen Verfahrens ist (wenn auch nicht ausschließlich) die Synthese von LUT (= look up table)-basierten FPGAs, bei denen Boolesche Funktionen bis zu einer bestimmten Anzahl von Eingängen durch eine einzige look up table realisiert werden können.
Die Hauptmerkmale des in diesem Projekt entwickelten Dekompositionsverfahrens sind die folgenden:
Identifizierung von Teillogik, die in mehreren Schaltungsteilen mit Vorteil verwendet werden kann. Dies gelingt durch Ausnutzung von Freiheiten bei der Wahl von Zerlegungsfunktionen. Bei der Realisierung von Funktionen mit mehreren Ausgängen wird darauf geachtet, daß möglichst viele gemeinsame Zerlegungsfunktionen berechnet werden.
Ausnutzung von Symmetrien.
Ausnutzung von don't cares bei partiellen Funktionen.
|
Paul Molitor, Prof. Dr., Christoph Scholl, Prof. Dr. Communication based multilevel synthesis for multi-output boolean functions Great Lakes Symposium on VLSI, 1994 |
|
Christoph Scholl, Prof. Dr., Paul Molitor, Prof. Dr. Efficient ROBDD based computation of common decomposition functions of multi-output boolean functions IFIP Workshop on Logic and Architecture Synthesis, 1994 |
|
Christoph Scholl, Prof. Dr., Paul Molitor, Prof. Dr. Efficient ROBDD based computation of common decomposition functions of multi-output boolean functions Logic and Architecture Synthesis, State-of-the-art and novel approaches, 1995 |
|
Christoph Scholl, Prof. Dr., Paul Molitor, Prof. Dr. Communication Based FPGA Synthesis for Multi-Output Boolean Functions Asia and South Pacific Design Automation Conference, 1995 |
|
Christoph Scholl, Prof. Dr. Mehrstufige Logiksynthese unter Ausnutzung funktionaler Eigenschaften Universität des Saarlandes, Ph.D. thesis, 1996 |
|
Christoph Scholl, Prof. Dr. Functional Decomposition with Integrated Test Generation GI/ITG Workshop ``Testmethoden und Zuverlässigkeit von Schaltungen und Systemen´´, 1997 |
|
Christoph Scholl, Prof. Dr., Stefan Melchior, Günter Hotz, Paul Molitor, Prof. Dr. Minimizing ROBDD Sizes of Incompletely Specified Functions by Exploiting Strong Symmetries Proceedings of the European Design and Test Conference, 1997 |
|
Christoph Scholl, Prof. Dr. Multi-output Functional Decomposition with Exploitation of Don't Cares In Proceedings of IWLS, 1997 |
|
Christoph Scholl, Prof. Dr. Multi-output Functional Decomposition with Exploitation of Don't Cares In Proceedings of DATE, 1998 |
|
Christoph Scholl, Prof. Dr., Dirk Möller, Paul Molitor, Prof. Dr., Rolf Drechsler, Prof. Dr. BDD Minimization Using Symmetries IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999 |