Modellgesteuerte Leistungsmessung und Analyse paralleler Programme

Eines der Hauptziele paralleler Rechensysteme ist die Leistungssteigerung. Jedoch kann dieses Ziel durch den Einsatz eines Parallelrechners alleine nicht erreicht werden. Hierfür müssen die parallelen Anwendungsprogramme so geschrieben werden, daß das Leistungspotentiel des Parallelrechners ausgenutzt wird. Um diese Aufgabe zu lösen, sind Werkzeuge zum Monitoring des Laufzeitverhaltens paralleler Programme bzw. zur Messung der Leistung paralleler Programme erforderlich. Im Vergleich zu sequentiellen Programmen stellen parallele Programme wegen deren inhärenter Komplexität, insbesondere der aus den Kommunikationsereignissen resultierenden Abhängigkeiten zwischen parallel laufenden Prozessen, eine Reihe von neuen spezifischen Anforderungen an die Leistungsmeßwerkzeuge. Die Für sequentielle Programme als nützlich befundenen Verfahren sind für parallele Programme nicht geeignet. Für parallele Programme sind zwar auch verschiedene Meßwerkzeuge veröffentlicht worden, jedoch sind die meisten nur für spezifische Systeme entwickelt worden und damit fehlt oft die allgemeine Einsetzbarkeit bzw. die Portierbarkeit. Weiterhin ist in diesem Gebiet die Problematik der Reduzierung von Meßdaten, der Behandlung von Meßstörungen und der Modellierung von Meßzielen noch sehr erforschungsbedürftig. In der vorliegenden Arbeit wurde ein neues Verfahren zur Messung und Analyse der Leistung (vor allem der Laufzeiten) von parallelen Programmen vorgestellt. Dieses Verfahren basiert auf der Software-Monitoring-Technik. Der Grundgedanke hierbei ist wie folgt: Die Meßziele (die Fragen nach der Programmleistung, die durch die Messung zu beantworten sind) werden mittels einer Meßspezifikationssprache mit direktem und eindeutigem Bezug auf den Quelltext des zu messenden Programms modelliert und damit wird ein Meßmodell aufgebaut. Ein solches Meßmodell ist systemunabhängig und kann damit auf verschiedenen Hardwarearchitekturen und unter verschiedenen Betriebssystemen bzw. Entwicklungsumgebungen eingesetzt werden. Gesteuert durch das Meßmodell, wird der Quelltext vollautomatisch instrumentiert, d.h. Meßsensoren werden an bestimmten Stellen in den Quelltext eingefügt. Bei der Instrumentierung wird ein Auswertungsmodell generiert, das die Beziehungen zwischen den einzelnen eingefügten Meßsensoren beschreibt und die Anweisungen zur Auswertung von Meßdaten enthält. Der instrumentierte Quelltext wird in der üblichen Weise erneut compiliert. Um Meßdaten zu reduzieren, werden bei der Ausführung des instrumentierten Programms nur die zum Erreichen der Meßziele erforderlichen Meßdaten aufgezeichnet. Die Meßdaten werden dann anhand des Auswertungsmodells automatisch ausgewertet und hierbei wird die entstandene Meßstörung abgeschätzt und korrigiert. Die Auswertungsergebnisse werden in verschiedenen Formen, wie z.B. Graphik, Tabelle und Text, präsentiert und können auch mit dem Quelltext in Verbindung gebracht werden. Da die Problematik der Leistungsmessung paralleler Programme im wesentlichen in der Interprozeß-Kommunikation liegt, wurde bei diesem Verfahren das Laufzeitverhalten der Kommunikation gründlich und weitergehend untersucht. Es wurde hier davon ausgegangen, daß sich ein paralleles Programm aus einer Reihe von parallel laufenden Prozessen zusammensetzt, die nach dem Message-Passing Mechanismus miteinander kommunizieren. Die Zielarchitektur besteht aus einer Anzahl von Prozessoren, die eigenen lokalen Speicher haben und durch ein Kommunikationsnetzwerk verbunden sind. Beruhend auf diesem Verfahren, wurde ein integriertes Meßwerkzeugsystem KOPA entworfen. Im wesentlichen besteht KOPA aus vier Komponenten: dem Modellierer, Transformator, Analysator und Visualisierer. Zwischen diesen Komponenten gibt es klar definierte Schnittstellen, somit können sie jeweils auch allein angewendet werden. Ganz kurz gesagt, erhält KOPA den Quelltext des zu messenden Programms und die Meßziele als Eingaben und liefert die Auswertungsergebisse zurück. Der Meß- und Analysevorgang wird durch das Meßmodell und Auswertungsmodell gesteuert und automatisiert. Ein Prototyp von KOPA ist in ANSI C unter dem X-Windowsystem und OSF/Motif implementiert worden und kann für parallele Programme in der Programmiersprache C, die um Kommunikationsprimitive erweitert ist, eingesetzt werden. Zum Testen der allgemeinen Einsetzbarkeit von KOPA wurden sowohl parallele Programme auf Transputernetzen als auch solche auf Sun-Workstations gemessen und analysiert. Ursprünglich wurde KOPA im Rahmen des Esprit-Projektes INTREPID konzipiert. Eine minimale Implementation, die den Kern von KOPA bildet, hat in diesem Projekt bereits einen erfolgreichen Einsatz zur Messung des verteilten OCR-Systems MultiSoft auf einem Transputernetz gezeigt [BBHS93]. Die in der vorliegenden Arbeit erzielten neuen Ergebnisse lassen sich wie folgt zusammenfassen: Es wurde die Meßspezifikationssprache MESP entwickelt. Mittels MESP können die Meßziele mit direktem und eindeutigem Bezug auf den Quelltest von der Programmebene bis auf die Anweisungsebene hierarchisch modelliert werden. Eine solche Modellierung ist prinzipiell vom System (Hardware und Software) unabhängig und daher allgemein einsetzbar. Um eine noch bessere allgemeine Einsetzbarkeit zu erreichen, wurde das Gerüst von MESP in einer abstrakten Syntax dargestellt. Darauf basierend wurde eine konkrete Syntax von MESP für die Programmiersprache C definiert.Mittels der Graphentheorie wurden Meßgraphen definiert, mit denen die Messung graphisch dargestellt werden kann. Beruhend auf Meßgraphen wurden Instrumentierungsschablonen für die elementaren Meßobjekte ausgearbeitet.Die Instrumentierung des Quelltextes wird durch das Meßmodell gesteuert und anhand der Intrumentierungsschablonen automatisch ausgeführt. Dieses Verfahren realisiert die meßzielorientierte Datenaufnahme: Es werden nur solche Meßdaten aufgezeichnet, die zum Erreichen der im Meßmodell dargestellten Meßziele notwendig sind. Dadurch kann nicht nur die Menge von Meßdaten, sondern auch die Meßstörung effektiv reduziert werden.Während der automatischen Instrumentierung wird ein Auswertungsmodell erzeugt, das wiederum die Automatisierung der Auswertung von Meßdaten ermöglicht.Es wurden verschiedene Methoden zur Minimierung der Meßstörung entwickelt. Darüber hinaus wurden Modelle zur Abschätzung und Korrektur der verbleibenden Meßstörung entworfen. Weiterhin wird in KOPA erlaubt, den Grad der Meßstörung durch die Veränderung des Meßmodell-Umfangs zu kontrollieren und in einem tolerierbaren Bereich einzuschränken. KOPA geht davon aus, daß die Prozessor-Uhren synchronisiert sind. Falls dies nicht der Fall ist, benutzt KOPA einen ringstruktuierten Sychronisationsalgorithmus, der auf dem Verfahren von De Carlini und Villano [DCV88] basiert. Mit diesem Algorithmus werden die Uhren nicht physikalisch synchronisiert; es werden aber die Abweichungen zwischen verschiedenen Uhren sowohl vor dem Starten des Monitors als auch vor dessen Terminieren ermittelt. Aus diesen Abweichungen wird eine globale Zeitbasis bestimmt und die Ereignisspuren werden dann entsprechend korrigiert. Die Tauglichkeit dieses Synchronisationsalgorithmus muß noch weiter untersucht werden. Allerdings ist die Genauigkeit der Meßergebnisse direkt von der Genauigkeit und Auflösung der im System verfügbaren Uhren abhängig. Wenn eine hohe Meßgenauigkeit gewünscht wird, muß durch die Hardware eine Uhr mit einer entsprechenden Hochauflösung zur Verfügung gestellt werden (vgl. [KKC93]). Das Konzept von KOPA basiert zwar auf der Software-Monitoring-Technik, jedoch ist die Möglichkeit, daß die Hybrid-Monitoring-Technik eingesetzt wird, nicht ausgeschlossen. Im Zusammenhang mit der Hardware-Unterstützung für die Prozessor-Uhr soll untersucht werden, wieweit die Hybrid-Monitoring-Technik hierbei einsetzbar ist und welche Vorteile dieser Einsatz bringen kann. Weiterhin ist bei diesem Prototyp von KOPA angenommen, daß auf einem Prozessor nur ein Prozeß läuft. Diese Annahme schließt die Verzahnung der Laufzeiten von verschiedenen Prozessen aus und damit kann die Auswertung von Meßdaten vereinfacht werden. Für den allgemeinen Fall, daß mehrere Prozesse gemeinsam auf einem Prozessor ausgeführt werden, muß der Schduling-Algorithmus so geändert werden, daß jedes Mal, wenn ein Prozeß die CPU zugeteilt bekommt, die Prozessor-Uhrzeit und die ID-Nummer dieses Prozesses protokolliert werden, damit die von den einzelnen Prozessen tatsächlich verbrauchten Zeiten ermittelt werden können. Dies führt im allgemeinen zwar nicht zu gravierenden Problemen, aber kompliziert die Auswertung von Meßdaten. Hierfür müssen die Auswertungsalgorithmen entsprechend erweitert werden. Da es bisher in der Literatur noch keine andere Meßspezifikationssprache gibt, die von der Funktionalität und dem Umfang her mit MESP vergleichbar ist, ist die Definition von MESP als ein ``Experiment'' anzusehen. Die jetzige Version von MESP ist zwar schon recht umfangreich, es soll jedoch durch verschiedenartige Anwendungen untersucht werden, ob alle Meßanweisungen von MESP notwendig sind, oder ob MESP noch erweitert werden muß. Durch solche Untersuchungen soll die Nützlichkeit der einzelnen Meßanweisungen festgestellt werden, um einen angemessenen Umfang von MESP zu bestimmen. Die Syntax von MESP wurde formal definiert, deren Semantik hingegen wurde lediglich verbal beschrieben. Die formale Definition der Semantik ist ein wichtiger, noch anzugehender Aspekt von MESP. Damit wird nicht nur die Verifikation des mit MESP erstellten Meßmodells ermöglicht, sondern auch die Möglichkeit angeboten, die Leistungsmessung mit KOPA und die Leistungsmodellierung mit anderen bekannten Verfahren (wie z.B. Warteschlangennetze) zu kombinieren bzw. zu integrieren. Die Grundkonzeption von KOPA ist recht allgemein gehalten und daher prinzipiell auf verschiedene Programmiersprachen anwendbar. Aufgrund der Tatsache, daß verschiedene Programmiersprachen unterschiedliche Sprachkonstrukte aufzuweisen haben, muß die Implementation von KOPA bei einigen Komponenten jedoch auf einer bestimmten Sprache basieren. So ist z.B. der derzeitige Prototyp für die Programmiersprache C implementiert. Um das Werkzeugsystem KOPA multisprachen-fähig zu machen, sind eine Schnittstelle zur Umschaltung unter verschiedenen Sprachen und die entsprechenden sprachspezifischen Komponenten zu entwickeln.