Technology Binding

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.

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.

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.

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.

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.

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. 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. 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.

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 oder kanonische Repräsentanten 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.

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.

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.

1. 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
2. Hinsberger, Uwe, Reiner Kolla: Optimal Technology Mapping for Single Output Cells. Proceedings of the 5th Great Lakes Symposium on 14-19, March 1995
3. Keutzer, K., DAGON: Technology Binding and Local Optimization by DAG Matching. Proceedings of the 24th Design Automation Conference (DAC87), 341-347, June 1987
4. Mohnke, Janett, Sharad Malik: Permutation and Phase Independent Boolean Comparison. Proceedings of the European Design Automation Conference (EDAC93), 86-92, 1993
5. Touati, H., C. Moon, R. Brayton, A. Wang: Performance-Oriented Technology Mapping. Proceedings of the MIT VLSI Conference, 1990
6. Uwe Hinsberger, Reiner Kolla: Boolean Matching for Large Libraries. Procceedings of the 35th Design Automation Conference, 206-211, June 1998
7. 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

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

© 2000 Informatik Spektrum, Springer-Verlag Berlin Heidelberg