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.

Der Aufwand für das Verstehen von Software umfasst in Entwicklungsprojekten bis zu 30% und in Wartungsprojekten bis zu 80% der Programmieraufwände. Deshalb wird in modernen Arbeitsumgebungen zur Software-Entwicklung eine effiziente und effektive Möglichkeit zum Software-Verstehen benötigt. Die dreidimensionale Visualisierung von Software steigert das Verständnis der Sachverhalte deutlich, und damit liegt eine Nutzung von Virtual-Reality-Techniken nahe. Im Rahmen des Holoware Projekts schaffen wir eine Umgebung, in der Software mit Hilfe von VR/AR (Virtual/Augmented Reality) und Technologien der Künstlichen Intelligenz (KI) kooperativ exploriert und analysiert werden kann. In dieser virtuellen Realität wird ein Software-Projekt oder -verbund dreidimensional visualisiert, sodass mehrere Benutzer gleichzeitig die Software gemeinsam und kooperativ erkunden und analysieren können. Verschiedene Nutzer können dabei aus unterschiedlichen Perspektiven und mit unterschiedlich angereicherten Sichten profitieren und erhalten so einen intuitiven Zugang zur Struktur und zum Verhalten der Software. Damit sollen verschiedene Nutzungsszenarien möglich sein, wie z.B. die Anomalieanalyse im Expertenteam, bei der mehrere Domänenexperten gemeinsam eine Laufzeitanomalie der Software analysieren. Sie sehen dabei die selbe statische Struktur der Software, jeder Experte jedoch angereichert mit den für ihn relevanten Detail-Informationen. Im VR-Raum können sie ihre Erkenntnisse kommunizieren und so ihre unterschiedliche Expertise einbringen.

Darüber hinaus werden die statischen und dynamischen Eigenschaften des Software-Systems analysiert. Zu den statischen Eigenschaften zählen beispielsweise der Source-Code, statische Aufrufbeziehungen oder auch Metriken wie LoC, zyklomatische Komplexität o. Ä. Dynamische Eigenschaften lassen sich in Logs, Ablaufspuren (Traces), Laufzeitmetriken oder auch Konfigurationen, die zur Laufzeit eingelesen werden, gruppieren. Die Herausforderung liegt darin, diese Vielzahl an Informationen zu aggregieren, analysieren und korrelieren. Es wird eine Anomalie- und Signifikanz-Detektion entwickelt, die sowohl Struktur- als auch Laufzeitauffälligkeiten automatisch erkennt. Zudem wird ein Vorhersagesystem aufgebaut, das Aussagen über die Komponentengesundheit macht. Dadurch kann beispielsweise vorhergesagt werden, welche Komponente gefährdet ist, demnächst auszufallen. Bisher werden die Ablaufspuren um die Log-Einträge angereichert, wodurch ein detailliertes Bild der dynamischen Aufrufbeziehungen entsteht. Diese dynamischen Beziehungen werden auf den statischen Aufrufgraph abgebildet, da sie Aufrufe beschreiben, die aus der statischen Analyse nicht hervorgehen (beispielsweise REST-Aufrufe über mehrere verteilte Komponenten).

Im Jahr 2018 konnten folgende wesentlichen Beiträge geleistet werden:     

• 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. 

Im Jahr 2019 konnten weitere Verbesserungen erreicht werden:     

• 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.  

In dem Papier "Towards Collaborative and Dynamic Software Visualization in VR", das auf der International Conference on Computer Graphics Theory and Applications (VISIGRAPP) 2020 angenommen wurde, haben wir die Wirksamkeit unseres Prototyps zur Effizienzsteigerung beim Software-Verstehen gezeigt.  Im Jahr 2020 wurde unser Papier "A Layered Software City for Dependency Visualization" auf der International Conference on Computer Graphics Theory and Applications (VISIGRAPP) 2021 angenommen und mit dem "Best Paper"-Award ausgezeichnet. Wir konnten belegen, dass das von uns entwickelte Layered Layout für Software-Städte das Analysieren von Software-Architektur vereinfacht und das Standard-Layout bei weitem übertrifft. Der finale Prototyp und die Publikationen, die im Rahmen des Forschungsprojektes entstanden sind, führten zu einem erfolgreichen Projektabschluss. 

Nach Auslaufen der offiziellen Projektförderung durften wir in 2021 eine erweiterte Version des Award-Papiers ("Static And Dynamic Dependency Visualization in a Layered Software City") als Zeitschriftenartikel zur Begutachtung einreichen. Hier stellen wir eine Nacht-Ansicht der Stadt vor, in der die dynamischen Aufrufbeziehungen als Bögen visualisiert werden. Wir widmeten uns also einem zentralen, noch offenen Punkt: der Visualisierung von dynamischen Abhängigkeiten. In dem Papier "Trace Visualization within the Software City Metaphor: A Controlled Experiment on Program Comprehension" auf der IEEE Working Conference on Software Visualization (VISSOFT) haben wir dynamische Abhängigkeiten innerhalb der Software-Stadt über Licht-Intensitäten aggregiert dargestellt und konnten zeigen, dass diese Darstellung hilfreicher ist als alle Abhängigkeiten zu zeichnen. Auch für dieses Papier wurden wir zur Einreichung eines erweiterten Artikels "Trace Visualization within the Software City Metaphor: Controlled Experiments on Program Comprehension" zur Begutachtung aufgefordert. Wir zeigen dort eine erweiterte Darstellung dynamischer Abhängigkeiten und färben Bögen basierend auf HTTP Statuscodes.

In 2022 wurden beide Journalbeiträge akzeptiert: "Static And Dynamic Dependency Visualization in a Layered Software City" ist im Springer Nature Computer Science Journal veröffentlicht und "Trace Visualization within the Software City Metaphor: Controlled Experiments on Program Comprehension" wurde für das Information and Software Technology Journal angenommen. Zur Finalisierung von Holoware wurden alle Erweiterungen zu einer Gesamtvisualisierung zusammengefasst. Dazu wurden unterschiedlichen Ansichten verwendet, zwischen denen der Nutzer umschalten kann: in der Tagesansicht kann die Software-Architektur im neuartigen Holoware-Schichten-Layout analysiert werden und in der Nachtansicht werden dynamische Abhängigkeiten dargestellt. Im Rahmen einer Abschlussarbeit wurde Holoware zudem als AR-Visualisierung umgesetzt, sodass sie leicht als Showcase oder im Arbeitsalltag eingesetzt werden kann.
Mitte 2023 wurde das Projekt mit der Dissertation "Visualisierung der Statik, Dynamik und Infrastruktur von Software mit Hilfe der Stadt‐Metapher" final abgeschlossen. Dort werden nochmal alle Aspekte zusammengefasst, die im Rahmen von Holoware untersucht wurden: (a) die Statik des Systems, um die Software-Architektur zu begreifen, (b) die Dynamik des Systems, um die dynamische Abhängigkeiten (z. B. moderner Microservice-Architekturen) zu verstehen, und (c) die Infrastruktur des Systems, um Kosten zu analysieren und das Verständnis des Software‐Betriebs zu fördern. Zudem wurde 2023 noch ein weiterer Anwendungsfall aufgedeckt: der Einsatz von Holoware auf Messen. Durch die Visualisierung der Software ist es einfach, mit anderen Software-Entwicklern ins Gespräch zu kommen, da sofort über die visualisierte Software diskutiert werden kann. Dazu wurde das Setup der AR- und VR-Visualisierung so vereinfacht, dass Holoware jetzt auch ohne große technische Vorkenntnisse gestartet werden kann. Zudem wurde der Kontrast der Visualisierung verbessert, damit Umrisse und Bögen auch bei sehr hellen Lichtverhältnissen noch klar zu erkennen sind.

Ü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.

Es wurde auch untersucht, wie man eine Listenreduktionen an einer Stelle unterbrechen und später fortsetzen kann. Die Idee war, auf der Basis einer Priorisierung zwischenzeitlich eine andere Liste zu reduzieren, die eine größere Auswirkung auf die Verkleinerung hat. In einigen Fällen trat der erhoffte Geschwindigkeitsgewinn zwar ein, es bleiben aber Fragen offen, die weitere Experimente mit priorisierenden Reduzierern und Listenreduktionsverfahren erfordern.
Im Jahr 2024 konnten wir erfolgreich erste Ergebnisse aus der Untersuchung der Listenreduktionsverfahren publizieren: Durch das Austauschen der Listenverfahren können etablierte Reduzierungsverfahren um bis zu 74,7% beschleunigt werden. Erwartungsgemäß profitieren Verfahren, die lange Listen verursachen, am stärksten von der Änderung.
Außerdem wurde untersucht, welchen Einfluss die Reihenfolge der Listenelemente hat.
Hier können auch bis zu 44,1% der Laufzeit eingespart werden, aber zwei Aspekte verringern die Effektivität einer Umsortierung:

1. Die textuelle Reihenfolge, in der die Listenelemente üblicherweise aufgereiht werden, ist bereits eine vergleichsweise gute Reihenfolge.
2. Die gleichen Aspekte, die ein Listenverfahren schnell machen, sorgen für einen geringeren Einfluss der Reihenfolge.

 Im Rahmen von zwei Abschlussarbeiten wurden zwei weitere Aspekte untersucht:

1. Das von 2018 - 2021 entwickelte Werkzeug zur Erzeugung von Testprogrammen nutzt den zu testenden Übersetzer nur als sogenannte "black box", d.h. es erzeugt Programme, ohne auf Informationen aus dem Übersetzer zurückzugreifen. In einer Abschlussarbeit wurde versucht, mittels Überdeckungsinformationen aus dem getesteten Übersetzer die erzeugten Programme zu verbessern.
2. Bei den Reduzierungsverfahren ist ein Cache wichtig, um für sich wiederholende Reduktionskandidaten nicht immer den zu testenden Übersetzer auszuführen. Naive Implementierungen dieser Caches werden jedoch sehr groß. Im Jahr 2023 wurde bereits ein dediziertes Cache-Verfahren vorgestellt, das die Cache-Größe um ca. 90% verkleinern kann. Leider ist dieses Cache-Verfahren nicht für alle in unserem Framework enthaltenen Reduzierungsverfahren geeignet und wurde deswegen in einer Abschlussarbeit entsprechend erweitert.

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.

Im Jahr 2020 wurden folgende wesentlichen Beiträge geleistet:

• Weiterentwicklung der Genetischen Optimierung.
• Aufbau eines Docker-Containers für zuverlässige Reproduzierbarkeit der Ergebnisse.
• Integration der Softwarekomponenten der Projektpartner.
• Plugin-Architektur für Low-Level-Platformen.
• Implementation und Integration zweier LLP-Plugin-Komponenten.
• Erweiterung des akzeptierten OpenMP-Sprachstandards.
• Erweiterung der Test-Suite.

Im Jahr 2021 wurden folgende wesentlichen Beiträge geleistet:

• Erweiterung der Benchmark-Suite.
• Erweiterung der Test-Infrastruktur.
• Erfolgreicher Projektabschluss mit Live-Demo für den Projektträger.
• Evaluation des Projekts.
• Veröffentlichung der Publikation "ORKA-HPC - Practical OpenMP for FPGAs".
• Veröffentlichung des Quell-Codes und der Disseminationsumgebung auf Github.
• Erweiterung des akzeptierten OpenMP-Sprachstandards um neue OpenMP-Klauseln für die Steuerung der FPGA-bezogenen Transformationen.
• Weiterentwicklung der Genetischen Optimierung.
• Untersuchung des Verhältnisses von HLS-Leistungsschätzwerten und tatsächlichen Leistungskennzahlen.
• Aufbau eines linearen Regressionsmodells für die Vorhersage der tatsächlichen Leistungskennzahlen auf Basis der HLS-Schätzwerte.
• Entwicklung von Infrastruktur für die Übersetzung von OpenMP-Reduktionsklauseln.
• Erweiterung um die Übersetzung vom OpenMP-Pragma `parallel for` in ein paralleles FPGA-System.

Im Jahr 2022 wurden folgende wesentlichen Beiträge geleistet:

• Generierung und Veröffentlichung eines Datensatzes zur Untersuchung des Verhältnisses von HLS-Ressourcenschätzwerten und tatsächlichen Leistungskennzahlen.
• Erstellung und vergleichende Evaluierung verschiedener Regressionsmodelle zur Vorhersage der tatsächlichen Systemperformanz aus frühen Schätzwerten.
• Analyse und Bewertung der durch die HLS generierten Ressourcenabschätzungen.
• Veröffentlichung der Publikation “Reducing OpenMP to FPGA Round-trip Times with Predictive Modelling”.
• Entwicklung eines auf dem Polyeder-Modell beruhenden Verfahrens zur Detektion und Entfernung von redundanten Lese-Operationen in FPGA-Stencil-Codes.
• Implementierung dieses Verfahrens in ORKA-HPC.
• Quantitative Evaluation der Stärken dieses Verfahrens und Ermittlung der Voraussetzungen, unter denen das Verfahren anwendbar ist.
• Veröffentlichung der Publikation “Employing Polyhedral Methods to Reduce Data Movement in FPGA Stencil Codes”.

Im Jahr 2023 wurden folgende wesentlichen Beiträge geleistet:

• Entwicklung und Implementierung eines Optimierungsverfahrens von kanonischen Schleifenschachteln (z.B. aus OpenMP-Target-Regionen) für die FPGA-Hardware-Erzeugung mittels HLS. Der Kern des Verfahrens ist eine auf dem Polyeder-Modell basierende Schleifenrestrukturierung, welche mithilfe von Schleifen-Kachelungen, Fließbandverarbeitung, und Port-Verbreiterung unnötige Datentransfers vom/zum FPGA-Board-RAM vermeidet, die Anzahl der parallel aktiven Schaltkreise erhöht, den Datendurchsatz zum FPGA-Board-RAM maximiert und Schreib/Lese-Latenzen versteckt.
• Quantitative Evaluation der Stärken und Anwendungsfelder dieses Optimierungsverfahrens mithilfe von ORKA-HPC.
• Veröffentlichung des Verfahrens im Konferenz-Papier “Employing polyhedral methods to optimize stencils on FPGAs with stencil-specific caches, data reuse, and wide data bursts”.
• Veröffentlichung eines Reproduktionspakets für das Optimierungsverfahrens.
• Vorstellung des Verfahrens auf der Tagung “14th International Workshop on Polyhedral Compilation Techniques” im Rahmen eines halbstündigen Vortrags.
• Entwicklung eines Verfahrens für die vollautomatische Integration von Multi-Purpose-Caches in aus OpenMP generierte FPGA-Lösungen.
• Evaluation von Multi-Purpose-Caches in Kombination mit HLS-generierten Hardwareblöcken.
• Veröffentlichung der Publikation “Multipurpose Cacheing to Accelerate OpenMP Target Regions on FPGAs” (Best Paper Award).

Im Jahr 2024 wurden folgende wesentlichen Beiträge geleistet:

• Anpassung mehrerer bereits publizierter Cacheing-Ansätze auf ausgelagerte OpenMP-Codes und Einbau der Verfahren in ORKA-HPC
• Entwicklung und Evaluation neuartiger mehrstufiger Caches für HLS-Kernel 
• Veröffentlichung der Ergebnisse in der Publikation "Multilayer Multipurpose Caches for OpenMP Target Regions on FPGAs" und Vorstellung der Arbeit bei der IWOMP 2024 in Perth

•  

Mit wachsender Verfügbarkeit von Information über eine Umgebung (z.B. eine Sporthalle) und über die Objekte darin (z.B. Sportler in der Halle) steigt das Interesse, diese Informationen gewinnbringend zusammenzuführen (sog. Information Fusion) und zu verarbeiten. Zum Beispiel will man physikalisch korrekte Animationen (z.B. in der virtuellen Realität) von komplexen und hochdynamischen Bewegungen (z.B. in Sportsituationen) in Echtzeit rekonstruieren. Ebenso könnten z.B. auch Fertigungsanlagen der Industrie, die unter ungünstigen Umgebungsverhältnissen leiden (bspw. Magnetfeldinterferenzen oder fehlendes GPS-Signal), von bspw. hochpräziser Warenortung profitieren. Typischerweise verwendet man, um Bewegungen zu beschreiben, entweder Posen, die einen „Snapshot" eines Bewegungszustands beschreiben (z.B. Stillstand), oder ein Bewegungsmodell, welches eine Bewegung im zeitlichen Verlauf beschreibt (z.B. Laufen oder Rennen). Außerdem können menschliche Bewegungen durch unterschiedliche Sensoren (z.B. am Körper) erfasst und in Form von Posen und Bewegungsmodellen abgebildet werden. Dabei liefern verschiedene Typen von modernen Sensoren (bspw. Kamera-, Funk- und Inertial-Sensoren) Informationen von unterschiedlicher Qualität.Prinzipiell ist mit Hilfe teurer und hochpräziser Messinstrumente die Extraktion der Posen und resp. des Bewegungsmodells bspw. aus Positionen (Positionen, z.B. menschlicher Extremitäten, können Posen und Bewegungsmodelle beschreiben oder durch diese beschrieben werden) auf kleinen Trackingflächen fehlerfrei möglich. Kamerabasierte Sensorik liefert dabei die benötigten hochfrequenten hochpräzisen Referenzmessungen auf kleinen Flächen. Allerdings sinkt mit zunehmender Größe der Trackingfläche die Tauglichkeit kamerabasierter Systeme (auf Grund von Ungenauigkeiten oder Problemen durch Verdeckung). Ebenso liefern Funk- und Inertial-Sensoren nur verrauschte und ungenaue Messungen auf großen Flächen. Eine auf Bayes‘schen Filtern basierende Kopplung von Funk- und Inertial-Sensoren erzielt zwar eine höhere Genauigkeit. Diese ist aber noch immer unzureichend, um z.B. im Sport menschliche Bewegungen (abrupte und schnelle Bewegungsänderungen) auf großen Flächen sensorisch präzise zu erfassen. Damit sind die resultierenden Bewegungsmodelle ungenau.Ferner ist jede menschliche Bewegung hochgradig nichtlinear (resp. nicht vorhersagbar). Diese Nichtlinearität lässt sich mit Hilfe heutiger Bewegungsmodelle, wie sie bspw. durch Bayes‘schen Filter beschrieben werden, nicht korrekt abbilden, da diese (statistischen) Methoden ein nichtlineares Problem in lineare Teilprobleme herunterbrechen, die wiederum die Bewegung nicht physikalisch korrekt repräsentieren können. Darüber hinaus erzeugen aktuelle Verfahren hohe Latenz, wenn Genauigkeit gefordert ist.Aufgrund dieser drei Probleme (ungenaue Positionsdaten auf großen Flächen, Nichtlinearität und Latenz) sind heutige Verfahren bspw. für Sportanwendungen unbrauchbar, die kurze Antwortzeiten fordern. Im Rahmen dieses Projekts wird mit Hilfe von Methoden des maschinellen Lernens diesen Nichtlinearitäten entgegengewirkt. So umfasst das Projekt die Erforschung rekurrenter neuronaler Netze (RNN) zur Bestimmung nichtlinearer Bewegungsmodelle. Nichtlineare menschliche Bewegungen (z.B. die Lage des Kopfes zum Rumpf während des Laufens oder Rennens), können mittels moderner Bayes‘scher Filterverfahren (z.B. Kalman- und Partikel-Filter) und anderer statistischer Methoden nur durch ihre linearen Anteile und somit physikalisch nicht vollständig korrekt beschrieben werden. Daher ist das Kernziel, zu evaluieren, wie Methoden des maschinellen Lernens zur Beschreibung von komplexen und nichtlinearen Bewegungen eingesetzt werden können. Es wurde deshalb untersucht, ob RNNs die Bewegungen eines Objektes physikalisch korrekt beschreiben und bisherige Methoden unterstützen oder ersetzen können. Im Rahmen einer großangelegten Parameterstudie wurden physikalische korrekte Bewegungen simuliert und auf diesen Simulationen RNN-Verfahren optimiert. Es konnte erfolgreich gezeigt werden, dass RNN-Modelle mit Hilfe geeigneter Trainingsverfahren entweder physikalische Zusammenhänge oder Bewegungsformen erlernen.
Im Rahmen dieses Projekts werden drei wesentliche Themen bearbeitet:
I. Eine Basisimplementierung untersucht, wie und warum Methoden des maschinellen Lernens zur Bestimmung von Bewegungsmodellen von Menschen eingesetzt werden können.
Im Jahr 2018 wurde zunächst ein tieferes Verständnis der Ausgangssituation und Problemstellung aufgebaut. Mit Hilfe verschiedener Basisimplementierungen (unterschiedlicher Bewegungsmodelle) wurde untersucht (1) wie sich unterschiedliche Bewegungen (z.B. Menschen: Laufen, Rennen, Slalom und Fahrzeuge: Mäander, Zig-Zag) auf Messungenauigkeiten der verschiedenen Sensorfamilien auswirken, (2) wie sich Messungenauigkeiten verschiedener Sensorfamilien (z.B. sichtbare Orientierungsfehler, hörbare Störgeräusche und bewusste künstliche Messfehler) auf die menschliche Bewegung auswirken und (3) wie sich verschiedene Filtermethoden zur Fehlerkorrektur (Balanceakt zwischen Genauigkeit und Latenz) auf die Bewegung und Sensoren auswirken. Darüber hinaus konnte (4) gezeigt werden, wie Messungenauigkeiten (bedingt durch den Einsatz aktueller Bayes‘scher Filterverfahren) mit der menschlichen Körperhaltung (bspw. Gangapparat) nichtlinear korrelieren und wie Auswirkungen der Messfehler auf die Gesundheit (Simulatorkrankheit) mittels maschinellen Lernens vorhergesagt werden können. Es wurden Methoden des maschinellen und tiefen Lernens zur Bewegungserfassung (Mensch: Kopf, Körper, obere und untere Extremität; Fahrzeug: ein- und zweiachsig) und Bewegungsrekonstruktion (5) auf Basis von Inertial-, Kamera- und Funksensoren studiert und verschiedene Methoden zur Merkmalsextraktion (bspw. SVM, DT, k-NN, VAE, 2D-CNN, 3D-CNN, RNN, LSTMs, M/GRU) untersucht. Diese wurden u. A. zu verschiedenen hybriden Filtermodellen verschaltet, um extrahierte Merkmale um zeitliche und kontextsensitive Bewegungsinformationen anzureichern und so möglicherweise genauere, robustere und echtzeitnahe Bewegungsmodelle zu erstellen. So konnten (6) Bewegungsmodelle für mehrachsige Fahrzeuge (Gabelstapler) auf Basis von Inertial-, Funk- und Kameradaten gelernt werden, die auf unterschiedliche Umgebungen, respektive Trackingflächen (Größe, Form und sensorische Struktur bspw. Magnetfeld, Mehrwege, Texturierung und Beleuchtung) generalisieren. Weiter (7) konnte ein tieferes Verständnis der Auswirkungen von nicht konstant beschleunigten Bewegungsmodellen auf Funksignale untersucht werden. Auf Basis dieser Erkenntnisse konnte ein LSTM Modell angelernt werden, das unterschiedliche Bewegungsgeschwindigkeiten und Bewegungsformen eines einachsigen Roboters (Segway) nahe Echtzeit und genauer als herkömmliche Verfahren vorhersagen kann.
Im Jahr 2019 wurde festgestellt, dass diese Modelle auch die menschliche Bewegung (menschliches Bewegungsmodell) vorhersagen können. Weiter wurde im Jahr 2019 festgestellt, dass die LSTM Modelle zur Laufzeit entweder vollständig autark oder als Stützstellen in Lokalisierungsschätzern (bspw. Pedestrian Dead Reckoning, PDR, Methoden) integriert werden können.
II. Darauf aufbauend soll versucht werden, wie diese Basis hinsichtlich ihrer Robustheit, Latenz und Wiederverwendbarkeit zu optimieren ist.
Im Jahr 2018 konnten die Erkenntnisse aus I. (1-7) genutzt werden, um sogenannte (1) relative Pedestrian Dead Reckoning (PDR) Verfahren mit Hilfe von Bewegungsklassifizierern zu stabilisieren. Diese konnten eine Generalisierung auf beliebige Umgebungen ermöglichen. Das tiefere Funksignalverständnis (2) ermöglichte das Abbilden von Langzeitfehlern in RNN-basierten Bewegungsmodellen, um die Positionsgenauigkeit und Stabilität zu verbessern und nahe Echtzeit vorherzusagen. Die Robustheit der Bewegungsmodelle (3) konnte in ersten Versuchen mit Hilfe verschiedener realer (den Modellen unbekannter) Bewegungstrajektorien für ein- und zweiachsige Fahrzeuge gezeigt werden. Weiter wurde untersucht, (4) wie hybride Filtermodelle (bspw. Verschaltung von Merkmalsextraktoren 2D/3D-CNN und Zeitreihe RNN-LSTM) sowohl genauere, als auch stabilere und gefilterte (um Ausreißer korrigierte) Ergebnisse liefert.
Im Jahr 2019 wurde gezeigt, dass Modelle der RNN Familie in der Lage sind, Bewegungen in die Zukunft zu extrapolieren, so dass diese die Latenz der Verarbeitungskette und darüber hinaus kompensieren. Weiter wurde im Jahr 2019 die Erklärbarkeit, Interpretierbarkeit und Robustheit der hier untersuchten Modelle und die Wiederverwendbarkeit auf die menschliche Bewegung untersucht.Mit Hilfe eines Simulators wurden im Jahr 2019 physikalisch korrekte Bewegungen, z.B. Positionen von Fußgängern, Fahrradfahrern, Autos und Flugzeugen erzeugt. Auf Basis dieser Daten wurde gezeigt, dass RNN Modelle zwischen unterschiedlichen Bewegungstypen interpolieren können. Weiter wurde gezeigt, dass RNN Modelle fehlende Datenpunkte kompensieren, weißes und zufälliges Rauschen als solches interpretieren und Bewegungen in die Zukunft extrapolieren können. Letzteres ermöglicht die Kompensation von verarbeitungsspezifischer Latenz und ermöglicht eine Vorhersage der menschlichen Bewegung aus Funk- und Inertial-Daten in harter Echtzeit.Neue RNN Architektur. Ferner wurde im Jahr 2019 eine neue Architektur, bzw. Topologie, eines neuronalen Netzes erforscht, welches die Stärken und Schwächen von flachen neuronalen Netzen und rekurrenter Netzen so kompensiert, dass eine optimales NN zur Bestimmung physikalisch korrekter Bewegung in einer großangelegten Parameterstudie gefunden werden konnte.Architektur Optimierung. Es wurde im Jahr 2019 eine großangelegte Studie zur Optimierung der Modellparameter für die Mensch-zentrierte Lokalisierung durchgeführt. Diese optimalen Architekturen können die menschliche Bewegung aus möglichst wenig Sensorinformationen weit in die Zukunft voraussagen. Die Architektur mit dem geringsten Lokalisierungsfehler kombiniert zwei DNNs mit einem RNN.Interpretierbarkeit von Modellen. Dieses neue Modell wurde im Jahr 2019 auf seine Funktionsweise untersucht. Dazu wurde eine neuartige Prozesskette zur Interpretation und Erklärung des Modells erforscht. Die Prozesskette nutzt den Fluss der gegenseitigen Information und die gegenseitige Übertragungsentropie in Kombination mit verschiedenen gezielten Manipulationen der versteckten Zustände und geeigneten Visualisierungstechniken, um den Zustand des Modells zu jedem Zeitpunkt zu bestimmen.Darüber hinaus wurde im Jahr 2019, um extrahierte Merkmale eines neuronalen Netzes besser zu visualisieren und zu interpretieren, ein "Variational Auto-Encoder" (VAE) adaptiert. Der VAE wurde so gestaltet und parametrisiert, dass der Rekonstruktionsfehler des Signals innerhalb des Messrauschens liegt und das Modell gleichzeitig gezwungen wird, entwirrte Merkmale im latenten Raum abzulegen. Dieses Entwirren ermöglicht erste subjektive Aussagen über die Zusammenhänge der Merkmale, die wirklich nötig sind, um den Kanalzustand eines Funksignals optimal zu kodieren.Kompression. Dabei wurde im Jahr 2019 ein netter Seiteneffekt des VAEs entdeckt. Ein solcher VAE bietet die Möglichkeit der dezentralen Vorverarbeitung der Kanalinformationen direkt an der Antenne. Diese Komprimierung führt dann zu weniger Datenverkehr, erzeugt weniger Kommunikationslast und erhöht somit die Anzahl möglicher Teilnehmer an der Kommunikation und Lokalisierung in einem abgeschlossenen Sensornetz.Einfluss der Variation der Eingabeinformationen. Weiter wurde im Jahr 2019 untersucht, wie sich Änderungen der Inputsequenzlänge eines rekurrenten neuronalen Netzes auf den Lernerfolg und die Art der Ergebnisse des Modells auswirken. Es wurde entdeckt, dass eine längere Sequenz das Modell überredet, eher ein Bewegungsmodell i.S.v. der Form der Bewegung zu erlernen, während kürzere Sequenzen dazu tendieren physikalische Zusammenhänge zu erlernen. Die höchste Genauigkeit erreicht man mit der optimalen Balance zwischen kurzen und langen Sequenzen.Es wurde im Jahr 2019 eine Geschwindigkeitsschätzung mittels des neuen Verfahrens untersucht. Diese floss dann direkt in ein PDR Modell ein, um die Positionsgenauigkeit zu erhöhen. Eine erste Arbeit im Jahr 2019 dazu hat im Detail untersucht, welche Verfahren am besten geeignet sind, um eine ungerichtete Geschwindigkeit der menschlichen Bewegung aus einem rohen Intertialsignal zu schätzen. Ein neues Verfahren, eine Kombination aus einem eindimensionalen CNN und einem BLSTM, hat hier den Stand der Technik abgelöst.
Im Jahr 2020 wurden die Modellarchitektur hinsichtlich der Vorhersagegenauigkeit optimiert und die Auswirkungen einer tiefen Kombination von Bayes'schen und DL-Methoden auf die Vorhersagegenauigkeit und Robustheit untersucht.
Optimierung. Im Jahr 2020 wurde die bestehende CNN- und RNN-Architektur verbessert und ein ResNet-BLSTM vorgeschlagen. Das CNN wurde durch ein Restnetzwerk ersetzt, um tiefere und qualitativ hochwertigere Merkmale aus einem kontinuierlichen Datenstrom zu extrahieren. Es konnte gezeigt werden, dass diese Architektur höhere Rechenkosten mit sich bringt, aber die genauesten, über den Stand der Technik hinausgehenden Ergebnisse liefert. Zusätzlich kann die RNN-Architektur verkleinert werden, um dem Ausbleichen des Kontextvektors der LSTM-Zellen entgegenzuwirken, da das verbleibende Netzwerk optimalere Merkmale bietet.Tiefe Bayes Verfahren. Im Jahr 2020 wurde untersucht, ob Methoden der RNN-Familie bestimmte Bewegungseigenschaften aus aufgezeichneten Bewegungsdaten extrahieren können, um die starren Mess-, Rausch- und Übergangsverteilungen eines Kalman-Filters (KF) zu ersetzen. Eine Studie konnte zeigen, dass hochoptimierte LSTM-Zellen robustere (geringe Fehlervarianz der Prädiktionen) und präzisere (Positionsgenauigkeit) Trajektorien rekonstruieren können als ein ebenso hochoptimierter KF. Das tiefe Ineinandergreifen von LSTM in KF, sogenanntes tiefe Bayes Verfahren, lieferte die robustesten und präzisesten Positionen und Trajektorien. Diese Studie zeigte auch, dass von allen Methoden, die auf realistischen synthetischen Daten trainiert wurden, die tiefe Bayes-Methode am wenigsten reale Daten benötigt, um sich an eine neue unbekannte Domäne anzupassen.
III. Abschließend soll eine Demonstration der Machbarkeit erprobt werden.
Im Jahr 2018 wurde im Rahmen einer Großstudie mit sozialwissenschaftlichem Hintergrund das weltgrößte virtuelle Dinosauriermuseum eröffnet. Es konnte gezeigt werden, dass ein vorausgewähltes (auf das Einsatzszenario optimiertes) Bewegungsmodell die menschliche Bewegung robust und genau (i.S.v. kein signifikanter Einfluss auf die Simulatorkrankheit) abbilden resp. vorhersagen kann. Dieses wird als Basis für Vergleichstest für weitere Modelle (mensch-zentriert und generalisierend auf unterschiedliche Umgebungen) genutzt.
Im Jahr 2019 wurden auf Basis der erzielten Forschungsergebnisse in I und II zwei neue Live-Demonstratoren entwickelt. (1) Eine Modelleisenbahn, welche in variablen Geschwindigkeiten eine Landschaft mit Tunnel durchquert. Dabei repräsentiert der Tunnel realistische und typische Umgebungscharakteristika, die zu nichtlinearen Mehrwegeausbreitungen eines zu lokalisierenden Funksenders führen und letztendlich zu fehlerhaften Positionsbestimmung. Dieser Demonstrator zeigt, dass die im Rahmen des Forschungsprojektes erforschten RNN Verfahren sowohl auf komplexen Kanalimpulsantworten, als auch auf dimensionsreduzierten Antwortzeiten hochgenau und robust lokalisieren können und darüber hinaus bessere Ergebnisse als herkömmliche Kalman-Filter liefern. (2) Der zweite Demonstrator dient zur Visualisierung der Bewegung der oberen Extremität eines Menschen. Dabei wurde die menschliche Bewegung mit kostengünstiger Inertialsensorik erfasst, klassifiziert und Bewegungsparameter abgeleitet. Eine grafische Oberfläche visualisiert nahe Echtzeit die Bewegung und die abgeleiteten Parameter.Die geplante Generalisierbarkeit, bspw. der mensch-zentrierten Modelle, und die Anwendbarkeit von RNN-basierten Verfahren in unterschiedlichen Umgebungen konnte mittels (1) und (2) demonstriert werden.Im Jahr 2019 konnten folgende Anwendungen der vorgeschlagenen Methode beforscht und entwickelt werden:Anwendung: Funksignal. Es wurden die Kanalinformationen eines Funksystems hierarchisch derart klassifiziert, dass das Lokalisierungsproblem eines Line of Sight (LoS) und Non Line of Sight (NLoS) Klassifizierers in ein binäres Problem übertragen werden konnte. So kann rein auf Basis einzelner Kanalinformationen einer einzelnen Antenne eine Position auf einen Meter genau lokalisiert werden, wenn die Umgebung heterogene Kanalausbreitung breitstellt.Ferner wurden LoS und NLoS Kanalinformationen simuliert und genutzt, um zwischen unterschiedlichen Kanälen zu interpolieren. Dies ermöglicht den Anbietern von Funksystemen, auf sich ändernde oder neue Umgebungen in den Kanalinformationen bereits a-priori in der Simulation einzugehen. Durch selektives Nachtrainieren der Modelle mit dem simulierten Wissen werden robustere Modelle ermöglicht.Anwendung: Kamera- und Funksignal. Weiter konnte gezeigt werden, wie sich die RNN Methoden auf Informationen anderer Sensorfamilien, z.B. Videobilder, übertragen lassen. Eine Kombination von Funk- und Kamerasystemen ermöglichte es, ein Modell zu trainieren, welches selbst in Verdeckungsfällen der Kamera eine reibungslose Fusion der beiden Sensorinformationen schafft und zu einer robusteren und genaueren Lokalisierung mehrerer Personen führt.Anwendung: Kamerasignal. In einer weiteren Arbeit wurde ein RNN-Verfahren genutzt, um die zeitlichen Zusammenhänge von Ereignissen in Bildern zu untersuchen. Im Gegensatz zu der vorangegangenen Arbeit, die heterogene Sensorinformationen nutzt, nutzt dieses Netz lediglich Bildinformationen. Das Modell nutzt die Bildinformationen allerdings so, dass es die Bilder unterschiedlich interpretiert: als räumliche Informationen i.S.v. ein einzelnes Bild, und als temporale Information i.S.v. mehrere Bilder im Input. Dieses Aufsplitten führt dazu, dass einzelne Bilder quasi als zwei fiktive virtuelle Sensorinformationsströme genutzt werden können, um Ergebnisse räumlich (Merkmale) zu erkennen und temporal (zeitliche Zusammenhänge) besser vorhersagen zu können. Eine weitere Arbeit nutzt Kamerabilder, um die Kamera selbst zu lokalisieren. Dazu wurde eine neue Verarbeitungskette erschaffen, welche das Videosignal über die Zeit aufbricht und absolute und relative Informationen in unterschiedlichen neuronalen Netzen erlernt und deren Ausgabe in einem Fusionsnetz zu einer optimalen Pose zusammenführt.Anwendung: EEG-Signal. In einem Kooperationsprojekt konnten die hier erforschten Methoden auf weitere Sensordaten angewendet werden. Es konnten Beta- und Gammawellen des menschlichen Gehirns in unterschiedlichen emotionalen Zuständen aufgezeichnet werden und diese von einem RNN genutzt werden, um die Emotionen einer Testperson in 90% aller Fälle aus rohen EEG Daten korrekt vorherzusagen.Anwendung: Simulatorkrankheit. In einer weiteren Arbeit konnte gezeigt werden, wie sich die Visualisierung in VR auf die menschliche Wahrnehmung und Bewegungsanomalien, respektive Simulatorkrankheit, auswirkt und wie sich die hier erforschten neuronalen Netze ausnutzen lassen, um die Effekte vorherzusagen.Im Jahr 2020 wurden auf Basis der erzielten Forschungsergebnisse in II ein neuer Live-Demonstrator entwickelt.Anwendung: Gangrekonstruktion in VR. Im Jahr 2020 wurde das vorhandene CNN-RNN-Modell verwendet, um die Bewegung des Menschen, nämlich den Gangzyklus und die Gangphasen, vorherzusagen. Dabei wurden Sensordaten eines am Kopf montierten Trägheitssensors verwendet, um einen virtuellen Avatar in VR in Echtzeit zu visualisieren. Es konnte gezeigt werden, dass das DL-Modell deutlich geringere Latenzen aufweist als der Stand der Technik, da es Gangphasen früher erkennen und zukünftige genauer vorhersagen kann. Dies geht jedoch zu Lasten des erforderlichen Rechenaufwands und damit der erforderlichen Hardware.
Das Projekt wurde im Jahr 2021 erfolgreich abgeschlossen. Im Jahr 2021 wurden im Rahmen einer erfolgreich abgeschlossenen Dissertation wesentliche Erkenntnisse aus dem Projektverlauf verknüpft und Schlussfolgerungen gezogen sowie zahlreiche Forschungsfragen aufgegriffen und beantwortet.
Im Rahmen des Forschungsvorhabens wurden mehr als 15 Qualifikationsarbeiten, 6 Patentfamilien und mehr als 20 wissenschaftliche Publikationen erfolgreich abgeschlossen und veröffentlicht. Kernbeitrag des Projekts ist die Kenntnis der Anwendbarkeit und Tücken rekurrenter neuronaler Netze (RNN), ihrer unterschiedlichen Zelltypen und Architekturen in unterschiedlichen Anwendungsgebieten. Fazit: Die Möglichkeit der RNN-Familie, mit Dynamiken in Datenströmen umzugehen, z.B. Ausfällen, Verzögerungen und unterschiedlichen Sequenzlängen in Zeitreihendaten, macht sie heute in einer Vielzahl von Anwendungsbereichen unverzichtbar.
Das Projekt wird im Rahmen von Seminaren an der FAU und außeruniversitären Forschungsaktivitäten bei Fraunhofer IIS im Rahmen des ADA Lovelace Center fortgeführt.
Im Jahr 2022 wurde die Augmentierung von Zeitreihen untersucht. Zu diesem Zweck wurden verschiedene generative Methoden, nämlich Variational Autoencoder (VAE) und Generative Adversarial Networks (GAN), hinsichtlich ihrer Fähigkeit evaluiert, Zeitreihen verschiedener Anwendungsdomänen zu generieren, z.B., Eigenschaften von Funksignalen, Signalstärke, Kanalimpulsantwort, Merkmale von GNSS-Spektren und mehrdimensionale Signale von Trägheitssensoren. Es wurde eine neuartige Architektur namens ARCGAN vorgeschlagen, die alle bekannten Vorteile der Stand der Technik-Methoden vereint und daher deutlich ähnlichere (nützlichere) Zeitreihen generieren kann als der Stand der Technik.

Im Jahr 2023 wurde begonnen, generative Methoden auf Basis von Aufmerksamkeitsmechanismen, Transformer-Architektur und GPT hinsichtlich ihrer Vorhersageleistung von Zeitreihen zu untersuchen. Zu diesem Zweck wurden Methoden wie Legendre Units (LMU), neuartige Transformatorarchitekturen und TimeGPT zur Vorhersage von Lokalisierungsinformationen evaluiert. Es zeigte sich, dass mittels entsprechender Eingabeaufforderungen und Kalibrierung vorkonfigurierter GPT-Modelle an neue Anwendungsbereiche angepasst werden können, wodurch das Training deutlich effizienter wird und Energie eingespart wird.

Im Jahr 2024 werden GPT-ähnliche Modelle weiter auf ihre Unsicherheit, Erklärbarkeit und Anpassungsfähigkeit untersucht. Darüber analysieren wir die Machbarkeit dieser generativen Verfahren in Bezug auf verschiedene Anwendungsfelder, z.B., Vorhersage und Anomalieerkennung, Anomaliecharakterisierung, Anomalielokalisierung sowie Anomaliemitigierung.

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.
Ein weiteres Teilziel war die quantitative und qualitative Verbesserung der in Informatik geschriebenen W-Seminar-Arbeiten. Dazu wurde eine 24-seitige Broschüre entwickelt und an Schulen in umliegenden Landkreisen verschickt. Mit dieser Broschüre sollen Lehrkräfte bei der Gestaltung und Durchführung von W-Seminaren in der Informatik mit Themenvorschlägen, Hinweisen und einer Checkliste für die Schülerinnen und Schüler unterstützt werden. Im Jahr 2019 endete das Projekt GIFzuMINTS mit einem besonderen Höhepunkt: Am 20.05.2019 besuchte uns der bayerische Staatsminister für Wissenschaft und Kunst, Bernd Sibler, zusammen mit dem stellvertretenden Hauptgeschäftsführer der vbw bayme vbm, Dr. Christof Prechtl, um sich über den Stand des Projekts zu informieren. Wissenschaftsminister Bernd Sibler zeigte sich beim Projektbesuch beeindruckt: "Das Konzept der FAU geht passgenau auf die Anforderungen eines Informatikstudiums ein. Die jungen Studentinnen und Studenten werden dort abgeholt, wo sie stehen. Das ist exakt unser Anliegen, das wir mit MINTerAKTIV verfolgen: Wir wollen, dass jede Studentin und jeder Student die Unterstützung bekommt, die sie bzw. er braucht, um das Studium erfolgreich abschließen zu können."Bis zum Projektende wurden die entwickelten und umgesetzten Maßnahmen gründlich evaluiert und als dauerhafte Angebote etabliert. Dabei wurde das Repetitorium Informatik in ein kontinuierliches virtuelles Angebot zum Selbststudium überführt und auf den neuesten Stand der Technik aktualisiert. Das an besonders begabte Studierende gerichtete Angebot der Vorbereitung auf die Teilnahme an internationalen Programmierwettbewerben wurde ausgeweitet und als Vertiefungsmodul eingerichtet. Damit die begonnenen Maßnahmen auch zukünftig reibungslos weitergeführt werden können, wurde bereits frühzeitig die Aufnahme in das anschließende Förderprojekt beantragt, das zukünftig als CS4MINTS auch bewilligt wurde.

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.
Im Jahr 2018 wurden im Rahmen von zwei Bachelorarbeiten Methoden zur symbolischen Ausführung und Funktionssynthese untersucht, um zu ermitteln, welche sich für unseren Ansatz am Besten eignet. Im Jahr 2019 wurde ein Ansatz auf Basis der LLVM Compiler Infrastruktur untersucht, der mittels konkolischer Ausführung (concolic execution, eine Kombination aus  symbolischer und konkreter Ausführung) ein Wasserzeichen in einem ungenutzten Hardwareregister versteckt. Hierzu wurde der LLVM-Registerallokator dahingehend verändert, dass er ein Register für das Wasserzeichen freihält. Im Jahr 2020 wurde das inzwischen LLWM genannte Rahmenprogramm für das automatische Einfügen von Software-Wasserzeichen in Quellcode auf Basis der LLVM Compiler Infrastruktur um weitere dynamische Verfahren erweitert. Grundlage der hinzugefügten Verfahren sind, unter anderem, das Ersetzen/Verschleiern von Sprungadressen sowie Modifikationen des Aufrufgraphen. Im Jahr 2021 wurde das Rahmenprogramm LLWM um weitere angepasste, bereits in der Literatur bekannte, dynamische Verfahren sowie um das eigene Verfahren erweitert, das wir nun IR-Mark nennen Die hinzugefügten Verfahren basieren unter anderem auf der Umwandlung von bedingten Konstrukten in semantisch äquivalenten Schleifen oder auf Integrieren von Hashfunktionen, die die Funktionalität des Programms unverändert lassen, die Widerstandsfähigkeit aber erhöhen. IR-Mark wählt nun nicht nur gezielt die wenigen Funktionen aus, in denen die Registerverwendung bei der Code. Erzeugung verändert wird, sondern umfasst nun auch dynamische Aspekte um in den freigehaltenen Registern sinnvoll erscheinende Tarnwerte zu berechnen. Ein Artikel über LLWM und IR-Mark konnte publiziert werden. Im Jahr 2022 wurde das Rahmenprogramm LLWM um ein weiteres angepasstes Verfahren ergänzt. Die Methode nutzt  Ausnahmebehandlungen, um das Wasserzeichen zu tarnen. Im Jahr 2023 wurden mehr Methoden angepasst, um das LLWM-Framework zu erweitern. Hierzu zählen Techniken zum Einbetten, die auf Prinzipien der Zahlentheorie und des Aliasings beruhen.Im Jahr 2024 wurden drei neue Wasserzeichen entwickelt: Register Expansion, SemaCall und SideData.
Diese Techniken konstruieren streufunktionsartige Arithmetiken, um während der Laufzeit einen Schlüsselwert in die Wasserzeichennachricht umzurechnen.
Die ersten beiden Techniken wurden in dem Papier „Register Expansion and SemaCall: 2 Low-overhead Dynamic Watermarks Suitable for Automation in LLVM" auf dem CheckMATE'24 Workshop in Salt Lake City publiziert. Eine erweiterte Fassung des Papiers enthält auch das SideData Wasserzeichen und befindet sich im Peer-Review-Prozess für das DTRAP-Journal.

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.

Das Projekt stellte bis 2019 einen Beitrag des Lehrstuhls Informatik 2 zum IZ ESI (Embedded Systems Initiative, http://www.esi.fau.de/ ) dar. In diesem Rahmen wurden verschiedene Ansätze zur Verbesserung der Qualität nebenläufiger Software untersucht. Zusammenfassend wurde festgestellt, dass verschiedenartige Verfahren notwendig und realisierbar sind, allerdings meistens die hohen Laufzeiten ein großes Problem darstellen.

Über das ESI Projekt hinaus wurde die Verwendung von Mutationstests durch die Entwicklung eines Werkzeugs zur Äquivalenzerkennung und Testfallgenerierung verbessert. Eine entsprechende Publikation wurde eingereich und angenommen.
Im Jahr 2020 evaluierten wir Ansätze und Techniken zur Erkennung von externen Wettlaufsituationen. Während bei klassischen Wettlaufsituationen mehrere Aktivitätsfäden eines Programms nicht richtig miteinander arbeiten, treten externe Wettlaufsituationen bei der Interaktion der Software mit anderen, unabhängigen und unbekannten Komponenten auf. Das können andere gleichzeitig laufende Programme sein, das Betriebssystem oder sogar Code eines böswilligen Angreifers, der gezielt mit der analysierten Software interferiert.
Im Jahr 2021 wurde ein Verfahren entwickelt, um statisch Wettlaufsituationen bei der Verwendung von externen Ressourcen zu erkennen. Ein häufiges Muster ist, dass Programme die Eigenschaften von Dateien abrufen und später auf Grund der vorherigen Überprüfungen auf die Dateien erneut zugreifen. Ändert sich der Zustand der Datei in der Zwischenzeit, kann eine Vielzahl von Problemen auftreten (time-of-check to time-of-use). Neben unerwartetem Verhalten können jedoch auch Angreifer durch geeignetes Anpassen der Datei, gezielt Fehlverhalten auslösen oder das System kompromittieren. Mit dem entworfenen Verfahren sollen solche Problemstellen in einer Software automatisch erkannt 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.

Im Jahr 2018 schlossen wir die im Vorjahr begonnen Arbeiten an einer Studie zur Effizienz von Graphstrukturen auf der GPU ab und haben weitere Optimierungen an ParCAn vorgenommen. Um die Leistungsfähigkeit unseres Frameworks zu untersuchen, haben wir es in das LLVM-Übersetzersystem integriert. Umfangreiche Vergleichsmessungen zeigten, dass wir mit ParCAn den LLVM-Übersetzungsprozess um bis zu 40% beschleunigen konnten. Die zugehörige Publikation wurde auf einer Fachkonferenz (28th International Conference on Compiler Construction) als Bestes Papier
ausgezeichnet.
Im Jahr 2019 wurde ParCAn an das veränderte Ausführungsmodell neuer NVIDIA GPU-Architekturen angepasst. Mit Einführung der Volta-Architektur können Aktivitäten unabhängig Fortschritt erzielen. Jede Aktivität besitzt seinen eigenen Befehlszähler und Aufrufstapel. Vorher teilten sich Gruppen von Aktivitäten (Warps), den gleichen Befehlszähler und Aufrufstapel. Aktivitäten in einem Warp führten entweder die selbe Anweisung aus oder waren inaktiv (engl.: lock-step execution). Da jetzt Aktivitäten unabhängig voneinander Fortschritt erzielen können, besteht jetzt die Gefahr von Nebenläufigkeitsfehlern innerhalb von Warps.

Der Programmcode von ParCAn wurde nach Programmstellen durchsucht, die durch das geänderte Ausführungsmodell zu Nebenläufigkeitsfehlern führen könnten. Die Anwendung wurde entsprechend angepasst. Somit lässt sich ParCAn auch auf den neusten NVIDIA Architekturen korrekt ausführen.
Im Jahr 2020 wurde das Forschungsprojekt erfolgreich beendet. Es konnte gezeigt werden, dass durch die Parallelisierung der besonders kostenintensiven Datenflussanalysen die Übersetzungszeit in unserer Testumgebung um bis zu 31% reduziert werden kann.  Das Forschungsprojekt zeigt somit erfolgreich einen Weg hin zum parallelisierten Übersetzer auf, der den Anforderungen heutiger Softwareprojekte besser entspricht. Die Wichtigkeit dieses Forschungsthema wurde 2019 durch einen „Best Paper Award“ auf der renommierten Fachkonferenz „Compiler Construction“ unterstrichen, siehe CC-Literaturangabe.

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 Programmierung

Eine 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 Programmanalyse

Um 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.

Unser erster Ansatz basiert darauf, die Probleme der Programmanalyse durch verbesserte Algorithmen zu lösen. Ein wichtiges Hilfsmittel ist dabei eine verzögerte Analyse, bei der ein Programmteil erst dann analysiert wird, wenn die zugehörigen Analyseergebnisse benötigt werden. Die Analyse soll auch inkrementell ablaufen, d.h. bei kleinen Änderungen im Programm-Code soll nur möglichst wenig des Programms neu analysiert werden. Dazu zerlegen wir ein Programm rekursiv in Teile und berechnen anschließend, welche Auswirkungen und Effekte diese Teile während einer Ausführung des Programms haben; diese Auswirkungen und Effekte speichern wir zusammenfassend in symbolischen Beschreibungen, die dann dazu verwendet werden, um die Fehler beim Zusammenspiel der zugehörigen Teile des Programms zu finden, um die Auswirkungen von größeren Teilen des Programms zu beschreiben und um bei Änderung eines Bestandteils des Programms nicht das komplette Programm neu analysieren zu müssen, sondern stattdessen die symbolischen Beschreibungen aller unveränderten Programmteile wieder zu verwenden.
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.

Im Jahr 2014 haben wir unser Werkzeug zur interaktiven Programmanalyse weiterentwickelt, um größere Code-Bestände zu analysieren und die Analyseergebnisse für spätere Verwendung aufzubewahren.  Dadurch wird auch Code präzise analysierbar, der (vorab analysierte) größere Bibliotheken benutzt.
Unser zweiter Ansatz basiert darauf, die Programmanalyse selbst zu parallelisieren und dadurch auf interaktive Geschwindigkeit zu beschleunigen.

Im Jahr 2013 haben wir begonnen, grundlegende Übersetzeranalysen in eine datenparallele Darstellung zu bringen. Dazu ist ein Rahmenprogramm für Prädikatspropagation in der Entwicklung. Diese datenparallelen Algorithmen sind dann einfach auf viele verschiedene Multi-Core Architekturen und GPUs portier

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.
SYFEX wurde im Jahr 2015 verfeinert und auf Code-Teilstücke aus Archiven von verschiedenen Software-Projekten angewendet. Der Schwerpunkt im Jahr 2016 lag auf einer Untersuchung, inwieweit SYFEX zum semantischen Vergleich von Abgaben eines Programmierwettbewerbs geeignet ist. In den Jahren 2017 und 2018 wurde SYFEX optimiert. Des Weiteren wurde mit der Erstellung eines Datensatzes semantisch ähnlicher Methoden aus quelloffenen Software-Archiven begonnen, der im Jahr 2019 veröffentlicht wurde.Verfahren zur symbolischen Ausführung beruhen auf Algorithmen zur Erfüllbarkeitsprüfung von logisch-mathematischen Ausdrücken, um zulässige Ausführungspfade in einem Programm zu bestimmen. Oftmals beanspruchen diese Algorithmen einen großen Teil der aufgewendeten Rechenzeit. Um diese Erfüllbarkeitsprüfung zu beschleunigen, wurde in den Jahren 2019 und 2020 mit einer Technik experimentiert, um komplizierte Ausdrücke durch einfachere Ausdrücke mit gleicher Bedeutung zu ersetzen. Hierbei werden die einfacheren Ausdrücke durch ein Verfahren zur Programmsynthese aufgedeckt. Im Jahr 2020 wurde diese Programmsynthese um ein neuartiges Verfahren ergänzt, das für eine bestimmte Menge an Operationen bereits vorab ermitteln kann, ob sich damit ein Ausdruck mit gleicher Bedeutung wie der kompliziertere Quellausdruck bilden lässt. Unsere im Jahr 2021 erschienene wissenschaftliche Publikation beschreibt dieses Verfahren und zeigt, dass durch dessen Einsatz die Laufzeit von gängigen Programmsynthetisierern im Mittel um 33% verringert werden kann. Ebenfalls im Jahr 2021 wurde das Verfahren auf weitere Klassen von Programmsyntheseproblemen erweitert. Im Jahr 2022 wurden diese Erweiterungen umfangreich evaluiert. Diese Evaluation zeigte, dass die Erweiterungen zu einer vergleichbaren Beschleunigung gängiger Programmsyntheseverfahren auf einer größeren Klasse von Syntheseproblemen führen. Die Arbeiten an Unlösbarkeitsdetektoren für Bitvektor-Programmsynthesen wurden 2023 fortgesetzt, umfassend ausgearbeitet und endeten in einer Dissertation.

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]
 ......}
 ...}
 }
 JaMP implementiert im Moment die Funktionalität von OpenMP 2.0 und Teile der Spezifikation 3.0 (z.B. die collapse clause). Die aktuelle JaMP Version erzeugt reinen Java Code und ist auf jeder JVM (die Java 1.5+ unterstützt) lauffähig. Die neueste Version kann sogar CUDA fähige Hardware verwenden um Schleifen auszuführen, wenn der Schleifenrumpf eine Transformation nach CUDA möglich macht. Ist die Transformation nicht möglich, wird nebenläufiger Code für gängige Multicore Prozessoren erzeugt. JaMP unterstütz auch die gleichzeitige Nutzung von mehreren Maschinen und Acceleratoren. Dieses wurde durch die Entwicklung von zwei Abstraktionsbibliotheken ermöglicht. Die untere Abstraktionsschicht bietet abstrakte Recheneinheiten, die von den eigentlichen Berechnungseinheiten wie CPUs und GPUs und ihrem Ort in einem Rechnerbündel abstrahieren. Eine weitere Abstraktionsschicht baut auf dieser Schicht auf und bietet Operationen um partitionierte und replizierte Arrays zu verwalten. Ein partitioniertes Array wird dabei automatisch über die abstrakten Berechnungseinheiten verteilt, wobei die Geschwindigkeiten der einzelnen Berechnungseinheiten berücksichtigt werden. Welcher abstrakte Arraytyp für ein Array in einem Java-Programm konkret eingesetzt wird, wird vom JaMP-übersetzer bestimmt, der erweitert wurde um ein Programm entsprechend zu analysieren.

Im Jahr 2010 wurde die JaMP-Umgebung erweitert, so dass die gleichzeitige Nutzung von mehreren Maschinen und Acceleratoren unterst ̈utzt wird. Dieses wurde durch die Entwicklung von zwei Abstraktionsbibliotheken erreicht. Die untere Schicht bietet abstrakte Recheneinheiten, die von den eigentlichen Berechnungseinheiten wie CPUs und GPUs und ihrem Ort in einem Rechnerb ̈undel abstrahieren. Die darauf aufbauende Schicht bietet partitionierte und replizierte Arrays. Ein partitioniertes Array wird dabei automatisch ̈uber die abstrakten Berechnungseinheiten verteilt, wobei die Geschwindigkeiten der einzelnen Berechnungseinheiten zwecks fairer Verteilung ber ̈ucksichtigt werden. Welcher abstrakte Array-Typ f ̈ur ein Array eines Java-Programms konkret eingesetzt wird, entscheidet der JaMP- ̈Ubersetzer mit Hilfe einer Code-Analyse.
Im Jahr 2012 wurde die JaMP-Umgebung erweitert, so dass Schleifen, die Java-Objekte verwenden, ebenfalls auf Rechnerbündeln ausführbar sind. Dabei werden zwei Klassen von Objekten unterschieden. Normale Shared-Objekte werden auf allen Berechnungseinheiten repliziert. Arrays, die Java als Objekte ansieht, können repliziert oder über die Berechnungseinheiten partitioniert werden. Dies ist unabhängig davon, ob es sich um ein Array von Objekten oder primitiven Datentypen handelt. Um die Laufzeit zu verkürzen, wurde mit der Java-Semantik gebrochen und die verzeigerte Objekt-Struktur des Programms wird nun für die Rechnerbündel auf eine flache Struktur abgebildet.
Im Jahr 2013 haben wir untersucht, wie man die Verwendung von Java-Objekten in parallelem OpenMP-Code optimieren kann. Es hat sich gezeigt, dass wir den Sprachumfang leicht einschränken müssen, indem wir Vererbung bei Objekten verbieten, die im parallelen Code eingesetzt werden. Das stellt sicher, dass zur Laufzeit keine anderen Typen als zur Übersetzungszeit vorliegen. Wir benutzen diese Eigenschaft, um Objekte in Arrays auf direkte Weise einbetten zu können. Dadurch wurde die Kommunikation mit den Recheneinheiten der GPU enorm beschleunigt und auch die Laufzeit auf den Berechnungseinheiten wurde leicht gesenkt.
Im Jahr 2014 wurde eine JaMP-Version für Android 4.0 entwickelt, die bisher nur das SIMD-Konstrukt von OpenMP unterstützt.
Im Jahr 2015 wurde das Task-Konzept (OpenMP 3.0) in JaMP integriert. Dadurch lassen .sich rekursive Algorithmen mit JaMP parallelisieren.

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.

Dieses im Rahmen der INI.FAU-Kooperation durchgeführte Projekt analysiert die Integration von Fahrzeugfunktionen auf Steuergeräte und entwickelt modellgetriebene Unterstützungsmöglichkeiten. Die gewonnenen Erkenntnisse werden exemplarisch anhand der Integration aller Komponenten eines Fahrdynamikregelsystems auf einem AUTOSAR-Steuergerät überprüft werden. In der Automobilindustrie ist es schon lange üblich, Fahrzeugfunktionen auf hohem Abstraktionsniveau modellbasiert zu entwickeln. Um frühzeitig Fehleinschätzungen bezüglich Laufzeit- und Ressourcenbedarf auszuschließen, ist es nötig, die entwickelte Software nicht nur zu simulieren, sondern auch auf der Zielhardware testen zu können. Aufgrund von Kosten- und Sicherheitsanforderungen ist die Integration auf ein Steuergerät aber sehr zeitaufwändig und erfordert Expertenwissen, das einem Funktionsentwickler normalerweise nicht zur Verfügung steht. AUTOSAR (AUTomotive Open System ARchitecture) etabliert sich als Standard für die Basissoftware auf Steuergeräten. Doch durch die Neuheit dieses Standards gibt es noch keine Verfahren und Werkzeuge, um die Integration von Funktionen auf einem Steuergerät zu unterstützen. Im Jahr 2008 wurden die Modellierungsmöglichkeiten in AUTOSAR in Bezug auf ihre Eignung bei Audi und auf mögliche Konflikte mit bestehenden Standards sowie mit bei Audi eingesetzten Technologien untersucht. Des Weiteren wurde die automatische Vervollständigung einer Reglerkomponente zu einer AUTOSAR-Softwarearchitektur prototypisch realisiert. Im Jahr 2009 wurde damit begonnen, die ermittelten Unterstützungsmöglichkeiten (automatische Konfiguration der Buskommunikation mit Hilfe einer Busdatenbank sowie automatisches Scheduling der auszuführenden Prozesse) mit Hilfe eines modellgetriebenen Ansatzes auf Basis des Eclipse Modeling Frameworks zu realisieren und in die Werkzeuglandschaft bei Audi zu integrieren. Durch die modellgetriebene Entwicklung wird eine leichte Anpassbarkeit des entstehenden Prototypen an sich verändernde Anforderungen erzielt. Im Jahr 2010 wurde die in einem AUTOSAR-Projekt zur Verfügung stehenden Informationen genutzt, um daraus automatisch sowohl die lokale Kommunikation zu konfigurieren, als auch diejenige, die Steuergerätegrenzen überschreitet. Ebenso konnten bereits vorhandene Abhängigkeitsspezifikationen mit Hilfe eines genetischen Algorithmus zur automatischen Erzeugung eines Taskscheduling verwendet werden, der die Kommunikationslatenzen zwischen kooperierenden Softwarebausteinen minimiert. Der bestehende Prototyp wurde um die erarbeiteten Verfahren erweitert.

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 2008 wurden folgende Ziele erreicht:

• Dokumentation und Veröffentlichung der Sourcen zur Verbreitung des Projekts,
• Implementierung einer angepassten graphischen Anzeige für DAGs,
• Begin der Erneuerung der graphischen Oberfläche und
• Erweiterung der Cluster-Verteilung zur Nutzung aller Kerne bei Bündeln aus Mehrkernrechnern.

Im Jahr 2009 wurden folgende Ziele angegangen:

• Beschleunigung der Suche mit einbettungs-bassierter Häufigkeit: Indem auf die zum Pruning benötigten Eigenschaften des Maximalen-Cliquen-Test intensiver eingegangen wurde, konnte gerade in dem für Anwendungen interessanten Bereich von niedrigen Häufigkeiten eine hohe Beschleunigung erreicht werden. Dies wird durch eine frühzeitige Erkennung im NP-vollständigen Test ermöglicht, die feststellt, ob ein überhaupt noch Fragment noch häufig vorhanden sein kann.
• Verbesserte Verteilung für Mehrkern-Cluster-Architekturen: Hier wurde und wird untersucht, wie sich die gemeinsame Positionierung verschiedener Threads im selben realen Speicher zur Beschleunigung der parallelen Suche ausnutzen lässt.

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.