Uni-Logo
English       Login
Rechnerarchitektur
        Startseite         |         Institut für Informatik         |         Technische Fakultät
 

Logiksynthese mit Funktionaler Dekomposition

| Beteiligte Mitarbeiter | Projektbeschreibung | Publikationen |


Beteiligte Mitarbeiter

Lehrstuhl für Rechnerarchitektur
Christoph Scholl, Prof. Dr.


Projektbeschreibung

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.



Publikationen
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