Defining and Searching Communication Patterns in Event Graphs

The trend indicates ever increasing numbers of processors in supercomputers. To utilize them it is necessary to build scalable parallel software to distribute the workload. Such software requires communication and synchronization between the processes running on their respective processors. An approach to debug and analyze such software is to use event graphs. These directed graphs show the processes and the events occurring on them as well as their relations. Although event graphs are useful, they get hard to read for programs with complex communication behavior, long runtimes or large numbers of processes. An approach to ease this is to simplify the event graph by marking occurrences of well known communication structures. This allows to quickly identify different regions of activity and helps to identify parts, where certain communication patterns are expected but do not occur. This work proposes a language for the description of such communication patterns, which allows to describe the patterns including variations. Furthermore it introduces an algorithm for detecting patterns in prerecorded event traces. Detecting the occurrences of a pattern is achieved by interpreting the description for creating a reference trace. Hashes for optimizing the search are used to find potential matches of the reference in the trace. These are then merged to instances of the described pattern. Based on this a variety of improvements for the processing and presentation of event graphs are imaginable. The pattern information could be used to optimize the analyzed program or to reduce the contents to areas of interest.Der Trend bei Hochleistungsrechnern zeigt eine Tendenz zu einer steigenden Anzahl an Prozessoren. Um diese effizient nutzen zu können ist es notwendig skalierbare parallele Programme einzusetzen, die die Arbeitslast verteilen können. Solche Programme benötigen Kommunikation und Synchronisation zwischen den Prozessoren. Ein Ansatz um solche Software zu analysieren und darin enthaltene Fehler zu finden basiert auf der Verwendung von Ereignisgraphen. In diesen gerichteten Graphen werden die Prozesse, darauf auftretende Ereignisse, als auch deren Relationen zueinander dargestellt. Obwohl Ereignisgraphen ein nützliches Werkzeug sind werden sie für Programme mit komplexen Kommunikationsstrukturen, langen Laufzeiten oder hoher Prozessanzahl schwer lesbar. Ein Ansatz dies zu lindern ist deren Vereinfachung durch Hervorheben von bekannten Kommunikationsstrukturen. Dadurch ist es möglich schnell unterschiedliche Abschnitte zu identifizieren oder Bereiche in denen ein gewisses Kommunikationsmuster erwartet worden wäre jedoch nicht aufgetreten ist. In dieser Arbeit wird eine Beschreibungssprache für solche Kommunikationsmuster vorgestellt. Diese erlaubt es Muster auf eine Weise zu beschreiben, sodass auch unterschiedliche Varianten davon gefunden werden können. Außerdem wird ein Algorithmus vorgestellt um diese Muster in aufgezeichneten Ereignisdaten zu suchen. Um Vorkommnisse eines Musters zu finden werden die Musterbeschreibungen interpretiert und Referenzereignisgraphen erstellt. Hash-Werte für die Referenzdaten werden generiert und verwendet um potenzielle Vorkommnisse auf Prozessebene zu finden. Daraufhin wird versucht diese zu einer Instanz eines gesuchten Musters zusammenzufügen. Basierend auf dem vorgestellten Ansatz sind Verbesserungen für die Darstellung und Verarbeitung von Ereignisgraphen denkbar. Die gewonnene Information über Vorkommnisse von Kommunikationsmustern könnte verwendet werden um das analysierte Programm zu optimieren, oder um die Darstellung des Ereignisgraphen kompakter zu machen.submitted by Thomas KöckerbauerZusammenfassung in deutscher SpracheAbweichender Titel laut Übersetzung der Verfasserin/des VerfassersUniversität Linz, Dissertation, 2017OeBB(VLID)197189