Massiv-parallele Systeme zur Globalen Zellularen Verarbeitung
Final Report Abstract
Zur hochsprachlichen Beschreibung von GGA-Algorithmen wurde die Sprache GCA-L entworfen. Der Anwender beschreibt seine Anwendung mit Zellobjekten, das sind Vektoren aus Zellen eines definierten Zelldatentyps. Zellobjekte sind Teilbereiche des gesamten verfügbaren Zellraums. Das foreach-Konstrukt erlaubt es, über die Zellen eines Zielobjekts zu iterieren (potentiell parallel), wobei gleichzeitig über eine Adressierungsfunktion die globalen Zellen eines Quellobjektes gelesen werden. Derartige Zellobjekte und Adressierungsmöglichkeiten sind also die Grundkonzepte, die in zukünftigen GCA-Sprachen oder GCA- Erweiterungen von Standardsprachen enthalten sein sollten. Als Zielarchitekturen wurde eine datenparallele Architektur (DPA) und eine Multiprozessor-Architektur (MPA) entworfen. Bei der DPA können konfiguriert werden: die Zellstrukur, die Anzahl der parallelen Pipelines mit applikationsspezifischen Regelberechnungen für den nächsten Datenzustand und für den nächsten globalen Zugriff. Bei der MPA können konfiguriert werden: die Zellstruktur, die Anzahl der Prozessoren und die Art des Verbindungsnetzes (Omega, Ring, Bus). Die Prozessoren haben lokale Speicher, die auch global gelesen werden können. Die Prozessoren besitzen zusätzliche Befehle (custom instructions), für Gleitkommaoperationen, die globalen Speicherzugriffe und der Barrieren-Synchronisation. Sowohl die DPA als auch die MPA sind von ihrem Architekturkonzept klar und übersichtlich strukturiert, so dass diese sich relativ einfach in Hardware umsetzen lassen. Die DPA ist stärker applikationsspezifisch konfigurierbar und damit für kleinere Anwendungen leistungsfähiger als die MPA, die dagegen den Vorteil der Programmierbarkeit hat. Das entwickelte Synthesetool, kann aus einem in GCA-L beschriebenen Algorithmus zwei Zielcodes generieren: A. eine applikationsspezifische DPA (Verilog-Code) inklusive eines Steuerprogramms (bestehend aus applikationsspezifischen.Befehlen (adapted operators)). Anschließend erfolgt die Logiksynthese (mit Quartus von Altera). B. C-Code (angereichert um spezielle Befehle für die Speicherzugriffe) für die Softcores einer MPA. Der übersetzte C-Code wird dann in die Speicher der vorher synthetisierten MPA geladen. Die Funktionsfähigkeit des Synthesetools sowie die Leistungsfähigkeit der generierten DPAs und MPAs konnten für verschiedene Anwendungen demonstriert werden. Die begleitenden theoretischen Untersuchungen haben gezeigt, dass sich die aus der Theorie bekannten PRAM Algorithmen leicht auf das GCA-Modell übertragen lassen, insbesondere durch Transformation in CROW- oder EREW-Algorithmen. Im Falle, dass für bestimmte Anwendungen Schreibzugriffe auf globale Nachbarn nicht vermieden werden können, können diese mit logarithmischem Zeitaufwand 0(log N), bei N Zellen, emuliert werden. Zusammenfassend kann festgestellt werden, dass das GCA-Konzept sich sowohl zur Modellierung paralleler Anwendungen als auch zur automatischen Übersetzung auf verschiedenartige parallele Hardware-Architekturen sehr gut eignet. Ein kommerziell weiter entwickeltes GCA-System (für verschiedene Zielplattformen mit Sprachunterstützung, Compiler und Synthese) könnte in der Praxis dazu dienen • effiziente applikationsspezifische Hardware zu generieren, oder • Code für Multiprozessorsysteme (mit oder ohne GCA-spezifische Unterstützung) zu generieren. Um universelle parallele Anwendungen zu unterstützen (nicht nur GCA-Algorithmen) musste man eine weitere abstrakte Sprachebene („universelle" parallele Sprache) auf die GCA- Sprachebene legen und die Übersetzung vornehmen. Hier sind entsprechende Arbeiten notwendig, betreffend Auswahl/Entwurf der universellen parallelen Sprache und der Compilertechniken. Grundsätzlich sollte man versuchen, von der Art der parallelen Zielarchitektur zu abstrahieren. Natürlich sind auch weitere Forschungen zur Optimierung der Zielarchitekturen mit GCA-Unterstützung erforderlich. Das GCA-Modell bietet auch die Möglichkeit, weitere theoretische Arbeiten durchzuführen, z.B. die Abbildung weiterer PRAM-Algorithmen auf das GCA-Modell, die „Erfindung" neuartiger GCA-Algorithmen, Komplexitätsbetrachtungen, die Abbildung auf Modelle mit lokaler Nachbarschaft (CA-Modell) und dergleichen.
Publications
- A multiprocessor architecture for the massively parallel model GCA. In International Parallel & Distributed Processing Symposium (IPDPS), Workshop on System Management Tools for Large-Scale Parallel Systems (SMTPS), 2006
Wolfgang Heenes, Rolf Hoffmann und Johannes Jendrsczok
- Entwurf und Realisierung von massivparallelen Architekturen für Globale Zellulare Automaten. Darmstädter Dissertation D17, Technische Universität Darmstadt, 2007
Heenes, Wolfgang
- Hirschberg's Algorithm on a GCA and Its Parallel Hardware Implementation. In Euro-Par, Seiten 815-824, 2007
Johannes Jendrsczok, Rolf Hoffmann und Jörg Keller
- Implementing APL- like data parallel functions on a GCA machine. In 21. PARS Workshop, Gesellschaft für Informatik (Gl), 2007
Johannes Jendrsczok, Rolf Hoffmann, Patrick Ediger und Jörg Keller
- Implementing Hirschberg's PRAM- Algorithm for Connected Components on a Global Cellular Automaton. In International Parallel & Distributed Processing Symposium (IPDPS), Workshop on Advances in Parallel and Distributed Computational Models (APDCM), 2007
Johannes Jendrsczok, Rolf Hoffmann und Jörg Keller
- The Global Cellular Automata Experimental Language GCA-L1. Technischer Bericht RA-1 -2007, Technische Universität Darmstadt. FB Informatik, 2007
Johannes Jendrsczok, Patrick Ediger und Rolf Hoffmann
- A scalable configurable architecture for the massively parallel GCA model. In IPDPS, Seiten 1-8. IEEE, 2008
Johannes Jendrsczok, Patrick Ediger und Rolf Hoffmann
- Implementing Hirschberg's PRAM-Algorithm for Connected Components on a Global Cellular Automaton. International Journal of Foundations of Computer Science, 19(6):1299-1316, 2008
Johannes Jendrsczok, Rolf Hoffmann und Jörg Keller
- A Generated Data Parallel GCA Machine forthe Jacobi Method. In 3. HiPEAC Workshop on Reconfigurable Computing 25. Januar 2009, Paphos, Zypern, Seiten 73-82, 2009
Johannes Jendrsczok and Rolf Hoffmann and Patrick Ediger
- A Multiprocessor Architecture with an Omega Network for the Massively Parallel Model GCA. In Koen Bertels, Nikitas J. Dimopoulos, Cristina Silvano und Stephan Wong, Herausgeber, Embedded Computer Systems: Architectures, Modeling, and Simulation, 9th International Workshop, SAMOS 2009, Samos, Greece, July 20-23, Band 5657 von Lecture Notes in Computer Science, Seiten 98-107. Springer Berlin / Heidelberg, 2009. ISSN 0302-9743 (Print) 1611-3349 (Online)
Christian Schäck and Wolfgang Heenes and Rolf Hoffmann
- A Scalable Configurable Architecture for the Massively Parallel GCA Model. International Journal of Foundations of Computer Science, 24(4):275-291, 2009
Johannes Jendrsczok und Patrick Ediger Rolf Hoffmann
- Application-Specific Data Parallel Machine Automatically Generated for the N-body Force Calculation. Technischer Bericht RA-2-2009, Technische Universität Darmstadt, FB Informatik, 2009
Johannes Jendrsczok, Thomas Lenck, Rolf Hoffmann, Jörg Keller und Andre Osterioh
- Das GCA-Modell im Vergleich zum PRAM-Modell. Technischer Bericht Informatik-Bericht 350 - 03/2009, FernUniversität in Hagen, 2009
Andre Osterioh und Jörg Keller
- GCA Multi-Softcore Architecture for Agent Systems Simulation. In Erik Maehle Stefan Fischer, Herausgeber, Informatik 2009 Im Focus das Leben, Band P-154 von Lecture Notes in Informatics, Seiten 278; 2268-82, 2009. ISSN 1617-5468
Christian Schäck and Wolfgang Heenes and Rolf Hoffmann
- Generated horizontal and vertical data parallel GCA machines for the N-body force calculation. In Mladen Berekovic, Christian Müller-Schloer, Christian Hochberger und Stephan Wong, Herausgeber, Architecture of Computing Systems - ARCS 2009, 22nd International Conference. Delft, The Netherlands, March 10-13, 2009. Proceedings, Band 5455 von Lecture Notes in Computer Science, Seiten 96-107. Springer, 2009
Johannes Jendrsczok, Rolf Hoffmann und Thomas Lenck
- Global Cellular Automata: a Path from Parallel Random Access Machines To Practical Implementations. In 22. PARS Workshop, Gesellschaft für Informatik (Gl), 2009. ISSN 0177-0454
Jörg Keller and Andre Osterioh
- Network Optimization of a Multiprocessor Architecture for the Massively Parallel Model GCA. In 22. PARS Workshop, Gesellschaft für Informatik (Gl). 2009. ISSN 0177-0454
Christian Schäck and Wolfgang Heenes and Rolf Hoffmann
