Hardware-Projekt HW01

- N a v i g a t i o n - - - - - - - -

- VI-ANEC

- Über das Institut

- Software-Projekte

- Hardware-Projekte

- Best-Paper-Best-Program-Awards

- Sponsoring

- Dienste

- Kontakt

Prüfe Eignung von CGP/CHP auf existierenden Standard- bzw. Prototyp-Hardware-Plattformen

Ziel ist die Prüfung der Eignung verschiedener Hardware-Plattformen für das Compiling Genetic Programming (CGP) bzw. die allgemeinere Formulierung als Compiling Heuristic Programming (CHP), für die ein eigenes Software-Projekt (SW02) existiert. Es soll ein Bewertungssystem entwickelt werden, mit dem die Eignung unterschiedlicher, auch zukünftiger Architekturen für CGP/CHP quantifiziert werden soll, gefolgt von Portierungen auf die am besten geeigneten Architekturen, sowie eingehende Tests und Anwendungen.

Die Performance eines CGP-Systems kann in dadurch gesteigert werden, indem auf Erweiterungen wie ADF und Rekursionen verzichtet wird, und ausschliesslich arithmetische und logische Operationen auf einen Input angewendet werden (Nordin (1997:99)). Eine Anpassung des Basis-CGP-Systems von Nordin, das auf der Basis von Integer arbeitet, zeigt, dass dieses Prinzip auch für FPUs geeignet ist (Nordin (1997:69)).

Gegenwärtige Prozessorarchitekturen zeichnen sich durch die Verwendung mehrerer Instruktionseinheiten mit jeweils mehreren Registern aus. Hinzu kommen Architekturen, die auf einem Chip mehrere unabhängige Prozessoren verwenden, wie z.B. Suns MAJC mit einer potentiellen Skalierbarkeit von 1000 Prozessoren pro Chip. Diese Architekturen besitzen verschiedene Formen der Effizienzsteigerung durch Parallelisierung, die von GP/HP-Systemen genutzt werden kann:

1) Parallele Nutzung der verschiedenen Instruktionseinheiten, was auch Szenarien einschliesst, dass zwei Spezies parallel in einem Prozessor verarbeitet werden, wobei die Individuen der einen Spezies durch Fest-Komma-Zahlen und die Individuen der anderen durch Fliess-Komma-Zahlen repräsentiert sind. Gemischte Individuen auf Maschinenbefehlebene zu erzeugen, ist ein schwieriges Problem, das hier ausgeklammert werden soll. Individuen der ersten Spezies werden ausschliesslich in Fix-Point-Units verarbeitet, während Individuen der anderen Spezies in Floating-Point-Units verarbeitet werden. Die beiden Spezies könnten zu unterschiedlichen Problemen gehören, sodass ein Genaustausch ausgeschlossen wird, oder sie könnten zu dem gleichen Problem gehören, sodass ein Genaustausch eine zusätzliche Übersetzung erfordert. Wird auf ein Austausch verzichtet, so kann dies als ein Experiment interpretiert werden, bei dem untersucht wird, ob eine Fix-Point- oder eine Floating-Point-Repräsentation für das Problem angemessener ist.

2) Parallele Nutzung der Register in den Instruktionseinheiten.

3) Aufteilung langer Register in unabhängige kürzere Register, z.B. ein 64 bit Register in 8 mal 8 bit Register (siehe Sub-machine-code GP von Riccardo Poli). Insbesondere C-RAM-Architekturen könnten für einen solchen Ansatz geeignet sein, wenn die 1 bit-Prozessoreinheiten mit der verbundenen Speicherbank als ein Element eines sehr grossen Registers interpretiert wird, das z.B. bei einem 64 MB-C-RAM-Baustein 64- oder 32-Tausend Registerelemente enthalten kann. Von besonderem Interesse ist dabei die Möglichkeit der flexiblen Aufteilung dieser grossen Register, d.h. es können zu einem Zeitpunkt unterschiedlich breite Register definiert und genutzt werden.

Es existieren Hardware-Architekturen, die speziell für die Signalverarbeitung, die 2D- und 3D-Graphikverarbeitung und den Multimediabereich konzipiert wurden, in denen eine grosse Zahl von Einzel-Registern existieren, und die somit sehr geeignet erscheinen, um eine Subpopulation von CGP-Individuen aufzunehmen und zu verarbeiten. Viele dieser Architekturen basieren auf dem VLIW-Konzept (Very-Long-Instruction-Word). Die Kosten für diese Prozessortypen sind bei gleicher GIPS-Leistung um einen Faktor von mehr als 10 kleiner als General-Purpose-CPUs, und die Entwicklungsdynamik zeigt, dass der Leistungsanstieg eine grössere Steigung besitzt als die CPUs. Die Leistung liegt momentan nahe bei 10 GIPS pro Chip, wobei verschiedene Architekturen auch eine massive Parallelverarbeitung auf der Chipebene unterstützen, wie z.B. die Trimedia-Architektur, bei der bis zu 16000 Chips zu einem Parallel-System verbunden werden können. Beispiele dieser DSP-Multimedia-Architekturen sind TMS320C6x von Texas Instruments, Trimedia von Philips, Mfast von IBM, oder HiPAR-DSP.

Eine weitere Architektur, die auf ihre CGP/AIMC-Eignung geprüft werden sollte, ist AltiVec von Motorola, wobei insbesondere die Permutationseinheit für evolutionäre Operationen wie Rekombinationsarten nützlich ist. Diese Multimedia-Architektur besitzt den Vorteil, dass sie in den PPC der G4-Macs enthalten sind, sodass von einer grossen Verbreitung im Gegensatz zu bestimmten anderen DSP-Architekturen ausgegangen werden kann. Demgegenüber besitzen die Graphikprozessoren ein wesentlich besseres Preis-Leistungsverhältnis.

Graphikprozessoren der jüngsten Generation zeichnen sich dadurch aus, dass sie FP-intensive Berechnungen zur Geometrie selbst übernehmen, und somit die CPU entlasten, wobei auf den Prozessoren viele FPUs integriert sein können. CGP/AIMC-Systeme auf der Basis von FPU-Befehlen in Verbindung mit Standard-Graphikkarten könnten konkurrenzlos günstige Leistungen erbringen. Auf die Eignung bezüglich CGP/AIMC könnten beispielsweise Karten mit dem Prozessor GeForce 256 von nVidia geprüft werden, wobei diesem Prozessor eine Leistung bis 50 GFLOPS zugeschrieben wird. Geplant sind auch massiv parallele SIMD-Architektur wie FUZION 150 von PixelFusion , die mit 50 Millionen Transistoren 1,5 TOPS bzw. 3 GFLOPS leistet.

Bezüglich des Preis-Leistungsverhältnisses, der Verwendung paralleler Verarbeitungseinheiten, der weiten Verbreitung und der einfachen Verfügbarkeit, sowie des schnellen Generationswechsels mit entsprechenden Leistungszuwächsen erscheinen Graphikprozessoren unter den Standard-Architekturen besonders geeignet, sodass dieses Hardware-Projekt diese Architekturklasse präferiert untersuchen soll.

Architekturen wie Dreamcast von Sega, Play-Station 2 von Sony oder Dolphin von Nintendo entwickeln sich zu Home-Entertainment-Systemen, in denen Audio, Video, 3D-Graphik und Internetzugang integriert sind. Besonders geeignet erscheinen diese Architekturen zur evolutionären Entwicklung von Multimedia-Technologien, da Video- und Audio-Prozessoren bereits integriert sind. Dieses Systeme sind sehr leistungsfähig bezüglich ihrer FPU-Leisting, kostengünstig und sehr weit verbreitet, da es sich meist um Zweit- oder Dritt-Geräte handelt, die neben konventionellen Computern in einem Haushalt vorhanden sind. Durch den Internetzugang, der zukünftig standardmässig vorliegen sollte, und der für verteilte Internetspiele gedacht ist, lassen sich mit diesen Architekturen Szenarien im Zusammenhang mit verteilten, Internet-basierten EA-Systemen entwickeln, wie sie im Software-Projekt SW01 vorgeschlagen werden.

Die Verarbeitungsgeschwindigkeit ist jedoch nur eine Komponente, welche die Gesamtleistung eines Systems definiert. Hinzu kommt der Umfang und die Zugriffsgeschwindigkeit auf den Speicher. Die hohen Bearbeitungsgeschwindigkeiten von CGP-Systemen werden jedoch durch Architekturen mit getrennter CPU und RAM relativiert, da die Bandbreite zwischen diesen Systemteilen verhältnismässig klein ist, sodass ein Grossteil des Effizienzgewinnes durch die Gesamtarchitektur wiederum verloren geht. Der naheliegende Lösungsansatz der Speicherung der Individuen einer Sub-Population im Prozessor- oder L2-Cache erzeugt jedoch Beschränkungen bezüglich des Populationsumfanges, was sich ebenfalls negativ auf die Gesamtleistung auswirkt.

Ein möglicherweise besserer Lösungsansatz wird durch die enge Integration von Speicher und Prozessorelementen auf einem Chip geliefert, was mit Computing-RAM oder Computing in RAM umschrieben wird. Vertreter dieser Hardware-Klasse, die als Kandidaten für Peta-Flop-Architekturen gehandelt werden, besitzen pro Speicherbank mit beispielsweise 2KBit ein 1bit-Prozessorelement, sodass bei MBit-Architekturen tausende von Prozessorelementen auf einem Chip enthalten sind, die bei Takten von 10 - 100 ns arbeiten können.

Von besonderer Bedeutung sind dabei die Skalierbarkeit und die Kosten solcher Architekturen, da die gleiche Grundstruktur aus Speicherblock und 1bit-Prozessor beliebig skalierbar ist, ohne dass grössere Designänderungen notwendig werden. Bei der Verfügbarkeit von lithographischen Verfahren mit höherer Auflösung kann die Architektur direkt weiter verwendet werden, ohne dass grössere Redesignkosten entstehen.

Auch im Hinblick auf die Verfahrensausbeute besitzt diese hochgradig modulare Architektur eindeutige Vorteile, da bei Fehlern in einer Speicherbank oder einem Prozessorelement die Möglichkeit besteht, dieses aus der Gesamtarchitektur durch Selbsttest-Mechanismen auszuklammern, was bei Speicherarchitekturen üblich ist. Dies wirkt sich nicht auf die Leistungsfähigkeit anderer Grundelemente auf dem Chip aus, sodass auf der Chipebene eine fast hundertprozentige Ausbeute existiert, da faktisch alle Chips nutzbar sind. Chips mit einer geringen Modularität können hingegen bei einer bestimmten Fehlerrate gar nicht mehr benutzt werden, und müssen vernichtet werden.

Bezüglich der Einführung hat dies auch den Vorteil, dass wesentlich vorher produziert werden kann. Dies folgt daraus, dass mehrere Jahre zwischen Labormuster und Serienfertigung mit einer akzeptablen Ausbeute vergehen können, die bei einer hochgradig modularen Struktur wesentlich verringert werden kann.

Für CGP erscheinen solche 1bit-SIMD-Architekturen besonders gut geeignet zu sein, da auf dem Bitlevel mit variabler Kodierungslänge operiert werden kann, und gleichzeitig durch die enge Verzahnung von Speicher und Prozessorelementen viele Individuen in einer Sub-Population auf einem Chip gehalten werden können. Zusätzlich wird diese gute Eignung der Architektur von geringen Kosten und hoher Skalierbarkeit begleitet.

Auch im Hinblick auf das Hardware-Projekt HW06, bei dem magnetoelektronische Speicher- und Prozessorelemente auf ihre Eignung innerhalb evolutionärer Hardware geprüft werden, ist eine CRAM-Architektur relevant. Die Integration von MRAM und Spin-Transistoren zu CMRAM-Architekturen verspricht einen deutlichen Performancevorteil von bis zu drei Zehnerpotenzen gegenüber CRAM-Architekturen auf der Basis konventioneller Elektronik, da magnetoelektronische Elemente deutlich schneller schalten können, und dadurch den vereinfachten Aufbau und der quasi Vertikal-Transistor-Technologie eine grössere Packungsdichte erreicht werden kann

Zu beachten ist, dass diese Hardwarearchitekturen Prototypen sind, und die somit keine Verbreitung besitzen. Eine Eignungsprüfung erfordert entweder die Kooperation der Institutionen, die Hardwaresamples herstellen, oder die entsprechende CRAM-Architektur muss emuliert werden, indem FPGAs und Standard-RAM verwendet wird. Dies hätte zudem den grossen Vorteil, dass unterschiedlichste CRAM-Architekturen getestet werden können, da das Verhältnis zwischen Prozessoren- und Speicherelementen eine Variable der CRAM-Architektur ist. Denkbar ist auch ein EA, der diese Variable für bestimmte Probleme einstellt, die mit einem darauf spezialisierten GP-System gelöst werden sollen.

Es existieren Hardware-Architekturen, die eine andere Form von Arithmetik wie beispielsweise eine Intervall-Arithmetik, implementiert. Ein CGP-System kann diese Features in der gleichen Weise nutzen, wie eine normale Arithmetik, mit dem Unterschied, dass bei einer entsprechenden Anpassung der Fitnessfunktion die Programme die Effektivitäts-Vorteile besitzen, die mit der Verwendung von Intervall-Arithmetiken verbunden sind, wie die Kontrolle von Rundungsfehlern und der Einschluss der wahren Lösung, sowie die Fähigkeit der Selbstverifikation (siehe Klatte et al. (1993)). Diese Eigenschaften sind besonders wichtig, wenn durch das CGP-System ein Simulationsprogramm erzeugt werden soll, das rekursiv seinen Output in seinen Input zurückführt, da in einer solchen Konstellation Fehler beliebig anwachsen, und somit Resultate jeglichen Wert verlieren können.

Die Verwendung von Intervall-Arithmetiken innerhalb Soft-GP-Systemen besitzt Effizienznachteile, wenn beispielsweise C-XSC in Verbindung mit einem GP-System verwendet wird, das C-Funktionen interpretiert, was jedoch der erste Schritt sein könnte, um ein Software-Intervall-GPS zu implementieren. Eine Verwendung von FPU-Maschinenbefehlen ist eine erste Performancesteigerung, wenn z.B. bestimmte Rundungsoperationen direkt angesprochen werden können. Durch die Verwendung von entsprechender Intervall-Arithmetik-Hardware lassen sich offensichtlich weitere Effizienzsteigerungen erzielen. Durch die Zusammenarbeit der Universität Karlsruhe, Harburg und Stuttgart, ist eine FPU auf der Basis der Kulisch-Intervall-Arithmetik entwickelt worden (XPA 3233, XPA 6400), die für eine Evaluierung eines Intervall-CGP-Systems geeignet ist. Der Vorteil ist eine entsprechende Geschwindigkeitssteigerung im Vergleich zu einer Software-Implementierung einer Intervall-Arithmetik, bei der es sich im Fall der Evaluierungs-FPU XPA 3233 um einen Faktor von ca. 30 handelt.

Zu beachten ist, dass diese Hardwarearchitektur ebenfalls ein Prototyp ist, was eine Eignungsprüfung von der Kooperation der beteiligten Institutionen abhängig macht. Aus diesem Grunde sollte vorab geklärt werden, ob eine C-RAM-Architektur oder 128-bit-Architekturen wie in AltiVec oder in verschiedenen Graphikprozessoren als effiziente Substitution einer Intervall-Arithmetik-Hardware eingesetzt werden könnte, da in diesem Fall die Erzeugung von Intervall-Arithmetik-Programmen durch ein CGPS im Rahmen der Untersuchungen über C-RAM-Architekturen durchgeführt werden könnte. Die genannten XPA-Architekturen basieren auf 128-bit-Registern, die von einer geeigneten C-RAM-Architektur emuliert werden können. Dies ergibt sich daher, dass die Grundelemente des C-RAMs eine Integration eines 1-bit-Prozessors und einer RAM-Bank sind, die parallel angeordnet sind, und die von ihren unmittelbaren Nachbarn einen Input erhalten können. Werden mindestens 128 dieser Elemente zusammengefasst, so kann damit ein 128-bit-Register emuliert werden, auf dem Kulisch-Intervall-Arithmetik-Operationen durchgeführt werden können. Von besonderem Vorteil wäre die C-RAM-Architektur dadurch, dass flexible Registergrössen festgelegt werden können, sodass auch grössere Register definierbar sind, mit denen beispielsweise Intervall-Arithmetiken mit Multi-Vektoren im Rahmen von Clifford-Algebras eingeführt werden können.

Sollte im Rahmen des Software-Projekt (SW01) als Entwicklungssprache des verteilten, internet-basierten EA-Systems die Java/Jini/Javelin-Architektur verwendet wird, so können als zugrundeliegende Hardware Systeme geprüft werden, die Java-Befehle direkt ausführen können, wie etwa Sun MAJC. Auf einer solchen Architektur könnte ein CGP/CHP-System Binärstrings erzeugen, die direkt als Maschinenprogramme verarbeitet werden können.

Durch die Sun MAJC-Architektur können die oben beschriebenen verschiedenen Formen der Parallelisierung genutzt werden, da zum einen mehrere (theoretisch bis zu 1000) CPUs auf einem Chip integriert werden können, wobei jede CPU vier 32 bit-Einheiten besitzt, die im Rahmen eines Sub-Machine-Code-GP diese weiter unterteilt werden könnten.

Relevant wird dieses Projekt insbesondere dadurch, dass zukünfig eine grosse Verbreitung dieser Hardware-Architektur, insbesondere im Hand-Held-Bereich, bei Internet-Phones bzw. allgemein im Consumer-Bereich erwartet werden kann.

Nachdem einige Hardware-Architekturen bezüglich ihrer Eignung für Software-CGP/CHP-Systeme geprüft wurden, werden die gewonnenen Erkenntnisse in eine massiv-parallele CGP/CHP-Problemlösungsumgebung umgesetzt.

Ein in einigen Punkten vergleichbares Projekt wird von der Genetic Programming Inc. unter der Leitung von John R. Koza und Forrest H. Bennett III durchgeführt, die den Aufbau eines lokalen Linux-Clusters entsprechend der Beowulf-Architektur planen, der in seiner grössten Ausbauphase ca. 1000 Prozessoren umfassen soll. Mit einem Leistungspotential im TFLOPS-Bereich und dem Genetic-Programming-Problem-Solving(GPPS)-System aus Koza et al. (1999) sollen u.a. evolutionäre analoge HW-Entwicklung durchgeführt und Probleme aus der Computational Molecular Biology (CMB) gelöst werden.

Bei der Umsetzung der CGP/CHP-Erkenntnisse soll hier das wahrscheinlichste Szenario dargestellt werden, d.h. die Nutzung von Graphikkarten mit Hochleistungs-Graphikchips. Es soll ein lokaler Linux-Cluster mit Standard-Boards aufgebaut werden, deren PCI-Slots vollständig mit Graphikkarten belegt werden, die nicht zur Graphikbearbeitung verwendet werden, sondern auf denen CGP/CHP-Programme reproduziert, evaluiert und selektiert werden. Denkbar ist eine hierarchische Populationsstruktur, wobei pro Karte, die neben einem oder mehreren Graphikchips auch lokalen Speicher besitzt, eine eigene Population verwendet wird. Die ca. 6 Karten pro Motherboard bei einem Towergehäuse bzw. ca. 12 bis 20 bei einem 19 Zoll Schranksystem bilden Populationsgruppen, in denen primär Migrationsprozesse stattfinden. Die einzelnen Knoten des Linux-Clusters sollen durch TCP/IP-Verbindungen verknüpft werden, damit aus dem lokalen Cluster ein über das Internet verteilter Cluster gebildet werden kann, an dem auch Nicht-Linuxsysteme beteiligt werden können.

Im Rahmen des Software-Projekt (SW01) wurde als mögliche Basis-Architektur der Linux-TurboCluster Server, als ein hochverfügbarer, ausfallsicher, fehlertoleranter Web-Server, untersucht, der als open-source zur Verfügung steht. Für den lokalen Linux-Cluster soll auch diese Option geprüft werden, sodass ein verteiltes CGP/CHP-System entsteht, bei dem Clients (Rechner mit dem gleichen Typ an Graphikhardware) über das Internet Populationen von dem Evo-Server erhalten, diese entwickeln und ausgewählte Individuen an den Evo-Server schicken, der eine globale Migrationsstrategie durchführt.

Klatte, R., Kulisch, U.; Wiethoff, A.; Lawo, C.; Rauch, M.: C-XSC. Springer, Berlin, 1993.

Koza, J.R; Bennett, F.H.; Andre, D.; Keane, M.A.: Genetic Programming III. Morgan Kaufmann, 1999.

Nordin, Peter: Evolutionary Programm Induction of Binary Machine Code and its Applications. Münster, 1997. 

Poli, Riccardo: Sub-machine-code GP. In: Poli et al. (1999), S. 65 - 82.

Poli, R.; Nordin, P.; Langdon, W.B.; Fogarty, T.C. (eds.): Genetic Programming. Second European Workshop, EuroGP'99, Springer Verlag, LNCS 1598, S. 65 - 82, 1999.