2 Methoden zur Reduktion von Konfigurationsdaten

2.1 Wildcard Registers

Das Ziel dieser Kompressionsmethode sind Xilinx FPGAs der Serie XC6200. Sie besitzen spezielle, als Wildcard Registers bezeichnete, Hardware, die als De-kompressor angesehen werden kann. Die Serie XC6200 sind SRAM-basierte Sea-Of-Gates FPGAs, deren schematischer Aufbau beispielhaft in Abbildung 1 dargestellt ist. Durch die Benutzung der Wildcard Register k ¨ onnen mehrere Zel-

len des FPGA gleichzeitig konfiguriert werden. Wenn das Row Wildcard Register den Wert 010001 hat und die Adresse des Row Address Decoder den Wert 110010 hat, dann werden gleichzeitig die Zeilen 100010, 100011, 110010 und 110011 uberall dort wo im Row Wildcard Register ge¨ andert. Das wird erreicht, indem ¨

eine 1 steht, der entsprechende Wert im Row Address Decoder egal ist. [2] Die Effektivit¨ at dieser Kompressionsmethode h¨ angt unmittelbar von der Anzahl der so genannten Don’t Care bits in einer Konfiguration ab. In [6] wird ein effektiver Algorithmus vorgestellt um mehr Don’t Care bits zu finden. Damit k ¨ onnen Konfigurationen mit einem Faktor von bis zu 7 komprimiert werden.

2.2 Allgemeine Kompressionsverfahren

Allgemeine Kompressionsverfahren k ¨ onnen nur bedingt zur Reduzierung von

Konfigurationsdaten verwendet werden, da eventuell zur Dekomprimierung komplexe Hardware n ¨ otig w¨ are. So wird in [1] eine verzeichnisbasierte Methode vorgestellt, die auf dem Lempel-Ziv-Algorithmus [12] basiert. Um die ben ¨ otigte Dekompressionshardware m ¨ oglichst gering zu halten, muss das Verzeichnis mit in den Konfigurationsspeicher aufgenommen werden, wodurch eine negative Kompression erreicht wird. Durch die vorgestellte Methode kann die Verzeichnisinformation so weit reduziert werden, dass Kompressionsraten zwischen 11% und 41% erreicht werden k ¨ onnen.

Ein spezielles Kompressionsverfahren f ¨ ur Xilinx Virtex FPGAs wurde in [7]

vorgestellt. Die Struktur der FPGAs der Virtex-Serie impliziert eine gewisse Regularit¨ at der Konfigurationsdaten. Die Konfiguration erfolgt in so genannten Frames, die zu großen Teilen aus 18 Bit f ¨ ur einen I/O-Block, N×18 Bit f ¨ ur N

Logik-Bl ¨ ocke und wieder 18 Bit f ¨ ur einen I/O-Block bestehen. Das vorgestell-

te Verfahren nutzt Regularit¨ at innerhalb eines Frames ebenso wie Regularit¨ at zwischen Frames aus. Es verwendet ebenso die bereits vorgestellten Techniken der Wildcard Register und der Lempel-Liv-Komprimierung, allerdings kommt hier LZ77 zum Einsatz. Die Methode erlaubt einen Kompressionsfaktor von 4. Das ist eine Verbesserung um den Faktor 2 gegen ¨ uber einer Komprimierung mit gzip.

2.3 SRAM-FPGAs mit eingebetteten Mikroprozessoren

Moderne FPGAs besitzen h¨ aufig einen eingebetteten Mikroprozessor, der ebenfalls zur Dekompression von Konfigurationsdaten benutzt werden kann. Die ben ¨ otigte Architektur, um einen solchen Prozessor zu benutzen, besteht aus einer internen Konfigurationsschnittstelle (die implementierte Logik hat dadurch Zugriff auf die Konfigurationsdaten, ICAP bei Xilinx), einem Mi-kroprozessor und einer so genannten Configuration IP, die die ¨ Ubergabe der

dekomprimierten Daten vom Mikroprozessor zur Konfigurationsschnittstelle regelt. Die Configuration IP kann mit Hilfe der im FPGA zur Verf ¨ henden Logik-Bl ¨ ocke realisiert werden. Sie muss dann w¨ ahrend der Startphase des Systems unkomprimiert

in den FPGA geladen werden. Danach k ¨ le weiteren Konfigurationsdaten komprimiert ¨ partielle Rekonfiguration verf ¨ Methode, verspricht Kompressionsraten von bis zu 82%. 2.4 Wiederverwendung von Konfigurationsdaten

Die bisher vorgestellten Kompressionsverfahren versuchten, z.B. durch verzeichnisbasierte Kompressionsverfahren, Redundanzen innerhalb eines Konfigurationsdatenstromes zu eliminieren. Die Wiederverwendung von Konfigurationsdaten zielt auf die Eliminierung von Redundanzen zwischen mehreren Konfigurationsdatenstr ¨ omen ab. Diese Kompressionsmethode findet in dynamisch rekonfigurierbaren FPGAs Anwendung.

In [3] werden Methoden zur Datenkompression innerhalb eines Konfigurationsdatenstromes vorgestellt, die effektiver arbeiten, als die bereits vorgestellten. Außerdem werden Verfahren entwickelt, die geeignet sind um Redundanzen zwischen Konfigurationsdatenstr ¨ omen zu vermeiden und dadurch bedeutend h ¨ ohere Kompressionsraten erreichen.

Die Redundanzen innerhalb eines Datenstroms werden durch die Berechnung eines so genannten reference frame vermieden, da nur noch die Abweichungen von diesem Frame ¨ ubertragen werden, die dann wiederum mit einem Lempel-Ziv-Verfahren komprimiert werden. Redundanzen zwischen Datenstr ¨ omen konnen minimiert werden, indem

nur die Differenz zwischen der aktuellen Konfiguration und der neuen Konfiguration ¨ ubertragen wird, die dann wiederum mit einem anderen Verfahren komprimiert werden kann.

2.5 Hyperkonfigurierbarkeit

In einem System implementierte Anwendungen ben ¨ otigen unter Umst¨ anden nicht ¨ uber die gesamte Laufzeit die komplette Flexibilit¨ at, die aktuelle rekonfigurierbare Systeme bieten. Hyperrekonfigurierbare Systeme stellen ein zweischichtiges Modell dar, mit dem die Konfigurierbarkeit eines Systems durch einen so genannten Hyperkontext eingeschr¨ ankt werden kann.[4] Ein Algorithmus zerf¨ allt damit in eine Folge von Hyperkontexten h i mit i = 1 . . . r, in denen einzelne Rekonfigurationen mit verschiedenen Ressourcenanforderungen c j mit j = 1 . . . n stattfinden.[5] Ein Algorithmus ben ¨ otigt somit die folgenden Ressourcen :

h 1 c 1 . . . c i 1 h 2 c i 1 +1 . . . c i 2 . . . c i r−1 h r c i r−1 +1 . . . c n

F ¨ ur einen Algorithmus mit einer gegebenen Folge von Ressourcenanforderungen ergibt sich das Problem der Partition in Hyperkontexte. Dieses Problem ist NP-vollst¨ andig, f ¨ ur bestimmte hyperrekonfigurierbare Architekturen existieren jedoch polynomiell beschr¨ ankte Algorithmen.

3 Selbstrekonfiguration

Die bisher vorgestellten Methoden implizieren jeweils einen vorab synthetisierten Konfigurationsdatenstrom, durch den zur Laufzeit die aktuelle Konfiguration ¨ uberschrieben wird.

In der Softwareentwicklung wurde das Prinzip der Selbstmodifikation be-

nutzt um gr ¨ oßere oder komplexere Anwendungen auszuf ¨ genug Platz im Hauptspeicher w¨ are. Eine M ¨ keit in Hardware zu erreichen wurde in [9] vorgestellt. Diese Architektur erlaubt Kontextwechsel und Zugriffe auf den Konfigurationsspeicher innerhalb eines Taktes. Die Methode des (selbst-)rekonfigurierenden endlichen Automaten [11] bietet einen allgemeineren Ansatz, bei der die Anwendung keinen technologieabh¨ angigen Konfigurationsdatenstrom erzeugen muss.

3.1 (Selbst-)rekonfigurierbarer endlicher Automat

Das Modell des endlichen Automaten wird um das Konzept der (Selbst-)rekonfiguration erweitert. Ein Mealy-Automat kann durch 6-Tupel dargestellt werden : M = {I, O, S, S 0 , F, G}

• S ist eine endliche Menge interner Zust¨ ande

• I ist eine endliche Menge von Eingabezust¨ anden

• O ist eine endliche Menge von Ausgabezust¨ anden

• F(i, s) ist eine Abbildung vom aktuellen Gesamtzustand (Paar aus Einga-bezustand und internem Zustand) auf den internen Folgezustand (F ⊆ I × S × S)