Forschungsprojekte
Laufende Forschungsprojekte
 |
AnaCoRe – Analyse von Code-RepositoriesProjektleitung: |
 |
AutoCompTest – Automatisiertes Testen von ÜbersetzernProjektleitung: |
 |
ORKA – OpenMP für rekonfigurierbare heterogene ArchitekturenProjektleitung: |
 |
SoftWater – Software-WasserzeichenProjektleitung: |
 |
V&ViP – Verifikation und Validierung in der industriellen PraxisProjektleitung: |
Abgeschlossene Forschungsprojekte
AuDeRace - Automatische Erkennung von Wettlaufsituationen
 |
Automatische Erkennung von Wettlaufsituationen(Projekt aus Eigenmitteln) Projektleitung: Abstract: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. 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. Publikationen:
|
AutoParR - Automatische Code-Parallelisierung zur Laufzeit
Automatische Code-Parallelisierung zur Laufzeit(Projekt aus Eigenmitteln) Projektleitung: , Abstract: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 . Publikationen: |
DfD - Design for Diagnosability
 |
Design for Diagnosability(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract: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. Vor dem erfolgreichen Projektabschluss im Juli 2016 konnten noch eine Reihe wesentlicher Beiträge geleistet werden:
Obwohl die Förderung im Jahr 2016 auslief, haben wir im Jahr 2017 noch weitere Beiträge geleistet:
Auch im Jahr 2018 haben wir noch weitere Beiträge im Forschungsprojekt geleistet:
Publikationen: |
EAAFLS - Entwicklung adaptiver Algorithmen in funkbasierten Lokalisierungssystemen
 |
Entwicklung adaptiver Algorithmen in funkbasierten Lokalisierungssystemen(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract:
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. 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. 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.
Publikationen: |
ErLaDeF - Embedded Realtime Language Development Framework
|
Embedded Realtime Language Development Framework(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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. 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. 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. 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. Publikationen: |
ESADEPS - Effiziente Software-Architekturen für verteilte Ereignisverarbeitungssysteme
 |
Effiziente Software-Architekturen für verteilte Ereignisverarbeitungssysteme(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract:
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. Publikationen: |
GIFzuMINTS - Grundlagen der Informatik als Fundament eines zukunftsorientierten MINT-Studiums
 |
Grundlagen der Informatik als Fundament eines zukunftsorientierten MINT-Studiums(Drittmittelfinanzierte Einzelförderung) Projektleitung: , , Abstract: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. Publikationen: |
GraTra - Graphen und Graphtransformationen
 |
Graphen und Graphtransformationen(Projekt aus Eigenmitteln) Projektstart: 01.10.2004 Abstract:
Graphen werden an vielen Stellen als intuitives Hilfsmittel zur Verdeutlichung komplizierter Sachverhalte verwendet. Außerhalb der Informatik trifft dies z.B. auf die Chemie zu, wo Moleküle graphisch modelliert werden. Innerhalb der Informatik werden beispielsweise Daten- bzw. Kontrollflussdiagramme, Entity-Relationship-Diagramme oder Petri-Netze zur Visualisierung sowohl von Software- als auch von Hardware-Architekturen verwendet. Graphgrammatiken und Graphtransformationen kombinieren Ideen aus den Bereichen Graphentheorie, Algebra, Logik und Kategorientheorie, um Veränderungen an Graphen formal zu beschreiben. Die Kategorientheorie ist ein attraktives Hilfsmittel, äußerst unterschiedliche Strukturen in einer einheitlichen Weise zu beschreiben, z.B. die unterschiedlichen Modelle für asynchrone Prozesse: Petri-Netze basieren auf gewöhnlichen markierten Graphen, Statecharts verwenden hierarchische Graphen, die parallele logische Programmierung kann mit Hilfe sogenannter Dschungel graphentheoretisch interpretiert werden, und die Aktorsysteme lassen sich als Graphen darstellen, deren Markierungsalphabet eine Menge von Termgraphen ist. In letzter Zeit haben wir uns auf einen theoretischen Aspekt konzentriert. Unsere Arbeiten zu den Graphtransformationen basieren auf Konzepten der Kategorientheorie. Der sogenannte Doppelpushout-Ansatz stellt eine Produktion durch zwei Morphismen dar, die an einem gemeinsamen Interface-Graphen ansetzen. Das eine Pushout fägt die linke Seite der Produktion in den Kontext ein, das andere die rechte Seite. Wenn wir einen Ableitungsschritt tatsächlich konstruieren wollen, müssen wir auf der linken Seite ein Pushout-Komplement finden, was als nachteilig empfunden wird. Raoult hat 1984 vorgeschlagen, die Graphersetzung durch ein einzelnes Pushout zu beschreiben; der Ansatz wurde dann von Loewe ausführlich diskutiert, wobei die Untersuchungen weitgehend auf injektive Morphismen beschränkt blieben. Unter dieser Voraussetzung sind die Ansätze äquivalent. Jedoch führen einige Anwendungen, z.B. die Termersetzung, zu nichtinjektiven Morphismen. Wir haben diese Fälle detailliert untersucht und konnten zeigen, dass sie auch in diesem Fall äquivalent sind, solange die Einbettung vernünftige Eigenschaften hat. Publikationen: |
Holoware - Kooperative Exploration und Analyse von Software in einer Virtual Reality / Augmented Reality Appliance
 |
Kooperative Exploration und Analyse von Software in einer Virtual/Augmented Reality Appliance(Drittmittelfinanzierte Gruppenförderung – Teilprojekt) Titel des Gesamtprojektes: Kooperative Exploration und Analyse von Software in einer Virtual/Augmented Reality Appliance Abstract: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:
Im Jahr 2019 konnten weitere Verbesserungen erreicht werden:
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. Publikationen:
|
InCA - Inkrementelle Code-Analyse
 |
Inkrementelle Code-Analyse(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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. 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. Publikationen: |
InThreaT - Inter-Thread Testing
 |
Inter-Thread Testing(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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. Publikationen: |
IWKMMASWEP - Integrierte Werkzeug-Kette zur metamodellbasierten Modellierung und Ausführung von Software-Entwicklungsprozessen
Integrierte Werkzeug-Kette zur metamodellbasierten Modellierung und Ausführung von Software-Entwicklungsprozessen(Drittmittelfinanzierte Einzelförderung) Projektleitung: , Abstract: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). Publikationen: |
Jackal - Cluster and Grid computing made easy
 |
Cluster and Grid computing made easy(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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. Publikationen: |
Java/OpenMP
 |
OpenMP/Java(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract: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: 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. Publikationen: |
JavaParty
 |
JavaParty(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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. 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: Publikationen: |
LBMMC - Übersetzerunterstützte Parallelisierung für Mehrkern-Architekturen
 |
Übersetzerunterstützte Parallelisierung für Mehrkern-Architekturen(Projekt aus Eigenmitteln) Projektleitung: Abstract: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 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. Publikationen: |
LOK - Funkortung
 |
Funkortung(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract: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. Publikationen: |
MDCC - Modellgetriebene Komponentenkomposition
 |
Modellgetriebene Komponentenkomposition(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract: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. Publikationen: |
ParCAn - Parallele Code-Analyse auf einer GPU
 |
Parallele Code-Analyse auf einer GPU(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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 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. 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. Publikationen:
|
ParSeMiS - die Parallele und Sequenzielle Mining Suite
 |
ParSeMiS - die Parallele und Sequenzielle Graph Mining Suite(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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. Aufbauend auf den Ergebnissen des Projekts ParMol2 wurden 2006/2007 folgende Ziele erreicht:
Im Jahr 2008 wurden folgende Ziele erreicht:
Im Jahr 2009 wurden folgende Ziele angegangen:
Im Jahr 2010 wurden die verteilten Stack-Implementierungen auch für andere Algorithmen und Daten getestet. Publikationen: |
| PARSEMIS auf Github |
PATESIA - Parallelisierungstechniken für eingebettete Systeme in der Automatisierungstechnik
 |
Parallelisierungstechniken für eingebettete Systeme in der Automatisierungstechnik(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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). Publikationen: |
RuNN - Rekurrente Neuronale Netze (RNNs) zur echtzeitnahen Bestimmung nichtlinearer Bewegungsmodelle
 |
Rekurrente Neuronale Netze (RNNs) zur echtzeitnahen Bestimmung nichtlinearer Bewegungsmodelle(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract: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 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. Publikationen:
|
Softwareleitstand
 |
Softwareleitstand(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract:
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: Publikationen: |
Tapir
 |
Tapir(Projekt aus Eigenmitteln) Projektleitung: Abstract:
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: 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. Publikationen: |
WEMUCS - Methoden und Werkzeuge zur iterativen Entwicklung und Optimierung von Software für eingebettete Multicore-Systeme
 |
Methoden und Werkzeuge zur iterativen Entwicklung und Optimierung von Software für eingebettete Multicore-Systeme(Drittmittelfinanzierte Einzelförderung) Projektleitung: Abstract:
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]. Publikationen: |
