Inhalt

Links

Teilprojekt T2: Programmierumgebungen und Übersetzer, Anwenderunterstützung

Folienpräsentation bei der Begehung durch die DFG 1999

Folienpräsentation bei der Begehung durch die DFG 2002

Ausgangssituation

Um trotz der Architekturunterschiede ein gewisses Maß an Portabilität und damit Investitionssicherung zu erreichen, finden standardisierte Kommunikationsbibliotheken in neueren parallelen Anwendungsprogrammen Verwendung.

Diese Kommunikationsbibliotheken sind jedoch der kleinste gemeinsame Nenner und haben auf Parallelrechnern zwei wesentliche Nachteile: Erstens geht ein großer Teil der Rechnerleistung bei der Abbildung der Kommunikationsbibliotheken auf die zugrundeliegende Hardware als Reibungsverlust verloren. Zweitens sind aus Sicht des Software Engineerings Kommunikationsbibliotheken ein ungenügendes Programmiermodell, das leider zu oft zu fehlerträchtigen, schlecht wartbaren und unverständlichen Programmen führt.

Im Rahmen von T2 sollen beide Nachteile für die besonderen Randbedingungen von Rechnerbündeln behoben werden. Es soll einerseits eine effiziente und optimierte Abbildung gängiger Kommunikationsbibliotheken auf ParaStation erfolgen, um existierende parallele Anwendungsprogramme kosteneffizienter ablaufen lassen zu können. Andererseits soll eine Programmierumgebung erstellt werden, die es ermöglicht, neue parallele Anwendungsprogramme erheblich einfacher zu erstellen. Statt mit Detailproblemen der parallelen Hardware zu kämpfen, soll sich der Programmierer darauf konzentrieren können, seine Anwendungsprobleme zu bearbeiten.

Zusätzlich soll intensiv mit den Anwendern (Datenbanken und Bildauswertung, Projekte N1, N2 und L1) zusammengearbeitet werden. Diese enge Zusammenarbeit hat zwei Ziele:

• die optimale Unterstützung der Anwender bei der Parallelisierung ihrer Anwendungen sowie bei der Nutzung paralleler Basisbibliotheken bzw. paralleler Programmierumgebung und
• die direkte Rückwirkung auf die Basistechnologien. Durch die Erfahrungen, die aus der aktiven Mitarbeit in den Anwendungsprojekten gewonnen werden, kommt es zu ständigen Verbesserungen der Basistechnologien, die den Anwendern wieder zur Verfügung gestellt werden können.

Stand des Teilprojekts:

JavaParty

JavaParty ist eine Java-Spracherweiterung für den Einsatz in Rechnerbündeln. Die zugehörige Laufzeitumgebung fügt mehrere virtuelle Java-Maschinen (JVMs) zu einer verteilten JVM mit virtuell gemeinsamem Adreßraum zusammen. Ein paralleles Java-Programm mit mehreren Kontrollfäden kann transparent in dieser verteilten Umgebung ablaufen. Dazu werden Klassen, die von einer anderen JVM aus referenziert werden können, durch ein neues Schlüsselwort remote markiert. Der JavaParty-Übersetzer transformiert solche entfernten Klassen zurück in reines Java plus RMI (remote method invocation). Dadurch wird ein Objekt dieser Klasse entfernt referenzierbar und seine Methoden können von einem entfernten Knoten aus aufgerufen werden. JavaParty ermöglicht im Gegensatz zur normalen Verwendung von RMI transparente entfernte Objekte, d.h. an die Stelle expliziten Exports und Nachschlagens entfernter Objekte tritt entfernte Objektinstanziierung. Ferner können auch statische Methoden aufgerufen werden und es ist entfernter Feldzugriff möglich. Weiterhin müssen in JavaParty im Gegensatz zu RMI keine zusätzlichen Ausnahmebedingungen behandelt werden und Migration entfernter Objekte auf einen anderen Knoten wird möglich. Details sind in [Phlipp98j] zu finden.

JavaParty wurde bereits erfolgreich bei einer geophysikalischen Anwendung eingesetzt  und, insbesondere mit den im folgenden dargestellten Ergebnissen im Bereich der
verbesserten Kommunikationsinfrastruktur und Anwenderunterstützung, auf den Messen CeBIT'98, Systems'98, JavaDays'98 und CeBIT'99 ausgestellt.
 

Kommunikationsinfrastruktur und Anwenderunterstützung

Neben der Verwendung des ParaStation-Netzwerks ergaben sich daher zwei weitere Ansatzpunkte für die Verbesserung der Kommunikationsleistung und damit für die
Ausführungsgeschwindigkeit von JavaParty-Programmen: Der Java-Mechanismus Objektserialisierung, der von RMI zur Übertragung von Methodenparametern eingesetzt wird, und der entfernte Methodenaufruf selbst.
 

Optimierte Objektserialisierung.

So verwendet die Java-Objektserialisierung zum Zugriff auf zu übertragende Objekte dynamische Typintrospektion, um zur Laufzeit für beliebige Objekte herauszufinden, welche Felder übertragen werden müssen, und so den Programmierer vom Schreiben expliziter Versenderoutinen für seine Klassen zu entlasten. Dynamische Typintrospektion  ist aber in Java im Vergleich zum direktem Zugriff eine zeitaufwendige Operation, die durch zwei zusätzliche Methoden zum Schreiben und Lesen von Objekten einer Klasse vermieden werden kann. Solche Versenderoutinen könnten auch durch ein Werkzeug automatisch erzeugt werden.

Um persistent gespeicherte Objekte nach langer Zeit auch dann wieder lesen zu können, wenn sich der Programmcode, der die Objekte geschrieben hat, geändert hat, erzeugt die  Java-Objektserialisierung Zusatzinformation zur Typbeschreibung. Diese Typinformation muß bei jedem Lesen von Objekten analysiert werden, um auf eventuelle Inkompatibilitäten reagieren zu können. Dieser Fall tritt bei der Kommunikation im Rechnerbündel jedoch nie ein, da alle Knoten Zugriff auf dieselbe Klassenbasis über ein gemeinsames Dateisystem haben.

Mit dem Ziel, eine effiziente Kommunikation im Rechnerbündel über entfernten Methodenaufruf in Java zu ermöglichen, haben wir daher eine eigene Objektserialisierung (UKA-Serialisierung) entwickelt. Die UKA-Serialisierung beschränkt sich darauf, die Konversion von Objektgraphen in ein plattformunabhängiges Leitungsformat durchzuführen, und verlangt das Schreiben expliziter Versenderoutinen (die allerdings automatisch generiert werden könnten). Auch im Manta-Projekt, das an der Universität Amsterdam durchgeführt wird, werden explizite Versenderoutinen eingesetzt. In den anderen Optimierungen und insbesondere in der Portabilität geht die UKA-Serialisierung aber über die Manta-Ergebnisse hinaus, die nur durch den Einsatz von maschinenabhängiger Übersetzung erreicht werden.

Im Vergleich zur Java-Serialisierung setzen wir in der UKA-Serialisierung u.a. ein besseres Puffermanagement ein und reduzieren die übertragene Zusatzinformation zur Rekonstruktion des richtigen Objekttyps auf der anderen Seite auf ein Minimum. Mit diesen und einer Reihe weiterer Optimierungen - Details finden sich in [Phlipp99a] - ist die UKA-Serialisierung die weltweit schnellste verfügbare Objektserialisierung, die ohne nativen Code auskommt und vollständig portabel in Java realisiert ist. Im Schnitt läßt sich der Aufwand für die Objektserialisierung mit der UKA-Serialisierung etwa um einen Faktor 10 reduzieren.

Diese Anstrengungen bilden den ersten Schritt hin zu einem effizienten entfernten Methodenaufruf in Java.

Die UKA-Serialisierung ist dabei ein in die Laufzeitumgebung durch Konfiguration einsteckbarer Ersatz für die Standardimplementierung. Unsere damit erzielten Ergebnisse haben auch bei Sun Microsystems Beachtung gefunden, so daß man dort erwägt, einige der in der UKA-Serialisierung eingesetzten Konzepte in eine spätere Version der Java-Bibliothek als wählbares neues Protokoll für die Objektserialisierung einfließen zu lassen.
 

Optimiertes RMI.

Ebenso wie die UKA-Serialisierung, so ist auch KaRMI derzeit weltweit ungeschlagen. Die Verbesserungen - Details sind [Phlipp99h] zu finden - lassen es zur derzeit weltweit schnellsten RMI-Implementierung in Java werden, die Nicht-TCP/IP-Netze unterstützt.
 

Lokalitätsoptimierung

Um den Programmierer von der Erstellung einer expliziten Objektverteilung zu entlasten, haben wir zwei weitere Ansätze verfolgt. Ein  vielversprechender Ansatz zur statischen Lokalitätsoptimierung durch den Übersetzer ist die Benutzung von Typinferenz zur Verbesserung des statischen Programmverständnisses. Aufgrund der allgegenwärtigen Polymorphie in objektorientierten Programmiersprachen lassen sich allein aus der bei der semantischen Analyse erzeugten statischen Typisierung des Programms keine ausreichenden Aussagen über den Kontroll- und Datenfluß des Programms gewinnen. Für JavaParty wurde daher ein Typinferenzalgorithmus zur Approximation der Laufzeittypen des Programms implementiert. Dessen Ergebnisse wurden weiter verfeinert, um Aussagen gewinnen zu können, die sich für die Lokalitätsoptimierung einsetzen lassen. Als problematisch bei diesem Ansatz hat sich herausgestellt, daß teilweise Informationen benötigt werden, die bis auf die Instanzebene einzelner Objekte herabreichen. Solche Informationen können durch statische Analyse nicht gewonnen werden. Hier ist noch offen, wie sich Ergebnisse der statischen Analyse mit Informationen kombinieren lassen, die erst zur Laufzeit vorliegen. Der zweite verfolgte Ansatz versucht, zur Laufzeit solche Informationen über Aufrufbeziehungen zwischen Objekten zu sammeln. Aufgrund dieser Informationen werden Objektmigrationen angestoßen, wenn sich herausstellt, daß eine ungünstige Plazierung vorliegt, die zu häufigen entfernten Methodenaufrufen zwischen Objekten führt. Die Arbeiten in diesem Bereich sind aber noch nicht beendet, so daß sich noch keine abschließende Bewertung durchführen läßt.
 

Ziele:

• Teilziel A: Kommunikationsinfrastruktur und Anwenderunterstützung: 
  Die Anstrengungen zur Verbesserung der Kommunikationsinfrastruktur für verteiltes paralleles Programmieren müssen in Zusammenarbeit mit den Projektpartnern aus T1, L1 und N1/2 noch intensiviert werden, da bei Anwendungen mit mehreren Kontrollfäden noch Effizienzprobleme beim Zusammenspiel mit den unterliegenden Protokollschichten auftreten. Nicht zufriedenstellende Ergebnisse bei der Kommunikationsleistung ließen sich auf eine mangelnde Unterstützung von Anwendungen mit mehreren Kontrollfäden durch die ParaStation-Bibliothek zurückführen. Aus diesem Grund erwiesen sich die inKaRMI eigentlich speziell an die ParaStation angepaßten Kommunikationsoperationen nicht immer als optimal. Nach einer Re-Integration der ParaStation-Bibliothek in den Betriebsystemkern muß daher erneut untersucht werden, ob sich die gewählten Strategien jetzt als erfolgreich herausstellen, oder ob unter den dann geänderten Voraussetzungen andere Kommunikationsoperationen zu besseren Ergebnissen führen. 
  
  Neben der Verbesserung der systemtechnischen Unterstützung konkurrierender Kontrollfäden sollte die Kommunikationsinfrastruktur auch noch dadurch verbessert werden, daß Latenzzeiten beim Zugriff auf entfernte Datenelemente verborgen werden. Da RMI und damit auch JavaParty keinen asynchronen Methodenaufruf unterstützen, muß hierfür noch eine geeignete Vorgehensweise gefunden werden. Zwar könnte ein asynchrones Anfordern von Datenelementen in KaRMI eingebaut werden, allerdings würde man dann die Kompatibilität zum Java-Standard aufgeben. 
  
  Bei der Anwenderunterstützung ist die Notwendigkeit folgender Arbeitsschritte absehbar: Portierung des JavaParty-Übersetzers auf den neuen Java-2-Standard und eventuell die Erstellung eines Werkzeugs zur automatischen Erzeugung von Versenderoutinen für die UKA-Serialisierung. Auch die UKA-Serialisierung muß an zukünftige Java-Versionen bei deren Erscheinen angepaßt werden. Zudem müssen bei Optimierungen in der Basis-Netzwerktechnologie diese neuen Vorteile auch für die Java Anwedungen nutzbar gemacht werden. 
  
  Lokalitätsoptimierung:
  Zur Lokalitätsoptimierung wurden bisher folgende Ansätze vorgeschlagen: statische Datenverteilung durch den Übersetzer, dynamische Datenverteilung durch das Laufzeitsystem, Aufbewahren von Lokalitätsinformation zwischen Programmläufen und die geeignete Einbeziehung des Programmierers in die Optimierungsentscheidungen. Hiervon wurden bereits zwei Ansätze in Angriff genommen, wobei sich aber abzeichnet, daß sich eine zufriedenstellende Lösung nicht durch ein Verfahren alleine gewinnen läßt. 
  
  
• Teilziel B: Statische Lokalitätsoptimierung mit Hilfe von Typinferenz. 
  Durch Typinferenz gewinnt man eine gute Approximation der Laufzeittypen des Programms und wird überhaupt erst in die Lage versetzt, Aussagen über den Kontrollfluß des Programms zu treffen.
  Diese Kontrollflußinformationen stellen eine Approximation des globalen Kontrollflußgraphen des Programms zur Laufzeit dar. Diese globale Sicht auf das Programm ermöglicht der Lokalitätsoptimierung, von einer Programmstelle aus einen gewissen Blick in die Zukunft des Programmablaufs zu werfen. So kann beispielsweise festgestellt werden, wo ein aktuell erzeugtes Objekt in Zukunft benutzt werden wird, d.h. wo dessen Methoden aufgerufen werden. Ohne Typinferenz verschwinden solche Informationen sofort hinter generischen Schnittstellen. In verteilten Java-Programmen tritt dieser Effekt aufgrund der allgegenwärtigen Verwendung von interfaces und Threads stärker als in anderen objektorientierten Sprachen ein. So ist beispielsweise ohne Datenflußanalyse und Typinferenz nicht einmal die Aufrufbeziehung zwischen einem Thread-Objekt und dem dazugehörigen Arbeitsobjekt automatisch nachvollziehbar, auch wenn beide direkt nebeneinander erzeugt werden. In diesem Fall liegt das daran, daß diese Beziehung für alle Threads und alle Arbeitsobjekte des Programms über die Standard-Schnittstelle Runnable realisiert wird. Die Verwendung von Typinferenz im Gegensatz zu reiner Datenflußanalyse hat den entscheidenden Vorteil, daß der Typinferenzalgorithmus unter gewissen Voraussetzungen in der Lage ist, die durch die Datenflußanalyse entdeckten Unsicherheiten z.B. in der Kontrollflußinformation aufzulösen. 
  Aus den durch diese statische Analyse gewonnenen Lokalitätsinformationen läßt sich im weiteren eine Transformation des Programms ableiten, die gewährleistet, daß zur Laufzeit die entsprechenden Daten bereits bei ihrer Allokation richtig angeordnet sind. Das vermeidet zur Laufzeit kostspielige Datenumverteilungen. 
  Der als Basis gewählte Typinferenzalgorithmus sucht für das Programm global eine Approximation der Laufzeittypinformation zu berechnen. Zur Auflösung von Unschärfen in der Datenflußinformation ist diese Berechnung mit wiederholten semantikerhaltenden Programmtransformationen verbunden, welche die Polymorphie durch Replikation von Strukturen des Programms auflösen. Dieser Typinferenzalgorithmus wurde erweitert, um eine Verbesserung des Auflösungsvermögens bei der Analyse nebenläufiger Programme zu erreichen. Die Verbesserung der Auflösung wird durch die Einführung von Hilfspolymorphie erreicht und dient dazu, die Verwendung von Objekten in unterschiedlichen Kontrollfäden zu erkennen. 
  
  Das iterative Vorgehen in Kombination mit dem globalen Herangehen an das Programm führt zu einer sehr langen Analysezeit während der Lokalitätsoptimierung. Eine zu untersuchende Frage ist, ob und wie die Analyse lokal auf einzelnen Klassen oder einzelnen Methoden durchgeführt werden kann, und inwieweit sich die daraus lokal gewonnenen Informationen für die Lokalitätsanalyse und Transformation des gesamten Programms kombinieren lassen. Bei diesem Ansatz ist vorstellbar, daß möglicherweise weite Teile des Programms gar nicht erst analysiert werden müssen, da frühzeitig erkannt wird, daß sie für die Lokalität gar nicht relevant sind. Eine sich direkt daran anschließende Fragestellung ist, ob sich dann nicht auch Analyseergebnisse z.B. für Bibliotheksklassen zur Wiederverwendung in weiteren Übersetzungsläufen aufbewahren lassen. Eine solche Wiederverwendung ist mit dem bisherigen Ansatz nicht möglich, da alle Klassen immer im globalen Kontext des zu übersetzenden Programms analysiert werden. 
  In manchen Fällen ist es notwendig, Verteilungsentscheidungen aufgrund von Informationen auf Instanzebene zu treffen. Werden z.B. Objekte in aufeinanderfolgenden Iterationen einer Schleife erzeugt, lassen sich diese Objekte nie statisch unterscheiden, da die Anzahl der Schleifendurchläufe i.d.R. unbekannt ist. Verhalten sich diese Objekte aber unterschiedlich (z.B. Benutzung in verschiedenen Threads) und ist daher ihre Unterscheidung für die Lokalitätsoptimierung wichtig, kann allein durch statische Analyse kein zufriedenstellendes Ergebnis erzielt werden. Alle diese Objekte werden von der statischen Analyse unter einer Äquivalenzklasse subsumiert, so daß auch die Programmtransformation nicht gesondert auf die einzelnen Instanzen eingehen kann. Es muß untersucht werden, wie sich statische Analyse und Laufzeitmessungen an einer solchen Stelle am besten ergänzen können. Der Typinferenzalgorithmus bietet bei einer nicht auflösbaren Unsicherheit nämlich die Möglichkeit, diese Unsicherheit durch den Kontrollflußgraphen zurückzuverfolgen und ihre Ursachen zu identifizieren. Ursachen sind i.d.R. weit von der Stelle der Kontrollflußunsicherheit entfernt und entstehen durch das Zusammenfließen von unterschiedlichen Datenflußwerten in einer Programmvariablen. Es soll untersucht werden, wie die so statisch gewonnene Information über kritische Programmstellen genutzt werden kann, um dynamische Optimierungsverfahren gezielter einsetzen und so Stärken von statischer und dynamischer Analyse bestmöglich kombinieren zu können.

 
• Teilziel C: Dynamische Lokalitätsoptimierung. 
  Lokalitätsoptimierung zur Laufzeit ist nur möglich, wenn das Programm beim Übersetzen darauf vorbereitet wurde. Es muß Code zum Sammeln relevanter Informationen eingestreut werden, die Auswertung dieser Informationen zur Laufzeit durchgeführt werden und es müssen bei Bedarf Objektumverteilungen angestoßen werden. Dieser Zusatzaufwand zur Laufzeit führt zu Geschwindigkeitseinbußen und zusätzlichem Speicherplatzverbrauch, um die gesammelten Daten zu halten. Beides, Rechenzeit- und Speichermehraufwand, muß minimiert werden. 
  
   Die dynamische Lokalitätsoptimierung hat dabei immer nur eine lokale Sicht auf das Programm, d.h. ist räumlich beschränkt auf höchstens den aktuellen Knoten, im schlimmsten Fall auf den aktuellen Methodenaufruf. Zeitlich gesehen ist kein Blick in die Zukunft wie bei der statischen Analyse möglich, da Informationen immer nur genau bis zu dem Punkt vorliegen, bei dem die Programmausführung gerade angekommen ist. Die zur Laufzeit vorliegenden Daten können daher auch nicht dazu verwendet werden, Plazierungsentscheidungen so zu treffen, daß in Zukunft möglichst wenig unnötige Kommunikation entsteht, sondern können lediglich benutzt werden, um schon bestehende ungünstige Objektverteilungen zu erkennen und in der Hoffnung nachzubessern, daß sich das Kommunikationsverhalten nicht ändert. Aufgrund der räumlichen Beschränktkeit sind aber nur lokal gute Nachbesserungen zu erwarten. Eine solche Nachbesserung findet in JavaParty mit Hilfe von Objektmigration statt. Es ist aber noch nicht klar, wie die Stelle im Programm zu identifizieren ist, an der die Fehlentscheidung bei der Plazierung getroffen wurde, die im nachhinein zu der Korrektur geführt hat. Dieser Blick in die Vergangenheit ist aber notwendig, um die gewonnene Information zwischen mehreren Programmläufen zu retten bzw. sie in eine Programmtransformation zur Lokalitätsoptimierung einfließen zu lassen, um bei folgenden Programmläufen gleich die richtigen Entscheidungen zu treffen. 
  
  Die Stärke dynamischer Lokalitätsoptimierung liegt darin, daß zur Laufzeit Information auf Instanzebene vorliegt. Messungen und eventuelle Korrekturen sind daher unabhängig davon, wo und wie die betreffenden Objekte erzeugt wurden. Probleme wie die Erzeugung von Objekten in aufeinanderfolgenden Iterationen einer Schleife bei der statischen Lokalitätsoptimierung spielen hier keine Rolle. Sollen die Ergebnisse eines Benchmarkinglaufs aber wie oben erwähnt in eine Programmtransformation einfließen, so sind auch hier die selben Probleme zu erwarten. Das Ziel bei dynamischer Lokalitätsoptimierung muß daher sein, sie nur gezielt da einzusetzen, wo statische Analyse versagt. Dafür ist zusätzlich zur oben schon erwähnten Problematik der Integration beider Verfahren zu klären, wie sich die Laufzeitmessungen so gezielt einschränken lassen, um einerseits entsprechend aussagekräftige Ergebnisse zu erzielen, andererseits aber den Mehraufwand zur Laufzeit deutlich reduzieren zu können.
• Teilziel D: Benutzereingriff in Plazierungsentscheidungen. 
  In JavaParty gibt es momentan zwei Möglichkeiten, die Objektplazierung von Hand zu bestimmen. Zum einen kann mit jeder Objekterzeugung die Maschinennummer angegeben werden, auf der das neue Objekt angelegt werden soll. Zum anderen kann beim Programmstart ein sog. Strategieobjekt/Objektdistributor mit angegeben werden, der bei einer Objekterzeugung aufgrund der Klasse des Objekts entscheidet, wo es angelegt werden soll. 
  Beide Alternativen haben sich allerdings als nur bedingt geeignet herausgestellt. Bei der direkten Angabe der Zielmaschine wird der Algorithmus zur Objektverteilung über das gesamte Programm verstreut, ist schlecht wartbar, behindert die Wiederverwendung von Teilen des Gesamtprogramms und läßt sich nicht gut zielplattformunabhängig formulieren. Ein Objektdistributor kapselt zwar den Verteilungsalgorithmus, hat meist aber zu wenig Information über das Objekt, welches gerade angelegt werden soll, um zu einer guten Verteilung führen zu können. Der erste Ansatz bietet also einen zu geringen Abstraktionsgrad, beim zweiten Ansatz geht an der Schnittstelle zur Objektverteilung zu viel Information verloren. Beide Ansätze haben gleichermaßen das Problem, daß der Programmierer den gesamten Verteilalgorithmus spezifizieren muß und nicht nur an entscheidenden Stellen helfend eingreifen kann. 
  
  Ein noch zu entwickelnder Ansatz muß dem Programmierer eine Notation an die Hand geben, mit der er dem System wichtige Hinweise auf die Beziehungen zwischen Programminstanzen geben kann, damit das System das Problem der Lokalitätsoptimierung für eine gegebene Zielplattform bestmöglich selbst lösen kann. Ansonsten müßte er die komplette Objektverteilung für alle möglichen Zielplattformen unter Berücksichtigung ihrer Parameter konkret ausformulieren. In diesem Zusammenhang erscheint es wünschenswerter, die Annotation der eigentlichen Objektverteilung durch die Annotation von erwarteten Kommunikationsbeziehungen bzw. anzustrebenden Lokalitäten zu ersetzen. Die dann zu lösende Aufgabe besteht darin, ein System zu bauen, das die so zur Verfügung gestellten Lokalitätsinformationen in eine geeignete Verteilung für die Zielplattform umsetzt.