Design Automation of Embedded Systems

Automatische Suchraumzerlegung bei der Entwurfsraumexploration eingebetteter Mehr- und Vielkernsysteme

Projekt- / Bachelor- / Masterarbeit

Thema

Zukünftige Mehr- und Vielkernplattformen werden es erlauben, eine Vielzahl von Anwendungen parallel auszuführen. Um die Einbettung einer Anwendung auf eine Architektur zu bestimmen, muss das NP-vollständige Systemsynthese-Problem (bestehend aus Allokation, Bindung, Routing und Ablaufplanung) gelöst werden. Durch die hohe Anzahl an Ressourcen in Mehr- und Vielkernarchitekturen ergibt sich für jede Anwendung eine Vielzahl an Einbettungsmöglichkeiten, die sich in Qualitätsmerkmalen wie Durchsatz, Zuverlässigkeit oder Sicherheit der Anwendungsausführung unterscheiden.
Aus diesem Grund sollen bereits zur Entwurfszeit Einbettungen durch eine sogenannte Entwurfsraumexploration untersucht und im Hinblick auf Zielgrößen wie Energieverbrauch, Latenz, etc. optimiert werden. Zur Laufzeit kann dann eine geeignete Einbettung aus einer Menge Pareto-optimaler Implementierungen ausgewählt werden.

Ein Problem klassischer Ansätze zur Entwurfsraumexploration liegt in der Größe des Suchraums, die von der Anzahl der Tasks in der Anwendung sowie der Größe der Architektur abhängt.
Weiterhin führen Symmetrien in der Architektur dazu, dass große Teile des Suchraums nur redundante Lösungen enthalten.

Ziele

In dieser Arbeit sollen daher Verfahren zur Verkleinerung des Suchraums für bestehende Entwurfsraumexplorationen (wie z.B. [1], [2]) entwickelt werden.

Der Suchraum des Optimierungsproblems soll dabei auf Architektur- und Anwendungsebene zerlegt werden, um zuerst in weniger komplexen Subsystemen nach Lösungen suchen zu können. Diese Lösungen sollen dann als Ausgangspunkt für weiterführende Optimierung auf iterativ vergrößerten Subsystemen (bis hin zum Gesamtsystem) genutzt werden.

Hierbei können verschiedene Strategien zur Suchraumzerlegung untersucht werden, z.B. mit Hilfe von Techniken aus Bereichen des Machine Learnings oder der Nachrichtentechnik.


Die Arbeit soll dabei untersuchen, inwiefern sich die Entwurfsraumexploration durch Suchraumzerlegung beschleunigen sowie in Bezug auf Optimierungsqualität verbessern lässt. Vor- und Nachteile der untersuchten Verfahren sollen experimentell analysiert werden.

Für die Implementierung verwenden wir das open-source Explorationsframework OpenDSE [3], sodass entwickelte Methoden auch weiterverwendet und evtl. veröffentlicht werden können.

Kontakt

Valentina Richthammer

Michael Glaß

 

Quellen

[1] Andreas Weichslgartner, Deepak Gangadharan, Stefan Wildermann, Michael Glaß, Jürgen Teich. DAARM: Design-Time Application Analysis and Run-Time Mapping for Predictable Execution in Many-Core Systems, 2014.

[2] Tobias Schwarzer, Andreas Weichslgartner, Michael Glaß, Stefan Wildermann, Peter Brand, Jürgen Teich. Symmetry-eliminating Design Space Exploration for Hybrid Application Mapping on Many-Core Architectures, 2018.

[2] OpenDSE, open-source Explorationsframework: https://github.com/felixreimann/opendse

Integration einer Answer-Set-Programming-basierten Entwurfsraumexploration in OpenDSE

Projekt- / Bachelor- / Masterarbeit

Thema

Zukünftige Mehr- und Vielkernplattformen werden es erlauben, eine Vielzahl von Anwendungen parallel auszuführen. Um die Einbettung einer Anwendung auf eine Architektur zu bestimmen, muss das NP-vollständige Systemsynthese-Problem (bestehend aus Allokation, Bindung, Routing und Ablaufplanung) gelöst werden. Durch die hohe Anzahl an Ressourcen in Mehr- und Vielkernarchitekturen ergibt sich für jede Anwendung eine Vielzahl an Einbettungsmöglichkeiten, die sich in Qualitätsmerkmalen wie Durchsatz, Zuverlässigkeit oder Sicherheit der Anwendungsausführung unterscheiden. Aus diesem Grund sollen bereits zur Entwurfszeit Einbettungen durch eine sogenannte Entwurfsraumexploration untersucht und im Hinblick auf Zielgrößen wie Energieverbrauch, Latenz, etc. optimiert werden. Zur Laufzeit kann dann eine geeignete Einbettung aus einer Menge Pareto-optimaler Implementierungen ausgewählt werden.

Ziele

Ziel der Arbeit ist die Integration eines auf Answer-Set-Programming basierenden Explorationsansatzes [1] in das open-source Explorationsframework OpenDSE [2], sowie der Vergleich mit weiteren aktuellen Ansätzen [3], [4].

Kontakt

Valentina Richthammer

Michael Glaß

 

Quellen

[1] Christian Haubelt, Kai Neubauer, Torsten Schaub, Philipp Wanko. Design Space Exploration with Answer Set Programming, 2018.

[2] OpenDSE, open-source Explorationsframework: https://github.com/felixreimann/opendse

[3] Andreas Weichslgartner, Deepak Gangadharan, Stefan Wildermann, Michael Glaß, Jürgen Teich. DAARM: Design-Time Application Analysis and Run-Time Mapping for Predictable Execution in Many-Core Systems, 2014.

[4] Tobias Schwarzer, Andreas Weichslgartner, Michael Glaß, Stefan Wildermann, Peter Brand, Jürgen Teich. Symmetry-eliminating Design Space Exploration for Hybrid Application Mapping on Many-Core Architectures, 2018.

Controller/Platform Co-Design

Event-Triggered Control

Masterarbeit

Das Institut für Eingebettete Systeme/Echtzeitsysteme beschäftigt sich unter anderem mit den Fragestellung der Einflussnahme von zeitlichen Einschränkungen auf das Systemverhalten von Reglern in verteilten Systemen.
Eine Regelstrategie, in der die zeitlichen Fristen und das Regelverhalten besonders stark ineinander greifen, ist die Ereignisgesteuerte Regelung (Event-Triggered Control).

Ereignisgesteuerte Regelungen versprechen eine effiziente Regelung bei stark reduziertem Rechenaufwand und geringem Verbrauch von Kommunikationsressourcen.
Dem gegenüber stehen eine nicht-periodische Abtastung und ein aufwändigerer Stabilitätsnachweis als bei konventionellen Reglern.

In der Masterarbeit soll mit Hilfe der Matlab Toolbox SimEvents solch ein Regelkreis modelliert und für einen am Institut entwickelten Prüfstand für Elektromotoren ausgelegt werden.
Dabei sollen die simulativen Erkenntnisse auf eine Zielplattform angewandt werden, sowie durch eine geeignete Hardwarebeschaltung eine flexible Ereignisgenerierung ermöglicht werden.

Nützliche Vorkenntnisse:

Kenntnisse in der Regelungstechnik, sowie Erfahrungen im Umgang mit Matlab/Simulink sind erwünscht.

Ansprechpartner:

Florian Hock

Integrierte Reglerplattform

Masterarbeit

In  Industrieanlagen  und  im  automotiven  Umfeld  werden  Regelstrecken zunehmend über Netzwerke und Bussysteme miteinander vernetzt. Diese Verteilung ermöglicht ressourcensparende Systeme und einen flexiblen Einsatz. Bei solchen verteilten Regelsystemen beein-
flussen sich Reglerfunktionalität und Hardwareplattform gegenseitig.


Die Funktionalität des Regelsystems gibt vor, in welchen Zeitintervallen Sollwertberechnungen durchgeführt werden und welche Sensor- und  Aktordaten  als  Nachrichten  verschickt  werden.  Die  Regelplattform beeinflusst die Reglerperformance, indem sich aus ihr Verzögerungen  ableiten,  die  zeitvariante  Totzeiten  im  Regelkreis  darstellen.
Um mit dieser gegenseitige Wechselwirkungen umzugehen, werden in zukünftigen Systemen die  Funktionalität  eines  Regelsystems  und die  verwendete  Regelplattform  in  einem  integrierten  Entwurf  entwickelt. Diese  Integration wird  besonders  im  automotiven  Umfeld  verlangt,  wo  durch  den  Kostendruck  eine  hohe  Auslastung  gefordert wird.


Ein  Ansatz  wäre  es,  aus  den  Kenntnissen  über  das  zu  regelnde  physikalische  System  und  den verwendeten Regelalgorithmen Aussagen über eine Reduktion der Rechenoperationen zu treffen. So wird beispielsweise  bei  der  modellprädiktiven  Regelung  zu  jedem  Abtastschritt  eine  Prädiktion  über  den  zu erwartenden Verlauf der Zustandsgrößen errechnet. Aus der Kenntnis des zu erwartenden Signalverlaufs können Eigenschaften des Zeitverhaltens der Plattformarchitektur abgeleitet werden. Ein Beispiel wäre die Reduktion  der  Stellwertberechnungen,  wenn  zu  erwarten  ist,  dass  sich  Systemzustände  nahe  des Stabilitätspunktes  befinden.  Weniger  Berechnungen  führen  zu  einer  reduzierten  Rechenzeitanforderung und somit zu einem effektiveren Systementwurf.


Im  Rahmen  der  Masterarbeit  soll  anhand  des  Beispielsystems  eines  Verladekrans  untersucht  werden, inwieweit aus der Zustandsprädiktion zeitliche Einschränkungen und Schmutzeffekte zugelassen werden können.  Diese  Erkenntnisse  sollen  dazu  verwendet  werden,  ein  neues  Anregungsmodell  der Berechnungen zu erstellen und dadurch Auswirkungen auf einen Plattformentwurf zu veranschaulichen.
Die Masterarbeit wird in Kooperation des Institutes für Mess-, Regel- und Mikrotechnik und des Institutes für Eingebettete Systeme/Echtzeitsysteme durchgeführt.
Voraussetzungen sind gute Kenntnisse der Regelungstechnik sowie Grundlagen der Echtzeitsysteme und der  Optimierung.  Alternativ  wird  der  Besuch  der  Vorlesung  „Methoden  der  Optimierung  und  optimalen Steuerung“ parallel zur Masterarbeit empfohlen.

Ansprechpartner:

Florian Hock

Kombination des Controller-Plattform Codesigns mit einem Kalmanfilter für verteilte Sensoren (Masterarbeit)

Es sind drei Möglichkeiten bekannt die asynchronität verteilter Sensoren in einer verteilten Anwendung der Regelungstechnik bei der Betrachtung der Stabilität der Regler zu betrachten: Synchronisation der Sensoren, Korrektur  der Sensorwerte durch ein Kalmanfilter  und Integration des Plattformverhaltens mittels Ereignisdichten aus dem Regler-/Plattform-Codesign  In dieser Masterarbeit sollen die drei Varianten im Hinblick auf Implementierungsaufwand und Qualität untersucht werden. Neben der getrennten Betrachtung aller drei Varianten liegt der Schwerpunkt der Arbeit auf der Kombination des Regler-/Plattform-Codesigns mit einer Lösung mit Kalmanfiltern. Die Frage, die mit der Arbeit beantwortet werden soll ist, ob eine Kombination zweier unterschiedlicher Verfahren zu kostengünstigeren Plattformen zur Realisierung derartiger Systeme führen kann. Die Arbeit soll modellbasiert durchgeführt werden und verschiedene Szenarien sollen mit Hilfe von Matlab/Simulink simuliert werden.

Nützliche Vorkenntnisse:

Nützlich, aber nicht zwingend notwendig, wären hierfür Vorkenntnisse aus dem Bereich der Nachrichtentechnik, HDL, Matlab/Simulink und C oder C++

Weiterführende Literatur:

 


Ansprechpartner:

Prof. Dr. Frank Slomka

Modellierung eines Fahrwerks (Masterarbeit)

In Zusammenarbeit soll mit einem bekannten Automobilzulieferer ein adaptives Fahrwerk modelliert werden. Ziel dieser Extern in einem Unternehmen durchzuführenden Arbeit ist es, ein Modell eines vorhandenen Fahrwerks als Regelstrecke zu modellieren und im Anschluss mit dem im Unternehmen bestehenden Reglern zu simulieren. Aus diesem Modell sind dann die notwendigen Parameter für eine Entwurfsstudie zum Regler-/Plattform-Codesign abzuleiten.

Nützliche Vorkenntnisse:

Nützlich, aber nicht zwingend notwendig, wären hierfür Vorkenntnisse aus dem Bereich der Nachrichtentechnik, Systemtheorie, Matlab/Simulink und C oder C++

Ansprechpartner:

Prof. Dr. Frank Slomka

Real-Time Analysis

Fallbeispiel Motorsteuerung

Bachelorarbeit / Projektarbeit

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.

Ansprechpartner: Timo Feld

Ereignisabhängigkeiten in verteilten Systemen

Masterarbeit

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 einigen Systemen können diese Parameter dynamisch durch äußere Einflüsse variieren. Dieses Verhalten tritt insbesondere bei Motorsteuergeräten auf, bei denen die Drehzahl die genannten Parameter beeinflusst. Zusätzlich zu der Abhängigkeit von einer Drehzahl, gibt es weitere Beziehungen zwischen den Tasks, die vorgeben, dass die jeweiligen Ereignisse nur in einem minimalen Abstand zueinander auftreten können.

Der Real-Time Calculus ist ein mathematisch fundiertes Modell zur Analyse und Synthese verteilter Echtzeitsysteme. Bei diesem Modell des Task-Graphen wird durch Ankunftskurven die Anregung des Systems beschrieben. Jede Task modifiziert diese und es verbleibt die ausgehende Ereignisdichte und die verbleibende Rechenzeitkapazität.

Im Rahmen der Masterarbeit soll eine Analyse entwickelt und implementiert werden, welche sowohl die Abhängigkeiten zur Drehzahl als auch die Abhängigkeiten zwischen den Tasks berücksichtigt. Diese Analyse soll auf den Real-Time Calculus aufbauen, so dass verteilte Systeme analysiert werden können.

Ansprechpartner: Timo Feld

Echtzeitanalyse für ratenabhängige Tasks

Masterarbeit

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 einigen Systemen können diese Parameter dynamisch durch äußere Einflüsse variieren. Dieses Verhalten tritt insbesondere bei Motorsteuergeräten auf, bei denen die Drehzahl die genannten Parameter beeinflusst. Im Institut wurde bereits eine Analyse für solche raten-abhängigen Tasks verwendet. Dabei wird allerdings von einem identischen Wert für die Beschleunigung und dem Abbremsen ausgegangen.

Ziel dieser Arbeit ist es, vorhandene Analysen so zu erweitern, dass unterschiedliche Werte für Beschleunigung und Bremsen angenommen werden können.

Ansprechpartner: Timo Feld

Echtzeitanalyse verteilter Systeme mit Berücksichtigung variabler Fristen

Masterarbeit

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 einigen Systemen können diese Parameter dynamisch durch äußere Einflüsse variieren. Dieses Verhalten tritt insbesondere bei Motorsteuergeräten auf, bei denen die Drehzahl die genannten Parameter beeinflusst.  [Pollex et al]

Der Real-Time-Calculus ist ein mathematisch fundiertes Modell zur Analyse und Synthese verteilter Echtzeitsysteme. Bei diesem Modell des Task-Graphen wird durch Ankunftskurven die Anregung des Systems beschrieben. Jede Task modifiziert diese und es verbleibt die ausgehende Ereignisdichte und die verbleibende Rechenzeitkapazität.

Im Institut für Eingebettete Systeme/Echtzeitsysteme wurden bereits aufbauend auf dem Real-Time Calculus Analysen für variable Parameter entwickelt. Bei diesen Analysen wird allerdings bei jeder Tasks von der minimalen Frist ausgegangen was die Analyse pessimistischer macht.

Ziel dieser Masterarbeit ist der Entwurf und die Implementierung einer neuen (oder die Erweiterung einer vorhandenen) Analyse für verteilte Systeme, welche variable Fristen berücksichtigt und die Genauigkeit verbessert.

Ansprechpartner: Timo Feld

Simulation eines Motorsteuergerätes mit ChronSim

Masterarbeit

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.

Ansprechpartner: Timo Feld

Implementierung und Vergleich einer Bibliothek zur min-plus und max-plus Algebra

Das Echtzeitkalkül ist ein Verfahren zur Echtzeitanalyse, welches maßgeblich Faltungs- und Entfaltungsoperationen in der min-plus und max-plus Algebra verwendet. Eine Implementation hierzu ist die RTC Toolbox. Es ist eine Bibliothek zu implementieren welche die RTC Toolbox ersetzen kann gemäß den Vorgaben aus der Veröffentlichung "An Algorithmic Toolbox for Network Calculus" von Anne Bouillard und Éric Thierry. Des Weiteren sollen die beiden Bibliotheken miteinander verglichen werden.

Ansprechpartner: Victor Pollex

Mathematischer Vergleich von Methoden der Antwortzeitanalyse und dem Echtzeitkalkül

Für die Echtzeitanalyse eines Systems existieren mehrere Methoden. Darunter befinden sich die Antwortzeitanalyse und das Echtzeitkalkül. Die Arbeiten in der Literatur zu diesen Analysemethoden befassen sich meist mit nur einer dieser Methoden. In den Arbeiten die sich mit beiden Methoden gemeinsam befassen werden diese meist empirisch miteinander verglichen. Daher sollen diese Methoden theoretisch / mathematisch verglichen werden. Die Abschlussarbeit beschränkt sich auf einzelne Aspekte dieser Methoden.

Ansprechpartner: Victor Pollex

Implementierung eines Echtzeitanalysepakets für Mathematica

In der Abschlussarbeit soll ein Paket für Mathematica implementiert werden. Das Packet soll dem Nutzer die Möglichkeit geben eine Echtzeitanalyse auf symbolischer Ebene durchführen zu können.

Ansprechpartner: Victor Pollex, Frank Slomka

Optimierung der Ausführungszeiten von eingebetteten Echtzeitsystemen mit Ereignisströmen

Masterarbeit

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.

Ansprechpartner:

Untersuchung des Laufzeitverhaltens effizienter Echtzeitanalysen mit Mathematik-Systemen

Masterarbeit

 

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.

Ansprechpartnern: Mohammadreza Sadeghi, Marco Philippi

Open Topics

The proposed topics offer several possibilities for a specific thesis. The actual assignment is individually defined by the student and his/her advisor and is based on the student's interests and previous knowledge as well as the necessary extend of the thesis. As long as they fit the spectrum of the institute, other topics are always welcome.

Real-Time Communication Systems

Echtzeitkommunikationsprotokoll für verteilte Regelungen

Masterarbeit

In dieser Masterarbeit soll eine Kommunikationshard- und ggf. Software für eine Echtzeitkommunikation entworfen werden. In der Bürokommunikation und bei Computernetzwerken ist das Protokoll TCP/IP und die physikalische Schnittstelle Ethernet Standard. In zunehmenden Maße sollen diese Technologien auch auf der Feldbus-Ebene in Fabriken und in Kraftfahrzeugen eingesetzt werden, um verteilte Regelungen zu ermöglichen bzw. Die Kosten für eine vernetzte Steuergeräte-Infrastruktur zu senken. In dieser Masterarbeit soll zunächst untersucht werden, wie das Echtzeitverhalten von Ethernet mittels moderner Kanalkodierungsverfahren echtzeitfähig gemacht werden kann. Im Anschluss ist eine entsprechende Hardware zu entwickeln und diese auf einem FPGA zu implementieren. Sind die eingeführten Methoden effektiv ist weiterhin zu untersuchen, ob diese auch bereits auf Protokollebene eingesetzt werden können, um kommerzielle Ethernetbausteine nutzen zu können.

Nützliche Vorkenntnisse:

Hilfreich, aber nicht zwingend erforderlich, sind Vorkenntnisse in den Grundlagen der Rechnernetze oder der Nachrichtentechnik. 

Ansprechpartner: 

Marcel Rieß, Marco Phillipi



Verbesserungen und Erweiterungen von Netzwerk-Simulatoren

Bachelorarbeit

Das Institut für Eingebettete Systeme/Echtzeitsysteme beschäftigt sich unter anderem mit der Fragestellung, wie Kommunikationsnetze echtzeitfähig realisiert werden können. Um verschiedene Ansätze zu erproben zu können, wird häufig auf Simulationen zurückgegriffen, da diese in einem frühen Stadium der Forschung Vorteile gegenüber aufwendigen Feldtests bieten.

Leider zeigen sich jedoch bei der Nutzung von Simulatoren verschiedene Defizite, die im Rahmen der folgenden Praktika beseitigt werden sollen:

  1. Auf dem Markt verfügbare Simulatoren für Netze liefern oft Routinen mit, mit denen gebräuchliche Systeme und weit verbreitete Standards (z.B. Ethernet, WLAN, usw.) simuliert werden können. Eigene Verfahren, etwa im Bereich des Medienzugriffs, lassen sich jedoch nur mit größerem Aufwand realisieren.

    Ziel des Praktikums ist es, eine Schnittstelle zu definieren, die das Einbauen eigener Verfahren nach dem Plugin-Prinzip ermöglicht.

  2. Die verfügbaren Simulationsplattformen bieten im Bereich der Eingabe von Simulationsszenarien Defizite. Insbesondere ist es beispielsweise in Fahrzeug-/Fahrzeug-Netz-Simulatoren bisher nicht üblich, eine Datenrepräsentation (eine Art Landkarte) als Eingabe zu verwenden, die sowohl Geländetopologien als auch Straßenzüge enthält. Diese Informationen wären dann an die Stellen des Simulators durchzureichen, die sie benötigen - etwa die Geländetopologie an die Funkkanal-Simulation und die Straßeninformation zusätzlich an das Bewegungsmodell.

    Ziel des Praktikums ist es, ein Eingabeformat zu definieren und zu implementieren, das es, idealerweise ergänzt um einen grafischen Editor, ermöglicht, eine umfassende Umgebungsbeschreibung (Topologie, Bebauung, Straßenkarte, usw.) in den Simulator zu geben, um so mit möglichst geringem Aufwand möglichst realitätsnah simulieren zu können.

Nützliche Vorkenntnisse:

Java und Grundlagenwissen im Bereich von Rechnernetzen oder in der Nachrichtentechnik sind von Vorteil.

Ansprechpartner:

Steffen Moser

Echtzeitkommunikation in Eingebetteten Systemen

Masterarbeit

Echtzeitkommunikation bedeutet, dass Nachrichten von einer Komponente zu einer weiteren Komponente übertragen werden, wobei von vorne herein feststeht, wie lange die Kommunikation maximal dauert. D.h. das Kommunikationssystem gibt harte Garantien bzgl. Latenz und Durchsatz. Weit verbreitete lokale Kommunikationsnetze wie Ethernet, Wireless LAN oder auch Weitverkehrsnetze wie das Internet geben solche Garantien nicht. Es gibt jedoch Anwendungen, bei denen solche harten Garantien notwendig sind, um technische Prozesse aufrecht erhalten zu können. Beispiele hierfür sind etwa steuergeräteübergreifende Regelungen im Automobil oder Leistungsregelungen in Stromnetzen. Diese Master-Arbeit beinhaltet die Grundlagen von Echtzeitkommunikation sowie den Aufbau von Komponenten eines Systems, in dem mit harten Zeitgarantien kommuniziert wird.

Ansprechpartner:

Steffen Moser

Quality of Service in Ad-hoc-Netzwerken

Masterarbeit

Mobile Ad-hoc-Netzwerke sind vermaschte drahtlose Kommunikationsnetze, zu denen sich einzelne Knoten spontan und unter Selbstkonfiguration zusammenfinden. Meist werden Datenpakete in solchen Netzen mit Hilfe von Multihop-Routing-Verfahren zugestellt, indem beispielsweise jeder Knoten Router-Funktionalitäten für die anderen Knoten übernehmen kann. Mögliche Einsatzgebiete sind Kommunikationssysteme, die ohne Infrastruktur (wie z.B. Mobilfunk-Basisstationen) auskommen müssen - wie etwa Netze für Helfer nach Naturkatastrophen oder für militärische Anwendungen. Ein weiteres Einsatzgebiet sind Fahrzeug-/Fahrzeug-Netze, sogenannte Vehicular Ad-hoc Networks (VANETs), die durch miteinander kommunizierende Fahrzeuge und mit Hilfe von Sensoren auf der Straße den Verkehr sicherer machen sollen.

Häufig wird zur Erforschung und Entwicklung solcher Ad-hoc-Netze auf vorhandene Technologien, wie etwa WLAN aufgesetzt. WLAN bietet aber zunächst keinerlei Quality-of-Service-Unterstützung an, d.h. zeitkritische Anwendungen bekommen etwa keine obere Schranke für die Zustellung einer Nachricht zugesichert. Das ist eine Eigenschaft des verwendeten Medienzugriffsverfahrens "Carrier Sense, Multiple Access with Collision Avoidance" (CSMA/CA).

Wir erforschen am Institut für Eingebettete Systeme/Echtzeitsysteme Möglichkeiten, solche Kommunikationssysteme echtzeitfähig zu realisieren. Im Rahmen dieser Arbeit sollen hierzu verschiedene neue Ansätze theoretisch analysiert und in Simulationen oder ggf. Feldtests praktisch erprobt werden.

Nützliche Vorkenntnisse:

Hilfreich sind gute Kenntnisse im Bereich der Rechnernetze bzw. des Ubiquitous Computing oder in den Grundlagen der Nachrichtentechnik. 

Ansprechpartner:

Steffen Moser

Verbesserung der Simulation der physikalischen Schicht von Kommunikationsnetzen

Masterarbeit

Für die Erforschung neuartiger komplexer Kommunikationsnetze ist der Einsatz von Simulatoren unverzichtbar geworden. Eine Simulation bietet in einem frühen Entwicklungsstadium zwei wesentliche Vorteile: Sie ist in der Regel zum einen kostengünstiger als ein vergleichbar großes reales Experiment. Zum anderen können in Simulationsumgebungen die Umweltparameter vorgegeben und systematisch untersucht werden, während man in realen Experimenten stets mit einer nicht beeinflussbaren und sich veränderbaren Größen zu kämpfen hat. Andererseits nähert eine Simulation ein reales Experiment nur dann gut an, wenn die Simulation entsprechend implementiert wurde. Genau hier gibt es oftmals Defizite, wenn etwa zu stark vereinfachte Annahmen über die Realität gemacht werden.

Für die Erforschung von Kommunikationsnetzen ist es insbesondere erforderlich, dass die physikalische Schicht, also die elektromagnetischen oder akustischen Signale, sowie der Kommunikationskanal, mit hinreichender Realitätsnähe simuliert werden.

Wir erforschen am Institut für Eingebettete Systeme/Echtzeitsysteme das Echtzeitverhalten in Ad-hoc-Netzen - sowohl funkbasiert als auch unter Wasser auf Akustikbasis. Im Rahmen dieser Arbeit soll ein vorhandenes strahlenoptisches Kanalmodell in Hinsicht auf Genauigkeit und Rechengeschwindigkeit, ggf. unter Hinzuzug von Hardware-Unterstützung, optimiert werden.

Nützliche Vorkenntnisse:

Hilfreich, aber nicht zwingend erforderlich, sind Vorkenntnisse in den Bereichen der Computergrafik (hier insbesondere im Bereich des Raytracing) und den Grundlagen der Nachrichtentechnik.

Ansprechpartner:

Steffen Moser

Fehlertolerante On-Chip-Kommunikation

Masterarbeit

Auf Grund der Tatsache, dass die Strukturgrößen in der Herstellung von Mikrochips immer kleiner werden, lassen sich nicht nur immer leistungsstärkere Prozessoren aufbauen. Vielmehr ergeben sich neuartige Anwendungen, wie beispielsweise die Integration kompletter Rechnersysteme auf einem Chip. Die Komponenten eines solchen System-on-a-Chip müssen dazu in der Lage sein, untereinander Nachrichten auszutauschen.

Wegen der Komplexität und der asynchronen Taktung der einzelnen Komponenten eines solchen Systems sind herkömmliche On-Chip-Busse nur bedingt als Kommunikationsstruktur geeignet. Stattdessen wird untersucht, inwiefern Technologien, die aus klassischen Rechnernetzen bekannt sind, für die On-Chip-Kommunikation verwendet werden können. Man spricht in diesem Zusammenhang auch von "Network-on-a-Chip" (NoC). Eine Technologie wären beispielsweise paketvermittelnde Netze, die mit einer geeigneten Switching- bzw. Routingstrategie die Nachrichten von der Quelle zur Senke leiten.

In diesem Zusammenhang ergeben sich interessante Fragestellungen, beispielsweise hinsichtlich der Fehlertoleranz und der Echtzeitfähigkeit.

Wir erforschen am Institut für Eingebettete Systeme fehlertolerante Echtzeitsysteme. Im Rahmen dieser Arbeit soll theoretisch und simulativ untersucht werden, inwiefern sich bestimmte Medienzugriffsverfahren und Routing-Strategien dazu eignen, Datenpakete in einem möglicherweise fehleranfälligen On-Chip-Netzwerk zu leiten. Eventuell wird der Aufbau einer Simulationsinfrastruktur notwendig sein. 

Nützliche Vorkenntnisse:

Hilfreich, aber keine zwingende Voraussetzung, sind gute Kenntnisse der Rechnernetze.

Ansprechpartner:

Steffen Moser

Echtzeitfähiges Ethernet

Masterarbeit

Ethernet nach IEEE 802.3 und seine Erweiterungen, wie Fast-Ethernet und Gigabit-Ethernet, sind aus der Welt der Kommunikationsnetze nicht mehr wegzudenken. Allerdings haben diese Verfahren einen Nachteil: Der Medienzugriff erfolgt mittels des Verfahrens "Carrier Sense, Multiple Access, Collision Detection" (CSMA/CD), das den Netzknoten keinerlei oberen zeitlichen Schranken gewährt. Das Problem ist zwar durch die heute üblichen Sterntopologien (gegenüber der früher üblichen Bustopologie) entschärft, dennoch gibt Ethernet auch heute keinerlei Garantien bei der Zustellung von Frames über (puffernde) Switches.

Im Rahmen dieser Arbeit soll untersucht werden, in wie fern sich andere Medienzugriffsverfahren für lokale Kommunikationsnetze eignen bzw. Kommunikationssysteme mit einem anderen Medienzugriffsverfahren  in einem Line-Sharing-Verfahren mit Ethernet kombinieren lassen.

Nützliche Vorkenntnisse:

Hilfreich, aber nicht zwingend erforderlich, sind Vorkenntnisse in den Grundlagen der Rechnernetze oder der Nachrichtentechnik.

Ansprechpartner:

Steffen Moser

Design Methods

Hardwaremonitor zur Laufzeit- und Energiemessung von Mikrokontrollern

Masterarbeit

Eingebettete Systeme sollen optimiert entworfen werden. Das heißt, die geforderte Funktion muss erfüllt werden und dabei soll die erforderliche Hardware so kostengünstig wie möglich sein. Das bedeutet, die Rechenleistung und der Energieverbrauch eines Prozessors müssen exakt an die Anforderungen des zu entwickelnden Systems angepasst sein. Beim Entwurf eines derartigen Systems schätzt man daher die Laufzeiten von Programmen und Programmteilen ab. Das gleiche gilt für den Energieverbrauch. Diese Abschätzungen müssen dann mit Hilfe von Messungen verifiziert werden. Die elektrische Leistung eines Prozessors bei der Programmausführung zu messen, erfordert ein Messsystem, das kleine elektrische Ströme und Spannungen gleichzeitig in kurzer Zeit messen kann. Daher ist die Anforderung sowohl an die digitale als auch an die analoge Hardware hoch. Die analoge Messschaltung soll mit Hilfe einer applikationsspezifischen digitalen Schaltung auf einem FPGAs angesteuert werden, dabei soll die digitale Schaltung in der Lage sein, die Programmausführung zu monitoren und Messungen in Abhängigkeit der jeweiligen Programmausführung automatisch zu starten oder zu beenden. Die Ergebnisse sollen gespeichert werden und statistisch ausgewertet werden können.

In dieser Masterarbeit soll ein FPGA-basierter Hardwaremonitor realisiert werden. Dazu soll das FPGA die bereits digitalisierten Werte von der analogen Messschaltung einlesen. Um die Messungen aber gezielt auswerten zu können, soll der Hardwaremonitor den Adress- und den Datenbus des Mikrokontrollers auswerten. Zum einen, um die gemessenen elektrischen Parameter gezielt Befehlen zuordnen zu können, zum anderen, um später ein spezifikationsgesteuertes Monitoring mit Hilfe von SystemC aufzubauen. Neben der Verwaltung einer Tabelle zur Messwertauswertung soll im FPGA eine schnelle Hardware zur Vorauswertung der Daten aufgebaut werden, um Mittelwerte und Standardabweichungen in Echtzeit bestimmen zu können. Dazu müssen unterschiedliche Konzepte zur Anbindung schneller Speicherbausteine untersucht werden. Ziel ist es, vollständige Programmsequenzen zu monitoren und dann den Energie- und Zeitverbrauch eines Programms in unterschiedlicher Granularität zu bestimmen.

Ansprechpartner: Prof. Frank Slomka

Analoge Strom und Spannungsmessung zur Laufzeit- und Energiemessung von Mikrokontrollern

Masterarbeit

Eingebettete Systeme sollen optimiert entworfen werden. Das heißt, die geforderte Funktion muss erfüllt werden und dabei soll die erforderliche Hardware so kostengünstig wie möglich sein. Das bedeutet, die Rechenleistung und der Energieverbrauch eines Prozessors müssen exakt an die Anforderungen des zu entwickelnden Systems angepasst sein. Beim Entwurf eines derartigen Systems schätzt man daher die Laufzeiten von Programmen und Programmteilen ab. Das gleiche gilt für den Energieverbrauch. Diese Abschätzungen müssen dann mit Hilfe von Messungen verifiziert werden. Die elektrische Leistung eines Prozessors bei der Programmausführung zu messen, erfordert ein Messsystem, das kleine elektrische Ströme und Spannungen gleichzeitig in kurzer Zeit messen kann. Daher ist die Anforderung sowohl an die digitale als auch an die analoge Hardware hoch. Die analoge Messschaltung soll mit Hilfe einer applikationsspezifischen digitalen Schaltung auf einem FPGAs angesteuert werden, dabei soll die digitale Schaltung in der Lage sein, die Programmausführung zu monitoren und Messungen in Abhängigkeit der jeweiligen Programmausführung automatisch zu starten oder zu beenden. Die Ergebnisse sollen gespeichert werden und statistisch ausgewertet werden können.

Insbesondere auf der analogen Seite des Messystems ist die Schaltung sorgfältig aufzubauen. In dieser Masterarbeit sollen mehrere unterschiedliche Schaltungskonzepte zur Messung kleiner Ströme untersucht werden. Dabei sollen verschiedene analoge Standard-ICs ausgewählt werden und im Hinblick auf die Messgenauigkeit und Messgeschwindigkeit untersucht werden. Ausgehend von diesen Bausteinen sollen verschiedene Messkonzepte entwickelt und die resultierenden Schaltungen untersucht werden. Dazu sollen die Schaltungen simuliert werden. Die Simulation kann mit Spice oder auch Matlab/Simscape erfolgen. ggf. können die unterschiedlichen Simulationsprogramme verglichen werden. Ziel der Arbeit ist es, am Ende ein analoges Schaltungskonzept auszuwählen, das in der Lage ist, mehrere Messungen pro Taktzyklus eines Mikrokontrollers zu Messen. Die Realisierung der Schaltung soll dann in einer nachfolgenden Arbeit erfolgen.

 

Ansprechpartner: Prof. Frank Slomka

Automatische Ableitung einer Rechnerarchitektur aus einem Modell

Bachelorarbeit

Die Modellierung zum Entwurf eingebetteter Echtzeitsysteme erfolgt zur Zeit hauptsächlich mit den Methoden der UML (Unified Modelling Language). Allerdings ist diese Modellierungssprache ehr für reine Softwaresysteme geeeignet. Zwar existieren Erweiterungen, wie MARTE und SysML, diese sind aber kaum ausgereift. Am Institut wurde eine neue graphische Beschreibungssprache entwickelt, die insbesondere auch den Hardwareentwurf unterstützt. Da die Sprache es explizit erlaubt die Funktionen des Betriebssystems bzw. die Softwarearchitektur abstrakt zu beschreiben, ist in dieser Bachelorarbeit zu untersuchen, wie die Hardwarestruktur des Systems automatisch aus einer vorhandenen Architekturbeschreibung abgeleitet werden kann. Um derartige Algorithmen oder Transformationen angeben zu können, sind zunächst di dafür notwendigen Datenstrukturen zu spezifizieren. Auf diesen sind dann die Transformationen zu programmieren. Anhand einer vorhandenen Entwurfsstudie (Sonar-System) sind die Ergebnisse der Arbeit dann zu validieren.

Ansprechpartner: Prof. Frank Slomka

Entwurfsraumexploration eingebetteter Systeme

Masterarbeit

Jedes eingebettete System kann unterschiedlich implementiert werden. So ist es denkbar die kompletten Funktionen auf einem starken und schnellen Rechner komplett in Software zu bauen oder aber eine Hardware zu entwerfen, die alle Funktionen durchführt. Heutzutage bestehen eingebettete Systeme aus eine eng verzahnten Hardware/Software-Architektur. Die optimale Hardware/Softwarearchitektur ist schwer zu finden, so sollen die Kosten der Hardware minimiert aber die Funktionen in vorgegebene Zeitfristen ausgeführt werden. Um automatisch eine derartige Hardware/Software-Partitionierung zu finden kann man Optimierungsverfahren einsetzten, die dann eine Entwurfsraumexploration durchführen. Auf der Grundlage der am Institut entwickelten Modellierungssprache zum Entwurf eingebetteter Systeme sollen Datenstrukturen für die Anwendung mit exakten und/oder heuristischen Optimierungsverfahren spezifiziert werden und mit ihrer Hilfe soll ein Verfahren zur Exploration eingebetteter Echtzeitsysteme implementiert und bezüglich seine Leitungsfähigkeit untersucht werden.

Ansprechpartner: Prof. Frank Slomka

Graphisches Entwurfswerkzeug für eingebettete Systeme

Masterarbeit

Auf der Grundlage von iOS und Cocoa/OS-X wurde am Institut ein Werkzeug zur graphischen Modellierung eingebetteter Systeme entwickelt. Mit diesem CASE-Werkzeug (Computer Aided Software Engineering) lassen sich eingebettete Systeme elegant graphisch modellieren. Dabei kommt ein neues Entwurfsparadigma zum Einsatz: Die Entwurfskarte. In der Masterarbeit sollen neue Bedienkonzepte für CASE-Werkzeuge entwickelt und untersucht werden. Insbesondere Handgesten wie sie bei Tablet-Computern zum Einsatz kommen stehen dabei im Fokus. In der Arbeit soll das vorhandene Werkzeug um neue Funktionen für den Hardwareentwurf und die Spezifikation extrafunktionaler Anforderungen erweitert werden. Dabei sollen insbesondere neue interaktive Konzepte der Benutzerführung erforscht werden. Die Programmierung erfolgt in Objective-C unter iOS oder OS-X u.a. auch auf dem iPad.

Ansprechpartner: Prof. Frank Slomka

Smart Systems

Display des Apollo Bordcomputers (DSKY)

Bachelorarbeit

In zukünftigen Laboren des Instituts für eingebettete Echtzeitsysteme soll ein Hardware-In-The-Loop Prüfstand aufgebaut werden. Die Studierenden sollen am praktischen Beispiel lernen, wie ein typischer Entwicklungsprozess für eingebettete Systeme abläuft. Als praxisnahes Beispiel soll der historische Bordcomputer aus dem Apolloraumschiff betrachtet werden. Um einen derartigen Computer zu betreiben wird ein Benutzerinterface benötigt. Im Apollo-Projekt hiess diese Schnittstelle DSKY (DiSplayKeYbord). In dem Labor wird der Computer in einem FPGA (Field Programmable Gate Array) implementiert. In der Bachelorabeit soll nun die Hardware für eine dem originalen DSKY nachempfundene Hardware aufgebaut werden. Dazu ist ein Mikrokontroller zu programmieren, der die Informationen auf dem Display darstellt und die Tastendrücke entgegen nimmt. Dieser Mikrokontroller soll dann über eine zu wählende Schnittstelle (USB, Ethernet) mit dem Computer auf dem FPGA kommunizieren.

Ansprechpartner: Prof. Frank Slomka

Energiemanagement in autonomen Unterwasserrobotern

Masterarbeit

In autonomen, computergestützten Fahrzeugen, setzt man normalerweise konventionelle Regelungen ein. Dabei versucht man einen Kurs und eine konstante Geschwindigkeit beizubehalten. Bei der Erkundung einer Umgebung hängt die Einsatzbereitschaft aber auch von der zur Verfügung stehenden Energie ab. Ist der Treibstoff aus oder die Batterie leer kann ein Roboter die Umgebung nicht mehr erkunden. Viel schlimmer noch, in bestimmten Anwendungen ist es möglich, dass der Roboter nicht mehr an einen Ort zurückkehren kann an dem er gewartet oder mit Energie versorgt werden kann. Das Fahrzeug würde also verloren gehen. In dieser Masterarbeit sollen Konzepte entwickelt werden, den Ladungszustand der Batterie in eine autonomen Unterwasserfahrzeug bei der Regelung und Missionsdurchführung zu berücksichtigen. Darauf aufbauend soll untersucht werden wie diese Eigenschaft der Roboters bei der Missionsplanung berücksichtigt werden kann.

Ansprechpartner: Prof. Frank Slomka

Generische FPGA-Platine

Bachelorarbeit

Für den am Institut entstehenden Unterwasserroboter wurde bereits eine Rechner-Backplane aufgebaut. Diese Backplane ermöglicht es mehrerere Steuerplatinen zu einem verteilten eingebetteten System zusammen zuschalten. Für diese Backplane ist nun eine geeignete Platine für den Steuerrechner aufzubauen. Dabei sollen marktübliche FPGA-Module (Field Programmable Gate Array) verwendet wenden und unter den Vorgaben der Spezifikation der Backplane auf einer zuverlässigen Platine mit passenden I/O-Modulen integriert werden.

Ansprechpartner: Florian Hock

Lernende Kalman-Filter für Inertialnavigation

Masterarbeit

Unterwasser funktioniert kein GPS. daher ist es eine Herausforderung die Position eines Unterwasserroboters zu bestimmen. In der Regel erfolgt die Positionsbestimmung von Unterwasserfahrzeugen mittels Inertial-Navigationssystemen. Laserkreisel oder mechanische Systeme, die die erforderliche Genauigkeit bereitstellen sind sehr teuer. In dieser Arbeit sollen kostengünstige Halbleitersensoren aus dem Automobilbau dahingehend untersucht werden, ob es möglich ist, mit einem lernenden Kalman-Filter die Drift der Sensoren soweit zu reduzieren, dass es möglich wird diese in einem Inertial-Navigationssystem zu verwenden.

Ansprechpartner: Prof. Frank Slomka

Trajektorienberechnung zur Mondlandung mit Hilfe von Variationsrechnung und Deep-Learning-Verfahren

Masterarbeit

Eine der vielen Herausforderungen der Mondlandung von 1969 war die Berechnung einer geeigneten Trajektorie vom Orbit zur Mondoberfläche. Neben der eingeschränkten Steuerbarkeit der Mondlandefähre stellt vor allem die Gravitation sowie die zeitlich variable Masse des Landemoduls (Treibstoffverbrauch!) eine Herausforderungen dar, die es zu bewältigen gilt.

 

Im Rahmen einer Projekt- oder Masterarbeit sollen alternative Ansätze zum Bestimmen geeigneter Landetrajektorien untersucht werden, deren Einsatz erst durch die gesteigerte Rechenkapazitäten heutiger Desktop-PCs möglich geworden sind.

 

In jeweils einer eigenständigen Arbeit soll das Problem der Trajektorienberechnungeinmal als Optimalsteuerungsproblemaufgefasst werden und in einer weiteren Arbeit  mit Hilfe von Deep-Learning-Verfahrenuntersucht werden.

Ziel der Arbeit ist es, die mit Hilfe dieser Verfahren berechneten Trajektorien, mit den Ergebnissen von 1969 zu vergleichen und zu evaluieren.

Ansprechpartnern: Mohammadreza Sadeghi, Marco Philippi

Digital Teaching

Algorithmus nach Quine und McCluskey zum Zuschauen

Masterarbeit

Quine und McCluskey stellten 1952–1956 ein Verfahren vor, mit dem Schaltfunktionen minimiert werden können. Die Ausgabe des von ihnen präsentierten bzw. verbesserten Algorithmus kann zwar auch unter Verwendung eines Karnaugh-Veitch-Diagramms ermittelt werden, doch ist das Quine-McCluskey-Verfahren wesentlich besser an die Durchführung mit Computern angepasst und ist auch bei großen Mengen von Eingangsvariablen noch einfach systematisch anwendbar.

Zur Verwendung in der Lehre ist es interessant, einer Implementierung des Verfahrens nach Quine und McCluskey „bei der Arbeit zusehen“ zu können, wobei jeder Teilschritt visualisiert werden sollte. Im Rahmen dieser Masterarbeit soll einerseits untersucht werden, wie das Verfahren didaktisch am geschicktesten präsentiert werden kann, und andererseits das konzipierte Visualisierungssystem implementiert werden.

Was die konkrete Art der visuellen Umsetzung anbelangt, gibt es noch keine feste Vorgabe; eigene Vorschläge sind willkommen. Wichtiges Vorwissen umfasst neben dem natürlich essenziellen Verständnis des Quine-McCluskey-Verfahrens gute Programmierkenntnisse in höheren Programmiersprachen und Kenntnis von bzw. Erfahrung mit für die Visualisierung eingesetzten Bibliotheken, Frameworks, Hilfsprogrammen und/oder Plattformen. Etwas didaktisches Gespür ist von Vorteil. Diese Masterarbeit richtet sich speziell an Studierende der Medieninformatik, aber auch andere Interessierte sind natürlich willkommen.

Ansprechpartner: Nicolas Roeser

Visualization of the Quine-McCluskey Algorithm

Master Thesis

From 1952 to 1956, Quine and McCluskey presented a technique which can minimize switching functions. Even though the output from the algorithm presented or improved by them can in an equal way be determined by utilizing a Karnaugh map, the Quine-McCluskey algorithm is far better tuned for execution by computers and is still easily and systematically usable in the case of large numbers of input variables.

For uses in teaching it is interesting to be able to “watch” an implementation of the Quine-McCliskey algorithm “at work”, where every single step should be visualized. Within this master thesis, it shall on the one side be investigated how to present the algorithm in the didactically most clever way, and on the other side the conceived visualization system shall be implemented.

There is no strict guideline for the precise way of visualization yet; own ideas are welcome. Important prior knowledge includes understanding of the Quine-McCluskey algorithm, which is essential, good programming skills in higher programming languages and knowledge about or experience with libraries, frameworks, tools and/or plattforms used for visualization. A bit of sense for didactics is an advantage. This master thesis primarily targets media informatics students, but others who are interested are of course welcome, too.

Contact: Nicolas Roeser

Security in Embedded Systems, PUFs

Komplexität von PUFs

Masterarbeit

Physical Unclonable Functions (PUFs) sind Schaltungen, die es ermöglichen, unterschiedliche Instanzen einzelner integrierter Schaltungen voneinander zu unterscheiden. Zwar werden alle Schaltungen im gleichen Prozess mit immer wieder denselben Masken gefertigt, trotzdem unterscheidet sich jede einzelne Schaltung auf einem Waver durch ungewollte Prozessvariationen während der Herstellung. Mit Hilfe der PUFs werden diese Variationen gemessen und aus diesen individuellen Schaltungseigenschaften wird dann ein möglichst eindeutiger geheimer Schlüssel zur Identifikation und Authentifizierung der Schaltung gewonnen.

Es gibt unterschiedliche Möglichkeiten, PUFs zu implementieren. Die bekanntesten sind die Arbiter-, die Ringoszillator- und die SRAM-basierte PUF. Inzwischen existieren unterschiedliche Implementierungen dieser Schaltungen auf FPGAs.

In der Masterarbeit soll ein am Institut entwickeltes Komplexitätsmaß für logische Schaltungen zur Komplexitätsmessung von PUFs erweitert werden. Zum einen sind die analogen Schaltungsteile einer PUF bezüglich ihrer Komplexität zu untersuchen, zum anderen ist die Komplexitätsmetrik für analoge Transistorschaltungen zu erweitern.

Ansprechpartner: Nicolas Roeser

PUF Complexity

Master Thesis

Physical Unclonable Functions (PUFs) are circuits which allow to differentiate multiple instances of integrated circuits. Even though the same masks are used over and over again within the same production process when circuits are fabricated, each single circuit on a waver differs from the others due to unwanted process variations at production time. PUFs enable measurement of these variations and the individual circuit characteristics are used as a source from which a secret key as unique as possible is extracted which allows for identification and authentication of the circuit.

There are varying possibilities which are used for implementing PUFs. The best known ones are an arbiter, ring oscillator or SRAM-based PUF. Nowadays, different implementations of this circuitry are available for FPGAs.

In this master thesis, a complexity metric for logic circuits which has been developed at our institute shall be extended to measure the complexity of PUFs. For one thing, analog circuit parts of a PUF need to be investigated with respect to their complexity; for another thing, the complexity metric needs to be extended to also cover analog transistor circuits.

Contact: Nicolas Roeser

Hardware and Software Complexity

Komplexität von PUFs

Masterarbeit

Physical Unclonable Functions (PUFs) sind Schaltungen, die es ermöglichen, unterschiedliche Instanzen einzelner integrierter Schaltungen voneinander zu unterscheiden. Zwar werden alle Schaltungen im gleichen Prozess mit immer wieder denselben Masken gefertigt, trotzdem unterscheidet sich jede einzelne Schaltung auf einem Waver durch ungewollte Prozessvariationen während der Herstellung. Mit Hilfe der PUFs werden diese Variationen gemessen und aus diesen individuellen Schaltungseigenschaften wird dann ein möglichst eindeutiger geheimer Schlüssel zur Identifikation und Authentifizierung der Schaltung gewonnen.

Es gibt unterschiedliche Möglichkeiten, PUFs zu implementieren. Die bekanntesten sind die Arbiter-, die Ringoszillator- und die SRAM-basierte PUF. Inzwischen existieren unterschiedliche Implementierungen dieser Schaltungen auf FPGAs.

In der Masterarbeit soll ein am Institut entwickeltes Komplexitätsmaß für logische Schaltungen zur Komplexitätsmessung von PUFs erweitert werden. Zum einen sind die analogen Schaltungsteile einer PUF bezüglich ihrer Komplexität zu untersuchen, zum anderen ist die Komplexitätsmetrik für analoge Transistorschaltungen zu erweitern.

Ansprechpartner: Nicolas Roeser

PUF Complexity

Master Thesis

Physical Unclonable Functions (PUFs) are circuits which allow to differentiate multiple instances of integrated circuits. Even though the same masks are used over and over again within the same production process when circuits are fabricated, each single circuit on a waver differs from the others due to unwanted process variations at production time. PUFs enable measurement of these variations and the individual circuit characteristics are used as a source from which a secret key as unique as possible is extracted which allows for identification and authentication of the circuit.

There are varying possibilities which are used for implementing PUFs. The best known ones are an arbiter, ring oscillator or SRAM-based PUF. Nowadays, different implementations of this circuitry are available for FPGAs.

In this master thesis, a complexity metric for logic circuits which has been developed at our institute shall be extended to measure the complexity of PUFs. For one thing, analog circuit parts of a PUF need to be investigated with respect to their complexity; for another thing, the complexity metric needs to be extended to also cover analog transistor circuits.

Contact: Nicolas Roeser

Portierung eines Verfahrens zur Hardwarekomplexitätsmessung auf Software

Masterarbeit

Möchte man eine neue Software entwickeln, ist es ratsam, zu Beginn den zu erwartenden Aufwand abzuschätzen. So kann einerseits die Realisierbarkeit des Projekts geprüft werden und können andererseits die voraussichtlich benötigten Ressourcen (Personen, Geld, Geräte usw.) eingeplant werden. Der Aufwand sollte auch im Laufe der Projektentwicklung ständig im Auge behalten werden, um schnell auf Änderungen reagieren zu können; nach Abschluss des Projektes lohnt sich das Festhalten des tatsächlichen Aufwands als Referenz für zukünftige Vorhaben.

Derzeit wird im Institut für Eingebettete Systeme/Echtzeitsysteme an einem Verfahren zur Bestimmung von Komplexität geforscht. Es unterscheidet sich wesentlich von existierenden Aufwands- bzw. Komplexitätsmetriken. Die neue Metrik ist für Aussagen über Hardware einsetzbar und soll nun über unterschiedliche Herangehensweisen auch auf Software (Computerprogramme) angewendet werden.

Die bei der Analyse von Hardwarekomponenten durchzuführenden Schritte können ähnlich auch auf Software angewendet werden, nur ist zuvor eine entsprechende Abbildung bzw. Zuordnungsvorschrift zu erstellen. Beispielsweise können Eingänge von Registern einer Hardwareschaltung als Werte von Variablen in Software auftreten. Diese Masterarbeit soll die Übertragung des Vorgehens der Hardware-Metrik auf die Software-Seite untersuchen.

Ein gutes Verständnis im Bereich technischer Informatik und speziell der Abläufe innerhalb von einfachen Rechnersystemen, wie zum Beispiel einer MIPS-Maschine, ist erforderlich. Darüber hinaus ist es eine wichtige Voraussetzung, solide Kenntnisse in einerseits Assemblerprogrammierung bzw. maschinennaher Programmierung in C und andererseits mindestens einer höheren Programmiersprache wie wiederum C oder Java oder einer Skriptsprache oder Ähnlichem zu haben.

Ansprechpartner: Nicolas Roeser

Porting a Hardware Complexity Measurement Method to Software

Master Thesis

Whenever a new software system is devised, it is advisable to start with an estimation of the effort that will likely be caused by the project. This allows, on the one hand, to verify whether a project can be realized, and on the other hand, to plan for the resources (people, money, equipment etc.) which are estimated to be required. The effort should be continuously monitored during the project development time in order to be able to quickly react to changes; after the project is completed, taking note of the actual effort is worthwhile as a reference for future projects.

At the Institute of Embedded Systems/Real-Time Systems research is being conducted on a method which determines complexity. It differs considerably from existing effort or complexity metrics. The new metric is suited for statements about hardware and shall be applied to software (computer programs) as well by different approaches.

The steps which must be followed when analyzing hardware components can also be applied to software in a similar way, it is only required to create a corresponding mapping or transformation instructions first. For example, register inputs from a hardware circuit can appear as values of variables in software. Within this master thesis, transfer of the process from the hardware metric to the software field shall be investigated.

Good understanding of computer engineering and particularly of what happens inside simple computer systems, like a MIPS machine, is required. Furthermore, important prerequisites include profound knowledge of assembler programming or machine-oriented programming in C on the one side and at least one higher programming language like C again, or Java, or a scripting language or similar on the other side.

Contact: Nicolas Roeser

Komplexitätsanalyse von SystemC-Projekten

Masterarbeit

Vor, während und nach der Laufzeit von Entwicklungsprojekten im Hard- oder Softwarebereich ist eine Abschätzung des zu erwartenden Restaufwands bzw. des bis dahin tatsächlichen Aufwands ein Hilfsmittel für die Machbarkeitsanalyse und für die Planung, Umsetzung und Optimierung der Vorgehensweise und auch der Kosten für die Entwicklung. Die Beschreibung von Projekten erfolgt über vielfältige Mittel und Sprachen, darunter beispielsweise Verilog, VHDL, SystemC, C, UML oder nach vorgegebenen Handbüchern strukturierte Textdateien.

Im Institut für Eingebettete Systeme/Echtzeitsysteme wird zurzeit die Komplexität von Hardware und Software mit neuartigen Analyseverfahren untersucht. Außerdem gibt es ein Projekt, in dem ein vorgegebenes Echtzeitsystem mittels SystemC auf verschiedenen Entwurfsebenen mit industrierelevanten Standards modelliert wird.

In dieser Masterarbeit soll nun an SystemC-Projekte wie das gerade genannte angeknüpft und eine Komplexitätsmessung auf mehreren Entwurfsebenen durchgeführt werden. Dies erfordert unter anderem die Adaption eines vorhandenen Komplexitätsanalyseverfahrens in Richtung SystemC. Solide Vorkenntnisse in SystemC sind vonnöten bzw. sich zu Beginn zügig anzueignen.

Dieses Thema kann auch bereits als Master-Projekt begonnen werden bzw. in diesem Themenbereich ist ein Master-Projekt mit angepasstem Umfang möglich.

Ansprechpartner: Nicolas Roeser

Complexity Analysis of SystemC Projects

Master Thesis

Before, during and after the life span of a development project in the hardware or software field, an estimation of the remaining necessary effort or of the actual effort that has gone into the project so far is a tool for analyzing feasibility and for planning, realization and optimization of development process and costs. Projects can be specified in various ways and languages, for example Verilog, VHDL, SystemC, C, UML, or text files structured according to given manuals, among others.

At the Institute of Embedded Systems/Real-Time Systems the complexity of hardware and software is analyzed with novel analysis methods. In addition to that, there is a project in which a given real-time system is modeled in SystemC on different design layers with standards used in the industrial sector.

This master thesis shall take SystemC projects up like the one mentioned above and conduct complexity measurements on different design layers. Among other things, this requires adapting an existing method for measuring complexity in the direction of SystemC. Solid knowledge in SystemC are necessary or need to be quickly acquired when starting.

This topic can also be taken up as a master project, or a master project with adjusted size can be started in this subject area.

Contact: Nicolas Roeser

Auswirkung der Komplexität auf Designentscheidungen

Masterarbeit

Insbesondere zu Beginn, aber auch während und nach der Umsetzung von Hardware- oder Softwareentwicklungen bietet der geschätzte Aufwand, der sich aus der Komplexität des Projekts ergibt, eine Richtschnur, um abzuschätzen, ob ein Projekt überhaupt in Angriff genommen werden kann, und, welche Teile davon umsetzbar sind und welche nicht. Nicht nur auf die Entscheidungen von Management-Ebenen, sondern auch direkt bei den Entwicklungsteams von Hard- oder Softwareprojekten hat die ermittelte Komplexität Einfluss.

Zurzeit wird im Institut für Eingebettete Systeme/Echtzeitsysteme eine neue Metrik zur Komplexitätsmessung von Hardware und Software gebildet und erprobt. Diese Metrik soll nun angewendet werden und im Rahmen einer Masterarbeit untersucht werden, inwiefern bei vordefinierten Schranken für den Aufwand eines Projekts (beispielsweise durch ein vorgegebenes Budget für Personalkosten) Designentscheidungen bezüglich Umsetzung von Projektanforderungen, Entwurf, Änderung oder Weiterentwicklung bspw. einer ALU oder CPU flexibel möglich sind oder erzwungen werden.

Vorkenntnisse und Interesse im Gebiet der Rechnerarchitektur, speziell der Konstruktion eines einfachen Rechners wie der MIPS, sind hilfreich.

Ansprechpartner: Nicolas Roeser

Impacts of Complexity on Design Decisions

Master Thesis

Especially at the start of hardware or software development efforts, but also during or after them the estimated effort which results from the complexity of the project provides a guideline for estimating whether a project can be tackled at all and which of its parts are feasible and which are not. Not only decisions made by management staff, but also those directly made by development teams for hardware or software projects are influenced by the complexity that has been determined.

Currently a new metric for complexity measurement targeting hardware and software is being created and tested at the Institute of Embedded Systems/Real-Time Systems. This metric shall be utilized and within a master thesis it shall be analyzed in what way, given predefined limits for the expenses put into a project (e.g. by a given budget for personnel costs), design decisions regarding implementation of project requirements, conception, changes or improvements to e.g. an ALU or CPU can be handled in a flexible manner or are enforced.

Previous knowledge in the topic of computer architecture, especially about construction of a simple computer like a MIPS, will be helpful.

Contact: Nicolas Roeser

Visualisierung von Komplexität

Bachelorarbeit

Eine prägnante, eingängige, intuitiv verständliche visuelle Darstellung von Sachverhalten ist oft für Menschen wertvoller als lange Texte, Tabellen oder Datenkolonnen. Im Gegensatz zu Computern sind Menschen in der Lage, relativ schnell Übersichten oder Zusammenhänge aus Bildern statt aus anderen Rohdaten zu erfassen.

Zurzeit wird im Institut für Eingebettete Systeme/Echtzeitsysteme die Komplexität von Hardware und Software mit neuartigen Analysemethoden untersucht. Die dafür entwickelten (Kommandozeilen-)Hilfsprogramme schreiben während der Analyse höchstens ein paar Debugging-Meldungen ins Log und geben als Ergebnisse reine Texte bzw. Zahlenreihen aus.

Wünschenswert wäre, während der Komplexitätsanalyse „zuschauen“ zu können und das Verfahren grafisch angezeigt zu bekommen, und vor allem, im Anschluss an die Analyse durch eine übersichtliche grafische Repräsentation des analysierten Systems die für große Komplexität verantwortlichen „Hotspots“ einfach identifizieren und durch das System „zoomen“/„navigieren“ zu können. Diese Funktionalität kann im Rahmen einer Bachelorarbeit entwickelt und angeschlossen werden.

Was die Art der Visualisierung anbelangt, gibt es noch keine verbindlichen Vorgaben; speziell Studierende der Medieninformatik werden hier großartige eigene Ideen einbringen können. Programmiererfahrung mit der Programmiersprache Java sowie gute Kenntnisse von Visualisierungs-Tools, -Bibliotheken und -Frameworks sind für die Bearbeitung dieses Themas nützlich.

Ansprechpartner: Nicolas Roeser

Visualizing Complexity

Bachelor Thesis

A concise, easy to grasp, intuitively understandable visual display of facts is mostly more useful for humans than long texts, tables or lines of numbers. Unlike computers, humans are able to grasp the overall picture or context relatively fast from images rather than from other raw data.

At the Institute of Embedded Systems/Real-Time Systems hardware and software complexity is being investigated by employing novel analysis methods. The (command line) tools developed for this purpose write a few debug messages to the log at the most, and produce plain text or raw numbers as their output.

It is preferable to have an ability to “watch” the complexity analysis work and to see a visualization of the method, and especially to receive a clear, graphical representation of the analyzed system after the analysis is complete in which “hotspots” responsible for high complexity can be easily identified and the user can “zoom”/“navigate” through the system. This functionality can be developed and connected in a bachelor thesis.

There are no binding requirements regarding the specific way and means of visualization yet; especially media informatics students will be able to introduce own great ideas here. Programming experience in the Java programming language, as well as good knowledge of visualization tools, libraries and frameworks are useful for dealing with this topic.

Contact: Nicolas Roeser

Datenanalyse in großen Mengen von Komplexitätskennzahlen

Bachelorarbeit

Zur Bestimmung der Komplexität von Schaltungen (oder anderer Hardware) und Software (zum Beispiel Assemblercode) wird im Institut für Eingebettete Systeme/Echtzeitsysteme an einem neuen Analyseverfahren geforscht. Eine Metrik kann bzw. soll dabei für eine eingegebene Schaltung oder ein eingegebenes Stück Software die Komplexität als Kenngröße liefern. Vielfach ist es nicht direkt möglich, gleich die bestmögliche Implementierung für diese Metrik anzugeben; dies ist eher ein stufenweiser Verbesserungsprozess. Daher ist es interessant, mit einer bestehenden Metrik einige tausende oder mehr Eingaben durchzuprüfen und die Ergebnisse anschließend auf Parallelen oder Auffälligkeiten zu untersuchen; die daraus gewonnenen Erkenntnisse können dann wiederum in eine Verbesserung des Ansatzes einfließen.

In dieser Bachelorarbeit soll unter Verwendung von Algorithmen und Verfahren aus dem Data Mining ein Vergleich der Kennzahlen von großen Mengen von Schaltungen/Funktionen durchgeführt werden, die zu diesem Zweck automatisch generiert werden können. So könnte ein Rechner beispielsweise Cluster in den Daten finden und Menschen auf Zusammenhänge aufmerksam machen.

Sinnvolle Vorkenntnisse liegen im Bereich des maschinellen Verarbeitens großer Datenmengen sowie sind Kenntnisse zu Datenreduktion und Data-Mining. Solide Programmierkenntnisse in einer gängigen Skriptsprache und/oder der Programmiersprache Java oder C werden vorausgesetzt.

Ansprechpartner: Nicolas Roeser

Data Analysis in Vast Amounts of Complexity Indexes

Bachelor Thesis

A new anaylsis method is under research at the Institute of Embedded Systems/Real-Time Systems for determining the complexity of circuits (or other hardware) and software (assembler code, for example). In this regard, a metric can or should provide as a characteristic value the complexity of a circuit or a piece of software which has been input.

It is in many cases impossible to deliver the best possible implementation for this metric straight away; there is rather an incremental process of improvement. Therefore it is interesting to analyze a few thousand or more inputs with an existing metric, and analyze the results afterwards with special regard to parallels or unexpected values; the lessons learned from that can then be incorporated again in further improvements of the approach.

In this bachelor thesis, algorithms and procedures from data mining shall be employed for comparing characteristical indexes for vast numbers of circuits/functions, which can be automatically generated for this purpose. To give an example, a computer could find clusters in the data and make humans aware of connections that have been detected.

Useful prior knowledge comes from the field of automatic processing large amounts of data and encompasses knowledge about data reduction and data mining. Solid programming skills in a common scripting language and/or in the Java programming language or C are expected.

Contact: Nicolas Roeser

Automatic Generation of Microcode Control Units from Architecture Description Languages

Master Thesis

Architecture description languages provide an elegant way of describing computer architectures, as they allow the creation of much more abstract descriptions than would be possible with a hardware description language like VHDL. In contrast to VHDL, though, they do not support step-by-step refinement in the design process.

This master thesis shall start with a comparison and a classification of several architecture design languages. This shall include an investigation of how to provide a similar abstraction with a hardware description language. Starting with a tool for automatic generation of microprogram control units, which has been developed at the institute, an architecture description language shall be developed which must be as abstract and simple as possible. Goal of the thesis is the automatic generation of processors, while also measuring the design complexity with a metric which has as well already been developed.

Contact: Nicolas Roeser

Development of Hardware on FPGAs

FPGA-based Control and Data Acquisition in a Parallel Super-Resolution Fluorescence Microscope

Master Thesis

Topic

Imaging of dynamic processes within biological tissue or living cells is a challenge in the field of microscopy. Many processes happen either on fast time scales or in nanoscopic dimensions and call for microscopes with fast data acquisition and high resolution.

In the Institute of Biophysics we are designing a new fluorescence microscope, which relies on the effect of stimulated emission depletion (STED) and a high degree of parallelization. A bundle of 64 laser beams will be scanned across biological samples and the emitted fluorescence will be detected by a custom-designed fast single photon detector array.

Goals

The aim of this thesis is to design and implement a real-time read-out and control unit for the microscope.  This includes FPGA design and programming using VHDL and fast hardware.

The project is at the interface of real-time computing and novel applications in biophysics and biological imaging, thus we are looking for highly motivated students open for working at the boundary of computing and instrumentation development.

Contact

Nicolas Roeser, Institute of Embedded Systems/Real-Time Systems

Uwe Jantzen, Institute of Biophysics

Prof. Frank Slomka, Institute of Embedded Systems/Real-Time Systems

Prof. Jens Michaelis, Institute of Biophysics