Universität - GH Paderborn

Universität - GH Paderborn
Fachbereich Mathematik-Informatik
AG ``Programmiersprachen und Übersetzer'' 

Prof. Dr. Uwe Kastens
 

Arbeitsschwerpunkte

In dieser Arbeitsgruppe befassen wir uns mit dem Entwurf, der Implementierung und der Anwendung von Programmiersprachen und von Sprachen für spezielle Anwendungsaufgaben (DSL = ``domain specific languages''). Wir untersuchen charakteristische Eigenschaften in Sprachen unterschiedlicher Klassen, deren Übersetzung und ihre systematische Anwendung in der Programmierung bzw. zur Beschreibung von Systemen in spezifischen Anwendungsbereichen.

Methoden und Werkzeuge zur Sprachimplementierung

Wir haben das Werkzeugsystem Eli entwickelt, das den Entwurf von Sprachen und den gesamten Herstellungsprozeß für ihre Implementierung unterstützt. Es enthält zahlreiche generierende Werkzeuge und Module, welche die Lösung von Übersetzungsaufgaben systematisieren und automatisieren. Eli ist auch ohne tiefgehende Kenntnisse in der Implementierung von Sprachen anwendbar, z.B. von Entwicklern bereichsspezifischer Sprachen in Informatik-fremden Gebieten. Eli wird in internationaler Kooperation dreier Gruppen weiterentwickelt und weltweit erfolgreich eingesetzt.

Parallelisierende Übersetzung

Heutige Rechner enthalten Prozessoren, die intern Operationen parallel ausführen. Übersetzer für solche Rechner müssen durch Programmanalyse die nutzbare Parallelität auffinden und die Operationen so anordnen, daß die parallelen Funktionseinheiten des Prozessors möglichst gut ausgenutzt werden. Wir arbeiten hierzu an speziellen Verfahren wie z.B. Software-Pipelining, Schleifenparallelisierung und systolischen Techniken. Solche Verfahren sind besonders wirksam für Rechner, in denen eine große Anzahl von Prozessoren parallel arbeitet.

Werkzeuge zur parallelen Programmierung

Die effiziente Implementierung von Algorithmen auf Parallelrechnern erfordert wesentlich mehr Expertenwissen, als es für sequentielle Rechner notwendig ist: Da die unterschiedlichen Charakteristika von Parallelrechnern nicht hinter allgemein anwendbaren Programmiersprachen verborgen werden können, schlagen sie in die Programmierung und sogar in den Algorithmenentwurf durch. Wir entwickeln deshalb Werkzeugsysteme, die algorithmisches und technisches Expertenwissen für spezifische Anwendungsgebiete verfügbar machen. Sie umfassen Bibliotheken kombinierbarer, generischer Algorithmenvarianten und automatisieren den Herstellungsprozeß für parallele Programme.

Diese Arbeiten sind ebenso wie die zur parallelisierenden Übersetzung in den DFG-Sonderforschungsbereich 376 ``Massive Massive Parallelität, Algorithmen, Entwurfsmethoden und Anwendungen'' eingebettet.
 

Projekte

Fortentwicklung des Eli-Systems

Eli macht aktuelles Know-How zur Konstruktion qualitativ hochwertiger Sprachimplementierungen aus anwendungsnahen Spezifikationen für einen großen Anwenderkreis verfügbar. Das Eli-System wird ständig fortentwickelt und erfordert auch in der Anwenderberatung und Systemwartung ein starkes Engagement der Gruppe.

Parallelisierende Übersetzung

Zu diesem Thema haben wir uns bisher hauptsächlich mit der fein-granularen Parallelisierung auf Instruktionsniveau befaßt: Analyseverfahren ermitteln die Freiheitsgrade zur parallelen Ausführung von Operationen, Transformations- und Anordnungsverfahren erzeugen möglichst effizienten parallelen Code für den jeweiligen Zielprozessor. Das Spektrum der von uns betrachteten Zielarchitekturen reicht von superskalaren Einzelprozessoren über VLIW-artige Prozessoren bis zu massiv parallelen SIMD-Rechnern. In mehreren Projekten haben wir

• eine Entwicklungsumgebung für konfigurierbare Übersetzer für superskalare und VLIW-Prozessoren hergestellt (abgeschlossenes DFG-Vorhaben),
• Varianten des Software-Pipelining-Verfahrens entwickelt, integriert und evaluiert (abgeschlossenes DFG-Vorhaben),
• Verfahren zur Schleifenanalyse und parallelisierenden Transformation fortentwickelt (SFB),
• systolische Verfahren zur Übersetzung für massiv parallele Rechner entwickelt (SFB),
• die Programmiersprache Occam-Light entwickelt, die Occam2 um Konzepte zur Programmierung mit gemeinsamen Speicher erweitert.

Analyse und Transformation für parallele Programme

Für die Untersuchung von neuen Übersetzungsverfahren zur automatischen Parallelisierung regulärer Anwendungen haben wir eine experimentelle Umgebung für Schleifen und Datentransformation entwickelt. Diese haben wir in unseren Arbeiten zur systolischen Übersetzung erstmals erfolgreich eingesetzt und Folgen von Schleifenschachteln unter dem Aspekt einer Datenverteilung mit geringem Reorganisationsaufwand parallelisiert.

Werkzeugsystem zur Entwicklung paralleler Software

Unsere bereichsspezifischen Werkzeugsysteme zur Entwicklung paralleler Software sollen die Anwender in die Lage versetzen, ihre Entwicklungsschritte auf die für das Problem wesentlichen Eigenschaften zu konzentrieren und diese in angemessener Terminologie von Programmier- und Spezifikationssprachen zu formulieren. Unsere Methodik zur Konstruktion solcher Systeme haben wir bisher an zwei Systemen zur Entwicklung paralleler Branch-and-Bound-Anwendungen bzw. paralleler Sortierverfahren erprobt.
 

Veröffentlichungen

• Uwe Kastens. Executable Specifications for Language Implementation. In Fifth International Symposium on Programming Language Implementation and Logic Programming, Tallinn, August 1993, Band 714 aus Lecture Notes in Computer Science, S. 1-11. Springer Verlag, 1993.
• Uwe Kastens und William M. Waite. Modularity and Reusabiltiy in Attribute Grammars. Acta Informatica, 31:601-627, 1994.
• Peter Pfahler und Uwe Kastens: Language Design and Implementation by Selection Proceedings of the First ACM SIGPLAN Workshop on Domain-Specific Languages, DSL'97, Paris, France.
• Peter Pfahler und Georg Piepenbrock. A Comparison of Modulo Scheduling Techniques for Software Pipelining. In Proc. 6th International Conference on Compiler Construction, CC' 96, Band 1060, S. 18-32. Lecture Notes in Computer Science, Springer-Verlag, 1996.
• Georg Piepenbrock. Methoden des Software-Pipelining für Prozessoren mit Instruktionsparallelität. Dissertation, Universität-GH Paderborn Fachbereich Mathematik-Informatik, 1995.
• Adrian Slowik, Georg Piepenbrock, und Peter Pfahler. Compiling nested loops for limited connectivity VLIWs. In Peter A. Fritzson, Hrsg., Proceedings International Workshop on Compiler Construction CC'94, Nummer 786 in Lecture Notes in Computer Science. Springer Verlag, April 1994.
• Friedrich Wichmann. Systolische Parallelisierung von Programmen durch Kombination von Schleifenschachteln. Dissertation, Universität-GH Paderborn Fachbereich Mathematik-Informatik, April 1997.

Produkte und Werkzeuge

• Eli: Werkzeugsystem zur Implementierung von Sprachen
• Experimentielle Umgebung für Schleifen- und Datentransformation
• LaCon: Erzeugung flexibler Konfigurierungswerkzeuge
• BBSys: Ein Werkzeugsystem zur Entwicklung paralleler Branch&Bound-Algorithmen

Kontaktadresse:

Prof. Dr. Uwe Kastens
Universität - GH Paderborn
Fachbereich Mathematik-Informatik
AG ``Programmiersprachen und Übersetzer''
Fürstenallee 11, D-33095 Paderborn
Tel.: +49 5251 60-6695
Fax: +49 5251 60-6697
uwe@uni-paderborn.de