http://www.hgesser.de/

Private Homepage von Hans-Georg Eßer

header

Navigation

Privates

Publikationen

Studium

Software

Vorlesungen

Online-Training

Sonstiges

Blaue Links: intern
Rote Links: extern


Vorläufiges Dissertationsthema

Automatische Leistungsanalyse paralleler Programme

Für die Lösung von komplexen, sehr rechenintensiven Aufgabenstellungen aus dem technisch-naturwissenschaftlichen Bereich werden immer häufiger hochparallele Mehrprozessorsysteme eingesetzt. Von besonderem Interesse sind zur Zeit zwei Architekturklassen. Dies sind zum einen Rechner mit verteiltem gemeinsamem Speicher (DSM - distributed shared memory), die einen globalen Adressraum auf dem physisch verteilten Speicher realisieren. Zum anderen handelt es sich um Rechner, deren Komponenten aus leistungsfähigen Mehrprozessorsystemen mit gemeinsamem Speicher bestehen, die über ein Hochgeschwindigkeitsnetzwerk gekoppelt sind.

Die Programmentwicklung für Parallelrechner besteht aus vier Phasen: Programmentwurf, Kodierung, Fehlersuche und Programmoptimierung. Der Programmoptimierung kommt hierbei eine weit größere Bedeutung zu als bei der Softwareentwicklung für sequentielle Rechner, da der Einsatz von Parallelrechnern nur für solche Anwendungen vertretbar ist, die aufgrund ihres Rechenaufwandes und ihrer Zeitvorgaben auf sequentiellen Rechnern nicht schnell genug bearbeitet werden können. Die Programmoptimierungsphase ist ein Zyklus mit zwei Schritten: die Leistungsanalyse zur Erkennung von Leistungsengpässen und die Ausführung von Programmtransformationen aufgrund der gefunden Engpässe.

Auch die Leistungsanalyse zerfällt wieder in zwei elementare Phasen, die zyklisch ausgeführt werden bis ein Leistungsengpass erkannt wurde, der dann durch geeignete Programmtransformationen entfernt oder zumindest gemildert werden kann. Diese Phasen sind das Messen von Leistungsdaten und das Bewerten der Messdaten.

Zur Erfassung von Leistungsdaten werden im wesentlichen zwei Techniken eingesetzt, das Sampling und das Tracing. Beim Sampling wird die Programmausführung in bestimmten Abständen unterbrochen und es werden geeignete Messwerte, z. B. die Zahl der Cachefehler oder die momentan ausgeführte Operation, erfasst. Aus diesen Messwerten können dann statistische Daten über die gesamte Programmausführung abgeleitet werden. Die Technik des Tracing basiert hingegen auf einer Instrumentierung des Programms, so dass bestimmte Ereignisse der Programmausführung, z. B. Start und Ende eines Unterprogramms oder Senden und Empfangen einer Nachricht, protokolliert werden. Die erfassten Daten geben ein sehr genaues Bild des Laufzeitverhaltens, werden aber meistens in so großer Menge erzeugt, dass sie weder effizient erfasst und gespeichert werden können, noch eine Auswertung ohne grafische Werkzeuge möglich ist.

Zur Bewertung der Leistungsdaten stehen eine Vielzahl von Werkzeugen zur Verfügung, die in zwei Klassen unterteilt werden können: Werkzeuge, die summarische Informationen in Bezug zum Programmtext darstellen, und Werkzeuge, die das dynamische Laufzeitverhalten durch grafische Diagramme veranschaulichen. So stehen zum Beispiel auf der CRAY T3E im ZAM die Analysewerkzeuge Apprentice und VAMPIR zu Verfügung. Apprentice ist eine Eigenentwicklung von Cray und erlaubt die Sortierung der Routinen eines Programms nach bestimmten Leistungsdaten, z. B. Ausführungszeit oder Overheadzeit, die über der gesamten Laufzeit und allen Prozessen summiert wurden. Aus den Unterprogrammen können dann einzelne Programmzeilen ausgewählt und ihre Leistungsdaten abgefragt werden. VAMPIR wurde am ZAM entwickelt und erlaubt u.a. die Visualisierung des dynamischen Programmverhaltens basierend auf Ausführungsprotokollen. Die zentrale Darstellung ist die sogenannte Timeline, in der alle Ereignisse der Prozesse nach ihrem Auftreten sortiert dargestellt werden und Nachrichten zwischen den Prozessen in Form von Pfeilen eingetragen sind. Wegen seiner flexiblen Visualisierungstechniken gilt VAMPIR als das leistungsfähigste Analysewerkzeug seiner Art.

Die hier exemplarisch vorgestellten Werkzeuge der CRAY T3E verdeutlichen den Stand der Technik in diesem Bereich: Es existieren leistungsfähige Werkzeuge, die unterschiedliche Verfahren zur Erfassung von Leistungsdaten einsetzen und unterschiedliche Hilfsmittel zur Identifikation von Leistungsengpässen bereitstellen. Es ist aber alleine die Verantwortung des Anwenders, das jeweils beste Werkzeug auszuwählen und es so zu benutzen, dass er auch tatsächlich die vorhandenen Engpässe bestimmen kann. Dies ist um so unerfreulicher, da viele parallele Programme eine kleine Menge häufig wiederkehrender Leistungsengpässe aufweist, so dass schon eine automatische Erkennung dieser wenigen Leistungsengpässe eine große Arbeitserleichterung für den Anwender darstellen würde.

Im Rahmen dieser Doktorarbeit soll eine automatische Steuerung des Leistungsanalysezyklus so realisiert werden, dass sie in Programmierumgebungen verschiedener Parallelrechner integriert werden kann. Hierzu müssen folgende Teilaufgaben gelöst werden:

  • Festlegung einer geeigneten Terminologie
  • Modellierung des Leistungsanalysezyklus
  • Entwurf eines Formalismus zur Beschreibung von Leistungsengpässen
  • Katalogisierung von Leistungsengpässen für verschiedene Programmierumgebungen
  • Entwicklung geeigneter Techniken zur Wissensrepräsentation und Wissensverarbeitung
  • prototypische Implementierung der entwickelten Konzepte
Die Implementierung erfolgt im Rahmen von KOJAK (Kit for Objective Judgement and Automatic Knowledge-based detection of bottlenecks), einer Analyseumgebung, die zur Zeit am ZAM realisiert wird. KOJAK stellt alle Komponenten zur Verfügung, die zur Erfassung von Leistungsdaten basierend auf den Werkzeugen einer gegebenen Programmierumgebung erforderlich sind. Hierbei handelt es sich um eine Datenbank zur Speicherung von Messwerten, und um Komponenten zur Kontrolle der Programminstrumentierung, der Programmausführung und der Übernahme von Leistungsdaten in die Datenbank.

Die auf die wissenschaftliche Fragestellung dieser Dissertation zielende Literatur ist in wichtigen Arbeiten und Quellen dem Arbeitsplan für die Durchführung der Dissertation beigefügt und bei den einzelnen Arbeitsphasen ausgewiesen. Die Dissertation ist weiterhin eingebunden in die Diskussionen der Esprit IV Arbeitsgruppe APART (Automatic Performance Analysis: Resources and Tools), die vom 1. Januar 1999 bis zum 31. Dezember 2000 von der EU gefördert wird. Die Arbeitsgruppe setzt sich aus drei europäischen Firmen, sechs europäischen Universitäten, drei amerikanischen Universitäten und dem Forschungszentrum Jülich zusammen, das auch für die Organisation verantwortlich ist.

Arbeitsplan für die Durchführung der Dissertation "Automatische Leistungsanalyse paralleler Programme"

von Herrn Hans-Georg Eßer
  1. Einarbeitung in die Architekturkonzepte und die Programmierung von Parallelrechnern
    • Architektur und Programmierung der CRAY T3E
    • Architektur und Programmierung der SGI Origin 2000 Literatur: Hersteller Zeitaufwand: 4 Monate
  2. Studium der Konzepte und Techniken von existierenden Leistungsanalysewerkzeugen und Erstellung einer Liste von Beispielen für Leistungsengpässe:
    • Gprof, Apprentice, PAT
    • VAMPIR, Medea, Pablo, Paradigm, Kappa-Pi Literatur: [1] - [11] Zeitaufwand: 4 Monate
  3. Sichtung von Techniken zur Wissensrepräsentation und Wissensverarbeitung und Bestimmung eines geeigneten Formalismus zur Darstellung von Leistungsengpässen
    • Einarbeitung in Literatur zu Expertensystemen und Wissensrepräsentation
    • Anwendung geeignet erscheinender Techniken auf die gesammelten Beispiele von Leistungsengpässen
    Literatur: [12] - [14] Zeitaufwand: 4 Monate
  4. Erstellung eines Katalogs von Leistungsengpässen für zwei verschiedene Programmierumgebungen unter Verwendung des gewählten Formalismus
    Zeitaufwand: 4 Monate
  5. Implementierung und Test der automatischen Steuerung im Rahmen von KOJAK
    Zeitaufwand: 14 Monate
  6. Fertigstellung der schriftlichen Arbeit
    Zeitaufwand: 6 Monate

Literatur

[1]D.M. Pase, Functional Design of the MPP Apprentice Performance Tool, CrayResearch, 1994
[2]A. Espinosa, T. Margalef, E. Luque, Automatic Performance Evaluation ofParallel Programs,Sixth Euromicro Workshop on Parallel and Distribued Processing,1998
[3]B.R. Helm, A.D. Malony, Automating Performance Diagnosis: a Theory andArchitecture, International Workshop on Computer Performance Measurement and Analysis (PERMEAN '95),1995
[4]M.T. Heath, A.D. Malony, D.T. Rover, The Visual Display of Parallel Performance Data, IEEE Computer, Vol. 28, No. 11, pp. 21-28, 1995
[5]J.K. Hollingsworth, Finding Bottlenecks in Large Scale Parallel Programs,Ph.D. Thesis, University of Wisconsin - Madison, 1994
[6]A. Hondroudakis, Performance Analysis Tools for Parallel Programs, Edingburgh Parallel Computing Centre, The University of Edingburgh, 1995
[7]Alan H. Karp, Horace P. Flatt, Measuring Parallel Processor Performance,Communications of the ACM, May 1990, Vol. 33, No. 5, 539-543, 1990
[8]B.P. Miller, M.D. Callaghan, J.M. Cargille, J.K. Hollingsworth, R.B. Irvin, K.L.Karavanic, K. Kunchithapadam, T. Newhall, The Paradyn Parallel Performance Measurement Tool, IEEE Computer, Vol. 28, No. 11, pp. 37-46, 1995
[9]W.E. Nagel, A. Arnold, M. Weber, H-C. Hoppe, K. Solchenbach, VAMPIR: Visualization and Analysis of MPI Resources, Supercomputer 63, Vol. 12, No. 1, pp. 69-80, 1996
[10]C.M. Pancake, M.L. Simmons, J.C. Yan, Performance Evaluation Tools for Parallel and Distributed Systems, IEEE Computer, Vol. 28, No. 11, pp. 16-19, 1995
[11]D.A. Reed, R.A. Aydt, T.M. Madhyastha, R.J. Noe, K.A. Shields, B.W.Schwartz, An Overview of the Pablo Performance Analysis Environment, Technical Report, University of Illinois, Department of Computer Science,1992
[12]R. Elmasri, S.B. Navathe, Fundamentals of Database Systems, The Benjamin/Cummings Publishing Company, 1989
[13]F. Puppe, Einführung in Expertensysteme, Springer Verlag, 1991
[14]S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 1995

Last modified: Tue Jan 4 22:41:38 CET 2000


Copyright © 1997-2018 Hans-Georg Eßer; Server: Debian Linux, Apache Web Server, letzte Änderung: Thursday, 15-Jun-2006 14:16:30 CEST
Theme: Hazard Area 1.6 (modified), created by Bryan Bell, Copyright © 2000-2006 Weblogger.com.