Themenbereich Echtzeitanalyse

Am Institut wurde eine neue Methode zur Analyse von Echtzeitsystemen entwickelt. Das neue Verfahren erlaubt eine elegantere Modellierung dieser Systeme. Die Analyse wurde prototypisch mit einem Computeralgebra-System (CAS) implementiert. In dieser Masterarbeit soll untersucht werden wie die Implementierung bezüglich der Rechenzeit effizienter gestaltet werden kann. Dazu sollen Parallelisierungen des CAS und bereits vorhandene Compiler genutzt werden. Ggf. ist zu untersuchen ob auch auf GPUs gerechnet werden kann. Zusätzlich kann das neue Verfahren in MATLAB implementiert werden. Die unterschiedlichen Umsetzungen sind dann bezüglich ihres Laufzeitverhaltens zu vergleichen.

Um bei eingebetteten Echtzeitsystemen Energie zu sparen, probiert man unter anderem, die Prozessorleistung herabzusetzen. Damit das System noch funktioniert, müssen bestimmte Anforderungen weiterhin gültig sein. Bei Echtzeitsystemen handelt es sich hierbei in erster Linie um die fristgerechte Abarbeitung von Teilaufgaben. Für einen ideellen Prozessor bestimmte Ausführungszeiten werden mit vorgegebenen Zeitschranken verglichen und damit die Echtzeitfähigkeit des Geräts geprüft. Eine Methodik, diesen Test möglichst schnell durchzuführen und Garantien abgeben zu können, sind Ereignisströme. Aus ihnen generiert man eine Rechenzeitanforderungsfunktion, um die benötigte Rechenzeit nach oben abzuschätzen und diese mit der tatsächlich verfügbaren zu vergleichen. Aufgabe dieser Arbeit ist es, in diesen Vergleich eine Optimierung einzubauen, die die einzelnen Ausführungszeiten maximiert und die Fristen optimiert. Aufgrund der Struktur dieses Problems eignet sich hierfür eine lineare Optimierung. Sicher ist dies nicht der erste Ansatz, dieses Problem anzugehen und so ist es Teil der Aufgabenstellung, bekannte Arbeiten zu studieren und die eigene Optimierung mit den Ergebnissen der bekannten Arbeiten zu vergleichen.

Um die Echtzeitfähigkeit eines Systems gewährleisten zu können, müssen alle zu bearbeitenden Tasks innerhalb ihrer Fristen durch den Prozessor ausgeführt werden. Zu diesem Zweck wird im Wesentlichen die maximale Antwortzeit (WCRT) benötigt. Die WCRT eines Tasks ist sowohl von den Taskeigenschaften wie die Berechnungsdauer, die Periode und die Frist, als auch vom dem genutztem Schedulingsverfahren abhängig. Für die Bestimmung der WCRT einer Taskmenge, welche offline priorisiert wurde, existieren  bereits mehrere Methoden. Allerdings ist das Problem der Bestimmung der WCRT einer online priorisierte Taskmenge, wie beim Schedulingsverfahren Earliest Deadline First (EDF) noch nicht vollständig gelöst.

Im Rahmen der Masterarbeit soll hierzu eine Analyse entwickelt und implementiert werden, welche die WCRT einer EDF-geplanten Taskmenge bestimmt. Die Konfiguration der Ankunftsmuster der Tasks, welches die maximale Antwortzeit liefert, spielt hierfür eine entscheidende Rolle.

In einer Motorsteuerung gibt es Aufgaben (Tasks) dessen Aufrufhäufigkeit, Berechnungsdauer und Zeitfristen von der Motordrehzahl abhängt. Diese Tasks und damit die Motorsteuerung als ganzes stellt deswegen eine große Herausforderung bezüglich seiner Echtzeitanalyse dar. Im Institut für Eingebettete System wurden mehrere Echtzeitanalysen [Feld et al.] für solche ratenabhängigen Tasks entwickelt.

Um die verschiedenen Analysen zu vergleichen soll daher in einer Bachelorarbeit ein Fallbeispiel (case-study) konstruiert werden, welches möglichst realistisch eine Motorsteuerung darstellt. Dabei müssen lediglich die für eine Echtzeitanalyse notwendige (also das Zeitverhalten beschreibende) Parameter generiert werden.

Der Umfang der Arbeit kann auf eine Projektarbeit angepasst werden.

Um ein System analytisch auf seine Echtzeitfähigkeit zu untersuchen werden im wesentlichen drei Parameter benötigt: die Berechnungsdauern (Worst Case Execution Times), die Perioden und die Fristen der einzelnen Tasks. Bei Motorsteuergeräten variieren diese Parameter dynamisch in Abhängigkeit der Motordrehzahl.

Chronsim ist ein Simulationstool mit dem man das Zeitverhalten eines eingebetteten Systems simulieren kann. Im rahmen einer Masterarbeit soll ein Motorsteuergerät mit ChronSim simuliert werden. Dabei sollen die Auswirkungen der variierenden Parameter in Abhängigkeit der Motordrehzahl untersucht werden.

Deutsch

Die Echtzeitanalyse-Gruppe des Instituts für eingebettete Systeme/Echtzeitsysteme der Universität Ulm hat eine neue Echtzeitanalysemethode, die Heaviside Real-Time Analyse (HeRTA), entwickelt. Angepasst an diese Methode wurde Echtzeit-Framework in Mathematica implementiert, welches nun kontinuierlich weiterentwickelt wird. Da die entwickelte Methodik eine Beschreibung von Ereignissen auf eine sehr allgemeine Art erlaubt, hat sie das Potenzial eine allgemeinere Darstellung der meisten Echtzeitereignismodelle darzustellen. Der nächste Schritt in der Entwicklung des Echtzeit-Frameworks ist es, das Framework mit Ereignissequenzen zu testen, welche bestimmte beobachtbare Eigenschaften aufweisen.

Ziel dieser Arbeit ist es daher eine Task Set Generator zu implementieren, der in der Lage Task Set mit verschiedensten Eigenschaften zu generieren. Dabei soll es nach möglich sein beliebig komplexe, wahlweise ungültige Ereignissequenzen zu produzieren. Weiterhin soll muss der Generator alle Schritte in einer Form zu dokumentieren, die es möglich macht, reproduzierbare Ergebnisse zu erzeugen und diese wissenschaftlich zu dokumentieren. Da das Framework in Mathematica implementiert ist, ist bevorzugt auch Mathematica für die Implementierung des Generators zu verwenden. Allerdings ist auch jede andere Programmiersprache gestattet, welche eine für das Framework nutzbare Ausgabe oder eine Wolfram Testdatei (.wlt) erzeugt.

English

The real-time researching group of the institute for embedded systems/real-time systems at the Ulm University developed a new real-time analysis method, the Heaviside Real-Time Analysis (HeRTA). This method has been implemented within a real-time framework, which is continuously developed by the research group. As this real-time analysis method provides a very general way to describe real-time task sets, it contains the potential to depict most of the know real-time event models. The next step within the development of this real-time framework is, to let it compute an observable various amount of task sets with certain properties. The goal of this project is the implementation of such a generator, which is able to handle multiple input parameter and produce feasible as well as purposely unfeasible task sets. Also, for every generated task set an automatically generated documentation has to be part of the output to document all parameters and the generated task set. As the HeRTA framework is implemented in Mathematica, the Wolfram language would be the preferred implementation technology. Other languages that are able to produce within the framework useable task sets or which generate Wolfram test files (.wlt) can also be used.

Ansprechpartner: Felix Heinzmann

Deutsch 

Das Computer Algebra System Mathematica bietet eine Vielzahl von Anwendungsmöglichkeiten. Neben der Erstellung von mächtigen mathematisch fundierten Bibliotheken ist es möglich Notizbücher zu erstellen und sogar ausführbaren Code in diese Notizbücher einzubetten. Bei der Entwicklung einer Echtzeitbibliothek basierend auf dem von der Echtzeitanalysegruppe erstellten Ereignismodell kam die Idee auf sich dies Eigenschaften von Mathematica zunutze zu machen, um wissenschaftliche Arbeiten direkt in Mathematica implementieren zu können. Zu diesem Zweck wurden FrontEnd-Funktionen implementiert, welche das Verständnis des Lesers fördern sollen. Der Export erstellter FrontEnd-Ausdrücke ist allerdings nicht einfach möglich.

Ziel dieser Arbeit soll es sein einen reibungslosen Export wissenschaftlicher Texte inklusive selbst erstellter Operatoren in LaTeX zu ermöglich und die notwendigen Schritte so zu dokumentieren, dass sie anschließend beliebig angewendet werden können.

English

The computer algebra system offers a various range of possible applications. Aside the mighty mathematically sound library, Mathematica allows the creation of so-called notebooks. These notebooks are not only able to display and present code, but also act as a live-script editor for the embedded code. As result the real-time analysis group of the institute for embedded systems/ real-time systems developed a new event model and implemented a real-time library according to this model. Next to the mathematically functions the implemented library also contains self-defined operators.

The next step within the work of the real-time group would be to enable to write scientific papers as Mathematica notebooks and export those as LaTeX-code.

The goal of this work would be to enable the export of Mathematica-code containing self-defined operators to LaTeX and document all needed work in a way, that it can be reproduced.

Ansprechpartner: Felix Heinzmann