Abb. 1. ASIC-Technologien
Informatik-Lexikon
T
Technology Binding
Transaktionen, geschachtelte
|
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 BindingDie 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