Kurzinfo Der Entwurf integrierter Schaltungen unterlag in den letzten 30 Jahren einem ganz enormen Automatisierungsprozess, der nicht zuletzt auch wegen der hohen Integrationsdichte unumgänglich war. Die Informatik steuerte mit ihren Methoden einen ganz wesentlichen Beitrag dazu bei, was im folgendem am Beispiel des „Technology Bindings" illustriert werden soll.

Erläuterung

Auf der einen Seite hat man für anwendungsspezifische Schaltungen zunächst Entwurfstile entwickelt, die einen hohen Automatisierungsgrad zulassen. Diese reichen von Standardzelltechnologien über sog. maskenprogrammierbare Chips (MPGAs, „mask programmable gate arrays") bis hin zu elektronisch konfigurierbaren Chips den sog. FPGAs („field programmable gate arrays").

Bei Standardzelltechnologien wird vom Hersteller ein Katalog von sog. Standardzellen vorgegeben, die in Reihen plaziert und automatisch verdrahtet werden. Maskenprogrammierbare Chips werden zu einem großen Teil unabhängig vom Kunden vorgefertigt. Ihre endgültige Funktionalität wird durch Aufbringen kundenspezifischer Verdrahtungslagen realisiert. Bei den FPGAs wird die Realisierung sogar durch reine Programmierung von Schaltern oder Antifuse-Verbindungen vom Kunden direkt vorgenommen. Eine Übersicht dazu gibt Abb. 1.

Abb. 1. ASIC-Technologien

Das Ende der Automatisierungskette bilden somit je nach Zieltechnologie dedizierte Werkzeuge, die die Bausteine zuordnen und die Verdrahtung realisieren. Sie erzeugen entweder alle Maskendaten, die Maskendaten der noch zu fertigenden Layer oder einfach nur Programmierbits.

Auf der anderen Seite der Automatisierungskette stehen Hardwarebeschreibungssprachen (HDLs). Diese erlauben nicht nur eine Modellierung des Verhaltens zu Simulationszwecken, sondern können, zumindest wenn man sich bei der Modellierung auf eine gewisse Teilmenge des Sprachumfangs beschränkt, auch automatisch in optimierte, synchrone Schaltwerke übersetzt werden. Das Resultat ist dann ein Schaltwerk, bestehend aus Registern, die durch kombinatorische Logik über den booleschen Grundoperationen miteinander verknüpft sind. Abbildung 2 zeigt exemplarisch, wie boolesche Gleichungen zunächst über einige technologieunabhängige Transformationen vereinfacht, und in ein sog. boolesches Netzwerk umgesetzt werden.

Abb. 2. Technology Binding im Syntheseprozess

Unter Technology Binding oder Technology Mapping versteht man nun die Aufgabe, das boolesche Netzwerk, bzw. die dadurch spezifizierte Schaltfunktion, optimal unter Verwendung der Vorgaben der Zieltechnologie zu realisieren. Kostenmaße sind dabei Fläche, Verzögerungszeit und Leistungsaufnahme der Realisierung. Man kann das Problem, wenn dieser Vergleich überhaupt erlaubt ist, als Parallele zur Kodeerzeugung und Optimierung bei Übersetzern sehen, und in der Tat stammten die ersten Methoden aus dem Bereich des Übersetzerbaus [3].

Verfahren zum Technology Binding

Die meisten Verfahren zum Technology Binding orientieren sich an der Struktur des schon optimierten booleschen Netzwerkes. Man kann das Problem, das Netzwerk durch ein äquivalentes Netzwerk über den Bausteinen der Zieltechnologie zu realisieren, als eine spezielle Form eines Graph-Überdeckungsproblems auffassen: Da die Funktion jedes Bausteins der Zieltechnologie als Schaltfunktion ebenfalls durch ein boolesches Netzwerk dargestellt werden kann, genügt es, das gegebene Netzwerk vollständig durch Bausteinnetzwerke zu überdecken. Abbildung 3 zeigt zwei Beispiele solcher Überdeckungen. Die grau unterlegten Teilnetzwerke entsprechen Bausteinen der Zieltechnologie. Man erkennt auch, dass die eine Überdeckung kantendisjunkt, die andere überlappend ist, wobei die Überlappungen gerade durch die dunkelgrau unterlegten Teilnetzwerke angedeutet sind.

Abb. 3. Technology Binding durch Überdecken

Es wird an diesem Beispiel schon klar, dass es sehr viele Überdeckungen geben kann, und dass es im Allgemeinen nicht leicht ist, kostenminimale Überdeckungen zu bestimmen. In der Tat sind, je nach Wahl der Zielfunktion und der Einschränkung des Suchraums auf allgemeine oder überlappungsfreie Überdeckungen, die meisten Probleme NP-vollständig. Lediglich bei einer lastunabhängigen Modellierung der Schaltverzögerung und bei der Beschränkung auf Zellen mit einem Ausgang lässt sich das Problem, eine verzögerungsminimale Überdeckung zu bestimmen, in Polynomzeit lösen.

Im überlappungsfreien Fall lassen sich mehr Kostenmaße in Polynomzeit minimieren. Die Algorithmen selbst basieren auf dynamischem Programmieren, und sollen hier nicht näher ausgeführt werden [2].

Geleitet von diesen komplexitätstheoretischen Einsichten hat man nun für viele Zieltechnologien clevere Heuristiken entwickelt, die gute Technology Bindings finden. So hat man sich in dem aus Berkley stammenden System SIS, dessen Methoden für viele kommerzielle Systeme Pate standen, für Standardzell- und MPGA-Zieltechnologien lediglich auf das Überdecken von Teilbäumen des Netzwerkes beschränkt, da dieses sog. Tree matching effizient durch dynamisches Programmieren lösbar ist [5].

Für FPGAs hat man hingegen spezielle Binding-Verfahren entwickelt, weil diese häufig sog. Lookup tables zur Realisierung von Grundfunktionen bereitstellen, d.h. man kann jede boolesche Funktion mit bis zu k Eingängen realisieren. Man hat also im Grunde eine sehr spezielle Form dieses Überdeckungsproblems vorliegen, da jedes Teilnetzwerk mit Ausgang u und höchstens k Eingängen durch einen Baustein realisiert werden kann. Hier wurden schon früh Verfahren gefunden, die verzögerungsminimale Überdeckungen in Polynomzeit berechnen können [1]. Darüberhinaus hat man gerade in diesem Bereich auch versucht, Bindings nicht rein an der Struktur des Ausgangsnetzwerks orientiert zu finden, sondern durch geschickte Dekomposition der Funktion selbst [7]. Die Fähigkeit, diese speziellen Graph-Überdeckungsprobleme effizient lösen zu können, ist jedoch nur die halbe Miete. Man muss natürlich auch in der Lage sein, für jeden Knoten des Netzwerks möglichst alle Teilnetzwerke mit diesem als Senke festzulegen, die durch einen Baustein der Zieltechnologie realisiert werden können. Dies ist relativ einfach bei vielen FPGAs als Zieltechnologie, wie oben schon erläutert. Liegt aber eine nichttriviale Zellbibliothek vor, ist das Problem sehr viel schwieriger. Zum einen sind die Kosten der Zellen in Bezug auf Fläche, Schaltverzögerung und Leistungsaufnahme sehr unterschiedlich, während bei Lookup tables die Kosten für jedes Teilnetzwerk gleich sind, zum anderen ist es nichttrivial zu entscheiden, ob ein gegebenes Teilnetzwerk durch Benutzung einer Zelle realisiert werden kann. So kann man etwa durch Koppeln von Eingängen oder Setzen von Eingängen auf konstante Werte mit einem einzigen Baustein mit k Eingängen auch Funktionen in weniger Eingängen realisieren. Abbildung 4 verdeutlicht dies für ein typisches CMOS-Komplexgatter.

Abb. 4. Konfigurierbare Funktionen

Es scheint zwar zunächst nicht besonders sinnvoll einen komplexeren Baustein als Ersatz für einen Baustein mit weniger Eingängen zu benutzen, es leuchtet aber ein, dass dies durchaus gewinnbringend geschehen kann, wenn man die Wahl hat, entweder einen großen Baustein mit ungenutzten Eingängen zu nehmen oder mehrere kleinere, um das gleiche Teilnetzwerk zu realisieren. Man steht damit vor dem Problem, für jedes Teilnetzwerk an einem Knoten u zu entscheiden, ob man die durch dieses Teilnetzwerk definierte Funktion durch Vertauschen und Negieren der Eingänge mit einer Funktion der Zellbibliothek zur Deckung bringen kann. Dieses Problem, das man auch als boolesches Matching bezeichnet, ist im Allgemeinen sehr schwierig zu lösen, weil man Äquivalenz von Formeln über dem Raum aller Umbenennungen von Variablen entscheiden muß. Die Lösung lässt sich durch die Benutzung von Signaturen [4] oder kanonische Repräsentanten [6] auf ein erträgliches Maß beschleunigen, wobei letztere Technik mehr Gewinn durch geeignete Vorverarbeitung der Bausteinkataloge bringt. Abbildung 5 zeigt an einem Beispiel, wie die Kanditatenauswahl durch boolesches Matching erfolgen kann.

Abb. 5. Boolesches Matching

Eingeschlossen in dieses Beispiel ist schließlich auch noch ein weiterer Freiheitsgrad, nämlich die Ausnutzung lokaler Don't cares. Im Allgemeinen sind nicht alle Eingangskombinationen an einem Teilnetzwerk über seine Umgebung einstellbar oder an den Primärausgängen des Schaltkreises beobachtbar. Solche lokalen Don't cares kann man mit geeigneten Datenstrukturen für kleinere bis mittelgroße Schaltungen berechnen, und damit den Suchraum bei der Kandidatenauswahl für das Überdeckungsproblem nochmals erweitern.

Ausblick

Aus den obigen Ausführungen wird klar, daß im Bereich des Werkzeuge zum Hardwareentwurf die Informatik mit ihren Methoden ganz entscheidend gefragt ist, um die erforderliche Performanz zusammen mit dem notwendigen Automatisierungsgrad zu gewährleisten. Technology Binding ist dabei nur eines von vielen Beispielen aus der Entwurfskette. Skizziert wurden lediglich die grundsätzlichen Methoden, viele von der gegeben Zieltechnologie stark abhängigen Optimierungstechniken mussten unerwähnt bleiben. Die direkte Einbeziehung der Technologie in die Synthesephase, also die Loslösung von einer strukturbasierten, technologiebezogenen Nachoptimierung, wurde bisher aus Komplexitätsgründen nur bei spezielleren Technologien gebührend beachtet und bleibt v. a. für Standardzell- und MPGA-Technologien ein aktuelles, und nach wie vor spannendes Problem.

Artikelanfang Seitenanfang

Literatur

Cong, J., Y. Ding: FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(1):1–12, 1994
Hinsberger, Uwe, Reiner Kolla: Optimal Technology Mapping for Single Output Cells. Proceedings of the 5th Great Lakes Symposium on 14–19, March 1995
Keutzer, K., DAGON: Technology Binding and Local Optimization by DAG Matching. Proceedings of the 24th Design Automation Conference (DAC87), 341–347, June 1987
Mohnke, Janett, Sharad Malik: Permutation and Phase Independent Boolean Comparison. Proceedings of the European Design Automation Conference (EDAC93), 86–92, 1993
Touati, H., C. Moon, R. Brayton, A. Wang: Performance-Oriented Technology Mapping. Proceedings of the MIT VLSI Conference, 1990
Uwe Hinsberger, Reiner Kolla: Boolean Matching for Large Libraries. Procceedings of the 35th Design Automation Conference, 206–211, June 1998
Wurth, B., K. Eckl, K. Antreich: Functional Multiple-Output Decomposition: Theory and an Implicit Algorithm. Proceedings of the 32nd Design Automation Conference, 54–59, 1995

Artikelanfang Seitenanfang

Autor & Copyright
Reiner Kolla
Lehrstuhl für Informatik V,
Bayerische Julius-Maximilians-Universität,
Am Hubland,
D-97074 Würzburg
kolla@informatik.uni-wuerzburg.de

Artikelanfang Seitenanfang