Michael Philippsen

Erkennung von Flaky-Tests auf Basis von Software-Versionsdaten und Testausführungshistorie
Regressionstests werden häufig und aufgrund ihres großen Umfangs zumeist vollautomatisiert ausgeführt. Sie sollen sicherstellen, dass Änderungen an einzelnen Komponenten eines Softwaresystems keine unerwünschten Nebenwirkungen auf das Verhalten von Teilsystemen haben, die von den Modifikationen eigentlich gar nicht betroffen sein sollten. Doch selbst wenn ein Testfall ausschließlich unveränderten Code ausführt, kann es trotzdem vorkommen, dass er manchmal erfolgreich ist und manchmal fehlschlägt. Derartige Tests nennt man "flaky" und die Gründe dafür können sehr vielfältig sein, u.a. Wettlaufsituationen bei nebenläufiger Ausführung oder vorübergehend nicht verfügbare Ressourcen (z.B. Netzwerk oder Datenbanken). Flaky-Tests sind für den Testprozess in jeder Hinsicht ein Ärgernis, denn sie verlangsamen oder unterbrechen sogar die gesamte Testausführung und sie untergraben das Vertrauen in die Testergebnisse: Ist ein Testlauf erfolgreich, kann daraus nicht zwangsläufig geschlossen werden, dass das Programm diesbezüglich wirklich fehlerfrei ist, und schlägt der Test fehl, müssen ggf. teure Ressourcen investiert werden, um das Problem zu reproduzieren und ggf. zu beheben.Der einfachste Weg, Test-Flakyness zu erkennen, besteht darin, Testfälle wiederholt auf der identischen Code-Basis auszuführen, bis sich das Testergebnis ändert oder mit einer gewissen statistischen Aussagesicherheit davon auszugehen ist, dass der Test nicht "flaky" ist. Im industriellen Umfeld ist dieses Vorgehen jedoch selten möglich, da Integrations- oder Systemtests extrem zeit- und ressourcenaufwendig sein können, z.B. weil sie die Verfügbarkeit spezieller Test-Hardware voraussetzen. Aus diesem Grund ist es wünschenswert, die Klassifikation von Testfällen hinsichtlich Flakyness ohne wiederholte Neuausführung vorzunehmen, sondern dabei ausschließlich auf die bereits verfügbaren Informationen aus den bisherigen Entwicklungs- und Testphasen zurückzugreifen.Im Jahr 2022 wurden verschiedene sogenannte Black-Box-Verfahren zur Erkennung von Test-Flakyness vergleichend untersucht, in einem realen industriellen Testprozess mit 200 Testfällen evaluiert und in ein praktisches Werkzeug implementiert. Die Klassifikation eines Testfalls erfolgt dabei ausschließlich auf Basis allgemein verfügbarer Informationen aus Versionskontrollsystemen und Testausführungswerkzeugen - also insbesondere ohne aufwändige Analyse der Codebasis oder Überwachung der Testüberdeckung, die im Falle eingebetteter Systeme in den meisten Fällen ohnehin unmöglich wäre. Von den 122 verfügbaren Indikatoren (u.a. z.B. die Testausführungszeit, die Anzahl der Code-Zeilen oder die Anzahl der geänderten Code-Zeilen in den letzten 3, 14 und 54 Tagen) wurden verschiedene Teilmengen extrahiert und ihre Eignung für die Erkennung von Test-Flakyness bei Verwendung unterschiedlicher Verfahren untersucht. Zu diesen Verfahren zählen regelbasierte Methoden (z.B. "ein Test ist flaky, wenn er mind. fünfmal innerhalb des Beobachtungsfensters fehlgeschlagen ist, aber dabei nicht fünfmal hintereinander"), empirische Bewertungen (u.a. die Bestimmung der kumulierten gewichteten "flip rate", also die Häufigkeit des Alternierens zwischen Testerfolg und -fehlschlag) sowie verschiedene Verfahren aus der Domäne des Maschinellen Lernens (u.a. Klassifikationsbäume, Random Forest oder Multi-Layer Perceptrons). Die Verwendung KI-basierter Klassifikatoren zusammen mit dem SHAP-Ansatz zur Erklärbarkeit von KI-Modellen führte zur Bestimmung der wichtigsten vier Indikatoren ("features") für die Bestimmung der Test-Flakyness im konkret untersuchten industriellen Umfeld. Als optimal hat sich dabei das sog. "Gradient Boosting" mit der kompletten Indikatorenmenge herausgestellt (F1-score von 96,5%). Nur marginal niedrigere Accuracy- und Recall-Kennwerte (bei nahezu gleichem F1-score) konnte das gleiche Verfahren mit nur vier ausgewählten Features erzielen.
Synergien von vor- und nachgelagerten Analysemethoden zur Erklärung künstlicher Intelligenz
Der Einsatz künstlicher Intelligenz verbreitet sich rasant und erobert immer neue Domänen des täglichen Lebens. Nicht selten treffen Maschinen dabei auch durchaus kritische Entscheidungen: Bremsen oder Ausweichen beim autonomen Fahren, Kredit(un)würdigkeit privater Personen bzw. von Unternehmen, Diagnose von Krankheiten aus diversen Untersuchungsergebnissen (z.B. Krebserkennung aus CT/MRT-Scans) u.v.m. Damit ein solches System im produktiven Einsatz Vertrauen verdient, muss sichergestellt und nachgewiesen sein, dass die gelernten Entscheidungsregeln korrekt sind und die Realität widerspiegeln. Das Trainieren eines maschinellen Modells selbst ist ein sehr ressourcenintensiver Prozess und die Güte des Ergebnisses ist in der Regel nur mit extrem hohem Aufwand und fundiertem Fachwissen nachträglich quantifizierbar. Der Erfolg und die Qualität des erlernten Modells hängt nicht nur von der Wahl des KI-Verfahrens ab, sondern wird im besonderen Maße vom Umfang und der Güte der Trainingsdaten beeinflusst.Im Jahr 2022 wurde daher untersucht, welche qualitativen und quantitativen Eigenschaften eine Eingabemenge haben muss ("a-priori-Bewertung"), um damit ein gutes KI-Modell zu erzielen ("a-posteriori-Bewertung"). Dazu wurden verschiedene Bewertungskriterien aus der Literatur vergleichend bewertet und darauf aufbauend vier Basisindikatoren definiert: Repräsentativität, Redundanzfreiheit, Vollständigkeit und Korrektheit. Die zugehörigen Metriken erlauben eine quantitative Bewertung der Trainingsdaten im Vorfeld. Um die Auswirkung schlechter Trainingsdaten auf ein KI-Modell zu untersuchen, wurde mit dem sog. "dSprites"-Datensatz experimentiert, einem verbreiteten Generator für Bilddateien, der bei der Bewertung von Bilderkennungsverfahren eingesetzt wird. Damit wurden gezielt verschiedene Trainingsdatensätze generiert, die sich jeweils in genau einem der vier Basisindikatoren unterscheiden und dabei quantitativ unterschiedliche "a-priori-Güte" haben. Damit wurden jeweils zwei verschiedene KI-Modelle trainiert: Random Forest und Convolutional Neural Networks. Anschließend wurde die Güte der Klassifikation durch das jeweilige Modell anhand der üblichen statistischen Maße (Accuracy, Precision, Recall, F1-score) quantitativ bewertet. Zusätzlich wurde SHAP (ein Verfahren zur Erklärbarkeit von KI-Modellen) genutzt, um die Gründe für eine etwaige Missklassifikation bei schlechter Datenlage zu ermitteln. Wie erwartet, korreliert die Modellqualität mit der Trainigsdatenqualität: Je besser letztere hinsichtlich der vier Basisindikatoren abschneiden, desto genauer klassifiziert das trainierte Modell unbekannte Daten. Eine Besonderheit hat sich jedoch bei der Redundanzfreiheit herausgestellt: Erfolgt die Bewertung eines trainierten Modells mit komplett neuen/unbekannten Eingaben, dann ist die Genauigkeit der Klassifikation teils signifikant schlechter, als wenn die verfügbaren Eingabedaten in einen Trainings- und einen Evaluationsdatensatz geteilt werden: In letzteren Fall suggeriert die a-posteriori-Bewertung irreführend eine höhere Modellqualität.
Few-Shot Out-Of-Domain-Erkennung in der maschinellen Verarbeitung natürlicher Sprache
Die maschinelle Verarbeitung natürlicher Sprache ("Natural Language Processing", kurz NLP) hat viele Anwendungsgebiete, z.B. telefonische oder schriftliche Dialogsystemen (sog. Chat-Bots), die eine Kino-Auskunft erteilen, eine Eintrittskarte buchen, eine Krankmeldung aufnehmen oder Antworten auf diverse Fragen in bestimmten industriellen Abläufen geben. Häufig beteiligen sich derartige Chat-Bots auch in sozialen Medien, um z.B. kritische Äußerungen zu erkennen und ggf. zu moderieren. Mit zunehmendem Fortschritt auf dem Gebiet der künstlichen Intelligenz im Allgemeinen und der NLP im Speziellen, verbreiten sich zunehmend selbstlernende Modelle, die ihr fachliches und sprachliches Wissen erst während des konkreten praktischen Einsatzes dynamisch (und daher meist unüberwacht) ergänzen. Doch derartige Ansätze sind empfänglich für absichtlich oder unabsichtlich bösartige Beeinflussung. Beispiele aus der industriellen Praxis haben gezeigt, dass Chat-Bots schnell z.B. rassistische Äußerungen in sozialen Netzen "erlernen" und anschließend gefährdende extremistische Äußerungen tätigen. Daher ist es von zentraler Bedeutung, dass NLP-basierte Modelle zwischen gültigen "In-Domain (ID)" und ungültigen "Out-Of-Domain (OOD)" Daten (also sowohl Ein- als auch Ausgaben) unterscheiden können. Dazu benötigen die Entwickler eines NLP-Systems für das initiale Training des KI-Modells jedoch eine immense Menge an ID- und OOD-Trainingsdaten. Während erstere schon schwer in hinreichender Menge zu finden sind, ist die a-priori-Wahl der letzteren i.d.R. kaum sinnvoll möglich.Im Jahr 2022 wurden daher verschiedene Ansätze zur OOD-Erkennung untersucht und vergleichend bewertet, die mit wenigen bis keinen ("few-shot") Trainingsdaten funktionieren. Als Grundlage für die experimentelle Evaluierung diente das derzeit beste und am weitesten verbreitete, Transformer-basierte und vortrainierte Sprachmodell RoBERTa. Zur Verbesserung der OOD-Erkennung wurden u.a. "fine-tuning" eingesetzt und untersucht, wie zuverlässig die Anpassung eines vortrainierten Modells an eine konkrete Domäne funktioniert. Zusätzlich wurden verschiedene Scoring-Verfahren implementiert und evaluiert, um Grenzwerte für die Klassifikation von ID- und OOD-Daten zu bestimmen. Um das Problem der fehlenden Trainingsdaten zu lösen, wurde auch ein Verfahren namens "data augmentation" evaluiert: Dabei wurden mittels GPT3 ("Generative Pretrained Transformer 3", ein autoregressives Sprachmodell, das Deep Learning verwendet, um menschenähnlichen Text zu erzeugen) zusätzliche ID- und OOD-Daten für das Training bzw. die Evaluation von NLP-Modellen generiert.
Anwendung gewichteter Kombinatorik bei der Erzeugung und Auswahl von Parametern und deren Repräsentanten im Software-Test

Einige funktionale Testverfahren (sogenannte Black-Box-Tests), beispielsweise die Äquivalenzklassenmethode oder Grenzwertanalyse, fokussieren sich auf einzelne Parameter. Für diese Parameter ermitteln sie Repräsentanten (Werte oder Klassen von Werten), die im Test zu berücksichtigen sind. Da für die Durchführung von Tests in der Regel nicht nur ein einzelner Parameter, sondern mehrere Parameter benötigt werden, müssen zur Ausführung eines Tests Repräsentanten mehrerer Parameter miteinander kombiniert werden. Üblicherweise werden dazu gut verstandene Kombinationsmethoden verwendet, wie "All Combinations", "Pair-wise" oder "Each choice". Dabei werden Informationen über Gewichte (Attribute wie bspw. die Wichtigkeit oder Priorität) der Parameter und Repräsentanten nicht berücksichtigt, die sich auf die Anzahl der zugehörigen Testfälle (z.B. aufgrund der Wichtigkeit) bzw. auf ihre empfohlene Reihenfolge (im Sinne der Priorisierung) auswirken sollten. Darüber hinaus gibt es im Falle der Äquivalenzklassenmethode Szenarien, bei denen eine Kombination mehrerer ungültiger Klassen in einem Testfall optional explizit gewünscht, gänzlich unerwünscht oder auf eine bestimmte Anzahl beschränkt bleiben sollte, um einerseits Fehlerkombinationen gezielt zu testen, aber andererseits die Fehlerlokalisierung zu vereinfachen. Es besteht Grund zur Annahme, dass durch die Berücksichtigung von derartigen Gewichten und Optionen zielgerichtetere und letztlich effizientere Testfälle abgeleitet werden können.

Im Jahr 2023 wurden daher zunächst bereits bekannte kombinatorische Ansätze untersucht und vergleichend bewertet, die Gewichte bei der Kombination von Parametern oder ihren Werten berücksichtigen. Darauf aufbauend wurde ein neuartiger Ansatz in der Erzeugung und Auswahl von Parametern und deren Repräsentanten im Software-Test entwickelt. Die vorgeschlagene Methode nutzt ein Gewichtungssystem, um individuelle Parameter, deren Äquivalenzklassen und konkrete Repräsentanten dieser Klassen in einer Testfallmenge zu priorisieren. Darüber hinaus können auch jeweils deren Interaktionen gezielt gewichtet werden, um bei Bedarf bestimmte Kombinationen häufiger in der generierten Testfallmenge vorkommen zu lassen. Zur Evaluation des Ansatzes wurde prototypisch eine geeignete Datenstruktur zur Repräsentation der verschiedenen Gewichtungen definiert. Anschließend wurden Bewertungsfunktionen für bestehende Testfallmengen implementiert, um quantitativ bestimmen zu können, wie gut eine Testfallmenge die vorgegebene Kombinatorik erfüllt. In einem weiteren Schritt wurden diese Bewertungsfunktionen in Kombination mit verschiedenen systematischen und heuristischen Verfahren verwendet (SAT-Solver Z3 bzw. Simulated Annealing und Genetische Algorithmen), um neue Testfallmengen passend zur Gewichtung zu generieren oder bestehende Testfallmengen durch Ergänzung fehlender Testfälle dahingehend zu optimieren. In den Versuchsreihen hat Simulated Annealing die schnellsten und besten Ergebnisse ermittelt. Das SAT-Verfahren funktionierte zwar für kleine Problemstellungen, war aber für größere Testfallmengen aufgrund exorbitanter Laufzeiten nicht mehr praxistauglich.

Die fortschreitende Digitalisierung verändert neben dem Arbeitsmarkt auch die Bildungslandschaft. Mit Mitteln aus dem DigitalPakt Schule werden u.a. im Zuge des Programms BAYERN DIGITAL II gravierende Veränderungen in der Informatikausbildung vorangetrieben, die wiederum neue Herausforderungen auf den verschiedenen Bildungsebenen mit sich ziehen. 
Das Projekt CS4MINTS begegnet eben diesen Herausforderungen entlang der Bildungskette und knüpft an bereits im Rahmen des Projekts MINTerAKTIV gestartete Maßnahmen, wie u.a. der Stärkung der Begegnung zunehmender Heterogenität der Studierenden im Zuge der Einführungsveranstaltung in die Informatik, an.So wird im Zuge der Begabtenförderung das Frühstudium in Informatik aktiv für Mädchen beworben und das Angebot explizit erweitert. Durch frühzeitiges Vorgehen gegen genderspezifische Stereotypen bzgl. Informatik sowie eine Erweiterung des Fortbildungsangebots um gendersensitiven Informatikunterricht in allen Schularten, soll langfristig ein signifikanter Anstieg des Frauenanteils im Fach Informatik erreicht werden.Durch die Erweiterung des Pflichtfachs Informatik in allen Schulen besteht außerdem ein großer Bedarf an geeigneten Unterrichtskonzepten und einer Stärkung der LehrerInnenbildung. Hierfür soll im Projektzeitraum ein regionales Netzwerk aufgebaut werden, um universitär erarbeitete und evaluierte Unterrichtsideen zur Stärkung von MINT im curricularen und extra-curricularen Rahmen zur Verfügung zu stellen. Im Jahr 2020 haben wir mit der ersten Pilotierung der Konzeption zur Automatisierung des Feedbacks im Übungsbetrieb der Einführungsveranstaltung in die Informatik begonnen. Dazu wurden die Rückgabewerte der JUnit-Tests von Abgaben analysiert und erste mögliche Fehlerquellen untersucht. Im nächsten Schritt soll eine Möglichkeit ausgearbeitet werden, wie auf Grundlage dieser Rückgabewerte auf Programmierfehler oder Fehlvorstellungen der Studierenden geschlossen werden kann. Ziel dieser Bemühungen ist es schließlich, den Studierenden ein automatisch generiertes, kompetenzorientiertes Feedback zu ermöglichen, welches ihnen nach Abgabe der Programmieraufgaben (oder ggfls. schon während der Erarbeitungsphase) zur Verfügung steht. Das Feedback soll aufzeigen an welcher Stelle Fehler im Programmcode auftraten sowie auf mögliche Ursachen hinweisen.Im Hinblick auf eine Begegnung von Heterogenität haben wir im Jahr 2020 die Inhalte des Repetitoriums für Informatik (RIP) dem bayerischen Lehrplan verschiedener Schularten gegenübergestellt. Die Inhalte sollen anschließend so angepasst werden, dass StudienanfängerInnen unterschiedlichster Bildungszweige gleiche Chancen haben, mittels des Repetitoriums mögliche Defizite zu erkennen und diese zu beheben. Außerdem wurde im Wintersemester 2020 während der Repetitoriumswoche erstmalig eine tägliche Programmiersprechstunde eingerichtet, in der es den TeilnehmerInnen möglich war Fragen zu stellen sowie Feedback zu den Aufgaben zu erhalten.Der Einstieg in die Programmierung stellt für viele Studierende eine der großen Hürden zu Beginn des Studiums dar. Um den Programmieranfänger:innen zusätzliches Feedback zu ermöglichen, haben wir im Jahr 2021 das Projekt Feedback+ konzipiert und pilotiert. Im Rahmen von Feedback+ haben die Studierenden die Möglichkeit, Probleme, welche während der Bearbeitung der Übungsaufgaben oder beim Einrichten/Benutzen der Programmierumgebung auftreten, zu dokumentieren und in wöchentlich buchbaren Einzelsprechstunden zusätzliches Feedback zu erhalten. Dazu wurde eine StudOn-Umgebung eingerichtet, in der Probleme systematisch dokumentiert werden können. Eine erste Evaluation in Form von Einzelinterviews mit den teilnehmenden Studierenden lieferte ein durchweg positives Feedback und einen Wunsch auf Fortsetzung des Projektes.

• Entwicklung eines funktionsfähigen VR-Visualisierungsprototyps zu Demonstrations- und Forschungszwecken.
• Mapping von dynamischer Laufzeitdaten auf die statische Struktur als Grundlage für deren Analyse und Visualisierung.    
• Entwurf und Implementierung der Anomalieerkennung von Ablaufspuren durch ein Unsupervised-Learning-Verfahren. 

• Erweiterung des Prototyps um die Darstellung dynamischen Software-Verhaltens.    
• Kooperative (Remote-)Nutzung des Visualisierungsprototyps.    
• Auswertung von Commit-Nachrichten zur Anomalieerkennung.    
• Clustering der Aufrufe eines Systems nach Anwendungsfällen.  

Übersetzer für Programmiersprachen sind äußerst komplexe Anwendungen, an die hohe Korrektheitsanforderungen gestellt werden: Ist ein Übersetzer fehlerhaft (d.h. weicht sein Verhalten vom dem durch die Sprachspezifikation definierten Verhalten ab), so generiert dieser u.U. fehlerhaften Code oder stürzt bei der Übersetzung mit einer Fehlermeldung ab. Solche Fehler in Übersetzern sind oftmals schwer zu bemerken oder zu umgehen. Nutzer erwarten deshalb i.A. eine (möglichst) fehlerfreie Implementierung des verwendeten Übersetzers.

Leider lassen sowohl vergangene Forschungsarbeiten als auch Fehlerdatenbanken im Internet vermuten, dass kein real verwendeter Übersetzer fehlerfrei ist. Es wird deshalb an Ansätzen geforscht, mit deren Hilfe die Qualität von Übersetzern gesteigert werden kann. Da die formale Verifikation (also der Beweis der Korrektheit) in der Praxis oftmals nicht möglich oder rentabel ist, zielen viele der Forschungsarbeiten darauf ab, Übersetzer möglichst umfangreich und automatisiert zu testen. In den meisten Fällen erhält der zu testende Übersetzer dabei ein Testprogramm als Eingabe. Anschließend wird das Verhalten des Übersetzers bzw. des von ihm generierten Programms überprüft: Weicht dieses vom erwarteten Verhalten ab (stürzt der Übersetzer also beispielsweise bei einem gültigen Eingabeprogramm mit einer Fehlermeldung ab), so wurde ein Fehler im Übersetzer gefunden. Soll dieser Testvorgang automatisiert stattfinden, ergeben sich drei wesentliche Herausforderungen:

• Woher kommen die Testprogramme, auf die der Übersetzer angewendet wird?
• Was ist das erwartete Verhalten des Übersetzers bzw. des von ihm erzeugten Codes? Wie kann bestimmt werden, ob das tatsächliche Verhalten des Übersetzers korrekt ist?
• Wie können Testprogramme, die einen Fehler im Übersetzer anzeigen, vorbereitet werden, um der Behebung des Fehlers im Übersetzer bestmöglich behilflich zu sein?

Während die wissenschaftliche Literatur diverse Lösungen für die zweite Herausforderung vorstellt, die auch in der Praxis bereits etabliert sind, stellt die automatisierte Generierung zufälliger Testprogramme noch immer eine große Hürde dar. Damit Testprogramme zur Detektion von Fehlern in allen Teilen des Übersetzers verwendet werden können, müssen diese allen Regeln der jeweiligen Programmiersprache genügen, d.h. die Programme müssen syntaktisch und semantisch korrekt (und damit übersetzbar) sein. Auf Grund der Vielzahl an Regeln "echter" Programmiersprachen stellt die Generierung solcher übersetzbarer Programme eine schwierige Aufgabe dar. Dies wird zusätzlich dadurch erschwert, dass das Programmgenerierungsverfahren möglichst effizient arbeiten muss: Die wissenschaftliche Literatur zeigt, dass die Effizienz eines solchen Verfahrens maßgebliche Auswirkungen auf seine Effektivität hat -- nur wenn in kurzer Zeit viele (und große) Programme generiert werden können, kann das Verfahren sinnvoll zur Detektion von Übersetzerfehlern eingesetzt werden.

In der Praxis scheitert das automatisierte Testen von Übersetzern deshalb oftmals daran, dass kein zugeschnittener Programmgenerator verfügbar ist und die Entwicklung eines solchen einen zu hohen Aufwand bedeutet. Ziel unseres Forschungsprojekts ist daher die Entwicklung von Verfahren, die den Aufwand für die Implementierung von effizienten Programmgeneratoren reduzieren.

Weil in der automatische Generierung zufälliger Testprogramme zumeist große Programme generiert werden müssen, um eine effiziente Fehlersuche zu ermöglichen, können diese Programme nur schwer zur Behebung des Fehlers verwendet werden. Üblicherweise ist nur ein sehr kleiner Teil des Programms ursächlich für den Fehler, und möglichst viele anderen Teile müssen automatisch entfernt werden, bevor die Behebung des Fehlers plausibel ist. Diese sogenannte Testfallreduktion nutzt auch die bereits angesprochenen Lösungen für die Erkennung des erwarteten Verhalten und ist für automatisch generierte Programme unerlässlich,
sodass eine gemeinsame Betrachtung mit den anderen Komponenten sinnvoll ist. Üblicherweise ist die Testfallreduktion so gestaltet, dass fehlerauslösende Programm aus allen Quellen verarbeitet werden können.

Leider ist oftmals nicht klar, welches der verschiedenen in der wissenschaftlichen Literatur vorgestellten Verfahren sich am besten für welche Situation eignet. Außerdem dauert eine Testfallreduktion in einigen Fällen sehr lange. Ziel unseres Forschungsprojekts ist daher, eine aussagekräftige Testfallsammlung zu schaffen und an dieser bestehende Verfahren zu vergleichen und zu verbessern.

Im Jahr 2018 haben wir mit der Entwicklung eines entsprechenden Werkzeugs begonnen. Als Eingabe dient eine Spezifikation der syntaktischen und semantischen Regeln der jeweiligen Programmiersprache in Form einer abstrakten Attributgrammatik. Eine solche erlaubt eine knappe Notation der Regeln auf hohem Abstraktionsniveau. Ein von uns neu entwickelter Algorithmus erzeugt dann Testprogramme, die allen spezifizierten Regeln genügen. Der Algorithmus nutzt dabei diverse technische Ideen aus, um eine angemessene Laufzeit zu erreichen. Dies ermöglicht die Generierung großer Testfallmengen in vertretbarer Zeit, auch auf üblichen Arbeitsplatzrechnern. Eine erste Evaluation hat nicht nur gezeigt, dass unser Verfahren sowohl effektiv als auch effizient ist, sondern auch dass es flexibel einsetzbar ist. So haben wir mit Hilfe unseres Verfahrens nicht nur Fehler in den C-Übersetzern gcc und clang entdeckt (unser Verfahren erreicht dabei eine ähnliche Fehleraufdeckungsgüte wie ein sprachspezifischer Programmgenerator aus der wissenschaftlichen Literatur), sondern auch diverse Bugs in mehreren SMT-Entscheidern. Einige der von uns entdeckten Fehler waren den jeweiligen Entwicklern zuvor noch unbekannt.

Im Jahr 2019 haben wir zusätzliche Features für das Schreiben von Sprachspezifikationen implementiert und die Effizienz des Programmgenerierungsverfahrens gesteigert. Durch die beiden Beiträge konnte der Durchsatz unseres Werkzeugs deutlich gesteigert werden. Des Weiteren haben wir mit Hilfe neuer Sprachspezifikationen Fehler in Übersetzern für die Programmiersprachen Lua und SQL aufgedeckt. Die Ergebnisse unserer Arbeit sind in eine Ende 2019 eingereichte (und inzwischen angenommene) wissenschaftliche Publikation eingeflossen. Neben der Arbeit an unserem Verfahren zur Programmgenerierung haben wir außerdem mit der Arbeit an einem Verfahren zur Testfallreduzierung begonnen. Das Verfahren reduziert die Größe eines zufällig generierten Testprogramms, das einen Fehler in einem Übersetzer auslöst, um die Suche nach der Ursache des Fehlers zu vereinfachen.

Im Jahr 2020 lag der Fokus des Forschungsprojekts auf sprachunabhängigen Verfahren zur automatischen Testfallreduzierung. Die wissenschaftliche Literatur schlägt unterschiedliche Reduzierungsverfahren vor. Da es bislang allerdings keinen aussagekräftigen Vergleich dieser Verfahren gibt, ist unklar, wie effizient und effektiv die vorgeschlagenen Reduzierungsverfahren tatsächlich sind. Wie wir festgestellt haben, gibt es dafür im Wesentlichen zwei Gründe, die darüber hinaus auch die Entwicklung und Evaluation neuer Verfahren erschweren. Zum einen verwenden die vorhandenen Implementierungen der vorgeschlagenen Reduzierungsverfahren unterschiedliche Implementierungssprachen, Programmrepräsentationen und Eingabegrammatiken. Mit diesen Implementierungen ist ein fairer Vergleich dieser Verfahren deshalb kaum möglich. Zum anderen gibt es keine umfangreiche Sammlung von (noch unreduzierten) Testprogrammen zur Evaluation von Reduzierungsverfahren. Dies hat zur Folge, dass die publizierten Reduzierungsverfahren jeweils nur mit sehr wenigen Testprogrammen evaluiert wurden, was die Aussagekraft der präsentierten Ergebnisse beeinträchtigt. Da in manchen Fällen darüber hinaus nur Testprogramme in einer einzigen Programmiersprache verwendet wurden, ist bislang unklar, wie gut diese Verfahren für Testprogramme in anderen Programmiersprachen funktionieren (wie sprachunabhängig diese Verfahren also tatsächlich sind). Um diese Lücken zu schließen, haben wir im Jahr 2020 mit der Implementierung eines Frameworks begonnen, das die wichtigsten Reduzierungsverfahren beinhaltet und so einen fairen Vergleich dieser Verfahren ermöglicht. Außerdem haben wir mit der Erstellung einer Testfallsammlung begonnen. Diese beinhaltet bereits etwa 300 Testprogramme in den Sprachen C und SMT-LIB 2, die etwa 100 unterschiedliche Fehler in realen Übersetzern auslösen. Diese Testfallsammlung erlaubt nicht nur aussagekräftigere Vergleiche von Reduzierungsverfahren, sondern verringert außerdem den Aufwand für die Evaluation zukünftiger Verfahren. Anhand erster Experimente konnten wir feststellen, dass es bislang kein Reduzierungsverfahren gibt, dass in allen Fällen am besten geeignet ist.

Außerdem haben wir uns im Jahr 2020 mit der Frage beschäftigt, wie das im Rahmen des Forschungsprojekts entstandene Framework zur Generierung zufälliger Testprogramme erweitert werden kann, um neben funktionalen Fehlern auch Performance-Probleme in Übersetzern finden zu können. Im Rahmen einer Abschlussarbeit ist dabei ein Verfahren entstanden, das eine Menge zufällig generierter Programme mit Hilfe von Optimierungstechniken schrittweise so verändert, dass die resultierenden Programme im getesteten Übersetzer deutlich höhere Laufzeiten als in einer Referenzimplementierung auslösen. Erste Experimente haben gezeigt, dass so tatsächlich Performance-Probleme in Übersetzern gefunden werden können.

Im Jahr 2021 haben wir die Implementierung der wichtigsten Reduzierungsverfahren aus der wissenschaftlichen Literatur sowie die Erstellung einer Testfallsammlung für deren Evaluation abgeschlossen. Aufbauend darauf haben wir außerdem einen quantitativen Vergleich der Verfahren durchgeführt; soweit wir wissen, handelt es sich dabei um den mit Abstand umfangreichsten und aussagekräftigsten Vergleich bisheriger Reduzierungsverfahren. Unsere Ergebnisse zeigen, dass es bislang kein Verfahren gibt, das in allen Anwendungsfällen am besten geeignet wäre. Außerdem konnten wir feststellen, dass es für alle Verfahren zu deutlichen Ausreißern kommen kann, und zwar sowohl hinsichtlich Effizienz (also wie schnell ein Reduzierungsverfahren ein Eingabeprogramm reduzieren kann) als auch Effektivität (also wie klein das Ergebnis eines Reduzierungsverfahrens ist). Dies deutet darauf hin, dass es noch Potenzial für die Entwicklung weiterer Reduzierungsverfahren in der Zukunft gibt, und unsere Ergebnisse liefern einige Einsichten, was dabei zu beachten ist. So hat sich beispielsweise gezeigt, dass ein Hochziehen von Knoten im Syntaxbaum unabdingbar für die Generierung möglichst kleiner Ergebnisse (und damit eine hohe Effektivität) ist und dass eine effiziente Behandlung von Listenstrukturen im Syntaxbaum notwendig ist. Die Ergebnisse unserer Arbeit sind in eine im Jahr 2021 eingereichte und angenommene Publikation eingeflossen.

Außerdem haben wir im Jahr 2021 untersucht, ob bzw. wie sich die Effektivität unseres Programmgenerierungsverfahrens steigern lässt, wenn bei der Generierung die Überdeckung der zugrundeliegenden Grammatik berücksichtigt wird. Im Rahmen einer Abschlussarbeit wurden dazu unterschiedliche, aus der wissenschaftlichen Literatur stammende kontextfreie Überdeckungsmetriken für den Anwendungsfall adaptiert sowie implementiert und evaluiert. Dabei hat sich gezeigt, dass die Überdeckung hinsichtlich einer kontextfreien Metrik nur bedingt mit der Fehleraufdeckung korreliert.  In zukünftigen Arbeiten sollte deshalb untersucht werden, ob Überdeckungsmetriken, die auch kontextsensitive, semantische Eigenschaften berücksichtigen, besser für diesen Anwendungsfall geeignet sind.

Im Jahr 2022 wurde im Rahmen einer Abschlussarbeit mit der Entwicklung eines Rahmenwerks für die Realisierung sprachadaptierter Reduktionsverfahren begonnen. Dieses Rahmenwerk stellt eine domänenspezifische Sprache (DSL) zur Verfügung, mit deren Hilfe sich Reduktionsverfahren auf einfache und knappe Art und Weise beschreiben lassen. Mit diesem Rahmenwerk und der entwickelten DSL soll es möglich sein, bestehende Reduktionsverfahren mit möglichst wenig Aufwand an die Besonderheiten einer bestimmten Programmiersprache anpassen zu können. Die Hoffnung dabei ist, dass solche sprachadaptierten Verfahren noch effizienter und effektiver arbeiten können als die bestehenden, sprachunabhängigen Reduktionsverfahren. Darüber hinaus soll das Rahmenwerk auch den Aufwand für die Entwicklung zukünftiger Reduktionsverfahren verringern und könnte so einen wertvollen Beitrag für die Forschung auf diesem Gebiet leisten.

In Jahr 2023 lag der Fokus des Forschungsprojekts auf den Listenstrukturen, die bereits in 2021 kurz angesprochen wurden: Nahezu alle seit 2021 untersuchten Verfahren gruppieren Knoten im Syntaxbaum in Listen, um aus diesen dann mittels eines Listenreduktionsverfahrens nur die notwendigen Knoten auszuwählen. Unsere Experimente haben gezeigt, dass teilweise 70% und mehr der Reduktionszeit in Listen mit mehr als 2 Elementen verbracht wird. Diese Listen sind deswegen relevant, weil es in der wissenschaftlichen Literatur verschiedene Listenreduktionsverfahren gibt, diese sich aber für Listen mit 2 oder weniger Elementen nicht unterscheiden. Da der zeitliche Anteil so hoch sein kann, haben wir diese verschiedenen Listenreduktionsverfahren in unsere in 2020/2021 entwickelten Implementierungen der wichtigen Reduktionsverfahren integriert. Dabei haben wir neben den Verfahren aus der Literatur auch solche aufgenommen, die nur auf einer Website beschrieben oder nur in einer frei zugänglichen Implementierung umgesetzt waren.

High-Performance Computing (HPC) ist ein wichtiger Bestandteil für die europäische Innovationskapazität und wird auch als ein Baustein bei der Digitalisierung der europäischen Industrie gesehen. Rekonfigurierbare Technologien wie Field Programmable Gate  Array (FPGA) Module gewinnen hier wegen ihrer Energieeffizienz, Performance und ihrer Flexibilität immer größere Bedeutung.
Es wird außerdem zunehmend auf HPC-Systeme mit heterogenen Architekturen gesetzt, auch auf solche mit FPGA-Beschleunigern. Die große Flexibilität dieser FPGAs ermöglicht es, dass eine große Klasse von HPC-Applikationen mit FPGAs realisiert werden kann. Allerdings ist deren Programmierung bisher vorwiegend Spezialisten vorbehalten und sehr zeitaufwendig, wodurch deren Verwendung in Bereichen des wissenschaftlichen Höchstleistungsrechnens derzeit noch selten ist.
Im HPC-Umfeld gibt es verschiedenste Programmiermodelle für heterogene Rechnersysteme mit einigen Typen von Beschleunigern. Gängige Programmiermodelle sind zum Beispiel OpenCL (opencl.org), OpenACC (openacc.org) und OpenMP (OpenMP.org). Eine produktive Verwendbarkeit dieser Standards für FPGAs ist heute jedoch noch nicht gegeben.

Ziele des ORKA Projektes sind:

1. Nutzung des OpenMP-4.0-Standards als Programmiermodell, um ohne Spezialkenntnisse heterogene Rechnerplattformen mit FPGAs als rekonfigurierbare Architekturen durch portable Implementierungen eine breitere Community im HPC-Umfeld zu erschließen.
2. Entwurf und Implementierung eines Source-to-Source-Frameworks, welches C/C++-Code mit OpenMP-4.0-Direktiven in ein ausführbares Programm transformiert, das die Host-CPUs und FPGAs nutzt.
3. Nutzung und Erweiterung existierender Lösungen von Teilproblemen für die optimale Abbildung von Algorithmen auf heterogene Systeme und FPGA-Hardware.
4. Erforschung neuer (ggf. heuristischer) Methoden zur Optimierung von Programmen für inhärent parallele Architekturen.

Im Jahr 2018 wurden folgende wesentlichen Beiträge geleistet:

• Entwicklung eines source-to-source Übersetzerprototypen für die Umschreibung von OpenMP-C-Quellcode (vgl. Ziel 2).
• Entwicklung eines HLS-Übersetzerprototypen, der in der Lage ist, C-Code in Hardware zu übersetzen. Dieser Prototyp bildet die Basis für die Ziele 3 und 4.
• Entwicklung mehrerer experimenteller FPGA-Infrastrukturen für die Ausführung von Beschleunigerkernen (nötig für die Ziele 1 und 2).

Im Jahr 2019 wurden folgende wesentlichen Beiträge geleistet:

• Veröffentlichung zweier Papiere: "OpenMP on FPGAs - A Survey" und "OpenMP to FPGA Offloading Prototype using OpenCL SDK".
• Erweiterung des source-to-source Übersetzerprototypen um OpenMP-Target-Outlining (incl. Smoke-Tests).
• Fertigstellung des technischen Durchstichs für den ORKA-HPC-Prototypen (OpenMP-zu-FPGA-Übersetzer).
• Benchmark-Suite für die quantitative Leistungsanalyse von ORKA-HPC.
• Erweiterung des source-to-source Übersetzerprototypen um das Genom für die genetische Optimierung der High-Level-Synthese durch Einstellen von HLS-Pragmas.
• Prototypische Erweiterung des TaPaSCo-Composers um ein (optionales) automatisches Einfügen von Hardware-Synchronisationsprimitiven in TaPaSCo-Systeme.

Die zunehmende Digitalisierung aller Wissenschafts- und Lebensbereiche hat dazu geführt, dass Kompetenzen in den Grundlagen der Informatik für Studierende aller Studiengänge der Technischen Fakultät (und darüber hinaus) als essentiell erachtet werden. Für den Studienerfolg haben sich diese, typischerweise direkt in der Studieneingangsphase verorteten, Lehrveranstaltungen allerdings für viele Studierende als problematische Hürde erwiesen, die letztlich häufig zum Studienabbruch führen kann. Aus diesem Grund widmen wir uns dem Ausbau der Unterstützung von angehenden Studierenden beim Übergang Schule-Hochschule sowie während der Studieneingangsphase.
Die Projektschwerpunkte liegen hinsichtlich der Studienorientierung in der Förderung des potenziellen MINT-Nachwuchses bereits vor Studienbeginn durch regionale und überregionale Kontakte wie z.B. Unterstützung bei W-Seminaren oder Fortbildungen von Lehrerinnen und Lehrern als Multiplikatoren für die Studienwahl. Hinsichtlich des Übergangs Schule-Hochschule steht der Ausgleich unterschiedlicher Vorkenntnisse der Studienanfänger durch Repetitorien im Vordergrund. In der Studieneingangsphase liegt der Schwerpunkt in der Senkung der Abbruchquote in MINT-Studiengängen durch spezielle Intensivierungsübungen und Tutorenschulungen unter Berücksichtigung der Heterogenität.
2018 stand unter anderem die Untersuchung der Wirksamkeit aller Maßnahmen im Fokus. Untersucht wurde der Einfluss des angestiegenen Übungsgruppenangebots und der umfangreichen Unterstützung durch die Tutorinnen und Tutoren. Außerdem war die Wirksamkeitsuntersuchung hinsichtlich des Zusammenhangs von Wahrnehmung des Übungsangebots und Abbruchquote Untersuchungsgegenstand. Weiterhin wurden die Auswirkungen der Teilnahme am Repetitorium auf die Leistungen in den Übungen und in der Klausur untersucht.
Um das Ziel der Gewinnung und Qualifizierung von Lehrerinnen und Lehrern als Multiplikatoren zu erreichen, wurde das Angebot an Lehrerfortbildungen weiter ausgebaut. In diesen Fortbildungen wurden innovative Herangehensweisen, Beispiele und Inhalte für den Unterricht mit dem Ziel aufgezeigt, dass die Teilnehmerinnen und Teilnehmer das Gelernte an ihre Schülerinnen und Schüler weitervermitteln.

Ziel dieses Projektes ist die Entwicklung adaptiver Algorithmen für den Einsatz in Funklokalisierungssystemen. Im Rahmen dieses Projekts werden drei wesentliche Themen bearbeitet:

Automatisierte Konfiguration der Ereignis-Detektoren. In vorangegangenen Forschungsprojekten wurden die Grundlagen zur Analyse verrauschter Sensordatenströme gelegt. Allerdings bestand hierbei noch das Problem, dass Ereignis-Detektoren aufwändig und genau parametrisiert werden müssen,  zufriedenstellende Ergebnisse zu produzieren. Dieses Arbeitspaket betrachtet Möglichkeiten einer automatisierten Konfiguration der Ereignis-Detektoren auf Basis vorhandener Ereignis- und Sensordatenströme.
In 2016 wurden erste Konzepte untersucht, um aus einer Vielzahl vorhandener Spieldaten die optimale Konfiguration der Ereignis-Detektoren zu bestimmen. Dabei wurden in einer Fußballanwendungen Spiele und Spielszenen durch Sportwissenschaftler manuell annotiert (z.B. Spieler A tritt Ball mit linkem Fuß zum Zeitpunkt t). Diese manuell annotierten Spielszenen sollen später zur Optimierung der Parameter in der Hierarchie von Ereignisdetektoren herangezogen werden.

Evaluierung von Methoden und Techniken des maschinellen Lernens für Anwendungen zur Lokalisierung. In vorhergehenden Forschungsprojekten wurden bereits erste Algorithmen des maschinellen Lernens im Kontext funkbasierter Lokalisierungssysteme entwickelt (z.B. evolutionäre Algorithmen zur Bestimmung von Antennenpositionen und -ausrichtungen). Im Rahmen dieses Arbeitspakets werden weitere Ansätze untersucht, um Lokalisierungssysteme durch derartige Methoden zu unterstützen.
Im Jahr 2016 wurden erste Ansätze evaluiert, um Teile der Positionsrechnung laufzeitbasierter Funklokalisierungssysteme durch Methoden des maschinellen Lernens zu ersetzen. Bislang werden die Rohdaten solcher Systeme durch eine Signalverarbeitungskette (Analog-Digital-Wandlung, Ankunftszeitbestimmung, Kalman-Filterung, Bewegungsanalyse) zu einer Position verrechnet. Dies erfordert einen vergleichsweise hohen Installations- und Konfigurationsaufwand für die Inbetriebnahme eines Lokalisierungssystems in der Zielumgebung und für die Zielanwendung.

Evaluierung bildgebender Verfahren zur Unterstützung funkbasierter Lokalisierungssysteme. Funkbasierte Lokalisierungssysteme können ihre Stärken gegenüber Kamera-basierten Lokalisierungssystemen immer dann ausspielen, wenn es zu Verdeckungen von Objekten kommen kann. Im Gegenzug haben Funkbasierte Systeme Probleme mit metallischen Aufbauten/Oberflächen, da die Funkwellen an metallischen Oberflächen reflektiert werden und damit über mehrere Pfade an den Empfangsantennen empfangen werden. In diesem Arbeitspaket sollen Algorithmen für eine Bild-basierte Ortungskomponente entwickelt werden, um Funk-Lokalisierungssysteme bei der Positionsrechnung zu unterstützen.
In 2016 wurde damit begonnen zwei unterschiedliche Systeme zu entwickeln: CNNLok, ein System zur kamerabasierten Eigenlokalisierung von Objekten (sog. inside-out tracking), sowie InfraLok ein System zur Lokalisierung mir Kameras in der Infrastruktur (sog. outside-in tracking) auf Infrarot-Basis. CNNLok nutzt ein Convolutional Neural Network, trainiert auf einer Vielzahl von in der Zielumgebung erstellter Kamerabilder. Das Netzwerk liefert anschließend zu einem aktuellen Kamerabild die Position der Kamera (bzw. des Objektes) im Raum. InfraLok detektiert Infrarot-LEDs über ein Multi-Kamerasystem und ermittelt deren Position im Raum.

 

Unter Software-Wasserzeichnen versteht man das Verstecken von ausgewählten Merkmalen in Programme, um sie entweder zu identifizieren oder zu authentifizieren. Das ist nützlich im Rahmen der Bekämpfung von Software-Piraterie, aber auch um die richtige Nutzung von Open-Source Projekten (wie zum Beispiel unter der GNU Lizenz stehende Projekte) zu überprüfen. Die bisherigen Ansätze gehen davon aus, dass das Wasserzeichen bei der Entwicklung des Codes hinzugefügt wird und benötigen somit das Verständnis und den Beitrag der Programmierer für den Einbettungsprozess. Ziel unseres Forschungsprojekts ist es, ein Wasserzeichen-Framework zu entwickeln, dessen Verfahren automatisiert beim Übersetzen des Programms Wasserzeichen sowohl in neu entwickelte als auch in bestehende Programme hinzufügen. Als ersten Ansatz untersuchten wir eine Wasserzeichenmethode, die auf einer symbolischen Ausführung und anschließender Funktionsynthese basiert.

Große Softwareprojekte, an denen hunderte Entwickler arbeiten, sind schwer zu überblicken und enthalten viele Fehler. Zum Testen solcher Software haben sich automatisierte Tests bewährt, die Teilbereiche der Software (Unit-Tests) oder die komplette Software (Systemtest) testen und Fehler reproduzierbar erkennen können. Dieses Vorgehen funktioniert gut bei sequentiellen Programmen, die ein deterministisches Verhalten aufweisen. Moderne Software enthält jedoch vermehrt Parallelität. Durch diese Nebenläufigkeit treten etliche neue, teils schwer zu lokalisierende, Fehler auf, die nicht mehr durch herkömmliche Testverfahren sicher detektiert werden können. Dazu gehören vor allem Verklemmungen und gleichzeitige Zugriffe auf die selbe Speicherstelle. Ob ein solcher Fehler auftritt, hängt von dem konkreten Ausführungsplan der Aktivitätsfäden ab. Dieser unterscheidet sich jedoch bei jeder Ausführung und ist auch stark von dem darunterliegenden System abhängig. Somit treten entsprechende Fehler normalerweise nicht bei jedem Testlauf auf, je nach Testsystem sogar niemals. Aus diesem Grund sind die herkömmlichen Testverfahren nicht mehr ausreichend für moderne, nebenläufige Software.
In dem Projekt AuDeRace werden Verfahren entwickelt, die Nebenläufigkeitsfehler reproduzierbar, effizient und mit möglichst geringen Aufwand für Entwickler erkennen können. Unter anderem wird eine Technik entwickelt, die es ermöglicht, Tests um einen Ablaufplan zu erweitern, durch den die Ausführung weiterhin deterministisch bleibt. Ein weiteres generelles Problem an Tests bleibt dabei aber bestehen: Der Entwickler muss sich zunächst Testfälle überlegen und diese anschließend implementieren. Insbesondere im Kontext von Parallelität ist es aber extrem schwer, sich das Verhalten von Programmen vorzustellen und problematische Stellen zu identifizieren. Deshalb sollen kritische Stellen automatisiert erkannt werden, bevor überhaupt entsprechende Tests geschrieben wurde. Es existieren bereits Ansätze, potentiell kritische Stellen zu detektieren, allerdings werden dabei entweder sehr viele fälschliche Warnungen generiert oder die Analyse ist immens zeitintensiv. Ziel dieses Projektes ist es, durch eine geeignete Kombination aus statischer und dynamischer Analyse, die Anzahl an falschen Erkennungen zu reduzieren, bzw. langsame Analysen zu beschleunigen, sodass die Verfahren nicht nur in kleinen Testbeispielen funktionieren, sondern auch komplexe Softwareprojekte effizient analysieren können.

Im Jahr 2016 wurden bestehende Ansätze und Programme auf ihre Tauglichkeit untersucht. Dabei wurde ein vielversprechendes Verfahren ausgemacht, das mithilfe von Model Checking und vorgegebenen Bedingungen Ablaufpläne konstruiert, die ungewolltes Verhalten erzeugen. Allerdings zeigten die Ergebnisse ein deutliches Problem hinsichtlich eines produktiven Einsatzes, da in sinnvoller Zeit nur sehr kleine Programme analysiert werden konnten. Daher beschäftigte sich das Projekt damit, die Programme um möglichst viele Anweisungen zu kürzen, die nichts mit den gesuchten Wettlaufsituationen zu tun haben. Dadurch sollen spätere Analysen beschleunigt werden.

Im Jahr 2017 wurden die Untersuchungen zur automatischen Reduktion von Programmen weitergeführt.  Außerdem wurde erforscht, ob sich die existierende Technik des Mutationstestens auch auf nebenläufige Programme erweitern lässt. Die Ergebnisse zeigen, dass es durchaus möglich ist, Tests für eine parallele Software qualitativ zu bewerten. Allerdings muss teilweise auf Heuristiken zurückgegriffen werden, um auch größere Projekte in vertretbarer Zeit bewerten zu können.

Im Jahr 2018 lag der Fokus auf einer deterministischen Ausführung von Testfällen. Es wurde ein Konzept erarbeitet, um reproduzierbare Ergebnisse bei der Ausführung zu erzielen: Ein zusätzlicher Ablaufplan spezifiziert das Ablaufverhalten der verschiedenen Aktivitäten. Eine Instrumentierung von vorher markierten Positionen im Code und anderen relevanten Bytecode-Instruktionen soll hier während der Ausführung entsprechend die Kontrolle an eine Verwaltungsaktivität abgeben, die den Ablauf steuert. Damit die Markierungen (Angabe von Positionen im Quellcode) auch nach Änderungen am Quellcode gültig bleiben, sollen diese automatisch auf eine neue Version angepasst werden können. Eine Merge-Technik ähnlich derer zu Versionsverwaltungssystemen soll hier eingesetzt werden.

Im Übersetzerbau (und auch an anderen Stellen) gibt es Analyseverfahren, bei denen Informationen solange durch einen Graphen propagiert und dabei verändert werden, bis sich das Analyseergebnis als Fixpunkt einstellt. In diesem Projekt entwickelten wir den Programmrahmen ParCAn, in dem verschiedene derartige Verfahren parallel und dadurch schneller auf der Graphikkarte ablaufen können.Der Forschungsschwerpunkt des Jahres 2016 lag auf der Weiterentwicklung eines Synchronisationsmechanismus für GPUs. Bekannte Synchronisationsverfahren für die CPU (z. B. Spin-Lock) können nicht ohne weitere Anpassung auf der GPU verwendet werden, weil sie aufgrund spezieller Eigenschaften der GPU-Architektur zu Dead- bzw. Livelocks führen. Synchronisation wird jedoch (auch bei vorwiegend datenparallen Graphimplementierungen) benötigt, wenn sich Abhängigkeiten dynamisch ergeben. Der im Projekt entwickelte GPU-Synchronisationsmechanismus löst zwei wesentliche, auf GPUs nicht-triviale Probleme: Erstens verhindern wir Dead- bzw. Livelocks. Zweites erreichen wir einen maximalen Parallelitätsgrad, indem datenparallele Threads, die an nicht-kollidierenden Stellen der Datenstruktur arbeiten, nicht blockiert werden sondern die Datenstruktur zeitgleich verändern können. Beispiele sind Threads, die disjunkte Stellen eines Graphen modifizieren, ohne die strukturelle Integrität des Graphen zu beeinflussen. Bei unserem Ansatz hat der Programmierer die Möglichkeit, Regeln zu formulieren, unter welchen Umständen eine derartige parallele Ausführung eines kritischen Abschnitts erlaubt ist. Zur Laufzeit wird dann geprüft, welcher Grad an Parallelität ausgenutzt werden kann.
In den folgenden Arbeitsschritten wird der Synchronisationsmechnismus um einen Ablaufplaner erweitert, der kollidierende Zugriffe auf eine Datenstruktur so umsortiert, dass die SIMD-Ausführungsweise der GPU weniger Serialisierung bedingt, als ohne diese Umsortierung. Dadurch steigt der Paralellitätsgrad. Die zugrundeliegende Idee nutzt aus, dass GPUs Threads in einer Hierarchie von Organisationseinheiten verwalten. Stellt der oben beschriebene Synchronisationsmeachnismus einen kollidierenden Zugriff auf einer Hierarchieebene fest, wird auf der nächstkleineren Organisationseinheit erneut auf das Vorhandensein des Konflikts geprüft. Falls dieser dort nicht besteht, dann ist eine parallele Ausführung von wenigen Threads möglich, was immer noch besser ist als die größere Hierarchieebene sequentiell auszuführen. Ziel des Ablaufplaners ist es dann, die entdeckten Kollisionen so über die Organisationseinheiten zu verteilen, dass möglichst viele Threads parallel ausgeführt werden können. Da diese Ablaufplanung zur Laufzeit ausgeführt wird, muss sie effizient und selbst parallel sein sowie evtl. ausnutzen, dass neuere GPUs zur Laufzeit weitere Threads dynamisch starten können.
Graphen sind eine fundamentale Datenstruktur zur Repräsentation der Beziehungen zwischen Daten (z.B. soziale Netzwerke, Analyse der Verlinkung von Webseiten). Zu analysierende Graphen können Millionen/Milliarden von Knoten/Kanten enthalten. GPUs können Graphen mit mehreren 1000 Threads parallel verarbeiten. Graph-Analysen arbeiten nach dem Bulk Synchrones Parallel (BSP) Model. Eine Graph-Analyse zerfällt in drei, strikt getrennte, Phasen: Rechnen, Kommunikation und Synchronisation. Letztere beiden setzen Interaktion mit dem Host (CPU) voraus, welche sich negativ auf die Laufzeit auswirken. Unser GPU-basierter Übersetzer arbeitet ebenfalls nach dem BSP Model: Ein Entwickler modifiziert Code, dieser wird in einen (Kontrollfluss-) Graphen transformiert und auf der GPU analysiert. Jede Code-Veränderung löst diesen Zyklus aus. Der Graph muss also sehr schnell aufgebaut und auf die GPU transferiert werden.
Publikationen im Bereich der Graph-Analysen beschränken sich darauf, das Rechnen zu beschleunigen und auch nur dies zu vermessen. Die Ende-zu-Ende Zeit der Ausführung eines Programmes wird nicht berücksichtigt. Der Einfluss der Kommunikation und Synchronisation wird außer Acht gelassen, hat aber einen entscheidenden Einfluss auf die Laufzeit.Für unseren GPU gestützten Übersetzer, betrachten wir alle drei Phasen des BSP-Models. 2017 veröffentlichten wir ein Papier, das die Synchronisation erheblich beschleunigt. Ferner fokussierten wir uns auf die Kommunikation. In diesem Kontext bedeutet Kommunikation das Kopieren des Graphen auf die GPU (und zurück). Während diese Zeit stark von der Datenstruktur des Graphen abhängt, beeinflusst sie auch die Dauer der Rechenphase. Weil bislang noch keine Untersuchung in der Literatur vorhanden ist, die die Datenstrukturen systematisch hinsichtlich ihrer Effizienz im Kontext von GPUs untersucht, implementierten wir einerseits mehrere Benchmarks, die unterschiedliche Eigenschaften von Graphen abfragen (Zugriff nur auf Vorgänger/Nachfolger, zufälliger Zugriff auf Knoten). Andererseits implementierten wir 8 Datenstrukturen zur Darstellung von Graphen auf der GPU. Die daraus resultierenden Kombinationen wurden mit, strukturell verschiedenen, Eingabegraphen vermessen. Die Ergebnisse sollen Entwickler bei der passenden Wahl der Datenstruktur für ihr GPU-Problem unterstützen.

Durch die Verwendung der GPU als Zielarchitektur wurden weitere forschungsrelevante Fragen beantwortet, die ebenfalls publiziert wurden.Einige Analysen sammeln ihre Informationen in einer globalen Datenstruktur, die von allen Aktivitäten gleichzeitig modifiziert werden kann. Gerade auf der GPU mit ihrer Vielzahl an gleichzeitig laufenden Aktivitäten stellt dies hohe Anforderungen an eine effiziente Synchronisation beim Zugriff auf die gemeinsam genutzte Datenstruktur. So wurde im Rahmen des Forschungsprojektes ein effizientes Rahmenwerk zum Herstellen von gegenseitigen Ausschluss implementiert, siehe LNCS-Literaturangabe. Bisherige Ansätze führten unweigerlich zu Verklemmungen, dem Blockieren des Programms. Zudem wurde die Effizienz des Rahmenwerks durch die Verwendung einer Variante des Inspektions-Ausführungs-Paradigmas erhöht.Eine andere Fragestellung befasste sich mit der Effizienz von Graphstrukturen auf GPUs. Im Kern implementiert ParCAn einen Graphtraversierungsalgorithmus. Das zu übersetzende Programm wird in einen Graphen umgewandelt, dem Kontrollflussgraphen (KFG), auf dem die Analysen ausgeführt werden. Durch die Vielzahl an parallelen Zugriffen stellt der KFG für die Leistungsfähigkeit von ParCAn eine kritische Datenstruktur dar. Aus diesem Grund wurde eine umfangreiche Studie durchgeführt, in der die Leistung von Graph-Datenstrukturen verglichen wurden. Die Ergebnisse wurden genutzt, um für ParCAn die bestmögliche Datenstruktur zur Repräsentation des KFG zu verwenden. Aus den Messdaten wurden allgemeine Kriterien zur Effizient einer Datenstruktur abgeleitet. Diese Kriterien - dargestellt als Entscheidungsbaum - ermöglichen es Entwicklern auch außerhalb des ParCAn-Kontextes, für ihre statischen Graphalgorithmen die am besten geeigneten Datenstrukturen zu wählen. Die Ergebnisse der Studie wurden auf dem GPGPU-Workshop vorgestellt, siehe Literaturangaben.

Viele Software-Systeme verhalten sich während der Testphase oder sogar im Regelbetrieb im negativen Sinne auffällig. Die Diagnose und die Therapie solcher Laufzeitanomalien ist oft langwierig und aufwändig bis hin zu unmöglich. Mögliche Folgen bei der Verwendung des Software-Systems sind lange Antwortzeiten, nicht erklärbares Verhalten oder auch Abstürze. Je länger die Folgen unbehandelt bleiben, desto höher ist der entstehende wirtschaftliche Schaden.
"Design for Diagnosability" beschreibt eine Werkzeugkette mit Modellierungssprachen, Bausteinen und Werkzeugen, mit denen die Diagnosefähigkeit von Software-Systemen gesteigert wird. Mit dieser Werkzeugkette werden Laufzeitanomalien schneller erkannt und behoben – idealerweise noch während der Entwicklung des Software-Systems. Unser Kooperationspartner QAware GmbH bringt ein Software EKG ein, mit dem die Exploration von Laufzeit-Metriken aus Software-Systemen, visualisiert als Zeitreihen, möglich ist.
Das Forschungsprojekt Design for Diagnosability erweitert das Umfeld dieses bestehenden Software-EKG. Die Software-Blackbox misst minimal-invasiv technische und fachliche Laufzeitdaten des Systems. Die Speicherung der erfassten Daten erfolgt in Form von Zeitreihen in einer neu entwickelten Zeitreihendatenbank Chronix. Chronix ist darauf ausgelegt, eine Vielzahl an Zeitreihen äußerst effizient hinsichtlich Speicherplatzbedarf und Zugriffszeiten zu speichern. Chronix ist ein Open Source Projekt (www.chronix.io) und kann frei benutzt werden. Die Zeitreihen werden mit der Time-Series-API analysiert, z.B. mittels einer automatisierten Strategie zur Erkennung von Ausreißern. Die Time-Series-API bietet Grundbausteine, um weitere Strategien zur Identifikation von Laufzeitanomalien in Zeitreihen umzusetzen.
Die aufgeführten Werkzeuge werden in Kombination mit dem bestehenden Software-EKG zum Dynamic Analysis Workbench ausgebaut, um eine zeitnahe Diagnose und Behebung von Laufzeitanomalien zu ermöglichen. Hierzu sind Diagnosepläne vorgesehen, die einen Software-Entwickler unterstützen, eine Laufzeitanomalie schneller und zuverlässiger einzugrenzen und zu erkennen. Das Ziel der Werkzeugkette ist die Qualität von Software-Systemen zu erhöhen, insbesondere hinsichtlich der Kennzahlen Mean-Time-To-Repair sowie Mean-Time-Between-Defects.

Vor dem erfolgreichen Projektabschluss im Juli 2016 konnten noch eine Reihe wesentlicher Beiträge geleistet werden:

• Wir haben Chronix und ein Framework zur verteilten Berechnung gekoppelt. Dadurch skaliert die Anomalieanalyse jetzt auf riesige Mengen an Zeitreihendaten.
• Wir haben Chronix fortentwickelt und weitere Komponenten ergänzt, wie z. B. ein noch effizienteres Speichermodell, mehrere Adapter für diverse Zeitreihendatenbanken, weitere server-seitige Analysefunktionen und neue Zeitreihentypen.
• Wir haben unseren Benchmark für Zeitreihendatenbanken veröffentlicht.
• Wir haben zur Analyse von Anomalien einen Ansatz entwickelt, der Aufrufe ausgehend von der Anwendung bis hinein auf die Betriebssystemebene nachvollzieht.

Obwohl die Förderung im Jahr 2016 auslief, haben wir im Jahr 2017 noch weitere Beiträge geleistet:

• Wir haben Chronix auf der USENIX Conference on File and Storage Technologies (FAST) im Februar 2017 in Santa Clara, CA, vorgestellt.
• Wir haben Chronix mit Schnittstellen ausgestattet, um in der Industrie verwendete Zeitreihendatenbanken anzubinden.
• Wir haben einen Ansatz entwickelt, der für eine gegebene Analyse (Funktion und zu analysierende Zeitreihen) die ideale Cluster-Konfiguration (bzgl. Verarbeitungszeit und Kosten) bestimmt.
• Wir haben Spark, ein Rahmenwerk zur verteilten Verarbeitung von Massendaten so erweitert, dass die GPU bei der verteilten Analyse von Zeitreihen genutzt werden kann. Ergebnisse haben wir auf der Apache Big Data Konferenz im Mai 2017 in Miami, Florida, vorgestellt.

Auch im Jahr 2018 haben wir noch weitere Beiträge im Forschungsprojekt geleistet:

• Wir haben ein Papier auf der PROFES 2018 veröffentlicht, in dem wir Techniken und Erkenntnisse beschreiben, wie man Laufzeitdaten in einem großen Software-Projekt schon zur Entwicklungszeit für alle Projektbeteiligten anbieten kann und damit die Zusammenarbeit verbessert.
• Wir haben das Open Source Projekt von Chronix gewartet und dabei weiter stabilisiert (Aktualisieren von Versionen, Fehlerbehebungen etc.).

Für eingebettete Systeme werden Multicore-Prozessoren immer wichtiger, da diese hohe Rechenleistung bei niedrigem Energieverbrauch ermöglichen. Die Entwicklung von paralleler Software für diese Systeme stellt jedoch neue Herausforderungen für viele Branchen dar, da existierende Software und Werkzeuge nicht für Parallelität entworfen wurden. Die effiziente Entwicklung, die Optimierung und das Testen von Multicore-Software, speziell für eingebettete Systeme mit hohen Zuverlässigkeits- und Zeitanforderungen, sind offene Probleme.

Im Verbundprojekt "WEMUCS" [http://www.multicore-tools.de/] wurden im 2-jährigen Verlauf des Projekts Techniken für die effiziente und iterative Entwicklung, die Optimierung sowie den Test von Multicore-Software durch neue Werkzeuge und Methoden geschaffen. Hierfür wurden mehrere Technologien und innovative Werkzeuge zur Modellierung, Simulation, Visualisierung, Tracing und zum Test entwickelt und zu einer Werkzeugkette integriert. Diese wurden in Fallstudien in der Automobilbranche, der Telekommunikation und der Automatisierungstechnik evaluiert und iterativ weiter entwickelt.

Während es für klassische Single-Core-Applikationen gut erforschte Methoden zur Erzeugung von Testfällen und bewährte Maße und Hierarchien für deren Überdeckung gibt, sind ebenfalls nötige Methoden für mehrkernfähige Anwendungen noch nicht etabliert. Gerade durch das Zusammenspiel gleichzeitig ablaufender Aktivitäten können sich aber erst Fehlerzustände ergeben, die durch das isolierte Testen jeder einzelnen, beteiligten Aktivität nicht identifiziert werden können. Als Teil des WEMUCS-Projektes (genauer: Arbeitspaket AP3 [http://www.multicore-tools.de/de/test.html]) haben wir ausgehend von einem Fallbeispiel ein generalisierbares Verfahren entwickelt (im Folgenden "Testing-Pipeline" genannt), um derartige Wechselwirkungen von parallelen Aktivitäten systematisch zu lokalisieren und etwaige Auswirkungen auf den Programmablauf durch Testmethoden gezielt zu untersuchen.

Zum Zweck der praktischen Erprobung der im AP3 entwickelten Testing-Pipeline, einschließlich der automatischen Parallelisierung von bislang sequentiellem Code, wurde vom Projektpartner Siemens eine Gepäckförderanlage, wie man sie von Flughäfen kennt, vollständig (inkl. Code) modelliert. Das modellierte Fallbeispiel ist so gestaltet, dass man unterschiedlich große Anlagen, d.h. u.a. mit unterschiedlich vielen Förderbändern für Zufuhr bzw. Abtransport, automatisiert generieren kann. Die Hardware der Förderanlage wird dabei durch das Simulationsgerät SIMIT von Siemens emuliert, während die Steuerungssoftware (in der Sprache: AWL) auf einer Software-basierten SPS ausgeführt wird.

Im ersten Schritt der Testing-Pipeline wird der AWL-Code durch ein vom Lehrstuhl für Programmiersysteme im Berichtszeitraum und im Vorjahr entwickeltes Werkzeug in die für Menschen verständlichere Programmiersprache HLL konvertiert und die in AWL noch sequentiell ausgeführte Abschnitte in einem direkt angeschlossenen zweiten Schritt automatisch in parallel ausgeführte HLL-Einheiten überführt. Für eine exemplarische Gepäckförderanlage mit acht Zufuhr- und acht Abtransportförderbändern sowie einem ringförmigen Zwischenband aus mehreren geraden und gewundenen Segmenten hat unser Werkzeug 11.704 Zeilen sequentiellen AWL-Code automatisch in 34 KB parallelen HLL-Code transcodiert.

Im dritten Schritt der Testing-Pipeline wird der HLL-Code analysiert und durch ein weiteres, im Projektverlauf vom Lehrstuhl entwickeltes Werkzeug in ein Testmodell überführt. Dieses Testmodell stellt den interprozeduralen Kontrollfluss der nebenläufigen Unterprogramme zusammen mit potentiellen und für den Test relevanten Thread-Wechseln als hierarchische UML-Aktivitäten dar (derzeit als XMI-Dokument, z.B. für den Import in Enterprise Architect von Sparx Systems). Für die vorangehend beschriebene Gepäckförderanlage hat unser Werkzeug ebenfalls automatisch 103 Aktivitätsdiagramme (mit 1.302 Knoten und 2.581 Kanten) erzeugt.

Nach einem optionalen Schritt, bei dem das Testmodell von einem Tester manuell angepasst werden kann (z.B. um Prioritäten zu ändern oder zusätzliche Prüfschritte einzubauen), kann das Modell dann in die MBTsuite des Projektpartners sepp.med GmbH geladen werden. Dieses umfangreich konfigurierbare Werkzeug dient zur Generierung von Testfällen, die eine möglichst vollständige Überdeckung des Modells anstreben. Für die exemplarische Gepäckförderanlage wurde u.a. auf einem haushaltsüblichen Standard-PC innerhalb von lediglich sechs Minuten eine hochgradig optimierte Testfallmenge generiert, die mit nur 10 Testfällen rund 99% der Knoten und 78% der Kanten im Gesamtmodell überdecken konnte.

Zusammen mit dem Projektpartner sepp.med GmbH demonstrieren wir im Projekt dass und wie zwei Export-Module für die MBTsuite entwickelt werden können, die die generierten Testfälle einerseits für den menschlichen Tester als Tabellendokument ausgibt, bei dem jeder Testfall ein Tabellenblatt füllt, dessen Spalten und Zeilen anschaulich den nebenläufigen Ablauf und die Thread-Wechsel zeigen, sowie andererseits zur weiteren Verarbeitung als ausführbare Testfallmenge (d.h. hier als Java-Programm für den nun folgenden Schritt). Die ausführbaren Tests bestehen aus mehreren Testfällen, bei dem jeder Testfall aus mehreren Testschritten und jeder Testschritt aus Steueranweisungen besteht, so dass ein Testlauf einer jederzeit eindeutig reproduzierbaren Programmausführung des zu testenden, nebenläufigen HLL-Codes entspricht. Werden diese Testfälle gestartet, dann schließt sich die Werkzeugkette, indem der HLL-Code in einem von Lehrstuhl entwickelten HLL-Emulator nach der Vorgabe im Testfall kontrolliert ausgeführt und dabei gleichzeitig ein detailliertes Protokoll der Testausführung zum Zweck der Visualisierung generiert wird.

Dieses Protokoll kann schließlich durch ein von der sepp.med GmbH entwickeltes Plug-In für Enterprise Architect wie eine zusätzliche Schicht/Ansicht "über" das Testmodell gelegt werden, so dass der Tester für jeden einzelnen Testfall bzw. für die gesamte Testfallmenge graphisch nachvollziehen kann, welche Abläufe getestet wurden und wo gegebenenfalls ein Fehler aufgetreten ist: Die "graphische Spur" endet in diesem Fall genau an der betroffenen HLL-Anweisung und lässt sich z.B. "rückwärts" untersuchen, um die Ursache des Fehlschlags zu identifizieren.

Das am Fallbeispiel prototypisch realisierte Verfahren stellt damit einen wesentlichen Beitrag zum Testen nebenläufigen Codes auf eingebetteten Systemen dar. Es ist ein Beitrag des Lehrstuhls Informatik 2 zum "IZ ESI" [http://www.esi.uni-erlangen.de].

Um sicherzustellen, dass Fehler im Programmdesign schon früh im Entwicklungsprozess gefunden werden, ist es nützlich, Fehler möglichst schon während des Editierens des Programms zu finden.  Dazu sollte die verwendete Analyse so schnell sein, dass ein interaktiver Einsatz möglich ist.  Eine Möglichkeit, dies umzusetzen, ist der Einsatz von inkrementeller Analyse, bei der die Analyseergebnisse von Teilen eines Programms zu Gesamtergebnissen kombiniert werden.  Vorteil von inkrementeller Programmanalyse ist, dass bei kleineren Änderungen ein großer Teil der Analyseergebnisse wieder verwendet werden kann, wie auch z.B. Analyseergebnisse von u.U. verwendeten Programmbibliotheken. Hierdurch kann der Analyseaufwand drastisch reduziert werden, wodurch die Analyse interaktiv nutzbar wird.
Unsere Analyse basiert darauf, für (Teile von) einzelnen Funktionen zu bestimmen, welche Auswirkungen die Ausführung auf den Zustand des Programms zur Laufzeit haben kann.  Hierzu wird der Laufzeitzustand eines Programms abstrakt durch einen Graphen dargestellt, der die im Speicher befindlichen Variablen und Objekte und ihre Verzeigerung beschreibt.  Die Funktion wird symbolisch ausgeführt und dabei wird bestimmt, welche Änderungen an dem Laufzeitzustand bzw. an dem diesen darstellenden Graphen verursacht werden können.  Um die Effekte von Hintereinanderausführung von Programmteilen, Funktionsaufrufen, Schleifen, etc. zu bestimmen, können die Änderungsbeschreibungen der Programmteile dann zu größeren Änderungsbeschreibungen kombiniert werden.  Die Analyse geht dabei Bottom-Up vor, analysiert also eine aufgerufene Funktion vor der aufrufenden Funktion (wobei Rekursion analysierbar ist).Im Jahr 2015 lag der Schwerpunkt der Forschung darauf, die eingesetzten Algorithmen und Datenstrukturen weiter zu entwickeln. So konnte die für die Analyse eines gegebenen Programmes benötigte Laufzeit deutlich verringert werden. Zum anderen dürfen die zu analysierenden Programme mehr und mächtigere Features und Elemente der Programmiersprache benutzen.Im Jahr 2016 lag der Schwerpunkt der Forschung darauf, die eingesetzten Algorithmen und Datenstrukturen weiter zu entwickeln. Im Fokus lagen hierbei zum einen die Skalierbarkeit der Analyse bis hin zu Programmen mit mehr als 1 Mio. Anweisungen und zum anderen die inkrementelle Analyse, bei der die Analyseergebnisse von unveränderten Programmteilen weiterverwendet werden, was die Analyse bei typischen Software-Entwicklungspraktiken (großes Code-Volumen, meist sehr kleine Änderungen) deutlich beschleunigt.Im Jahr 2017 lag der Schwerpunkt unserer Forschung darauf, die eingesetzten Algorithmen und Datenstrukturen weiter zu entwickeln. Zusätzlich zu einer besseren Skalierbarkeit der Analyse bei großen zu analysierenden Programmen und einer Weiterentwicklung der inkrementellen Analyse (bei der die Analyseergebnisse von unveränderten Programmteilen weiterverwendet werden), lag der Fokus darauf, die Analyse anschaulich zu dokumentieren, ihre Korrektheit nachzuvollziehen und eine theoretische Grundlage zu konstruieren.

Zur Beschleunigung von Rechensystemen setzen Prozessor-Hersteller schon lange nicht mehr auf steigende Taktraten - im Gegenteil: Die absolute Taktzahl sinkt, stattdessen werden in Prozessoren immer mehr unabhängige Recheneinheiten (cores) verbaut. Dafür müssen die Entwickler nun umdenken: Sie bekommen ihre Applikationen nur dann performanter (effizienter), wenn sie ihre Programme so modularisieren, dass unabhängige Codeabschnitte nebenläufig ausgeführt werden. Leider sind heutige Systeme schon funktional so komplex geworden, dass selbst die Entwicklung für eine sequentielle Ausführung noch nicht fehlerfrei gelingt - die Parallelisierung auf mehrere Rechenkerne fügt der System-Konzeption eine weitere nicht-funktionale Komplexitätsdimension hinzu. Zwar hat die Forschung auf dem Gebiet der Softwaretechnik eine Vielzahl von Qualitätssicherungsmaßnahmen hervorgebracht, da aber die zunehmende Verbreitung von Mehrkernsystemen noch verhältnismäßig neu ist, fehlen bislang wirksame Verfahren zum Testen nebenläufiger Applikationen.

Das vorliegende Projekt hat zum Ziel, diese Lücke durch Bereitstellung eines automatisierten Testsystems zu schließen. Dazu bedarf es zunächst einer Testkriterienhierarchie, die Überdeckungsmaße speziell für das Konzept der Nebenläufigkeit bereitstellt. Vergleichbar z.B. der Verzweigungsüberdeckung für sequentielle Programme, die die Ausführung jedes Programmzweigs im Test fordert (z.B. die Bedingung eines if-statements sowohl wahr als auch falsch erzwingt - auch dann, wenn es keinen expliziten else-Zweig gibt), muss ein fundiertes Testendekriterium für nebenläufige Applikationen die systematische Ausführung aller relevanten Verschränkungen fordern (z.B. alle Reihenfolge-Kombinationen die auftreten können, wenn zwei Fäden einen gemeinsamen Speicherbereich verändern dürfen). Eine Testkriterienhierarchie schreibt dem Tester zwar vor, welche Eigenschaften seine 'fertige' Testfallmenge vorweisen muss, hilft dem Tester aber nicht bei der Identifikation der einzelnen Testfälle. Dabei genügt es nicht, wie im Falle sequentieller Tests, das Augenmerk auf die Testfälle allein zu richten: Testszenarien für parallele Module müssen zusätzlich Steuerungsinformationen zur gezielten Ausführungskontrolle der TUT (Threads Under Test) enthalten.

Im Jahr 2012 ist ein Framework für Java entstanden, das diese gezielte Ablaufsteuerung für TUT automatisch generiert. Der Tester muss lediglich die Byte-Code-Dateien seiner Applikation bereitstellen, weitere Details wie z.B. Quellcode oder Einschränkungen auf bestimmte Testszenarien kann er optional angeben, er muss sie aber nicht zwangsweise mühsam einpflegen. Der Ansatz verwendet Aspekt-Orientierte Programmierung, um die für typische Nebenläufigkeitsfehler verantwortlichen Speicherzugriffe (Lesen bzw. Schreiben von Variablen) mittels automatisch generierten Advices zu umschließen. Werden die Aspekte ins SUT (System Under Test) eingewoben, dann werden Variablenzugriffe zur Ausführungszeit abgefangen und die ausführenden Threads in der Ablaufsteuerung 'geparkt', bis das gewünschte Testszenario erreicht ist, und dann kontrolliert in der gewünschten Reihenfolge zur weiteren Ausführung reaktiviert. Zur Demonstration wurden einige naive Ablaufsteuerungen umgesetzt, die individuelle Variablenzugriffe z.B. gezielt abwechselnd verschiedenen Threads erlauben.

Der 2012 begonnene Prototyp des InThreaT-Framework wurde im Jahr 2013 zum Eclipse-Plugin umgebaut. Damit ist der Ansatz Multi-Projekt-fähig geworden und die erforderliche Funktionalität integriert sich nahtlos in die vertraute Entwicklungsumgebung (IDE) des Entwicklers bzw. des Testers. Darüber hinaus verringert sich für den Tester dadurch auch der Konfigurationsaufwand, der nunmehr ebenfalls intuitiv in der gewohnten IDE erfolgt - z.B. die Auswahl und Persistenz der im Test zu beobachtenden Verschränkungspunkte, welche schließlich Grundlage der automatische Variation der zu testenden Verschränkungen sind. Für die automatische Exploration der relevanten Verschränkungen bedarf es außerdem einer Infrastruktur zur Anreicherung von Testfällen mit Steuerungsinformationen zwecks kontrollierter (Wieder-)Ausführung einzelner Tests. Im Jahr 2013 wurde exemplarisch ein solcher Ansatz für JUnit untersucht und implementiert, bei dem einzelne Testmethoden und/oder ganze Testklassen mit geeigneten Annotationen versehen werden.

ErLaDeF ist unsere Testumgebung für die Erforschung neuer Programmiersprachen und Compiler-Techniken. Unser Zielbereich ist die Infrastruktur, die nötig ist, um Programmieren von eingebetteten parallelen Systemen (insbesondere im Echtzeitbereich) zu vereinfachen.Im Bereich der eingebetteten Systeme und der Echtzeit-Software gibt es feste Grenzen für den Verbrauch an Betriebsmitteln wie Hauptspeicher oder Rechenzeit. Ein typischer Steuerrechner z. B. darf für eine Regelungsaufgabe im Allgemeinen nicht beliebig viel Zeit verbrauchen, um eine Fehlfunktion des gesteuerten Systems zu verhindern.  Die Hardware-Entwicklung der letzten Jahre hat dazu geführt, dass vermehrt Mehrkern-Prozessoren in eingebetteten Systemen eingesetzt werden. Um die damit verbundene Leistungssteigerung auszunutzen, ist es daher nötig, die Steuerungs- und Systemsoftware, die auf diesen eingebetteten Systemen laufen soll, ebenfalls zu parallelisieren, ohne dabei die Anforderungen an Echtzeitfähigkeit und Resourcenverbrauch zu verletzen.Wir erforschen verschiedene Strategien, um diese Parallelisierung von Software in den Griff zu bekommen: Vereinfachung der Fähigkeiten von Programmiersprachen, automatische Parallelisierung, Bibliotheken mit Entwurfsmustern für die parallele Programmierung, tiefgehende Analyse im Übersetzer, Model Checking und Beschleunigung von Übersetzeranalyse bis hin zur interaktiven Nutzung.

Parallelisierung von Programmen zur Laufzeit

Aktuell konzentrieren wir uns bei der automatisierten Parallelisierung auf Laufzeit-Parallelisierung. Das zu parallelisierende Programm wird während seiner Ausführung auf Schleifen untersucht, die parallel ausführbar sind. Unser Ansatz besteht darin, laufzeitintensive Schleifen zunächst in zwei Durchläufen auf ihre Parallelisierbarkeit zu untersuchen. Die Analysedurchläufe werden parallel ausgeführt. Im ersten Analysedurchlauf werden die Adressen aller Schreibzugriffe auf den Hauptspeicher in einer gemeinsam genutzten Datenstruktur gespeichert. Zugriffe auf diese Datenstruktur müssen nicht synchronisiert werden, wenn sichergestellt wird, dass bei konkurrierenden Schreibzugriffen überhaupt ein Wert geschrieben wird. Im zweiten Durchlauf wird für jeden Speicherzugriff (auch lesende!) überprüft, ob eine Datenabhängigkeit zu einem Schreibzugriff besteht. Falls keine Datenabhängigkeiten gefunden werden, wird die Schleife parallel ausgeführt - anderenfalls sequentiell.Im Jahr 2013 konnten wir die Analyse verfeinern, indem wir in der Analyse beachten, dass die Speicherzugriffe der sequenziellen Ausführung der ersten Schleifen vor den parallelen Ausführungen der restlichen Schleifen stattfindet. Dadurch ist in mehr schwierigen Fällen eine Parallelisierung möglich. Zusätzlich sorgt das dafür, dass falls eine Schleife nicht parallel ausgeführt werden kann, unsere Analyse nur geringen Overhead verursacht.Im Jahr 2014 konnten wir das Verfahren so verbessern, dass mit der Ausführung der ersten Schleifeniterationen zusammen mit der Analyse begonnen werden kann. Um das zu ermöglichen, musste die Analyse so verbessert werden, dass sie auch dann noch zuverlässig funktioniert, wenn sich die Daten (durch die gleichzeitige Ausführung) ändern. Durch diese Verbesserung konnten wir den Overhead für nicht-parallelisierbare Schleifen erheblich senken. Außerdem haben wir eine Programmiersprache entwickelt, die diejenigen Schleifen wie den beschriebenen zur Laufzeit parallelisiert, welche der Programmierer als Kandidaten zur Parallelisierung markiert hat. Eine Analyse prüft zuvor, ob die Schleifen illegale Konstrukte enthalten, mit denen der Parallelisierer noch nicht umgehen kann. Ansonsten wird Code erzeugt, der die Schleifen zur Laufzeit inspiziert und dann potenziell parallel ausführt.
Entwurfsmuster für parallele ProgrammierungEine Bibliothek von Entwurfsmustern der parallelen Programmierung erlaubt es einem Programmierer, bekannte Strategien auszuwählen und bei ihrer Implementierung auf erprobten, effizienten Code zur ̈uckzugreifen. Wir erforschen, welche Entwurfsmuster für parallele Programmierung und insbesondere Kommunikation in parallelen Programmen es überhaupt gibt, und wann diese angewendet werden können. Aus unserer bereits über 30 verschiedene Kommunikationsmuster enthaltenden Bibliothek versuchen wir in diesen Projekt für einen gegebenen Anwendungsfall automatisiert das zu seinen Anforderungen passende Entwurfsmuster zu selektieren. Im Jahr 2013 haben wir diese Bibliothek um NUMA-taugliche Kommunikationskanäle zur Verwendung auf Network-on-Chip Prozessoren erweitert.Skriptsprache Pylon für eingebettete Systeme

Pylon ist eine statisch getypte Skriptsprache und kommt zwecks einfacher Erlernbarkeit mit wenigen Schlüsselwörtern aus. Ein Großteil der Komplexität (z.B. Typinferenz) ist in den Übersetzer verschoben. Der Programmierer muss sich keine Gedanken über Datentypen machen. Trotzdem bleibt das Programm statisch typisiert. Alleine aus dem Wert einer Zuweisung kann der Übersetzer den gerade benötigten Datentyp ableiten (Duck-Typing). Da die Sprache zudem implizit parallel ist, erfordert die Parallelisierung einer Anwendung kein Expertenwissen.
Beim Entwurf der Sprache wurde darauf geachtet, auf Sprachkonstrukte zu verzichten, welche die Analysierbarkeit erschweren (z.B. Zeiger, Vererbung, Polymorphie usw.), bzw. diese durch leichter analysierbare Alternativen zu ersetzen, die in früheren Projekten erarbeitet wurden. Der Fokus liegt darauf, den Anwender schon bei der Erstellung von robustem Programmcode bestmöglich zu unterstützen und Fehler statisch zu melden, die bei anderen Sprachen erst zu Laufzeit auftreten.
Interaktive ProgrammanalyseUm sicherzustellen, dass Fehler im Programmdesign möglichst schon früh im Entwicklungsprozess gefunden werden, ist es nötig, Fehler möglichst schon während des Editierens des Programms zu finden. Dazu muss die verwendete Analyse so schnell sein, dass interaktiver Einsatz möglich ist. Wir arbeiten an zwei Ansätzen, dies zu verwirklichen.

In 2013 lag der Schwerpunkt der Forschung auf der Erstellung von sowohl präzisen als auch kompakten Datenstrukturen zur Repräsentation der Effekte und Auswirkungen von Programmteilen, sowie der Erarbeitung von effizienten Algorithmen zur Erstellung und Nutzung dieser Datenstrukturen.

Objektorientierte Sprachen bieten im Allgemeinen die Möglichkeit, mittels Konstruktoren dynamisch Objekte zu erstellen. Der hierfür benötigte Speicher wird vom Laufzeitsystem angefordert. Im Unterschied zu Desktop-Systemen ist bei eingebetteten Systemen der Speicher noch sehr limitiert. Eine häufige Verwendung des new-Operators kann dazu führen, dass zur Laufzeit nicht genügend Speicher zu Verfügung steht und das Programm unerwartet beendet wird.
Im Jahr 2015 wurde daher eine Analyse entwickelt, um dieses Problem bereits zur Entwicklungszeit zu erkennen und an den Entwickler rückzumelden. Dazu ermittelt die Analyse die Lebensspanne einer Referenz auf ein Objekt. Existiert keine Referenz mehr auf dieses Objekt, kann das Objekt aus dem Speicher entfernt werden. Wir setzen hierzu das aus der automatischen Speicherbereinigung als Reference Counting (RC) bekannte Verfahren statisch und interaktiv während der Entwicklung eines Programmes ein, um Fehler zum frühestmöglichen Zeitpunkt zu erkennen. Wurde ein Objekt detektiert, das keine Referenzen mehr hat, muss der Programmierer es durch gezieltes Einfügen von Anweisungen löschen (z.B. delete) oder wiederverwenden. Damit kann der Speicherverbrauch einer Anwendung bereits zur Entwicklungszeit abgeschätzt werden. Die weitgehend sprachunabhängige Analyse basiert auf Pylon und dem im Vorjahr entwickelten parallelen Propagationsframework für Prädikate.

Das Projekt stellt einen Beitrag des Lehrstuhls Informatik 2 zum IZ ESI dar, siehe auch http://www.esi.uni-erlangen.de.

Die Entwicklung von schnelleren und immer effizienteren Rechnerarchitekturen ist in den letzten Jahren an verschiedene Grenzen gestoßen. Althergebrachte Techniken trugen nicht mehr oder nur noch wenig zur Beschleunigung der Hardware bei. Grundprobleme sind dabei das auseinander driftende Verhältnis der Latenzen von Speicher und CPU und die Abwärme bei steigenden Taktfrequenzen. Als Lösung drängen sich homogene und heterogene Mehr- und Vielkern-Architekturen auf, die durch verringerte Taktfrequenzen und mehrschichtige Speicherhierarchien einen Großteil der genannten Problematik vermeiden. Unter Umständen wird mittels Spezialisierung einzelner Komponenten die Rechenleistung weiter erhöht. Aktuelle Zielarchitekturen sind dabei vor allem Grafikkarten mit Hunderten von Recheneinheiten und der Intel XeonPhi-Prozessor, der auf einem Board 60 Kerne inkl. Hyperthreading zur Verfügung stellt.

Während sich datenparallele Probleme mit Hilfe der neuen Architekturen meist relativ einfach beschleunigen lassen, ist die Umsetzung von auf Arbeitspaketen basierenden (sog. Task-parallelen) Probleme Gegenstand der aktuellen Forschung. Die Schwierigkeit ergibt sich dabei meist durch die Irregularität des entstehenden Task-Baumes und der damit verbundenen unterschiedlichen Ausführungsdauer. Dadurch ergeben sich die folgenden Fragestellungen: Welcher Kern führt welche Arbeitspakete in welcher Reihenfolge aus? Wann werden Arbeitspakete vom aktuellen Rechenknoten auf einen anderen Rechenknoten verschoben? Welche Daten gehören zu einem Arbeitspaket, können mehrere Kerne/Rechnerknoten parallel auf die Daten zugreifen? Wie müssen die Daten von verschiedenen Rechnerknoten wieder zusammengeführt werden? In welcher Form kann der Übersetzer in Zusammenarbeit mit dem Laufzeitsystem selbständig Arbeitspakete erzeugen und verteilen?

Im Jahr 2011 wurde in diesem Projekt das Programmiermodell Cilk für die heterogene CellBE-Architektur (ein PowerPC-Kern (PPU) mit acht SPU "Koprozessoren" zur Ausführung paralleler Berechnungen) implementiert und erweitert. Die CellBE-Architektur bietet sich aufgrund ihrer enormen Leistung auf einem einzelnen Chip als Zielarchitektur an. Um ein Arbeitspaket in der heterogenen Architektur verschieben zu können, haben wir das Cilk-Programmiermodell um ein weiteres Schlüsselwort ergänzt. Dazu entwickelten wir eine Quell-zu-Quelltext-Transformation, die aus einem Quelltext den entsprechenden Quelltext sowohl für die PPU als auch für die SPU erzeugen kann. Desweiteren wurden die entsprechenden Daten zu den Arbeitspaketen per DMA-Transfer passend in die lokalen Caches der Koprozessoren verschoben und nach Abarbeitung eines Teilbaumes auf den entfernten Koprozessoren der Speicher mit Hilfe eines automatischen Speicherbereinigers wieder
freigegeben.

Im Jahr 2012 wurden Grafikkarten (GPUs) als weitere Zielarchitektur ins Auge gefasst, die heutzutage eine weitaus höhere Rechenleistung im Gegensatz zu normalen Prozessoren anbieten. Diese Rechenleistung kann durch die Programmierung mit Cuda (NVidia) oder OpenCL (AMD) aufgrund ihrer Struktur für datenparallele Probleme relativ einfach abgerufen werden. Weitaus schwieriger ist die Umsetzung Task-paralleler Anwendungen, die im weiteren Verlauf des Projekts untersucht werden sollen. Dazu werden verschiedene Lastausgleichsalgorithmen entworfen, prototypisch umgesetzt und miteinander verglichen werden. Im Jahr 2012 wurde ein erstes Verfahren mit mehrstufigen Warteschlangen und dem Prinzip der Arbeitsspende (work donation) entworfen.

Im Jahr 2013 wurden neben der Weiterentwicklung der Lastausgleichsalgorithmen für die Grafikkarte mit dem Intel XeonPhi-Prozessor die Gruppe der Zielarchitekturen weiter vergrößert. Der XeonPhi-Prozessor stellt mit seiner Vielzahl an Kernen und der großen Registerbreite und der damit verbundenen Vektorisierbarkeit neue Herausforderung an die Algorithmen zur Verteilung der Arbeitspakete. Konkret wurde das Cilk-Verfahren für den XeonPhi erweitert und angepasst, um automatisch während der Quellcode-Transformation Funktionen zu verschmelzen und die Möglichkeiten zur (automatischen) Parallelisierung durch den Intel-Compiler zu erhöhen. Dabei wurden mehrere Analysen implementiert, die nicht nur die Anzahl verschmelzbarer Funktionen erhöhen, sondern darüber hinaus auch das Auseinanderlaufen von Kontrollflusspfaden in den verschmolzenen Funktionen verhindern (bzw. zumindest abfangen).

Im Jahr 2014 wurde die vorhandene Implementierung der Lastausgleichsalgorithmen für den Intel XeonPhi-Prozessor so erweitert, dass die Arbeit auf mehrere XeonPhi-Prozessoren verteilt werden kann. Im Gegensatz zum Arbeitsdiebstahl, der weiterhin auf einer einzelnen Instanz des XeonPhi zur Lastverteilung zwischen den Kernen verwendet wird, wird die Arbeit aktiv an andere Prozessoren abgegeben. Mit einer neu entwickelten Annotation werden zur Abarbeitung des Arbeitspakets notwendige Daten gekennzeichnet und mit verschoben. Die Herausforderung dabei ist das Verschmelzen der Daten an Synchronisationspunkten. Desweiteren wurde begonnen, Cilk in den clang-Übersetzer des LLVM-Frameworks einzubauen, um automatisiert den CUDA-Code zur Ausführung auf Grafikkarten zu erzeugen. Dieser Code soll dabei auf ein leichtgewichtiges Laufzeitsystem zur Ordnung und Ausführung der Arbeitspakete aufsetzen. Dazu werden Analysen implementiert, die Divergenz soweit möglich vermeiden sollen.

Im Jahr 2015 wurden verschiedene Lastverteilungsalgorithmen zur Auführung von Cilk-Programmen auf der Grafikkarte evaluiert und verglichen. Dazu wurden Warteschlangenalgorithmen mit parallelem Zugriff implementiert und die automatische Erzeugung des CUDA-Codes verfeinert. Da weiterhin das korrekte Setzen der Cilk-Schlüsselwörter zur Synchronisation eine Herausforderung für den Programmierer darstellt, werden zur Übersetzungszeit aus rekursivem Quelltext ohne Cilk-Annotationen "plausible" Code-Varianten inkl. Synchronisationsanweisungen erzeugt. Diese Code-Varianten werden dann zur Laufzeit spekulativ ausgeführt und das Ergebnis der schnellsten, korrekten Variante für die weitere Berechnung verwendet. Desweiteren ist die Größe des Basisfalls der Rekursion entscheidend für den optimalen Geschwindigkeitsgewinn. Deswegen wurde begonnen, die Größe des Basisfalls durch Analysen zur Übersetzungs- und Laufzeit zu optimieren und rekursive Aufrufe durch Funktionseinbettung und Vektorisierung zu ersetzen.

Aktuell konzentrieren wir uns bei der automatisierten Parallelisierung auf Laufzeit-Parallelisierung. Das zu parallelisierende Programm wird während seiner Ausführung auf Schleifen untersucht, die parallel ausführbar sind. Unser Ansatz besteht darin, laufzeitintensive Schleifen zunächst in zwei Durchläufen auf ihre Parallelisierbarkeit zu untersuchen. Die Analysedurchläufe werden parallel zueinander und parallel zu einer sequenziellen Ausführung der Schleife ab der ersten Iteration ausgeführt. Im ersten Analysedurchlauf werden die Adressen aller Schreibzugriffe auf den Hauptspeicher in einer gemeinsam genutzten Datenstruktur gespeichert. Zugriffe auf diese Datenstruktur müssen nicht synchronisiert werden, wenn sichergestellt wird, dass bei konkurrierenden Schreibzugriffen überhaupt ein Wert geschrieben wird. Im zweiten Durchlauf wird für jeden Speicherzugriff (auch für lesende!) überprüft, ob eine Datenabhängigkeit zu einem Schreibzugriff besteht. Damit die sequenzielle Ausführung parallel zur Analyse gestartet werden kann, muss diese die Speicherzugriffe, die sie durchführt, protokollieren und überprüfen. Falls keine Datenabhängigkeiten gefunden werden, wird die Schleife parallel ausgeführt.  Anderenfalls wird die sequentielle Ausführung ohne weitere Instrumentisierung fortgeführt.

Im Jahr 2015 haben wir begonnen, das Verfahren in eine bestehende Javascript-Engine einzubauen.  Die Wahl ist auf Javascriptcore aus Webkit gefallen, weil dort in der letzten Optimierungsstufe LLVM verwendet wird. Damit ist es einfacher möglich, das Verfahren auch für andere LLVM Sprachen zu verwenden, oder auf Analysen zurückzugreifen, die für LLVM entwickelt wurden. Javascriptcore verwendet ein mehrstufiges JIT Verfahren. In der letzten (am meisten optimierten) Stufe wird LLVM Zwischencode erzeugt, der dann von dem LLVM-Compiler mit den dort verfügbaren Optimierungen übersetzt wird. An diesen Punkt bauen wir unsere Parallelisierung ein. Wenn diese Optimierungsstufe erreicht ist, ist sichergestellt, dass der Code oft ausgeführt wird und sich unser aufwändiges Verfahren lohnt. Wir setzen unser Verfahren vor der Erzeugung des LLVM Code an, um Zugriff auf die JIT-Protokolldaten zu haben, die uns bei der Entscheidung unterstützen, welche Schleifen parallelisiert werden sollen.

Das Projekt stellt einen Beitrag des Lehrstuhls Informatik 2 zum IZ ESI dar, siehe auch http://www.esi.uni-erlangen.de .

Funkortungssysteme, auch bekannt als Real-Time Location Systems (RTLS), geraten immer mehr in den Fokus der Logistik, Produktion und vieler weiterer Prozesse. Diese Systeme liefern wertvolle Informationen über den Aufenthaltsort von beteiligten Objekten zur Laufzeit. Damit können Prozesse verfolgt, analysiert und optimiert werden. Neben den Forschungsbereichen an der Basis von Ortungssystemen, wie robuste und störsichere Ortungstechnologien oder Verfahren zur hochgenauen Positionsbestimmung, rücken mehr und mehr Methoden in den Vordergrund, die aus Positionsdatenströmen wertvolle Informationen für weitere Verarbeitungsstufen gewinnen. In diesem Kontext erforscht das Projekt Verfahren zur Ereignisdetektion in Positionsdatenströmen zur Laufzeit.

2011 wurde damit begonnen, auftretende Ereignisse in Lokalisierungssystemen zu erkennen und vorherzusagen. Hierfür werden Ereignisströme zur Laufzeit analysiert und ausgewertet. Somit konnten Modelle erlernt werden, um Ereignisse aus Ereignisströmen zu prädizieren.

2012 wurden für die Laufzeitanalyse von Positionsdatenströmen mehrerer Methoden entwickelt, um Ereignisse mit möglichst geringer Latenz detektieren zu können. Hierbei können einzelne Teilereignisse durch sog. Ereignisdetektoren dazu verwendet werden, höhere Zusammenhänge in den Daten hierarchisch zusammenzusetzen. Hierdurch wird die Komplexität der einzelnen Detektionskomponenten drastisch reduziert. Diese werden somit wartbarer und durch die Ausnutzung paralleler und verteilter Rechnerstrukturen wesentlich effizienter. Es ist nun möglich, Ereignisse in den Positionsdatenströmen innerhalb von nur einigen hundert Millisekunden zu erkennen.

2013 wurde die Verzögerung v.a. verteilter Ereignisverarbeitungssysteme weiter minimiert und ein spezielles Migrationsverfahren entwickelt, das die Verteilung von Softwarekomponenten im laufenden Betrieb so modifizt, dass möglichst wenig zeitliche Verluste durch Netzwerkkommunikation auftreten. Des Weiteren wurde ein spekulatives Verfahren puffernder Ereignisverarbeitungssysteme zur Optimierung erarbeitet. Überschüssige Systemressourcen werden effizient verwendet, um die Latenz in Ereignisverarbeitungssystemen auf ein Minimum zu reduzieren. Es wurde außerdem ein repräsentativer Datensatz (mit Sensor- und Positionsdatenströmen sowie manuell eingefügten Ereignissen) sowie eine praxisrelevante Aufgabenstellung veröffentlicht.

2014 wurden grundlegende Verfahren zur Bewältigung von Unsicherheiten (bezüglich der Definition von Ereignisdetektoren) und Unschärfe (im Sinne von Ungenauigkeiten innerhalb von Ereignissen an sich) untersucht. Im Rahmen des Forschungsprojekts wurde ein vielversprechender Ansatz verfolgt, der ohne den üblichen Determinismus ereignisverarbeitender Systeme auskommt und stattdessen parallele Berechnungspfade verfolgt und dabei durch die parallel Betrachtung mehrerer möglicher Zustände eine robustere und genauerere Ereignisverarbeitung erreicht. Dabei kann ein Anwendungsentwickler Wahrscheinlichkeiten oder Funktionen hinterlegen, welche die Ereignisdetektoren bzw. die generierten Ereignisse parametrisieren.

Dieses Verfahren wurde 2015 weiter verbessert, optimiert und veröffentlicht. Des Weiteren wurden erste Ansätze zum Erlernen optimaler Parameterkonfigurationen für Ereignisdetektoren untersucht. Damit wird eine manuelle Einstellung und Optimierung von Threshold-Parametern innerhalb der Detektoren unnötig.

Das Projekt stellt einen Beitrag des Lehrstuhls Informatik 2 zum IZ ESI (http://www.esi-anwendungszentrum.de) dar.

Bei der Weiterentwicklung von Software führen die Entwickler oftmals sich wiederholende, ähnliche Änderungen durch. Dazu gehört beispielsweise die Anpassung von Programmen an eine veränderte Bibliotheksschnittstelle, die Behebung von Fehlern in funktional ähnlichen Komponenten sowie die Parallelisierung von sequentiellen Programmteilen. Wenn jeder Entwickler die nötigen Änderungen selbst erarbeiten muss, führt dies leicht zu fehlerhaften Programmen, beispielsweise weil weitere zu ändernde Stellen übersehen werden. Wünschenswert wäre stattdessen ein automatisiertes Verfahren, das ähnliche Änderungen erkennt und mit dieser Wissensbasis Software-Entwickler bei weiteren Änderungen unterstützt.

Änderungsextraktion
In 2017 entwickelten wir ein neues Vorschlagssystem mit Namen ARES (Accurate REcommendation System). Verglichen mit bisherigen Ansätzen erzeugt es genauere Vorschläge, da seine Algorithmen Code-Verschiebungen während der Muster- und Vorschlagserzeugung berücksichtigen. Der Ansatz basiert darauf, dass zwei Versionen eines Programms miteinander verglichen werden. Das Werkzeug extrahiert dabei automatisch, welche Änderungen sich zwischen den beiden Versionen ergeben haben, und leitet daraus generalisierte Muster aus zu ersetzenden Code-Sequenzen ab. Diese Muster können anschließend von ARES dazu verwendet werden, analoge Änderungen für den Quellcode anderer Programme automatisch vorzuschlagen.
Zur Extraktion der Änderungen verwenden wir ein baumbasiertes Verfahren. Im Jahr 2016 wurde ein neuer Algorithmus (MTDIFF) für solche baumbasierten Verfahren entwickelt und gut sichtbar publiziert, der die Genauigkeit der Änderungsbestimmung verbessert.

Symbolische Ausführung von Code-Fragmenten
Im Jahr 2014 wurde ein neues Verfahren zur symbolischen Code-Ausführung namens SYFEX entwickelt, welches die Ähnlichkeit des Verhaltens zweier Code-Teilstücke bestimmt. Mit diesem Verfahren soll eine Steigerung der Qualität der Verbesserungsvorschläge erreicht werden. Abhängig von der Anzahl und Generalität der Muster in der Datenbank kann SIFE ohne das neue Verfahren unpassende Vorschläge liefern. Um dem Entwickler nur die passenden Vorschläge anzuzeigen, wird das semantische Verhalten des Vorschlags mit dem semantischen Verhalten des Musters aus der Datenbank verglichen. Weichen beide zu sehr voneinander ab, wird der Vorschlag aus der Ergebnismenge entfernt. Die Besonderheit von SYFEX besteht darin, dass es auf herausgelöste Code-Teilstücke anwendbar ist und keine menschliche Vorkonfiguration benötigt.

Detektion von semantisch ähnlichen Code-Fragmenten
SYFEX erlaubt es, die semantische Ähnlichkeit zweier Code-Fragmente zu bestimmen. So ist es damit prinzipiell möglich, Paare oder Gruppen von semantisch ähnlichen Code-Fragmenten (semantische Klone) zu identifizieren. Auf Grund des hohen Laufzeitaufwands verbietet sich der Einsatz von SYFEX -- wie auch von anderen Werkzeugen dieser Art -- allerdings, um in größeren Code-Projekten nach semantisch ähnlichen Code-Fragmenten zu suchen. Im Jahr 2016 wurde deshalb mit der Entwicklung eines Verfahrens begonnen, mit dessen Hilfe die Detektion semantisch ähnlicher Code-Fragmente beschleunigt werden kann. Grundlage dieses Verfahrens ist eine Reihe von sog. Basiskomparatoren, die zwei Code-Fragmente jeweils hinsichtlich eines Kriteriums (beispielsweise die Anzahl bestimmter Kontrollstrukturen oder die Beschaffenheit der Kontrollflussgraphen) miteinander vergleichen und dabei möglichst geringen Laufzeitaufwand haben. Diese Basiskomparatoren können anschließend zu einer Hierarchie von Verfahren verknüpft werden. Um damit die semantische Ähnlichkeit zweier Fragmente möglichst genau bestimmen zu können, wird mit Hilfe der Genetischen Programmierung nach Hierarchien gesucht, die die von SYFEX für eine Reihe von Code-Paaren berechneten Ähnlichkeitswerte möglichst gut approximieren. Im Rahmen einer ersten Untersuchung hat sich gezeigt, dass sich das implementierte Verfahren tatsächlich für die Bestimmung von semantisch ähnlichen Code-Paaren eignet.
Die Implementierung dieses Verfahrens wurde in den Jahren 2017 und 2018 weiter verbessert. Zudem spielte die tiefergehende Evaluation des Verfahrens auf Basis von Methodenpaaren aus Software-Archiven sowie von Abgaben für Programmieraufgaben eine wichtige Rolle.

Semantische Code-Suche
Häufig steht die bei der Software-Entwicklung zu implementierende Funktionalität bereits in ähnlicher Form als Teil von Programmbibliotheken zur Verfügung. In vielen Fällen ist es ratsam, diese bereits vorhandene Realisierung zu verwenden statt die Funktionalität erneut zu implementieren, beispielsweise um den Aufwand für das Entwickeln und Testen des Codes zu reduzieren.
Voraussetzung für die Wiederverwendung einer für den Anwendungszweck geeigneten Implementierung ist, dass Entwickler diese überhaupt finden können. Zu diesem Zweck werden bereits heute regelmäßig Code-Suchmaschinen verwendet. Etablierte Verfahren stützen sich dabei insbesondere auf syntaktische Merkmale, d.h. der Nutzer gibt beispielsweise eine Reihe von Schlüsselwörtern oder Variablen- und Methodennamen an, nach denen die Suchmaschine suchen soll. Bei diesen Verfahren bleibt die Semantik des zu suchenden Codes unberücksichtigt. Dies führt in der Regel dazu, dass relevante, aber syntaktisch verschiedene Implementierungen nicht gefunden werden ("false negatives") oder dass syntaktisch ähnliche, aber semantisch irrelevante Ergebnisse präsentiert werden ("false positives"). Die Suche nach Code-Fragmenten auf Basis ihrer Semantik ist Gegenstand aktueller Forschung.
Im Jahr 2017 wurde am Lehrstuhl mit der Entwicklung eines neuen Verfahrens zur semantischen Code-Suche begonnen. Der Nutzer spezifiziert dabei die gesuchte Funktionalität in Form von Eingabe-Ausgabe-Beispielen. Mit Hilfe eines aus der Literatur stammenden Verfahrens zur Funktionssynthese wird eine Methode erzeugt, die das durch die Beispiele beschriebene Verhalten möglichst genau realisiert. Diese synthetisierte Methode wird dann mit Hilfe des im Rahmen dieses Forschungsprojekts entwickelten Verfahrens zur Detektion von semantisch ähnlichen Code-Fragmenten mit den Methodenimplementierungen vorgegebener Programmbibliotheken verglichen, um ähnliche Implementierungen zu finden, die dem Nutzer als Ergebnis der Suche präsentiert werden. Eine erste Evaluation der prototypischen Implementierung zeigt die Umsetzbarkeit und Verwendbarkeit des Verfahrens.

Cluster-Bildung von ähnlichen Code-Änderungen
Voraussetzung für die Erzeugung generalisierter Änderungsmuster ist es, die Menge aller aus einem Quelltext-Archiv extrahierten Code-Änderungen in Teilmengen zueinander ähnlicher Änderungen aufzuteilen. Im Jahr 2015 wurde diese Erkennung ähnlicher Änderungen im Rahmen eines neuen Werkzeugs C3 verbessert. In einem ersten Schritt wurden verschiedene Metriken für den paarweisen Ähnlichkeitsvergleich der extrahierten Code-Änderungen implementiert und evaluiert. Darauf aufbauend wurden aus der Literatur bekannte Clustering-Algorithmen evaluiert und neue Heuristiken zur automatisierten Bestimmung der jeweiligen Parameter implementiert, um das bisherige naive Verfahren zur Identifizierung ähnlicher Änderungen zu ersetzen. Mit den im Rahmen von C3 implementierten Verfahren konnte im Vergleich zum bisherigen Ansatz eine deutliche Verbesserung erzielt werden. So können mit den neuen Verfahren mehr Gruppen ähnlicher Änderungen identifiziert werden, die sich für die Weiterverarbeitung im Rahmen von SIFE zur Generierung von Vorschlägen eignen.
Die zweite Verbesserung zielt darauf ab, die erhaltenen Gruppen ähnlicher Änderungen zusätzlich automatisiert zu verfeinern. Zu diesem Zweck wurden verschiedene Verfahren aus dem Umfeld des maschinellen Lernens zur Ausreißererkennung untersucht, um Änderungen, die fälschlicherweise einer Gruppe zugeordnet wurden, wieder zu entfernen.
Im Jahr 2016 wurde C3 um eine weitere Metrik zum Vergleich zweier Code-Änderungen erweitert, die im Wesentlichen den textuellen Unterschied zwischen den Änderungen (wie er beispielsweise von dem Unix-Werkzeug 'diff' erzeugt wird) bewertet. Des Weiteren wurde das in C3 implementierte Verfahren im Rahmen eines Konferenzbeitrags veröffentlicht. In diesem Zusammenhang wurde auch der zur Evaluation des Verfahrens erzeugte Datensatz von Gruppen ähnlicher Änderungen unter einer Open-Source-Lizenz veröffentlicht, siehe https://github.com/FAU-Inf2/cthree . Dieser kann zukünftigen Arbeiten als Referenz oder Eingabe dienen. Außerdem wurden prototypisch Verfahren implementiert, mit denen die Ähnlichkeitsberechnung und das Clustering in C3 inkrementell erfolgen können. Diese erlauben es, dass bei neuen Änderungen, die zu einem Software-Archiv hinzugefügt werden, die zuvor bereits berechneten Ergebnisse weiterverwendet werden können und nur ein Teil der Arbeit wiederholt werden muss.

Prototypische Entwicklung eines neuartigen Werkzeugs zur Qualitätsabsicherung bei der Softwareentwicklung.

Moderne Softwaresysteme werden sowohl fachlich, technisch als auch organisatorisch zunehmend komplexer: So steigen die Anzahl und der Vernetzungsgrad der zu realisierenden Anforderungen pro System stetig, die technischen Vorgaben z.B. an den Verteilungsgrad und die Zuverlässigkeit der Systeme werden komplexer und die Softwareentwicklung selbst findet zunehmend in global verteilten Teams und mit wachsendem Zeitdruck statt. Aus diesen Gründen wird es auch zunehmend schwieriger, Softwareentwicklungsprojekte fachlich, technisch und organisatorisch zu steuern.

Als Softwareleitstand bezeichnen wir ein Werkzeug, das leitenden Projektrollen wie dem Projektleiter, dem Softwarearchitekten, dem Anforderungsarchitekten und dem Entwicklungsleiter eine hohe Transparenz und damit verbesserte Steuerbarkeit von Softwareentwicklungsprojekten ermöglicht.

Transparenz herrscht dann, wenn sowohl Zusammenhänge zwischen den vielfältigen Erzeugnissen eines Softwareentwicklungsprojekts als auchderen Eigenschaften schnell und gesamtheitlich zugänglich sind und entsprechend dem individuellen Informationsbedarf eines Projektbeteiligten aufbereitet sind.

Der Softwareleitstand ist ein Werkzeug, das den Zugang zu den Zusammenhängen (Traceability) und den Eigenschaften (Metriken) der Erzeugnisse von Softwareentwicklungsprojekten vereinheitlicht. Damit kann die Effizienz von Softwareentwicklungsprojekten maßgeblich gesteigert werden. Es sollen Erzeugnisse des Softwareentwicklungsprojekts (Artefakte) und ihre Zusammenhänge (Relationen), sowie zu den Artefakten zuordenbare Metriken zentral erfasst, integriert und analysiert werden können. Die entsprechenden Analysen werden in Form von Visualisierungen des Artefaktgraphen mitsamt den zugeordneten Metriken und Regelprüfungen durchgeführt.

Das Projekt Softwareleitstand wird in Kooperation des Lehrstuhls mit der QAware GmbH München durchgeführt. Die ersten 30 Projektmonate wurden aus Mitteln des BMWi gefördert.

Die Umsetzung des Softwareleitstands erfolgte dabei in zwei Arbeitssträngen, die auch den beiden Subsystemen des Werkzeugs entsprechen: Der Integration Pipeline, die Traceability Informationen und Metriken aus verschiedensten Werkzeugen der Softwareentwicklung zusammen sammelt, sowie dem Analysis Core (Analysekern), der eine gesamtheitliche Auswertung der integrierten Daten ermöglicht.

Die Integration Pipeline wurde durch den Projektpartner QAware GmbH entwickelt. Dabei wurde zunächst eine Modellierungssprache für Traceability Informationen in Kombination mit Metriken (TraceML) definiert. Die Sprache besteht dabei aus einem Meta-Modell sowie einer Modellbibliothek zur einfachen Definition von angepassten Traceability Modellen. Aufbauend auf der TraceML wurde das Integration Pipeline Framework auf Basis des Eclipse Modeling Projekts entwickelt. Dabei wird sowohl das Eclipse Modeling Framework zur Abbildung der Modelle und Metamodelle, als auch die Modeling Workflow Engine zur Modelltransformation und Eclipse CDO als Modell-Repository verwendet. Auf Basis des Integration Pipeline Frameworks wurden dann eine Reihe von gängigen Werkzeugen der Softwareentwicklung wie z.B. Subversion, Eclipse, JIRA, Enterprise Architect und Maven angebunden.

Der Analysekern wurde durch den Lehrstuhl entwickelt. Zentrales Thema waren dabei die Konzeption und Realisierung einer domänenspezifischen Sprache für die graph-basierte Traceability-Analyse. Die Traceability Query Language (TracQL) reduziert den Aufwand zur Umsetzung von Traceability-Analysen zu reduzieren. TracQL erleichtert dabei sowohl die Extraktion als auch die Transformation der Traceability-Daten, so dass diese dann mittels kurzer funktional formulierter Graph-Traversierungen analysiert werden können. Die Sprache baut auf der multi-paradigmen Sprache Scala auf und wurde bereits mehrfach in realen Industrieprojekten zur Analyse erfolgreich eingesetzt.
Im Jahr 2014 erweiterten wir die Modularität der Sprache, um sie sowohl strukturell als auch operational anpassbar und erweiterbar zu machen. Dies erhöht nicht nur die Ausdrucksstärke der Sprache, sondern verbessert auch die Wiederverwendbarkeit bereits erstellter Traceability-Analysen.Der Schwerpunkt des Jahres 2015 lag auf der Evaluation und Dokumentation des Ansatzes. Ziel war dabei, die zentralen Eigenschaften des Ansatzes hervorzuheben und deren Wirksamkeit nachzuweisen. Im Wesentlichen handelt es sich dabei um folgende drei Eigenschaften:
- Repräsentationsunabhängigkeit: TracQL ist an eine Vielzahl an Datenquellen anbindbar und macht deren Datentypen statisch typisiert verfügbar.
- Modularität: Der Ansatz ist sowohl strukturell als auch operational anpassbar und erweiterbar.
- Anwendbarkeit: Die Sprache besticht durch Ausdrucksstärke und Performanz im Vergleich zu anderen Ansätzen.

JaMP ist eine Implementierung des bekannten OpenMP Standards für Java. JaMP erlaubt es (unter anderem) Schleifen zu parallelisieren, ohne sich mit der low-level Thread-API von Java befassen zu müssen. Eine parallele Schleife hätte in JaMP folgende Form:
class Test {
 ...void foo() {
 ......//#omp parallel for
 ......for (int i=0;i .........a[i] = b[i] + c[i]
 ......}
 ...}
 }

Dieses im Jahr 2009 gestartete Projekt befasst sich mit der Refaktorisierung und Parallelisierung von Anwendungen aus der Automatisierungstechnik. Die Programme laufen dabei auf speziellen eingebetteten Systemen. Diese Hardware bildet einen Industriestandard und kommt weltweit zum Einsatz. Da auch in eingebetteten Systemen zunehmend Multicore-Architekturen eingesetzt werden, muss bestehende, sequentielle Software für diese neuen Architekturen parallelisiert werden, um einen Zuwachs an Leistung zu gewinnen. Da die Programme typischerweise in der Industrie zur Regelung von Prozessen und zur Fertigungsautomatisierung eingesetzt werden, haben sie einen langen Lebenszyklus, um die Investitionskosten für die Unternehmen gering zu halten. Aufgrund der langen Einsatzzeit der Programme werden diese oftmals nicht mehr durch die ursprünglichen Entwickler gepflegt. Weiterhin wurde für die Programme oftmals ein hoher Aufwand betrieben, um eine zuverlässige Funktionsweise zu gewährleisten. Erweiterungen an der Software werden daher nur zögerlich vorgenommen.

Eine Migration dieser Altanwendungen auf neue Systeme und ihre anschließende Parallelisierung kann daher nicht von Hand vorgenommen werden, da sich dies als zu fehlerträchtig erweist. Es sind also Werkzeuge nötig, die diese Aufgaben automatisch vornehmen bzw. den Entwickler bei der Migration und Parallelisierung unterstützen.

Erforschung von Parallelisierungstechniken

Zur Parallelisierung von bestehenden Anwendungen aus der Automatisierungstechnik wurde ein spezieller Übersetzer entwickelt, der zunächst Programme aus der Automatisierungstechnik auf ihre automatische Parallelisierbarkeit untersuchte. Hierbei zeigte sich, dass eine automatische Parallelisierung mit existierenden Techniken nicht effizient durchführbar ist. Deshalb konzentriert sich dieses Teilprojekt auf zwei Schritte. Im ersten Schritt wurde eine Datenabhängigkeitsanalyse entwickelt, die potentielle kritische Abschnitte in einem parallelen Programm erkennt und diese dem Entwickler vorschlägt und deren Schutz in den Code einbaut. Die Analyse erlaubt es, atomare Blöcke zu identifiziert, die sehr gut mit den atomaren Blöcken übereinstimmen, die ein Experte im Code platzieren würde. Es wurde außerdem nachgewiesen, dass die Laufzeit nur unmaßgeblich beeinträchtigt wird, falls das Verfahren in seltenen Fällen kritische Abschnitte annimmt, die tatsächlich gar nicht existieren oder kritische Abschnitte ermittelt, die größer als tatsächlich notwendig sind.

Im zweiten Schritt wurden die bestehenden Verfahren Software-Transaktionaler-Speicher (STM) und Lock-Inferenz zur Implementierung atomarer Blöcke verfeinert und verbessert. In dem neuen Ansatz verwendet ein atomarer Block STM, solange Lock-Inferenz keine feingranulare Synchronisation garantieren kann, und wechselt zur Laufzeit von STM zu Lock-Inferenz, sobald feingranulare Synchronisation mit Locks möglich ist. Damit wird jeder atomare Block feingranular synchronisiert, wobei der Laufzeitaufwand von STM minimiert wird. Um die Effektivität des kombinierten Verfahrens zu steigern, wurden bestehende Lock-Inferenz-Algorithmen verbessern, um in mehr Fällen als bisher feingranular synchronisierte atomare Blöcke mit Lock-Inferenz zu implementieren. Es konnte gezeigt werden, dass das kombinierte Verfahren zur Implementierung atomarer Blöcke die Ausführungszeiten gegenüber einer reinen Umsetzung mit STM oder Lock-Inferenz um einen Faktor zwischen 1.1 und 6.3 beschleunigt. Obwohl feingranulare Synchronisation im Allgemeinen zu besserer Leistung als eine grobgranulare Lösung führt, gibt es Fälle, in denen eine grobgranulare Implementierung die gleiche Leistung zeigt. Daher wurde ein Laufzeitmechanismus für STM entwickelt, der ebenfalls mit der kombinierten Technik funktioniert. Dieser Mechanismus startet mit einer kleinen Anzahl an Locks, d.h. mit einer grobgranularen Synchronisierung, bei der Zugriffe auf unterschiedliche gemeinsame Variablen durch die selbe Schlossvariable synchronisiert werden. Falls dieses grobgranulare Locking dazu führt, dass zu viele Zugriffe auf unterschiedliche Variablen auf das selbe Lock warten müssen, dann erhöht die entwickelte Technik graduell die Anzahl an Locks. Dies erhöht die Granularität des Lockings, sodass unabhängige Zugriffe häufiger nebenläufig ausgeführt werden können. Dieser Laufzeitmechanismus zur dynamischen Anpassung der Locking-Granularität führt zu einer bis zu 3.0 mal besseren Laufzeiten als eine statische grobgranulare Lösung.

Das Teilprojekt wurde im Jahr 2014 abgeschlossen.

Erforschung von Migrationstechniken

Unsere Forschung zur Migration von Altanwendungen bestand ursprünglich aus dem Ansatz, veraltete Code-Konstrukte durch ein spezielles Werkzeug automatisch durch besseren Code ersetzen zu lassen. Die zu ersetzenden Code-Konstrukte und der verbesserte Code wurden dabei von Programmierern in einer speziell entwickelten Beschreibungssprache spezifiziert. Hierbei stellte sich jedoch die Handhabbarkeit dieses Werkzeugs für unerfahrene Entwickler als zu schwierig heraus.

Daher wurde mit der Entwicklung eines neues Werkzeugs begonnen, das zu ersetzende Code-Sequenzen automatisch aus Software-Versionsarchiven erlernt, diese dann generalisiert und Verbesserungen vorschlägt. Der Ansatz basiert darauf, dass zwei Versionen eines Programms miteinander verglichen werden. Unser Werkzeug extrahiert dabei, welche Änderungen sich zwischen den beiden Versionen ergeben haben und leitet daraus generalisierte Muster aus zu ersetzenden Code-Sequenzen und die dazugehörigen Code-Verbesserungen automatisch ab. Diese Muster werden in einer Datenbank gespeichert und können anschließend von unserem Werkzeug dazu verwendet werden, analoge Änderungen für den Quellcode anderer Programme vorzuschlagen.

Im Jahr 2014 wurde ein neues Verfahren zur symbolischen Code-Ausführung entwickelt, das die Anzahl falscher Vorschläge reduziert. Abhängig von der Anzahl und Generalität der Muster in der Datenbank kann es ohne das neue Verfahren zu unpassenden Vorschlägen kommen. Um die unpassenden Vorschläge zu verwerfen, wird das semantische Verhalten des Vorschlags mit dem semantischen Verhalten des Musters aus der Datenbank verglichen. Weichen beide zu sehr voneinander ab, wird der Vorschlag aus der Ergebnismenge entfernt. Die Besonderheit des Verfahrens besteht darin, dass es auf herausgelöste Code-Teilstücke anwendbar ist und keine menschliche Vorkonfiguration benötigt.

Die aktuellen Ergebnisse von unserem Werkzeug SIFE sind online zu finden (letztes Update: 2014-05-09).

Aufgrund ständig wachsender Anforderungen, die an die Entwicklung komplexer Softwaresysteme gestellt werden, gewinnt die Einhaltung wohldefinierter Software-Entwicklungsprozesse (SWEPe) immer mehr an Bedeutung. Im Kontext umfangreicher, global verteilter Entwicklungsprojekte ist dabei insbesondere ein Trend zu organisationsübergreifenden, langlaufenden und dabei dynamisch veränderbaren Prozessen erkennbar. Zur effektiven Beschreibung und Unterstützung solcher Entwicklungsprozesse sind speziell geeignete Prozessmodellierungssprachen und eine mächtige Werkzeugunterstützung unverzichtbar. Die Ergebnisse vorangegangener Untersuchungen machten deutlich, dass der Markt für SWEP-Beschreibungs- und -Ausführungsumgebungen derzeit noch keine Lösungen bietet, die eine hinreichend präzise und flexible Modellierung von Entwicklungsprozessen sowie deren automatisierte Ausführung, Steuerung und überwachung ermöglichen. Diese Lücke wurde im Rahmen eines Kooperationsprojektes geschlossen, das in Zusammenarbeit mit der develop group als Industriepartner durchgeführt und mit Mitteln des BMWi gefördert wurde. Es wurde im Oktober 2008 mit drei wissenschaftlichen Mitarbeitern gestartet und im September 2011 abgeschlossen. Ziel dieses Kooperationsprojektes war es, auf Grundlage eines durchgängigen, metamodellbasierten Ansatzes eine integrierte Werkzeugkette für die Modellierung und Ausführung industrieller Software-Entwicklungsprozesse prototypisch zu realisieren. Im Hinblick auf die Praxistauglichkeit der Lösung lag das Hauptaugenmerk dabei auf der Anpassbarkeit der Prozessmodelle an verschiedene industrielle Entwicklungsszenarien, auf der Anwenderfreundlichkeit der Prozessbeschreibung und auf einer weitgehenden Automatisierung der Prozessausführung, die zur Effizienzsteigerung in der Entwicklung entscheidend beiträgt. Diese charakteristischen Vorzüge werden durch einen relativ hohen Formalisierungsgrad der Prozessmodellierung, durch eine weitgehende Generizität der Modellierungs- und Prozessausführungswerkzeuge sowie durch die Verwendung verbreiteter und akzeptierter Industriestandards (UML, SPEM) erreicht. Als Basis für die integrierte Werkzeugkette kommt eine Erweiterung des SPEM-Standards (eSPEM - enactable SPEM) zum Einsatz. eSPEM erweitert das SPEM um Konzepte zur Verhaltensmodellierung auf Grundlage der UML-Aktivitäts- und -Zustandsmaschinendiagramme. Als Ergänzung bietet das eSPEM spezifische Sprachkonstrukte, um bestimmte für SWEPe typische Sachverhalte angemessen modellieren zu können, darunter u.a. die dynamische Erzeugung und Planung von Entwicklungsaktivitäten und Arbeitsschritten. Im Berichtszeitraum 2012 wurde eine Zusammenfassung der integrierten Werkzeugkette und des eSPEM anlässlich des Workshops "First Workshop on Academics Modeling with Eclipse" auf der "8th European Conference on Modelling Foundations and Applications" veröffentlicht. Bei der Definition von SWEPen im industriellen Kontext wurde außerdem deutlich, dass Referenzmodelle und Normen einen zunehmend starken Einfluss auf die Modellierung von SWEPen ausüben. Im Mittelpunkt solcher Normen und Referenzmodell, die nachfolgend als Qualitätsstandards bezeichnet werden, stehen dabei oft Verfahren und Vorgehensweisen (sogenannte Best Practices), die auf eine Verbesserung der Qualität des zu entwickelten SW-Produktes abzielen oder eine gesteigerte Effizienz des Entwicklungsvorhabens zum Ziel haben (z.B. CMMI oder Automotive SPICE). Andere Qualitätsstandards, wie z.B. die ISO 26262 Functional Safety - Road Vehicles, stellen Anforderungen an die im SWEP definierten Maßnahmen zur Entwicklung eines sicheren SW-Produktes (Safety). In diesem Zusammenhang ist ein weiteres Ziel des Forschungsprojektes, diese Anforderungen aus Qualitätsstandards mit dem SWEP zu verknüpfen. Damit soll die effiziente Durchführung von Assessments des SWEPes und Prozessverbesserungsprojekten unterstützt werden. Der Schwerpunkt liegt dabei insbesondere auf Szenarien, in denen mehr als ein Qualitätsstandard zum Einsatz kommt (z.B. CMMI, Automotive SPICE und ISO 26262).

Funkortungssysteme, auch bekannt als Real-Time Location Systems (RTLS), geraten immer mehr in den Fokus der Logistik, Produktion und vielen weiteren Prozessen. Diese Systeme liefern wertvolle Informationen über den Aufenthaltsort von beteiligten Objekten zur Laufzeit. Damit können Prozesse verfolgt, analysiert und optimiert werden. Neben den Forschungsbereichen an der Basis von Ortungssystemen, wie robuste und störsichere Ortungstechnologien oder Verfahren zur hochgenauen Positionsbestimmung, rücken mehr und mehr Methoden in den Vordergrund, die aus Positionsdatenströmen wertvolle Informationen für weitere Verarbeitungsstufen gewinnen. In diesem Kontext erforscht das Projekt Funkortung die automatisierte Einmessung von Funkortungssystemen, die Generierung von generischen dynamischen Bewegungsmodellen und Verfahren zur Ereignisdetektion in Positionsdatenströmen zur Laufzeit. Im Jahr 2009 wurden Algorithmen zur Berechnung der Position und Orientierung der Empfangsantennen eines Funkortungssystems weiterentwickelt. Die Algorithmen berechnen selbstständig Messpunktkoordinaten, die eine schnelle und genaue Einmessung ermöglichen. Zur automatisierten Einmessung wurden hierzu Roboter verwendet. Unser Algorithmus berücksichtigt Hindernisse und die Empfangseigenschaften des Ortungssystems und kann Fehlmessungen wie Mehrwegeempfang in der Berechnung der Position und Orientierung der Empfangsantenne aussortieren. 2010 wurden Modelle entwickelt, die dynamische Bewegnungsmodelle ermöglichen. Hier wurden lernende Verfahren eingesetzt, um Modelle während der Laufzeit anzupassen. Es wurde die formale Sprache TBL (Trajectory Behavior Language) konstruiert, mittels derer Trajektorien beschrieben werden können. Weitere Algorithmen können die Darstellung nochmals verkleinern und somit die zur Speicherung von Trajektorien erforderliche Datenmenge komprimieren. Nun werden Verfahren untersucht, mit denen die entwickelten Bewegungsmodelle zur Laufzeit gelernt werden können. Diese sollen in einer Untersuchung zur Prädiktion von Bewegungen evaluiert werden. Desweiteren wird untersucht, inwieweit sich auftretende Ereignisse in Lokalisierungssystemen vorhersagen lassen können, indem vorhandene Ereignisströme zur Laufzeit analysiert und gelernt werden.

JavaParty [http://svn.ipd.uni-karlsruhe.de/trac/javaparty/wiki/JavaParty] erlaubt eine einfache Portierung von parallelen Java-Programmen mit mehreren Threads auf eine verteilte Umgebung wie z.B. einem Cluster. Das Standard-Java unterstützt parallele Programme durch Threads und Synchronisationsmechanismen. Während Mehrprozess-Java-Programme auf einen einzelnen Speicheraddressbereich beschränkt sind, dehnt JavaParty die Möglichkeiten von Java auf verteilte Systeme aus.
Die übliche Art, parallele Anwendungen auf eine verteilte Umgebung zu portieren, ist die Verwendung von Kommunikationsbibliotheken. Java's entfernter Methodenaufruf (RMI) macht die Verwendung expliziter Kommunikationsprotokolle unnötig, führt aber immer noch zu einer erhöhten Programmkomplexität. Gründe dafür sind die beschränkten Möglichkeiten des RMIs und die benötigte zusätzliche Funktionalität für die Erzeugung und den Zugriff auf entfernte Objekte.
Der Ansatz von JavaParty ist anders. JavaParty-Klassen können direkt als entfernt (remote) deklariert werden. Während normale Java Klassen auf eine einzelne Virtuelle Maschine beschränkt sind, sind entfernte Klassen und deren Instanzen in der gesamten verteilten JavaParty-Umgebung sichtbar und erreichbar. Soweit man nur entfernte Klassen betrachtet, kann die JavaParty-Umgebung als eine Virtuelle Maschine angesehen werden, die sich über verschiedene Computer verteilt. Der Zugriff und die Erzeugung von entfernten Klassen sind syntaktisch nicht von dem regulärer Java-Klassen zu unterscheiden.In den Jahren 2007/08 wurde eine neue Version des JavaParty-Übersetzers implementiert, die mit den in Java 1.5/1.6 neu eingeführten Kontrollstrukturen zurecht kommt. Diese Implementierung beruht auf dem öffentlichen und frei verfügbaren Eclipse-Übersetzer. Dadurch können zukünftige Weiterentwicklungen der Sprache Java und zugehörige Anpassungen desÜbersetzers direkt in JavaParty einfließen.Im Jahr 2009 wurde der JavaParty-Übersetzer um eine Semantik für innere Klassen erweitert.Im Jahr 2010 wurden folgende Ziele erreicht:
- Viele in der Vergangenheit selbstimplementierte Datenstrukturen des Laufzeit Systems wurden aus Stabilitätsgründen durch inzwischen effizientere Java-eigene Implementierungen ersetzt.
- Die Kommunikationsschicht (KaRMI) wurde aufgrund von Kompatibilitäts- und Sicherheitsproblemen bassierend auf der aktuellesten Java-Socket-Technologie neu implementiert.
- Entfernte Klassen wurden um einen ”nahen” Kontext erweitert, der für jedes Objekt auf jedem Rechner lokalen Speicher zur Verfügung stellt. Damit lassen sich lokalitätsgewahre Algorithmen ausdrücken.

Die Arbeitsgruppe ParSeMiS (Parallele und Sequenzielle Graph Mining Suite) beschäftigt sich mit der Suche nach häufigen interessanten Strukturen in Graphdatenbanken; ein Forschungsgebiet, das in den letzten Jahren sehr reges Interesse findet. Da viele Forschungs- und Wirtschaftsdaten in strukturierter Form erfasst werden können, bietet sich die Speicherung komplexer Zusammenhänge in Form von allgemeinen oder speziellen Graphen an.
Diese meist unüberschaubaren Datenmengen sind nur schwer mit Hand und Auge zu erfassen, so dass Algorithmen zur Entdeckung interessanter Korrelationen unabdingbar sind. Da deren Entdeckung in Graphen im Allgemeinen aufwändig ist (NP-vollständig), ist die Suche nach parallelen und spezialisierten Algorithmen und Heuristiken notwendig, die den benötigen Rechenzeit- und Speicheranforderungen auch bei immer größer werdenden Datenmengen gewachsen sind.
Das Ziel dieses Projektes ist es, ein effizientes und flexibles Werkzeug zur Suche in beliebigen Graphdaten bereitzustellen, um sowohl die Einbindung in neue Anwendungsgebiete als auch die Entwicklung neuer Suchverfahren zu beschleunigen und zu vereinfachen.Aufbauend auf den Ergebnissen des Projekts ParMol2 wurden 2006/2007 folgende Ziele erreicht:

• Restrukturierung und Neudesign der gewachsenen ParMol-Strukturen zu einer flexiblen Graphbibiliothek.
• Ergänzung des objekt-orientierten Graphdesigns zu kompakteren, zur Parallelisierung besser geeigneten Datenstrukturen.
• Überführung und Zerlegung der Algorithmen gSpan und Gaston in die neuen Strukturen und Einbau von Erweiterungen für das aktuelle Anwendungsgebiet ”Prozedurale Abstraktion”.
• Entwurf und Implementierung eines neuen Algorithmus zur Suche in gerichteten azyklischen Graphen (DAGs) als Spezialisierung für die Prozedurale Abstraktion.
• Implementierung einer angepassten grafischen Anzeige für DAGs.

Im Jahr 2010 wurden die verteilten Stack-Implementierungen auch für andere Algorithmen und Daten getestet.

Tapir ist eine neue Programmiersprache zur Vereinfachung der Systemprogrammierung. Systemprogrammierung bezeichnet unter anderem die Programmierung von Netzwerkprotokollen, Betriebssystemen, Middleware- und DSM-Systemen. Diese Komponenten stellen essentielle Teile eines Systems dar, da sie Dienste bereitstellen, auf denen andere Applikationen aufbauen. Das Betriebssystem stellt einer Anwendung z.B. eine Ausführungsumgebung bereit, die von der konkreten Hardware abstrahiert, so dass die Applikation eine robuste, Hardware-unabhängige Schnittstelle nutzen kann. Ein weiteres Beispiel für Systemprogrammierung ist ein DSM-System. Es simuliert in einem Rechnerbündel mit verteiltem Speicher einen gemeinsamen Adressraum und verbirgt die Kommunikation im Rechnerbündel vor der Anwendung.

Im Vergleich zu Anwendungssoftware stellt systemnahe Software völlig andere Anforderungen an die Programmierung. Die Leistung der einzelnen Systemkomponenten kann sich auf alle Anwendungen und somit das gesamte System auswirken. Deshalb muss der erzeugte Maschinen-Code besonders effizient ausführbar sein. Fehler auf der Systemebene beeinflussen nicht nur einzelne Anwendungen sondern können ebenfalls das gesamte System beeinträchtigen. Systemsoftware sollte aus diesem Grund möglichst (beweisbar) fehlerfrei sein. All diese Anforderungen haben direkte Auswirkungen auf die verwendbaren Programmiersprachen und den verwendeten Programmierstil:
- Hochsprachen wie C++, C# und Java verstecken Implementierungsdetails vor dem Programmierer. Der Programmierer benötigt z.B. kein Wissen darüber, wie ein Methodenaufruf konkret durchgeführt wird. Dieses Wissen ist jedoch bei der Entwicklung von Systemsoftware erforderlich.
- Hochsprachen stellen Funktionen bereit, die für Systemsoftware in der Regel nicht benötigt werden oder sogar unerwünscht sind. Beispielsweise wird innerhalb eines Betriebssystems keine automatische Speicherbereinigung oder Ausnahmebehandlung verwendet.
- Systemprogramme erfordern kein so hohes Abstraktionsniveau, wie es meist von Hochsprachen gefordert wird. Ebenso verzichtet man bei der Erstellung von Systemsoftware zumeist auf die Benutzung externer Bibliotheken, da viele Bibliotheken auf die Systemsoftware als Basis angewiesen sind und somit nicht zur Verfügung stehen.

Tapir ist an existierende Hochsprachen wie C++ und Java angelehnt, verzichtet aber auf Eigenschaften und Funktionen die ohne Bedeutung für eine Sprache zur Systemprogrammierung sind. Beispielsweise besitzt Tapir keine Speicherbereinigung, Ausnahmebehandlung oder Typumwandlung. Klassen und Objekte können zwar definiert werden, eine Vererbungsbeziehung zwischen Klassen ist aber nicht erlaubt. Das mit Tapir spezifizierte Systemprogramm kann mit Model Checking-Techniken bereits während der Entwicklung auf Fehler überprüft werden. Ein Übersetzerprototyp und ein Werkzeug zum Model Checking sind bereits implementiert. Tapir-Code ist leicht verifizierbar, da Programmteile als Implementierungsdetails markiert werden können, die danach bei der Verifizierung ignoriert werden. Tapir-Programme können (z.B. auf Grafikkarten) parallel ausgeführt werden, ohne dass es zu Verklemmungen oder ähnlichen Fehlern kommt, die üblicherweise bei paralleler Programmierung auftreten.

Schon während sich Tapir noch in der Entwicklung befindet, wurde es bereits verwendet, um eine Spezifikation für das DSM-Protokoll von Jackal zu erarbeiten. Zur Erweiterung des Tapir-Sprachentwurfes wurden RDMA-basierte DSM-Protokolle evaluiert. Die semantische Analyse von Tapir-Programmen ist sehr speicherintensiv, da sie auf Model Checking beruht. Um die Analyse zu beschleunigen, war es erforderlich, eine eigene, auf sehr große Objektmengen spezialisierte, Virtuelle Maschine für Java zu entwickeln. Die neu entwickelte, LVM genannte virtuelle Maschine zeigt wesentlich bessere Laufzeiteigenschaften als übliche Java Virtual Machine Implementierungen, sobald der verfügbare Hauptspeicher nicht mehr ausreicht und das Auslagern auf den Hintergrundspeicher notwendig wird.2006/2007 wurde an den grundlegenden Spracheigenschaften von Tapir gearbeitet. Obwohl Tapir an existierende Hochsprachen wie C++ und Java angelehnt ist, wurden alle unnötigen Eigenschaften und Funktionen entfernt. Beispielsweise fehlen Tapir Speicherbereinigung, Ausnahmebehandlung und Typwandlungen; Klassen und Objekte können zwar definiert werden, jedoch ist keine Vererbungsbeziehung zwischen Klassen erlaubt. Das mit Tapir spezifizierte Systemprogramm kann mit Model Checking-Techniken bereits während der Entwicklung auf Fehler überprüft werden. Ein prototypischer Übersetzer und ein Verifikationswerkzeug wurden 2006/2007 implementiert.
Im Jahr 2008 lag der Schwerpunkt unserer Arbeiten auf der Weiteentwicklung dieser VM, die nun über mehrere Maschinen verteilt effizient arbeitet. Dadurch können Tapir-Programme schneller verifiziert werden und in Java geschriebene wissenschaftliche Anwendungen laufen schneller ab.Im Jahr 2009 wurde die Sprachspezifikation von Tapir verbessert. Die neue Sprachspezifikation erleichtert die automatische Verifizierung und erlaubt die Generierung von effizienterem Maschinencode. Um die Sprache leichter verifizieren zu können, ist es nun möglich, Programmteile als Implementierungsdetails zu markieren. Diese markierten Teile können danach problemlos bei der Verifizierung ignoriert werden. Die höhere Effizienz der Sprache wurde durch die Unterstützung von Nebenläufigkeit erreicht. Programme können damit (z.B. auf Grafikkarten) parallel ausgeführt werden, ohne dass es zu Verklemmungen oder ähnlichen Fehlern kommt, dieüblicherweise bei paralleler Programmierung auftreten.

Im Jackal Projekt wird ein Distributed Shared Memory Systems (DSM) für Java entwickelt. Das System erlaubt es, ein Programm mit mehreren Threads auf einem Rechnerbündel auszuführen. Gleichzeitig bleibt das Programm auf normalen JVMs (die nur einen Rechner unterstützen) lauffähig. Zur besseren Fehlertoleranz beinhaltet Jackal ein Checkpoint System, das in periodischen Abständen den Programmzustand auf die Festplatte speichern kann. Es ist dann möglich, diesen gespeicherten Zustand zu einem späteren Zeitpunkt zu laden und die Ausführung fortzusetzen. Außer normalen nebenläufigen Programmen lassen sich mit Jackal Anwendungen, die OpenMP Direktiven beinhalten, verwenden. Durch eine Kombination aus dem Checkpoint System und den OpenMP Direktiven kann man Anwendungen (ab dem gespeicherten Checkpoint) mit einer beliebigen Rechnerzahl wiederaufnehmen. Man ist dadurch nicht mehr an die Anzahl der Rechner gebunden, die beim Starten des Programms festgelegt wurde. Das Jackal-DSM ist nicht nur für klassische Rechnerbündel ausgelegt. Es gibt Erweiterungsarbeiten sowohl für den Einsatz im Grid als auch für Rechnerbündel mit Multicore-Prozessoren.

Seit 1977 wird der International Collegiate Programming Contest (ICPC) ausgetragen. Dabei sollen Teams aus je drei Studierenden ca. 13 Programmieraufgaben lösen. Als Erschwernis kommt hinzu, dass nur ein Computer pro Gruppe zur Verfügung steht. Die Aufgaben erfordern solide Kenntnisse von Algorithmen aus allen Gebieten der Informatik und Mathematik, wie z.B. Graphen, Kombinatorik, Zeichenketten, Algebra und Geometrie. Bei der Lösung kommt es darauf an, einen effizienten und richtigen Algorithmus zu finden und zu implementieren.
Der ICPC wird jedes Jahr in drei Stufen ausgetragen. Zuerst werden innerhalb der Universitäten in lokalen Ausscheidungen die maximal drei Teams bestimmt, die dann zu den regionalen Wettbewerben entsandt werden. Erlangen liegt seit dem Jahr 2009 im Einzugsbereich des Northwestern European Regional Contest (NWERC), an dem u.a. auch Teams aus Großbritannien, den Benelux-Staaten und Skandinavien teilnehmen. Die Sieger aller regionalen Wettbewerbe der Welt (und einige Zweitplatzierte) erreichen die World Finals, die im Frühjahr des jeweils darauffolgenden Jahres stattfinden.

Am 27. Januar 2024 fand erneut der Winter Contest statt. Daran beteiligten sich 108 Teams von 17 Hochschulen und Universitäten, darunter 15 Teams aus Erlangen. Unser bestes Team erreichte den 32. Platz. Am 22. Juni wurde der German Collegiate Programming Contest an verschiedenen deutschen Universitäten und Hochschulen ausgetragen, mit 15 Teams aus Erlangen. Das beste FAU-Team belegte den 22. Platz unter den 94 teilnehmenden Teams aus ganz Deutschland. Der NWERC fand am 24. November in Delft statt. Dort wurde die FAU durch ein Team vertreten, das Platz 19 von insgesamt 80 teilnehmenden Teams erreichte. Das Hauptseminar "Hallo Welt! - Programmieren für Fortgeschrittene" fand auch im Jahr 2024 wieder statt.