Massiv parallele Programmierung mit dem Parallaxis-Modell

ISBN-13: 9783540528531 / Niemiecki / Miękka / 1990 / 168 str.

Thomas Braunl

Opis

Die vorliegende Arbeit entstand wiilirend meiner Zeit als wissenschaftlicher Mitarbeiter der Universitat Stuttgart am Lehrstuhl fUr Programmiersprachen und ihre Ubersetzer, bei Herrn Prof. Dr. Gerhard Barth (inzwischen Leiter des Deutschen Forschungszentrums fUr Kiinstliche Intelligenz in Kaiserslautern, DFKI), sowie wahrend meines fast zweijiilirigen Aufenthalts in den USA, an der University of Southern California, Los Angeles, der durch ein Stipendium der Fulbright-Kommission ermoglicht wurde. Dieses Buch gliedert sich in fiinfzehn Kapitel und einen Anhang. Nach der Einleitung und der Definition der Anforderungen an das parallele Modell in Kapitel 1 und 2 werden in Kapitel 3 einige grundlegende Konzepte der parallelen Programmierung dargestellt. Hier wird sowohl auf Rechnerarchitekturen als auch auf parallele Operationen und deren Realisierungen durch bekannte Konstrukte zur Parallelverarbeitung und Synchronisation eingegangen. In Kapitel 4 werden die wichtigsten Punkte des hier vorgestellten parallelen Modells knapp dargestellt. Die Kernpunkte sind die SpezifIkation der Netzwerkstruktur sowie die Kon strukte zur parallelen Ausfiihrung und zum parallelen Datenaustausch zwischen Prozessoren. Kapitel 5 ist der SpezifIkation der Rechnerarchitektur gewidmet. Nach der Beschrei bung des verwendeten SIMD-Maschinenmodells wird eine funktionale Syntax vorgestellt, mit der jede beliebige Verbindungsstruktur definiert werden kann. 1m AnschluB an zwei Erweite rungen der Speziflkations Konstrukte werden typische Verbindungsstrukturen mit ihren Spe ziflkationen in dieser Syntax dargestellt. Die Behandlung moglicher Fehlerquellen in einer Netzwerk-Spezifikation und ihre Erkennung wiilirend der Ubersetzung sowie eine Diskussion machtigerer Spezifikations-Konstrukte beenden das Kapitel."

Spis treści

1. Einleitung.- 2. Anforderungen und Ziele.- 3. Parallele Programmierung.- 3.1 Parallele Rechnerarchitekturen.- 3.2 Parallele Operationen.- 3.2.1 Vektor-Skalar Operationen.- 3.2.2 Vektor-Reduktionen.- 3.2.3 Vektor-Vektor Operationen.- 3.3 Parallelverarbeitung in bestehenden Programmiersprachen.- 3.3.1 Coroutinen.- 3.3.2 Fork und Join.- 3.3.3 Cobegin und Coend.- 3.3.4 Explizit deklarierte und synchronisierte Prozesse.- 3.3.5 Server/Client Beziehungen.- 3.3.6 Implizite Parallelität.- 4. Sprachkonzepte.- 4.1 Datenelemente und Deklarationen.- 4.2 Spezifikation der parallelen Verbindungsstruktur.- 4.3 Paralleler Datenaustausch.- 4.4 Parallele Verarbeitung.- 4.5 Prozeduren und Funktionen.- 5. Spezifikation der Rechnerarchitektur.- 5.1 Das parallele Maschinenmodell.- 5.2 Spezifikationskonstrukte der Netzwerkstruktur.- 5.3 Definitions- und Wertebereiche von Transfer-Funktionen.- 5.4 Strukturierte Transfer-Funktionen.- 5.4.1 Zusammengesetzte Transfer-Funktionen.- 5.4.2 Parametrisierte Transfer-Funktionen.- 5.5 Komplexe Verbindungsstrukturen.- 5.5.1 Torus.- 5.5.2 Hexagonales Gitter.- 5.5.3 Ring.- 5.5.4 Vollständiger Graph.- 5.5.5 Perfect Shuffle.- 5.5.6 Binärer Baum.- 5.5.7 Quadtree.- 5.5.8 Hypercube.- 5.6 Semantische Prüfung von Topologien.- 5.7 Erweiterungen der Spezifikation.- 6. Konzepte der Parallelverarbeitung.- 6.1 Paralleler Anweisungsblock.- 6.2 Kollektiver Datenaustausch.- 6.3 Mehrstufiger Datenaustausch.- 6.4 Datenreduktion.- 6.5 Parallelverarbeitung am Beispiel einer Ring-Topologie.- 6.6 Propagate Splitting.- 7. Kommunikationskonzepte.- 7.1 Datenaustausch zwischen Prozessoren im Netzwerk.- 7.2 Datenübermittlung von und zur zentralen Steuerung.- 7.3 Ein-/Ausgabe-Operationen des Steuerrechners.- 8. Parallele Semantik.- 8.1 Das Modell der Parallelverarbeitung.- 8.2 Darstellung einer formalen parallelen Semantik.- 8.2.1 Hilfsdefinitionen.- 8.2.2 Definition der parallelen Semantik.- 8.3 Beweis-Regeln.- 8.4 Bestimmung von Vorbedingungen.- 9. Datenstrukturen und Datentypen.- 9.1 Deklaration von Variablen.- 9.1.1 Variablen des Steuerrechners.- 9.1.2 Variablen der parallelen Prozessoren.- 9.2 Konstanten.- 9.3 Erweitertes Datentypkonzept.- 9.4 Vordefinierte Einheiten.- 9.4.1 Basiseinheiten.- 9.4.2 Abgeleitete Einheiten.- 9.5 Definition von neuen Einheiten-Systemen.- 9.5.1 Definition von neuen Größen.- 9.5.2 Definition von weiteren Einheiten-Größenordnungen.- 9.6 Regeln beim Rechnen mit Einheiten.- 9.7 Verwandte Arbeiten.- 10. Implementierung des Parallaxis-Systems.- 10.1 Definition der Schnittstelle.- 10.2 Definition der parallelen Zwischensprache.- 10.2.1 Spezifikation der Verbindungen.- 10.2.2 Variablen-Deklarationen.- 10.2.3 Einfache Befehle.- 10.2.4 Stackoperationen und Prozeduren.- 10.2.5 Die parallele Verzweigung.- 10.2.6 Der parallele Datenaustausch.- 10.3 Der Compiler.- 10.4 Der Simulator.- 10.5 Graphische Darstellung der Netzwerk-Topologie.- 10.6 Debugging-Hilfen.- 11. Systolische Programmierung mit Parallaxis.- 11.1 Parallele Matrix-Multiplikation.- 11.2 Beziehung zwischen systolischen Arrays und dem Parallaxis-Modell.- 12. Anwendungen des parallelen Modells.- 12.1 Parallele Bilderzeugung.- 12.1.1 Fraktale Geometrie.- 12.1.2 Ray Tracing Verfahren.- 12.2 Parallele Bildverarbeitung.- 12.3 Implementierung von Neuronalen Netzen.- 12.4 Realisierung schneller kinematischer Systeme in der Robotik.- 13. Einbindung in parallele Rechnerarchitekturen ..- 13.1 Anpassung an eine Parallel-Architektur.- 13.2 Geeignete Rechnerarchitekturen.- 13.3 Theoretische Leistungswerte.- 13.3.1 Das Gesetz von Amdahl.- 13.3.2 Parallelitätsgewinn eines SIMD Systems unter Parallaxis.- 13.3.3 Vergleich zwischen SIMD- und MIMD-Leistungen.- 14. Analyse der Konzepte im Vergleich mit verwandten Arbeiten.- 14.1 Connection Machine Lisp.- 14.2 *Lisp.- 14.3 Concurrent Prolog, Parlog und Guarded Horn Clauses.- 14.4 Modula-P, Concurrent Pascal und Ada.- 14.5 Occam.- 14.6 Vector C und PASM Parallel C.- 14.7 Refined C und Refined Fortran.- 14.8 C*.- 15. Ausblick.- A. Syntax der Programmiersprache Parallaxis.- B. Syntax der Zwischensprache PARZ.- C. Programme.- C. 1 Bestimmen des größten Elements einer Matrix.- C.1.1 Lösungsstrategie.- C.1.2 Parallaxis Programm.- C.1.3 PARZ Programm.- C.1.4 Ausführung.- C.2 Parallele Bildrotation durch rekursive Verschiebungen.- C.3 Parallele Primzahlenerzeugung.- C.4 Linear-Paralleles Sortieren.- D. Literatur.

O autorze

Bräunl is Associate Professor at the University of Western Australia, Perth, where he founded and directs the Mobile Robot Lab and is also Director of the Centre for Intelligent Information Processing Systems (CIIPS). Professor Bräunl received a Diploma in Informatics in 1986 from Univ. Kaiserslautern, an MS in Computer Science in 1987 from the University of Southern California, Los Angeles, and a PhD and Habilitation in Informatics in 1989 and 1994, respectively, from Univ. Stuttgart. He has worked in the past for BASF and Daimler Chrysler and has founded a company for innovative mobile robot design. Professor Bräunl s research interests are robotics, vision, graphics, and concurrency. He is author of several research books and textbooks and has developed the Eye Bot mobile robot family.