Novel techniques for performance modeling and prediction of parallel and distributed programs

Abstract

Um komplexe technische Probleme zu lösen, beziehungsweise um die Zeit für das Lösen eines Problems zu reduzieren, werden die Programme für ressourcenintensive, wissenschaftlich-technische Aufgaben auf parallelen und verteilten Rechnersystemen ausgeführt, die meistens mehrere Rechnerknoten enthalten. Die Diskrepanz zwischen der theoretisch erreichbaren Performanz und der erreichten Performanz, wenn ein bestimmtes Programm auf einem parallelen und verteilten Rechnersystem ausgeführt wird, ist jedoch sehr groß. Diese Diskrepanz kann durch das Abstimmen der Performanz eines Programms für ein bestimmtes Rechnersystem verringert werden. Der Programmierer entwickelt normalerweise mehrere Versionen eines Programms, basierend auf verschiedenen Parallelisierungsstrategien. Danach setzt der Programmierer die Performanz jeder Programmversion fest und wählt jene Programmversion aus, die die höchste Performanz erzielt. Die Entwicklung solcher Programme stellt einen zeitaufwendigen, fehleranfälligen Prozess dar, der mehrere Zyklen der Codeentwicklung, Kompilierung, Ausführung und Performanzanalyse umfasst.<br />In dieser Dissertation präsentieren wir eine Reihe von Techniken und die dazugehörigen Softwarewerkzeuge für die Performanzanalyse und Performanzabschätzung der parallelen und verteilten Programme. Diese Techniken und Werkzeuge werden während des Entwicklungsprozesses der performanzintensiven Programme benutzt, um die Resultate der Performanzabschätzung von Beginn der Entwicklung an anzubieten.<br />Basierend auf dem Performanzmodell kann die Performanz abgeschätzt werden und die Designentscheidungen können, ohne zeitintensive Veränderungen der bereits implementierten Teile des Programms, beeinflusst werden.<br />Unser Ansatz unterstützt die graphische Spezifizierung der Performanzmodelle, einerseits intuitiv für die Menschen, die es benutzen, andererseits einsetzbar für die maschineneffiziente Modellevaluierung. Um unseren Ansatz evaluieren zu können, haben wir ein System für die Performanzanalyse und -abschätzung, den sogenannten Performance Prophet, entwickelt. Mit Hilfe des Performance Prophet können viele Programmversionen untersucht werden, da die Zeit für Evaluierung eines Programmmodells sehr kurz ist. Die rasche Evaluierung der Performanzmodelle durch den Performance Prophet basiert auf der Methodik, die Modellvereinfachung und Kombination der mathematischen Modellierung mit diskreter Ereignismodellierung beinhaltet. Des Weiteren bietet der Performance Prophet eine UML-basierte Benutzerschnittstelle, welche die Spezifizierung und die Veränderung des Performanzmodells beschleunigt. Der Benutzer spezifiziert ein Performanzmodell graphisch mit Hilfe von UML. Der Performance Prophet übersetzt automatisch das auf UML basierende Performanzmodell in C++ und evaluiert es mit Hilfe der Simulation.<br />Wir demonstrieren die Brauchbarkeit des Performance Prophet mit der Modellierung und Simulation eines realen materialwissenschaftlichen Programms das ungefähr 15.000 Codezeilen beinhaltet. In unserer Fallstudie ist die Modell-evaluierung mit dem Performance Prophet auf einem Einprozessorarbeitsplatzrechner mehrere tausend Mal schneller als die Ausführung des Programms auf einem Cluster.<br />Die wichtigsten Beiträge dieser Dissertation beinhalten: (1) eine Bestandsaufnahme der aktuellen Techniken in diesem Forschungsbereich; (2) die UML-basierte domänen-spezifische Sprache für parallele und verteilte Programme; (3) die UML-basierte domänen-spezifische Sprache für Grid Workflows; (4) die Methodik für die automatische Modellübersetzung aus UML in C++; (5) die Methodik um die Zeit, die für die Evaluierung des Performanzmodells eines Rechnersystems notwendig ist, zu reduzieren; (6) ein objektorientierter Ansatz für die Arbeitslastmodellierung; (8) ein integrativer Ansatz für die Simulation der Rechnersysteme; (9) eine Klassifizierung der Techniken für die Simulation der Rechnersysteme. Die Software, die im Kontext dieser Dissertation erstellt wurde, wurde auf Anfrage an 450 Personen weltweit verteilt.<br />

The solution of resource-demanding scientific and engineering computational problems involves the execution of programs on parallel and distributed computing systems, which commonly consist of multiple computational nodes, in order to solve large problems or to reduce the time to solution for a single problem. However, there is a widening gap between the maximal theoretical performance and the achieved performance when a certain program is executed on a parallel and distributed computing system. This gap may be reduced by tuning the performance of a program for a specific computing system. Commonly, the programmer develops multiple versions of the program following various parallelization strategies. Thereafter, the programmer assesses the performance of each program version, and selects the program version that achieves the highest performance. Therefore, the program development for parallel and distributed computing systems is a time-consuming and error-prone process that involves many cycles of code editing, compiling, executing, and performance analysis.<br />In this thesis we present a set of techniques and the corresponding tool-support for performance modeling and prediction of parallel and distributed programs, which may be used in the process of performance-oriented program development for providing performance prediction results starting from the early program development stages.<br />Based on the performance model, the performance can be predicted and design decisions can be influenced without time-consuming modifications of large parts of an implemented program.<br />Our approach supports the graphical specification of performance models in a human-intuitive fashion on the one hand, and on the other hand is amenable to the machine-efficient model evaluation. For the purpose of evaluation of our approach we have developed a performance modeling and prediction system called Performance Prophet. Performance Prophet is suitable to explore a large set of possible program's versions, because the time spent for evaluation of the program model with Performance Prophet is very short. The rapid performance model evaluation capability of Performance Prophet is due to our methodology that involves model simplification, and combination of mathematical modeling with discrete event simulation. Furthermore, Performance Prophet provides a UML based graphical user interface, which alleviates the problem of specification and modification of the performance model. The user specifies graphically the performance model using UML. Afterwards, Performance Prophet automatically transforms the performance model from UML to C++ and evaluates it by simulation.<br />We demonstrate the usefulness of Performance Prophet by modeling and simulating a real-world material science program that comprises about 15,000 lines of code. In our case study, the model evaluation with Performance Prophet on a single processor workstation is several thousand times faster than the execution time of the real program on our cluster.<br />The major contributions of this thesis include: (1) a survey of the state of the art, (2) a UML-based domain specific language for parallel and distributed programs, (3) a UML-based domain specific language for Grid workflows, (4) a method for automatic model transformation from UML to C++, (5) a methodology for reducing the time needed to evaluate the performance model of a computing system, (6) an object-oriented approach for workload modeling, (7) a scalable approach for performance modeling of large-scale computing systems, (8) an integrated approach for simulation of computing systems, and (9) a taxonomy of techniques for simulation of computing systems.<br />The software that is developed in the context of this thesis is distributed worldwide at the request to more than 450 persons.