HOME | ENGLISH | IMPRESSUM | KIT

Aufgabenstellung: Visualisierung von Programmgraphen

Zurück zur Übersicht

image In diesem Praktikum entwickeln Sie eine Anwendung zur Visualisierung von Programmgraphen.

Motivation

Sowohl Übersetzer als auch Werkzeuge zur Programmanalyse verwenden Graphen zur Repräsentation von Programmen. Knoten solcher Graphen stehen beispielsweise für Anweisungen und Ausdrücke des Programms, Kanten des Graphen für Abhängigkeiten zwischen solchen Knoten, oder repräsentieren den Steuerfluss des Programms. Solche Graphen sind das Ergebnis von Übersetzung, Optimierung und Analyse von Programmen. Für die Entwicklung neuer Optimierungen und Analysen ist es für Entwickler unabdingbar, die Graphen problematischer Programme manuell zu inspizieren. Nur so können Gelegenheiten zur Verbesserungen der Verfahren identifiziert, und deren Ergebnisse nachvollzogen werden. Möglich ist dies nur durch automatische Visualisierung von Programmgraphen unter Verwendung geeigneter Graphlayout-Algorithmen.

Mit den Themengebieten Programmanalyse, Compilerbau und Graphzeichnen bekommen Sie zu dem Einblick in die Forschung von gleich zwei Lehrstühlen, dem IPD Snelting und dem ITI Wagner.

Aufgabe

Sie realisieren eine Anwendung zur Visualisierung von Programmgraphen. Dazu adaptieren Sie aus der Literatur bekannte Graphlayout-Algorithmen an die spezifischen Anforderungen für Programmgraphen. Neben der Darstellung und dem Layout von Programmgraphen implementieren Sie auch einfache Funktionen zur interaktiven Exploration der Graphen.

Anforderungen an die Visualisierung von Programmgraphen

Allgemein ergibt aus dem Programmfluss die Anforderung, dass die Aufrufsreihenfolge der Anweisungen und Ausdrücke sich in der Visualisierung wieder finden soll. Im Graphzeichnen werden hierzu typischerweise so genannte Lagen-Layouts verwendet. Bei diesen Layouts wird jedem Knoten eine Ebene zu geordnet, so dass möglichst viele Kanten einer höher liegenden Ebene gerichtet sind. Das Framework von Sugyiama unterteilt die Berechnung eines Lagen-Layouts in verschiedenen Phasen, z. B. in das Zuordnen der Knoten auf die verschiedenen Lagen und die Kreuzungsminimierung zwischen zwei Ebenen.

Das Framework bietet eine Vielfalt von Möglichkeiten um weitere Kriterien aus dem Bereich der Visualisierung von Programmgraphen aufzunehmen. Die Anforderungen an die Visualisierung von Programmgraphen hängen von der Art von Programmgraphen ab: Programmabhängigkeitsgraphen zur Sicherheitsanalyse unterscheiden sich strukturell von Zwischenrepräsentationen für optimierende Übersetzer, und müssen daher unterschiedlich visualisiert werden. Dazu entwickeln Sie entweder zusammen mit Entwicklern des Übersetzer-Frameworks libFirm oder mit Entwicklern des Sicherheitsanalysewerkzeugs JOANA geeignete Anforderungen an die Visualisierung entsprechender Graphen. Beispielsweise erfordern libFirm-Graphen eine besondere Behandlung von Blöcken und sogenannter φ-Knoten, während JOANA geeignete Unterstützung von Summary-Kanten erfordert.

Minimale Leistungsmerkmale

Folgende minimale Leistungsmerkmale soll Ihr Programm erfüllen:

  • Einlesen und Visualisierung generischer Graphen im GraphML Format.
  • Einlesen und Visualisierung von entweder
    • JOANA-Programmabhängigkeitsgraphen, oder
    • libFirm-Graphen (Zwischenrepräsentation im Übersetzerbau)
    im jeweiligen Format, und unter der Beachtung der spezifischen Anforderungen.
  • Elementare Funktionen zur Exploration der Graphen: Zoom, Scrollen, Filterung (z. B. nach Knoten-/ Kantentyp, Ausblendung selektierter Knoten)
  • Implementierung eines Verfahrens zum Zeichnen von Graphen.
    • Dies kann beispielsweise ein Kräfte-basiertes Verfahren sein oder das Framework von Sugiyama
    • Anpassungen an dem Framework werden entsprechend der Anforderungen gegeben durch die Struktur der JOANA-Graphen oder libFirm-Graphen vorgenommen.
  • Modulare Architektur (z. B. Model-View-Controller-Prinzip)
  • Implementierungssprache: Wir schlagen Java vor, aber nach Absprache mit den Betreuern sind auch andere objektorientierte Sprachen möglich.

Bemerkung

Dies ist Ihr Projekt. Dieses Dokument ist kein Katalog von Aufgaben, der Punkt für Punkt abgearbeitet werden muss, um nachher den Schein zu bekommen, sondern lediglich eine Reihe von Hinweisen, was wir erwarten. Wie Ihr Programm nachher aussieht, müssen Sie selbst entscheiden.

Organisatorisches

Für jede Phase des Praktikums muss ein Phasendokument abgegeben werden. Dieses Dokument ist Grundlage für das Kolloquium am Ende jeder Phase, in dem die Gruppe die Ergebnisse der Phase vorträgt.

Erste Schritte

  • Programmiersprache festlegen!

  • Werkzeuge sichten:
    Versionsverwaltung mit Subversion oder Git? Dokumente mit LaTeX oder Office schreiben? UML-Diagramme?

  • Funktionale Anforderungen überlegen:
    Markt sichten, Muss-Kriterien, Wunsch-Kriterien und Abgrenzungskriterien.

  • Tipps-Dokument lesen. Siehe Website.

Literatur

Weitere Quellen zu den Themen der Aufgabe.

Bewertung

Die Benotung Ihres Systems richtet sich nach folgenden Kriterien:

  • Qualität aller abgegebenen Dokumente und Artefakte

  • Qualität der Kolloquien (10 Minuten Vortrag)

  • Qualität der Abschlusspräsentation

  • Erfüllung der minimalen Leistungsmerkmale (s.o.)

  • sinnvolle Erweiterungen über diese Merkmale hinaus

  • Robustheit des erstellten Programms

  • Teamarbeit (TSE)

Diese Liste hat keine Reihenfolge, die einer Gewichtung entspricht. Es gibt sicherlich weitere Punkte, die als selbstverständlich gelten und sich bei Nichterfüllen negativ auswirken (z.B. ist die Geschwindigkeit der implementierten Algorithmen sekundär, aber jedem sollte klar sein, dass das Errechnen einer Lösung oder das Generieren nicht 10 Minuten dauern darf).

Weitere Pflichten

  • Anmeldung per Studienportal für PSE und TSE

  • Anwesenheit bei den wöchentlichen Treffen mit dem Betreuer

  • Team-internes Management (z.B. Phasenverantwortliche, Versionskontrolle)

  • Artefakte 1–2 Tage vor Kolloquium beim Betreuer