Wer die zentrale Hardware eines Computers entwirft, muß bis- lang den Konflikt der Ziele Arbeitsgeschwindigkeit und Vielseitigkeit bewältigen. Entweder konstruiert er einen Mikrochip, der zahlreiche unterschiedliche Aufgaben relativ langsam bewältigt, oder aber einen sehr schnellen, aber auf eine einzige Anwendung beschränkten integrierten Schaltkreis (application-specific integrated circuit, ASIC).

Zur ersten Kategorie gehören die Mikroprozessoren der Personal Computer wie der Pentium von Intel oder der PowerPC-Chip von Motorola. Über ein breites Sortiment von Instruktionen kann man sie anweisen, nahezu jede logische oder mathematische Operation auszuführen, die überhaupt programmierbar ist. Der Pentium-Prozessor etwa wurde weder für eine bestimmte Textverarbeitungs-Software noch für irgendein Computerspiel konzipiert; gleichwohl ist er imstande, all diese Programme abzuarbeiten.

Hingegen kann ein ASIC nur ein bestimmtes Problem lösen – aber das schneller, billiger und mit geringerem Stromverbrauch und Platzbedarf als ein programmierbarer Chip. So bringt der Graphikprozessor eines PC Linien und Bilder zehn- bis hundertmal so schnell auf den Bildschirm wie der zentrale Prozessor selbst.

Beim Entwurf eines integrierten Schaltkreises sind außerdem die hohen Fixkosten zu berücksichtigen. Ein gut konstruierter ASIC löst mit Bravour das Problem, für das er gebaut ist; doch falls sich die Aufgabenstellung nachträglich auch nur geringfügig ändert, ist er im allgemeinen unbrauchbar. Und selbst wenn auch die Änderung am Entwurf des Chips nur geringfügig ist, muß man den kompletten Aufwand für die Umsetzung vom modifizierten Plan bis zum fertigen Produkt aufs neue leisten. Deshalb muß sich ein solcher Schaltkreis schon bei einer relativ kleinen Stückzahl bezahlt machen.

Nun eröffnet eine Neuentwicklung einen dritten Weg: große, schnelle, umprogrammierbare Gattermatrizen (field-programmable gate arrays, FPGAs). Gatter (gates) sind die Elementarbausteine eines Rechenwerks: Sie nehmen jeweils zwei (oder mehr) Bits an Information auf, verknüpfen sie gemäß einer Regel und geben als Ergebnis eines wieder aus. Damit realisieren sie elementare logi-sche Operationen wie UND, ODER und NICHT. Mehrere Gatter wirken zusammen, um beispielsweise mehrstellige Binärzahlen zu addieren oder zu vergleichen (Spektrum der Wissenschaft, Januar 1997, Seite 78).

In klassischen programmierbaren Schaltkreisen gibt es für jede solche Operation einen logischen Block: eine fest verdrahtete Gattergruppe. Wenn beispielsweise im Ablauf eines Programms zwei Zahlen zu addieren sind, fließen die zugehörigen Daten von zentralen Registern ins Addierwerk. Bevor die Summe weiterverarbeitet wird, muß sie zurück ins Register fließen; erst dann schaltet die Steuereinheit den Weg in den Block frei, der den nächsten Befehl im Programm ausführt. Hingegen liegen in einem ASIC die Blöcke so hintereinander, wie es dem – festliegenden – Gang der Rechnung entspricht. Wenn zwei Zahlen zu addieren sind und die Summe mit einer dritten zu vergleichen ist, fließen die Daten aus einem Addierblock auf einer vorher festgelegten Leitung – ohne Umwege und Schaltvorgänge – in einen Vergleichsblock.

Ein FPGA ähnelt nun, oberflächlich betrachtet, einem ASIC: Es besteht aus lauter logischen Blöcken, die in einer Matrix (einem array) aus Zeilen und Spalten angeordnet und mit manchen ihrer nächsten Nachbarn verbunden sind (Bild 1). Während aber bei einem ASIC die Art jedes Blocks und seine Verbindungen bei der Herstellung ein für allemal festgelegt werden, lassen sich diese Merkmale bei einem FPGA mehrfach und auf unterschiedliche Weise während des Betriebs durch Signale von außen verändern (Bild 2).

Die ersten Chips dieser Art benötigten für diesen internen Umbau einige Sekunden oder noch länger. Das reichte aus, um alternative Designs von Schaltkreisen zu testen oder um schon kommerziell eingesetzte Prozessoren dieser Art alle paar Monate mit einer neuen Version des in ihnen realisierten Algorithmus zu versehen. Aber erst mit der Entwicklung extrem schnell schaltbarer FPGAs ergeben sich völlig neue Anwendungsmöglichkeiten. Die Umstellung dauert bei den neueren Modellen ungefähr eine Millisekunde; wir erwarten, daß sie in zwei Jahren noch zehnfach rascher gelingen wird. Letztlich werden Rechner ihre Hardware nahezu kontinuierlich den Eingabedaten und ihren Arbeitsbedingungen anpassen können.


Ein Grundmuster, zahlreiche Varianten

Bei aller Vielfalt in den Einzelheiten sind FPGAs nach einem einheitlichen Bauplan konstruiert: Sie bestehen aus einer großen Anzahl konfigurierbarer logischer Blöcke sowie einem Netz von Leitungen, das jedes angeforderte Muster von Verbindungen zwischen den Blöcken bereitstellen kann. Dafür stehen an den Kreuzungspunkten der Leitungen Schalter zur Verfügung, die durch externe Signale betätigt werden (siehe Kasten auf dieser Seite). Es gibt grobkörnige FPGAs mit relativ wenigen, leistungsfähigen Blöcken – etwa solchen, die zwei Zahlen addieren oder vergleichen können – und feinkörnige mit sehr vielen primitiven Blöcken; im Extremfall ist ein Block mit dem Vergleichen zweier Bits voll ausgelastet und somit nichts weiter als ein einzelnes logisches Gatter. Es hängt von der zu lösenden Aufgabe und der für den Entwurf verfügbaren Zeit ab, ob ein grob- oder ein feinkörniges FPGA geeigneter ist.

Die neue Technik ist auf vielerlei Weise nutzbar. Am einfachsten ist wohl das Hin- und Herschalten zwischen mehreren Funktionen auf Befehl. Dabei erledigt die Hardware, was ansonsten geschieht, wenn man auf einem PC ein Programm beendet und ein anderes aufruft. Wenn sie dafür mehrere Sekunden braucht, kann das durchaus akzeptabel sein. Schnellere FPGAs lassen sich für jeden Arbeitsschritt innerhalb eines Programms oder für das abwechselnde Bedienen konkurrierender Anforderungen (time-sharing) umstrukturieren. Dabei entsteht bisweilen der Eindruck, der Chip übe all die verschiedenen Funktionen zugleich aus.

Nach diesem Konzept haben wir ein Videoübertragungssystem konstruiert, das sich selbst viermal pro Einzelbild rekonfiguriert und somit nur einen Chip anstelle von vier ASICs benötigt. Das FPGA speichert das ankommende Signal und wendet zwei Bildbearbeitungsprozesse darauf an, bevor es sich schließlich in ein Modem verwandelt und das Resultat weiterleitet (Bild 4).

Die anspruchsvollste, aber auch weitreichendste Entwicklung zielt auf Hardware, die sich während der Abarbeitung eines Programmes selbst optimiert. Ein Schaltkreis für Bilderkennung zum Beispiel könnte an sich Feineinstellungen vornehmen, während er eine Szene analysiert. Kommt darin etwa ein Lastwagen vor, sollten sich die Bausteine einer Schaltung, die ansonsten der Verfolgung schneller Flugzeuge oder langsamer Fußgänger dienen, auf Landfahrzeuge einstellen. Durch eine so radikale Abkehr von der traditionellen Denkweise, welche die Hardware als gegeben voraussetzt, können elektronische Systeme zugleich schneller und vielseitiger werden als solche mit herkömmlichen Mikroprozessoren oder maßgeschneiderten Chips.

Mustervergleich

Besonders aussichtsreich scheint der Einsatz dieser Technik beim automatischen Mustervergleich; das ist die Technik, die unter anderem zur Handschriftenerkennung, zur Identifizierung von Gesichtern (Spektrum der Wissenschaft, April 1992, Seite 18), zum Auffinden von Information in Datenbanken und zur Zielfindung in Waffensystemen eingesetzt wird. Die elementare Operation ist der Vergleich einer gegebenen Bitfolge – die ein Bild, einen Text oder andere Daten repräsentiert – mit einer Reihe von gespeicherten Vorlagen. Ein Muster gilt als identifiziert, wenn die Anzahl der mit einer der Vorlagen übereinstimmenden Bits einen bestimmten Schwellenwert überschreitet.

Bei der militärischen Zielerkennung – einer Aufgabe, die einige unserer ersten Versuche motivierte – ist das Schwierigste, das aktuelle Eingabebild hinreichend schnell mit Tausenden von Vorlagen zu vergleichen, zum Beispiel verschiedenen Ansichten eines bestimmten Panzertyps. Jedes Bild besteht aus einigen hunderttausend Pixeln (Bildelementen), und ein Ziel kann an jeder Position im Bild erscheinen, was die Zahl der Vergleichsoperationen nochmals in die Höhe treibt. Insgesamt ist für militärische Anforderungen eine Rechenleistung von mehreren Billionen Operationen pro Sekunde (Teraflops) erforderlich.

Mit Unterstützung der Forschungsagentur des amerikanischen Verteidigungsministeriums (DARPA) haben wir einen Prototypen gebaut, der mit erheblich weniger Hardware auskommt als bisherige Zielfindungssysteme, weil diese sich selbsttätig der jeweiligen Vorlage anpaßt. Viele der Pixel einer typischen Vorlage tragen nämlich nicht zum Resultat des Vergleichs bei (Bild 3); also sollte die Maschine keine Zeit auf ihre Verarbeitung verschwenden. Aber die vernachlässigbaren Pixel sind in jeder Vorlage andere. Ein konventioneller Prozessor müßte für jedes Pixel einzeln entscheiden, ob er es in den Vergleich einbezieht, aber diese Entscheidung kostet ebensoviel Zeit wie der Vergleich selbst. Hingegen bearbeitet ein FPGA die irrelevanten Pixel erst gar nicht, weil zu ihnen keine Leitung geschaltet ist.

Man kann noch weiter gehen und Ähnlichkeiten zwischen verschiedenen Vorlagen ausnutzen. Dabei bearbeitet die Hardware mehrere von ihnen parallel; Pixel, die in allen Vorlagen gleich sind, vergleicht ein Gatter ein für allemal mit dem aktuellen Zielphoto und bringt das Ergebnis in die Berechnung zu allen Vorlagen ein.

Datenverschlüsselung

Kürzlich haben wir, ebenfalls mit Unterstützung der DARPA, den Prototyp eines Codierungssystems entwickelt. Es arbeitet nach dem DES-Verfahren, dem data encryption standard, der vor allem im Datenverkehr unter Banken verwendet wird und vor wenigen Jahren einem großangelegten Versuch, ihn zu knacken, widerstanden hat (Spektrum der Wissenschaft, Mai 1993, Seite 19). Beim Verschlüsseln mit DES wird der Datenstrom in Stücke zu 64 Bit zerlegt; auf jedes dieser Stücke werden 16 Transformationen hintereinander angewandt. Eine Transformation besteht darin, die Bitfolge auf komplizierte Weise mit einem sogenannten Teilschlüssel zu mischen; die 16 Teilschlüssel wiederum sind Bitfolgen, die aus dem geheimzuhaltenden, 56 Bit langen Hauptschlüssel hergeleitet werden. Für eine vertrauliche Datenübertragung sind also im allgemeinen zunächst die Teilschlüssel zu erzeugen und dann auf sämtliche 64-Bit-Stücke des zu übertragenden Textes anzuwenden.

Ein geeignetes Programm berechnet zunächst die Teilschlüssel und paßt hernach die Schaltkreise eines FPGAs optimal an diese an. Somit hat dessen Hardware nur noch die eigentliche Anwendung des DES zu erledigen und kann deswegen erheblich weniger aufwendig sein; unser Prototyp benötigt nur 13000 statt zuvor 25000 logische Gatter. Wenn der Hauptschlüssel auszuwechseln ist, etwa aus Sicherheitsgründen oder weil die nächste Nachricht an einen anderen Empfänger geht, berechnet das System die neuen Teilschlüssel und lädt das zugehörige Schaltschema in den konfigurierbaren Chip.


Absehbare Entwicklungen

Sowie die Hardware eines Computers sich von Fall zu Fall der Struktur heterogener externer Daten anpassen kann, gewinnt er eine enorme, sonst nicht zu erzielende Flexibilität. Außer Zielerkennung und Datenverschlüsselung sind viele andere Anwendungen denkbar, etwa in der digitalen Telekommunikation, beim automatischen Design und zur Filterung von Radarsignalen.

Gegenwärtig stecken Entwicklung und Anwendung konfigurierbarer Schaltkreise noch in den Anfängen. Obwohl Gerald Estrin von der Universität von Kalifornien in Los Angeles das Prinzip bereits Ende der sechziger Jahre zur Diskussion gestellt hatte, gab es erst vor wenigen Jahren Demonstrationsmodelle, und die derzeit verfügbaren Chips mit bis zu 100000 Logikelementen schöpfen die Möglichkeiten dieser Technologie nicht annähernd aus. Künftige FPGAs werden weit größer sein; auch für sie gilt – wie bei den klassischen integrierten Schaltkreisen – der Erfahrungssatz, daß sich die Anzahl der Elemente pro Chip etwa alle 18 Monate verdoppelt. Noch vor dem Ende dieses Jahrzehnts erwarten wir wandlungsfähige Prozessoren mit einer Million logischen Elementen und einem größeren Spektrum von hochkomplexen Algorithmen, so für die Bearbeitung und Übertragung von Bild- und Tondaten.

Einstweilen sind FPGAs nicht für alle Rechenoperationen geeignet. Sie sind sehr leistungsfähig bei Operationen mit einzelnen Bits, wie sie typisch für Mustervergleich und Arithmetik mit ganzen Zahlen sind; aber zum Beispiel bei der Multiplikation von Gleitkommazahlen oder mit hoher Genauigkeit bleiben sie hinter den eigens dafür optimierten Prozessoren zurück. Außerdem gibt es auf den gegenwärtigen FPGAs nur sehr wenig internen Speicherplatz für Zwischenergebnisse. Deshalb erfordern viele Anwendungen große externe Datenspeicher; die Kommunikation mit ihnen kostet Zeit, Material und Energie.

Aber an Abhilfe für alle genannten Schwächen wird schon gearbeitet. So haben André DeHon und Thomas F. Knight vom Massachussetts Institute of Technology in Cambridge einen Chip konzipiert, der in einem Speicherblock verschiedene, vom Programm per einfachen Befehl abrufbare Konfigurationen bereithält. Während eines einzigen Taktzyklus – innerhalb von 10 bis 100 Nanosekunden – soll der Schaltkreis von der gerade genutzten zu einer anderen Konfiguration übergehen, ohne Zwischenergebnisse zu löschen.

Brad L. Hutchings von der Brigham-Young-Universität in Provo (Utah) hat einen wandlungsfähigen Schaltkreis mit einem gewöhnlichen Mikroprozessor zu einem Gerät neuen Typs gekoppelt: Der Computer mit variablem Befehlssatz (dynamic instruction set computer, DISC) demonstriert, welche Möglichkeiten das automatische Nachladen vorgespeicherter Konfigurationen bietet. Wenn das FPGA während des Programmablaufs feststellt, daß es für die nächste Aufgabe eine bestimmte Schaltung benötigt, ruft es sie - wenn es sie nicht schon vorrätig hat – aus einer umfänglichen Datenbank ab, baut sich oder seinesgleichen um und rechnet weiter (Bild 5). Für den Programmierer ist das Aktivieren einer vorgespeicherten Schaltung sehr ähnlich dem Aufruf eines üblichen Unterprogramms.

Eine Gruppe an der Technischen Universität von Virginia in Blacksburg unter Leitung von Peter M. Athanas arbeitet an einem Verfahren namens Wormhole (Wurmloch), das vor allem für das Parallelrechnen auf voneinander unabhängigen Computern vorgesehen ist. Nach ihrem Konzept ist das handelnde Subjekt nicht mehr – wie üblich – das Programm, sondern der Datenstrom: Er eilt nicht nur von Rechner zu Rechner mit der Aufforderung "bearbeite mich", sondern windet sich auch wie ein Wurm durch einen Chip und macht sich dort die Schaltung zurecht, die er gerade braucht.

John Wawrzynek und seine Kollegen von der Universität von Kalifornien in Berkeley schließlich beschäftigen sich ebenfalls mit Kombinationen von Mikroprozessoren und FPGAs, insbesondere auf ein und demselben Chip. Ihnen geht es vor allem um die Entwicklung spezieller Compiler, die aus gewöhnlichem Programmcode statt einer Folge von Maschinenbefehlen eine Mixtur aus Maschinenbefehlen und FPGA-Konfigurationen machen und so die Systemleistung insgesamt optimieren.

FPGAs werden gewiß niemals den Allzweckprozessor überflüssig machen; doch das Konzept wird höchstwahrscheinlich mehr und mehr in neue Hochleistungsrechner eingehen. Die Flexibilität der FPGAs prädestiniert sie für Algorithmen, bei denen eine schnelle Anpassung an die Eingabedaten gefordert ist.

Zudem wird sich die Trennlinie zwischen programmierbaren Prozessoren und FPGAs verwischen: Künftige konfigurierbare Chips werden über einen großen internen Speicher und Multiplikationseinheiten verfügen, etliche Mikroprozessoren der nächsten Generation in begrenztem Umfang konfigurierbar sein. Des weiteren dürften Computer sich Schaltungsmuster nach Bedarf aus dem Internet holen, so wie heute schon Unterprogramme. Wir zweifeln nicht, daß binnen zehn Jahren in manchen Rechnern programmierbare und konfigurierbare Hardware eng zusammenwirken werden.

Literaturhinweise

- A Dynamic Instruction Set Computer. Von M. J. Wirthlin und B. L. Hutchings in: Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, April 1995. IEEE Computer Society Press, 1995.

– A First Generation DPGA Implementation. Von E. Tau, D. Chen, I. Eslick, J. Brown und A. DeHon in: Proceedings of the Third Canadian Workshop on Field-Programmable Devices, Seiten 138 bis 143, Mai 1995.

– Configurable Computing Solutions for Automatic Target Recognition. Von John Villasenor, Brian Schoner, Kang-Ngee Chia, Charles Zapata, Hea Joung Kim, Chris Jones, Shane Lansing und Bill Mangione-Smith in: Fourth IEEE Symposium on FPGAs for Custom Computing Machines, April 1996. IEEE, 1996.

– Wormhole Run-Time Reconfiguration. Von Ray Bittner und Peter Athanas in: FPGA '97: ACM/SIGDA International Symposium on Field Programmable Gate Arrays. Special Interest Group on Design Automation (SIGDA), Association for Computing Machinery, 1997

Kasten: Chips mit programmierbarer Verdrahtung

Eine programmierbare Gattermatrix (ein FPGA) enthält in einem regelmäßigen Gitter angeordnete logische Blöcke (violett), die ihrerseits aus elementaren Funktionseinheiten (gates) wie UND-, ODER- und NICHT-Gattern zusammengesetzt sind. Die Verbindungen zwischen den Blöcken oder zu externen Bausteinen wie Speicherchips oder Mikroprozessoren sind nicht – wie sonst üblich – fest verdrahtet, sondern wählbar: In den Chip eingebaut sind horizontale und vertikale Leitungsstränge, die je nach Bedarf zu Verbindungen zusammengeschaltet werden (blaue Linien). Mehrere Firmen, darunter Xilinx und Altera, haben Geräte mit 100000 gleichartigen Gattern entwickelt.


Aus: Spektrum der Wissenschaft 8 / 1997, Seite 44
© Spektrum der Wissenschaft Verlagsgesellschaft mbH