Abstrakte parallele Maschinen für das Polytopenmodell

• Applicant: Professor Christian Lengauer, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: from 2000 to 2003
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5238782

... Die Anwendbarkeit des Polytopenmodells ist im letzten Jahrzehnt erheblich erweitert worden. Dies führt allerdings auch oft zu weit komplizierteren parallelen Lösungen als die gegenwärtige Compilertechnologie verarbeiten kann. Daher muß jetzt das Hauptaugenmerk auf der Umsetzung dieser Erfolge auf der Modellebene in effizenten Lösungen auf der Zielcodeebene liegen. Dabei müssen eine Anzahl oft maschinenabhängiger Entscheidungen getroffen werden. Die Vorgehensweise in gegenwärtigen Implementierungsprojekten ist, diese Entscheidungen in einer sequentiellen Reihenfolge mit Blick auf eine einzige Zielimplementation, ohne vergleichende Studien zu fällen. PolyAPM verfolgt dagegen den Ansatz der "Familie alternativer Implementierungen". Hier wird von der Modellebene ausgehend ein Baum von alternativen Verfeinerungen, sog. "abstrakten parallelen Maschinen" (APMs), entwickelt. Die Blätter des voll entwickelten Baums stellen alternative Zielcodelösungen dar. Das Ziel von PolyAPM ist, auf diese Weise einen systematischeren Überblick über die Fürs und Widers alternativer paralleler Implementierungen zu erlangen. Wir werden unsere Bewertung verschiedener Implementierungen mit experimentellen Fallstudien untermauern. Ein Sondergutachter für Informatik schreibt:"... Als Ausgangspunkt wird die funktionale Programmiersprache "Haskell" gewählt; auch die verschiedenen abstrakten parallelen Maschinen werden durch Haskell-Programme repräsentiert. Der endgültige Zielcode soll hingegen C-Code, also eine imperative Programmiersprache, samt entsprechenden Kommunikationsprimitiven sein. Der Antragsteller verspricht sich von dieser Vorgehensweise nicht nur eine Erleichterung der Arbeit, sondern auch ein Demonstrationsbeispiel, um die Möglichkeiten und Vorzüge funktionaler Programmierung anstelle der üblichen imperativen Programmierung im wissenschaftlichen Rechnen deutlicher herauszustellen. Insgesamt ist dies ein wohldurchdachter Antrag für ein lohnendes Ziel. Die dem Antrag beigefügte Arbeit zeigt bereits erste veröffentlichungsreife Ergebnisse auf dem Weg zum angestrebten Ziel. ... Entscheidungsvorschlag: bewilligen wie beantragt." Ein Fachgutachter für Praktische Informatik teilt mit:"... Das Vorhaben hat zum Ziel, verschiedene parallele Implementierungen für Schleifenprogramme zu entwickeln und zu vergleichen. Die Schleifenprogramme sind dabei in "Haskell" formuliert und verwenden als wesentliches Konstrukt sogenannte "array comprehensions". Die verschiedenen Implementierungszweige auf Basis "abstrakter paralleler Maschinen" sollen ebenfalls in "Haskell" formuliert werden. Die Vorarbeiten zu diesem konkreten Vorhaben sind relativ dürftig; die bisher erzielten experimentellen Ergebnisse mager. Es gibt zwei, nicht sonderlich aufregende Workshop-Veröffentlichungen aus den Jahren 1997 und 1999 - die letztere skizziert den Ansatz grob. ... Insgesamt ist festzuhalten, daß der Antrag aufgrund unzureichender Vorarbeiten, eines zu schwammig abgefaßten Arbeitspaketes und inhaltlicher Unstimmigkeiten als nicht förderungswürdig erachtet wird." Der Vorsitzende des Fachausschusses Informatik meint abschließend: "Zu diesem Projekt liegt ein sehr positives Vorgutachten eines Sondergutachters und Experten im gesamten Bereich der Programmierung und ein negatives Vorgutachen eines Fachgutachters vor, der jedoch selber schreibt, daß er auf dem zentralen Gebiet des Antrags kein Experte ist. Die Kritikpunkte beziehen sich daher mehr auf mangelndes Kontextwissen (und damit auf eine kleine Schwäche des Antrags, sich zu stark an Experten zu wenden). Mein eigener Eindruck von dem Antrag stimmt mit dem positiven Vorgutachten überein. Der Antragsteller publiziert seit Jahren auf internationalem Niveau im Bereich der Parallelprogrammierung. Vorarbeiten zu diesem speziellen Vorhaben liegen umfassend vor, ein technischer Bericht enthält veröffentlichungswürdige Resultate. Es geht um die automatische Parallelisierung sequentieller Algorithmen auf Vektoren und Matritzen. Dabei werden ganz neue Ansätze vorgeschlagen, um implizite Abhängigkeiten zu erkennen. Dies wird Entscheidungen, wie parallelisiert werden soll, unterstützen. Ziel und Arbeitsprogramm lassen auf gute Ergebnisse in einem zentralen Gebiet hoffen. Die Förderungsempfehlung kann uneingeschränkt ausgesprochen werden. Entscheidungsvorschlag: Förderung durch eine BAT IIa-Stelle für 2 Jahre; 1 HK-Stelle (19 Std./Woche) für 2 Jahre; DM 4.000,-- für Reisen."

• DFG Programme: Research Grants