Refine
Year of publication
Document Type
- Doctoral Thesis (9)
- Habilitation (1)
Has Fulltext
- yes (10)
Is part of the Bibliography
- no (10)
Keywords
- Organic Computing (3)
- ALICE (1)
- Autonomie (1)
- Data Acquisition (1)
- Echtzeitsystem (1)
- Eingebettetes System (1)
- Event Buffering (1)
- FPGA (1)
- FPGAs (1)
- Hash Funktionen (1)
Institute
- Informatik (7)
- Informatik und Mathematik (3)
Um Wissen in einer Form abzulegen, in der es automatisiert verarbeitet werden kann, werden unter anderem Ontologien verwendet. Ontologien erlauben über einen als Inferenz bezeichneten Prozess die Ableitung neuen Wissens. Bei inhaltlichen Überschneidungen werden Ontologien über Ontologie-Alignments miteinander verbunden, die Entitäten aus den verschiedenen Ontologien in Beziehung zueinander setzen. Üblicherweise werden diese Alignments als Mengen von Äquivalenzen formuliert, die beschreiben, welche Konzepte aus einer Ontologie Konzepten aus einer anderen Ontologie entsprechen. Ebenfalls verbreitet sind Ober- und Unterklassenbeziehungen in Alignments.
Diese Ontologie-Alignments werden zum Beispiel in der Biomedizin in Forschungsdatenbanken verwendet, da durch Alignments Informationen aus verschiedenen Bereichen zusammengeführt werden können. Der manuelle Aufwand, um große Ontologien und Alignments zu erstellen, ist sehr hoch. Dementsprechend wäre es wünschenswert, bei einer Veränderung von Ontologien nicht wieder von vorne beginnen und eine neue Ontologie erstellen zu müssen und möglichst viel aus der veränderten Ontologie und den die Ontologie betreffenden Alignments wiederverwenden zu können. Daher sollten möglichst automatisierte Verfahren verwendet werden. Diese Arbeit untersucht vier Ansätze, um die Anpassung von Alignments an Veränderungen in Ontologien zu automatisieren.
Der erste Ansatz bezieht Inferenzen in den Prozess zur Vorhersage von Alignment-Änderungen mit ein. Dazu werden die Inferenzen vor und nach der Änderung der Ontologien berechnet und auf Basis der Unterschiede mit einem regelbasierten Algorithmus bestimmt, wie sich das Alignment ändern soll. Der zweite Ansatz, wie auch die weiteren Ansätze, hat nicht zum Ziel das Alignment direkt anzupassen. Stattdessen soll vorhergesagt werden, welche Teile des Alignments angepasst werden müssen. Dazu werden die Ontologien und das Alignment als Wissensgraph-Embeddings repräsentiert. Diese Embeddings bilden Knoten aus den Ontologien in einen Raum mit 300-1000 Dimensionen so ab, dass in dem Raum auch die Beziehungen zwischen den Entitäten der Ontologien repräsentiert werden können. Diese Embeddings werden dann verwendet, um verschiedene Klassifikationsalgorithmen zu trainieren. Auf diese Weise wird vorhergesagt, welche Teile des Alignments sich verändern werden. Der dritte Ansatz verbindet Embeddings mit einem Veränderungsmodell. Das Veränderungsmodell kategorisiert die an den Ontologien vorgenommenen Veränderungen. Auf diese Kategorisierung und das Embedding werden dann Klassifikationsalgorithmen angewandt. Der vierte Ansatz verwendet eine speziell auf Wissensgraphen ausgerichtete Architektur für neuronale Netze, sogenannte Graph Convolutional Networks, um Veränderungen an Alignments vorher zu sagen.
Diese Ansätze werden auf ihre jeweiligen Vor- und Nachteile untersucht. Dazu werden die Verfahren an zwei Anwendungsfällen untersucht. Der Ansatz zur regelbasierten Einbeziehung von Inferenzen wird anhand eines Anwendungsbeispiels aus dem Bereich der Interweaving Systems betrachtet. In dem Beispiel wird eine allgemeine Methode für Interweaving Systems angewandt um das Selbstmanagement von Ampelsteuerungen zu ermöglichen. Die auf maschinellem Lernen aufbauenden Ansätze werden auf einem Auszug aus der biomedizinischen Forschungsdatenbank UMLS evaluiert.
Dabei konnte festgestellt werden, dass die betrachteten Ansätze grundsätzlich zur Anpassung von Alignments an Ontologie-Veränderungen eingesetzt werden können. Der Ansatz zur regelbasierten Einbeziehung von Inferenzen kann dabei vor allem auf sehr kleinen Datensätzen eingesetzt werden, bei denen alle Gesetzmäßigkeiten der Veränderungen grundsätzlich bekannt sind. Diese Anwendbarkeit ergibt sich aus dem Entwurf der Problemstellung für den ersten Ansatz. Die auf maschinellem Lernen aufbauenden Ansätze eignen sich besonders für große Datensätze und bieten den Vorteil, dass auch ohne ein vollständiges Verständnis des Veränderungsprozesses Vorhersagen getroffen werden können.
Unter den Ansätzen, die maschinelles Lernen einsetzen, zeigte die Einbeziehung von Veränderungsmodellen keine Vorteile gegenüber den anderen Ansätzen. Auf einem etwas
kleineren Datensatz waren die Ergebnisse des Embedding-basierten Ansatzes und der Relational Graph Convolutional Networks vergleichbar, während auf einem größeren Datensatz
die Graph Convolutional Networks etwas bessere Ergebnisse erreichen konnten.
Weitere Ergebnisse dieser Arbeit stellen eine Formalisierung der Problemstellung der Anpassung von Ontologie-Alignments an Veränderungen sowie eine formale Darstellung der Ansätze dar. Ein weiterer Beitrag der Arbeit ist die Vorstellung eines Anwendungsfalls aus dem Bereich der Interweaving Systems für Ontologie-Alignments. Außerdem wurde das Problem der Anpassung von Alignments an Veränderungen so formuliert, dass es mithilfe von
maschinellem Lernen betrachtet werden kann.
In dieser Arbeit wird die Verteilung von zeitlich abhängigen Tasks in einem verteilten System unter den Gesichtspunkten des Organic Computing untersucht. Sie leistet Beiträge zur Theorie des Schedulings und zur selbstorganisierenden Verteilung solcher abhängiger Tasks unter Echtzeitbedingungen. Die Arbeit ist in zwei Teile gegliedert: Im ersten Teil werden Tasks als sogenannte Pfade modelliert, welche aus einer festen Folge von Aufträgen bestehen. Dabei muss ein Pfad ununterbrechbar auf einer Ressource ausgeführt werden und die Reihenfolge seiner Aufträge muss eingehalten werden. Natürlich kann es auch zeitliche Abhängigkeiten zwischen Aufträgen verschiedener Pfade geben. Daraus resultiert die Frage, ob ein gegebenes System S von Pfaden mit seinen Abhängigkeiten überhaupt ausführbar ist: Dies ist genau dann der Fall wenn die aus den Abhängigkeiten zwischen den Aufträgen resultierende Relation <A irreflexiv ist. Weiterhin muss für ein ausführbares System von Pfaden geklärt werden, wie ein konkreter Ausführungsplan aussieht. Zu diesem Zweck wird eine weitere Relation < auf den Pfaden eingeführt. Falls < auf ihnen irreflexiv ist, so kann man eine Totalordnung auf ihnen erzeugen und erhält somit einen Ausführungsplan. Anderenfalls existieren Zyklen von Pfaden bezüglich der Relation <. In der Arbeit wird weiterhin untersucht, wie man diese isoliert und auf einem transformierten Pfadsystem eine Totalordnung und damit einen Ausführungsplan erstellt. Die Größe der Zyklen von Pfaden bezüglich < ist der wichtigste Parameter für die Anzahl der Ressourcen, die für die Ausführung eines Systems benötigt werden. Deshalb wird in der Arbeit ebenfalls ausführlich untersucht, ob und wie man Zyklen anordnen kann, um die Ressourcenzahl zu verkleinern und somit den Ressourcenaufwand zu optimieren. Dabei werden zwei Ideen verfolgt: Erstens kann eine Bibliothek erstellt werden, in der generische Zyklen zusammen mit ihren Optimierungen vorliegen. Die zweite Idee greift, wenn in der Bibliothek keine passenden Einträge gefunden werden können: Hier erfolgt eine zufällige oder auf einer Heuristik basierende Anordnung mit dem Ziel, den Ressourcenaufwand zu optimieren. Basierend auf den theoretischen Betrachtungen werden Algorithmen entwickelt und es werden Zeitschranken für ihre Ausführung angegeben. Da auch die Ausführungszeit eines Pfadsystems wichtig ist, werden zwei Rekursionen angegeben und untersucht. Diese schätzen die Gesamtausführungszeit unter der Bedingung ab, dass keine Störungen an den Ressourcen auftreten können. Die Verteilung der Pfade auf Ressourcen wird im zweiten Teil der Arbeit untersucht. Zunächst wird ein künstliches Hormonsystems (KHS) vorgestellt, welches eine Verteilung unter Berücksichtigung der Eigenschaften des Organic Computing leistet. Es werden zwei Alternativen untersucht: Im ersten Ansatz, dem einstufigen KHS, werden die Pfade eines Systems direkt durch das KHS auf die Ressourcen zu Ausführung verteilt. Zusätzlich werden Mechanismen zur Begrenzung der Übernahmehäufigkeit der Pfade auf den Ressourcen und ein Terminierungs-mechanismus entwickelt. Im zweiten Ansatz, dem zweistufigen KHS, werden durch das KHS zunächst Ressourcen exklusiv für Klassen von Pfaden reserviert. Dann werden die Pfade des Systems auf genau den reservierten Ressourcen vergeben, so dass eine Ausführung ohne Wechselwirkung zwischen Pfaden verschiedener Klassen ermöglicht wird. Auch hierfür werden Methoden zur Beschränkung der Übernahmehäufigkeiten und Terminierung geschaffen. Für die Verteilung und Terminierung von Pfaden durch das einstufige oder zweistufige KHS können Zeitschranken angegeben werden, so dass auch harte Echtzeitschranken eingehalten werden können. Zum Schluss werden beide Ansätze mit verschiedenen Benchmarks evaluiert und ihre Leistungsfähigkeit demonstriert. Es zeigt sich, dass der erste Ansatz für einen Nutzer einfacher zu handhaben ist, da die benötigten Parameter sehr leicht berechnet werden können. Der zweite Ansatz ist sehr gut geeignet, wenn eine geringe Anzahl von Ressourcen vorhanden ist und die Pfade verschiedener Klassen möglichst unabhängig voneinander laufen sollen. Fazit: Durch die in dieser Arbeit gewonnenen Erkenntnisse ist jetzt möglich, mit echtzeitfähigen Algorithmen die Ausführbarkeit von zeitlich abhängigen Tasks zu untersuchen und den Ressourcenaufwand für ihre Ausführung zu optimieren. Weiterhin werden zwei verschiedene Ansätze eines künstlichen Hormonsystems zur Allokation solcher Tasks in einem verteilten System bereit gestellt, die ihre Stärken unter jeweils verschiedenen Randbedingungen voll entfalten und somit ein breites Anwendungsfeld abdecken. Für den Rechenzeitaufwand beider Ansätze können Schranken angegeben werden, was sie für den Einsatz in Echtzeitsystemen qualifiziert.
As an integral part of ALICE, the dedicated heavy ion experiment at CERN’s Large Hadron Collider, the Transition Radiation Detector (TRD) contributes to the experiment’s tracking, triggering and particle identification. Central element in the TRD’s processing chain is its trigger and readout processor, the Global Tracking Unit (GTU). The GTU implements fast triggers on various signatures, which rely on the reconstruction of up to 20 000 particle track segments to global tracks, and performs the buffering and processing of event raw data as part of a complex detector readout tree.
The high data rates the system has to handle and its dual use as trigger and readout processor with shared resources and interwoven processing paths require the GTU to be a unique, high-performance parallel processing system. To achieve high data taking efficiency, all elements of the GTU are optimized for high running stability and low dead time.
The solutions presented in this thesis for the handling of readout data in the GTU, from the initial reception to the final assembly and transmission to the High-Level Trigger computer farm, address all these aspects. The presented concepts employ multi-event buffering, in-stream data processing, extensive embedded diagnostics, and advanced features of modern FPGAs to build a robust high-performance system that can conduct the high- bandwidth readout of the TRD with maximum stability and minimized dead time. The work summarized here not only includes the complete process from the conceptual layout of the multi-event data handling and segment control, but also its implementation, simulation, verification, operation and commissioning. It also covers the system upgrade for the second data taking period and presents an analysis of the actual system performance.
The presented design of the GTU’s input stage, which is comprised of 90 FPGA-based nodes, is built to support multi-event buffering for the data received from the 18 TRD supermodules on 1080 optical links at the full sender aggregate net bandwidth of 2.16 Tbit/s. With careful design of the control logic and the overall data path, the readout on the 18 concentrator nodes of the supermodule stage can utilize an effective aggregate output bandwidth of initially 3.33 GiB/s, and, after the successful readout bandwidth upgrade, 6.50 GiB/s via 18 optical links. The high possible readout link utilization of more than 99 % and the intermediate buffering of events on the GTU helps to keep the dead time associated with the local event building and readout typically below 10%. The GTU has been used for production data taking since start-up of the experiment and ever since performs the event buffering, local event building and readout for the TRD in a correct, efficient and highly dependable fashion.
Die vorliegende Arbeit stellt ein organisches Taskverarbeitungssystem vor, das die zuverlässige Verwaltung und Verarbeitung von Tasks auf Multi-Core basierten SoC-Architekturen umsetzt. Aufgrund der zunehmenden Integrationsdichte treten bei der planaren Halbleiter-Fertigung vermehrt Nebeneffekte auf, die im Systembetrieb zu Fehler und Ausfällen von Komponenten führen, was die Zuverlässigkeit der SoCs zunehmend beeinträchtigt. Bereits ab einer Fertigungsgröße von weniger als 100 nm ist eine drastische Zunahme von Elektromigration und der Strahlungssensitivität zu beobachten. Gleichzeitig nimmt die Komplexität (Applikations-Anforderungen) weiter zu, wobei der aktuelle Trend auf eine immer stärkere Vernetzung von Geräten abzielt (Ubiquitäre Systeme). Um diese Herausforderungen autonom bewältigen zu können, wird in dieser Arbeit ein biologisch inspiriertes Systemkonzept vorgestellt. Dieses bedient sich der Eigenschaften und Techniken des menschlichen endokrinen Hormonsystems und setzt ein vollständig dezentrales Funktionsprinzip mit Selbst-X Eigenschaften aus dem Organic Computing Bereich um. Die Durchführung dieses organischen Funktionsprinzips erfolgt in zwei getrennten Regelkreisen, die gemeinsam die dezentrale Verwaltung und Verarbeitung von Tasks übernehmen. Der erste Regelkreis wird durch das künstliche Hormonsystem (KHS) abgebildet und führt die Verteilung aller Tasks auf die verfügbaren Kerne durch. Die Verteilung erfolgt durch das Mitwirken aller Kerne und berücksichtigt deren lokale Eignung und aktueller Zustand. Anschließend erfolgt die Synchronisation mit dem zweiten Regelkreis, der durch die hormongeregelte Taskverarbeitung (HTV) abgebildet wird und einen dynamischen Task-Transfer gemäß der aktuellen Verteilung vollzieht. Dabei werden auch die im Netz verfügbaren Zustände von Tasks berücksichtigt und es entsteht ein vollständiger Verarbeitungspfad, ausgehend von der initialen Taskzuordnung, hinweg über den Transfer der Taskkomponenten, gefolgt von der Erzeugung der lokalen Taskinstanz bis zum Start des zugehörigen Taskprozesses auf dem jeweiligen Kern. Die System-Implementierung setzt sich aus modularen Hardware- und Software-Komponenten zusammen. Dadurch kann das System entweder vollständig in Hardware, Software oder in hybrider Form betrieben und genutzt werden. Mittels eines FPGA-basierten Prototyps konnten die formal bewiesenen Zeitschranken durch Messungen in realer Systemumgebung bestätigt werden. Die Messergebnisse zeigen herausragende Zeitschranken bezüglich der Selbst-X Eigenschaften. Des Weiteren zeigt der quantitative Vergleich gegenüber anderen Systemen, dass der hier gewählte dezentrale Regelungsansatz bezüglich Ausfallsicherheit, Flächen- und Rechenaufwand deutlich überlegen ist.
Effiziente kryptographische Algorithmen sind ein wichtiger Grundstein für viele neue Anwendungen, wie zum Beispiel das Internet der Dinge (IoT) oder kontaktlose Zahlungssysteme. Daher ist es wichtig, dass neue Algorithmen mit verbesserten Sicherheitseigenschaften und speziellen Leistungseigenschaften entwickelt und analysiert werden. Ein Beispiel ist der aktuelle Trend zu leichtgewichtigen Algorithmen. Diese Entwicklungen erleichtern die Implementierung neuartiger Systeme und ermöglichen auch einen Schutz von bestehenden Systemen durch eine Anpassung auf den neuesten Stand der Technik. Neben der kryptologischen Analyse, ist die Bewertung von Implementierungs-Aspekten sehr wichtig, damit eine realistische Einschätzung der erzielbaren Leistung möglich ist.
Daher müssen für jeden neuen Algorithmus unterschiedliche Software- und Hardwarearchitekturen evaluiert werden. Die systematische Bewertung von Software-Implementierungen für unterschiedliche Hardware-Architekturen hat in den letzten Jahren große Fortschritte gemacht, zum Beispiel durch den SHA-3 Wettbewerb. Im Vergleich dazu ist die Evaluation für Hardware-Plattformen wie z.B. FPGAs weiterhin sehr zeitaufwendig und fehleranfällig. Dies liegt an vielen Faktoren, z.B. an den mannigfaltigen Möglichkeiten der verschiedenen Zieltechnologien. Ein möglicher Verbesserungsansatz besteht darin, die Bewertung mit einem abstrakteren Ansatz zu beginnen, um interessante Architekturen und Implementierungen anhand von theoretischen Eigenschaften auszuwählen.
Der erste Hauptbeitrag dieser Arbeit ist die Entwicklung einer abstrakten Bewertungsmethodik, die auf einem theoretischen Modell von getakteten Schaltungen basiert. Das Modell verbessert das Verständnis von Grundeigenschaften dieser Schaltungen und erleichtert auch die abstrakte Modellierung von Architekturen für einen spezifischen Algorithmus. Wenn mehrere verschiedene Architekturen für den gleichen Algorithmus ausgewertet werden, ist es auch möglich zu bestimmen, ob ein Algorithmus gut skaliert. Beispielsweise können Auswirkungen einer Verkleinerung des Datenpfades auf die Größe des Speicherverbrauchs analysiert werden. Basierend auf der entwickelten Methodik können wichtige Eigenschaften, wie der Speicherbedarf, die Anzahl an Taktzyklen oder die Pipeline-Tiefe systematisch bewertet werden. Damit kann eine grobe Schätzung für die Effektivtät einer Architektur abgeleitet werden.
Die Performance-Abschätzung wird auch durch ein theoretisches Konzept der Optimalität der Anzahl an Taktzyklen untermauert. Optimal in diesem Sinne ist eine Architektur, wenn sie verzögerungsfrei ist, d.h. keine Wartezyklen benötigt. Durch die Betrachtung von Datenabhängigkeiten zwischen den einzelnen Runden kann eine minimale und maximale Anzahl an Taktzyklen ermittelt werden. Eine Verletzung dieser Grenzen würde bedeuten, dass die Berechnung der Runden-Funktion nicht alle Ausgangs-Bits produziert hat, wenn diese für die nächste Runde benötigt werden und somit würden Wartezyklen entstehen.
Der zweite Beitrag der Dissertation nutzt die Analysemethodik für mehrere Hash-Funktion. Es werden sechs Hash-Funktionen bewertet: BLAKE, Grøstl, Keccak, JH, Skein und Photon. Die ersten fünf Hash-Funktionen sind die Finalisten des SHA-3 Wettbewerb. Die SHA-3 Finalisten haben eine hohe Sicherheit als oberstes Design-Ziel und nur in zweiter Linie eine hohe Performance. Im Gegensatz dazu wurde Photon für leichtgewichtige Anwendungen konzipiert, z.B. RFID-Tags. Dazu wurde auch die Sicherheit von Photon reduziert. Für jeden Algorithmus wird eine oder mehrere mögliche Organisationensformen des Speichers entwickelt. Als nächstes wird die Anzahl von Taktzyklen auf der Grundlage der Speicherorganisation ermittelt. Das generelle Ziel dabei ist die Entwicklung von Architekturen mit einer optimalen Anzahl von Taktzyklen. Die Diskussion konzentriert sich als nächstes auf verschiedene Möglichkeiten die Runden-Funktion optimal umzusetzen. Das Ergebnis der Evaluierung umfasst mindestens die Schätzung der minimalen Speicheranforderung, die analysierte Pipeline-Tiefe und den theoretischen Durchsatz für lange Nachrichten mit einer festgelegten Taktfrequenz. Diese Ergebnisse lassen eine Einschätzung über die mögliche Leistung der jeweiligen Architekturen zu.
Der dritte Beitrag der Arbeit besteht aus mehreren Implementierungs-Ergebnissen. Zunächst werden Ergebnisse für die SHA-3 Finalisten BLAKE, Grøstl, JH, Keccak und Skein gezeigt. Von den fünf Algorithmen haben alle außer Skein eine relativ hohe Performanz, während Skein abgeschlagen ist. Eine weitere Untersuchung konzentriert sich auf kleinere Implementierungen des SHA-3 Siegers Keccak. Dazu gehören auch nicht standardisierte Varianten mit einem kleineren Zustand. Diese kleineren Versionen werden mit ersten FPGA-Ergebnissen für die Photon Hash-Funktion verglichen. Eine wesentliche Erkenntnis davon ist, dass Keccak auch für FPGA-Anwendungen mit beschränktem Ressourcen-Bedarf prinzipiell sehr wettbewerbsfähig ist.
Ein Ansatz für semantisches Selbstmanagement von verteilten Anwendungen im privaten Lebensumfeld
(2014)
Die Anreicherung des privaten Lebensumfelds mit intelligenten technischen Assistenzsystemen wird in den nächsten Jahrzehnten stark zunehmen. Als Teil dieser Entwicklung wird die Nutzung von externen und hauseigenen IT-Diensten steigen, wodurch sich auch die Komplexität der entstehenden Gesamtsysteme erhöht. Hier sind Ansätze gefordert, diese Systeme auch für technisch nicht versierte Benutzer produktiv nutzbar und beherrschbar zu gestalten, um eine Überforderung zu vermeiden. Im Umfeld häuslicher Dienstplattformen, die eine zentrale Rolle in solchen Systemen übernehmen, nimmt seit ein paar Jahren die Bedeutung der semantischen Modellierung von Diensten stark zu. Diese dient zum einen der formalen Repräsentation von zugehörigen Kontextinformationen, die durch Interaktion mit Sensoren und Aktoren entstehen, und zum anderen der Verbesserung der Interoperabilität zwischen Systemen unterschiedlicher Hersteller. Bisherige Ansätze beschränken sich jedoch auf den Einsatz eines zentralen Rechenknotens zur Ausführung der Dienstplattform und nutzen Semantik – wenn überhaupt – nur zur Verarbeitung von Kontextinformationen. Ein technisches Management des Gesamtsystems findet i.d.R. nicht statt.
Vor diesem Hintergrund ist das Ziel dieser Arbeit die Entwicklung eines Ansatzes für semantisches Selbstmanagement von verteilten dienstbasierten Anwendungen speziell im Umfeld häuslicher Dienstplattformen.
Die vorliegende Arbeit definiert zunächst formale Ontologien für Dienste, Dienstgütemanagement, Selbstmanagement und zugehörige Managementregeln, die zur Laufzeit mit konkreten Diensten und deren erfassten Leistungskenngrößen integriert werden. Durch einen modellgetriebenen Architekturansatz (Model Driven Architecture, MDA) wird ein technologieunabhängiges Management auf abstrakter Ebene ermöglicht, das die Wiederverwendbarkeit von Managementregeln in anderen Szenarien erlaubt.
Dieser Ansatz wird zunächst in eine Architektur für einen hochverfügbaren autonomen Manager überführt, der die Überwachung und Steuerung von Diensten und zugehörigen Dienstplattformen übernehmen kann und auf der aus dem Autonomic Computing bekannten MAPE-K-Kontrollschleife (Monitor, Analyze, Plan, Execute, Knowledge) basiert.
Den Abschluss der Arbeit bildet eine qualitative und quantitative Evaluation (mittels einer OSGi-basierten prototypischen Umsetzung) der erreichten Ergebnisse, die einen Einsatz über die Grenzen des privaten Lebensumfelds hinaus nahelegen.
Hierarchical self-organizing systems for task-allocation in large scaled distributed architectures
(2019)
This thesis deals with the subject of autonomous, decentralized task allocation in a large scaled multi-core network. The self-organization of such interconnected systems becomes more and more important for upcoming developments. It is to be expected that the complexity of those systems becomes hardly manageable to human users. Self-organization is part of a research field of the Organic Computing initiative, which aims to find solutions for technical systems by imitating natural systems and their processes. Within this initiative, a system for task allocation in a small scaled multi-core network was already developed, researched and published. The system is called the Artificial Hormone System (AHS), since it is inspired by the endocrine system of mammals. The AHS produces a high amount of communication load in case the multi-core network is of a bigger scale.
The contribution of this thesis is two new approaches, both based on the AHS in order to cope with large scaled architectures. The major idea of those two approaches is to introduce a hierarchy into the AHS in order to reduce the produced communication load. The first and more detailed researched approach is called the Hierarchical Artificial Hormone System (HAHS), which orders the processing elements in clusters and builds an additional communication layer between them. The second approach is the Recursive Artificial Hormone System (RAHS), which also clusters the system’s processing elements and orders the clusters into a topological tree structure for communication.
Both approaches will be explained in this thesis by their principle structure as well as some optional methods. Furthermore, this thesis presents estimations for the worst case timing behavior and the worst-case communication load of the HAHS and RAHS. At last, the evaluation results of both approaches, especially in comparison to the AHS, will be shown and discussed.
Eingebettete Systeme sind Rechnersysteme, die in einem technischen Umfeld eingebettet sind und dort ihre Arbeit verrichten. Kennzeichen heutiger und zukünftiger eingebetteter Systeme sind, dass sie in einer immer größeren Anzahl in der Industrie, im Haushalt und in Büros, in Eisenbahnen und Flugzeugen und in vielen weiteren Umgebungen auftreten. Sie sind oftmals stark vernetzt und müssen hochverlässlich sein, um Unfälle zu vermeiden und so Anwender und Nutzer vor Schaden zu bewahren. Die Beherrschung dieser eingebetteten Systeme ist meist hochkomplex, da durch die Vernetzung eine Vielzahl von Komponenten zusammenarbeiten. Für den Anwender ist es daher schwer, den Überblick zu behalten. Im Hinblick auf die Verlässlichkeit ist es wichtig, Reaktionen auf Fehler und unvorhergesehene Situationen in diesen Systemen innerhalb definierter Zeitschranken zu liefern, um Schaden zu vermeiden.
Selbstorganisation wird heutzutage als probates Mittel angesehen, um die Herausforderungen, die sich mit der Inbetriebnahme, Nutzung und Instandhaltung von komplexen eingebetteten Systemen ergeben, zu meistern. Der Beitrag dieser Arbeit ist eine Untersuchung selbstorganisierender eingebetteter Systeme:
Im ersten Teil wird ein Überblick über den aktuellen Stand der Forschung bei eingebetteten Systemen sowie über den Bereich der Selbstorganisation für eingebettete Systeme gegeben. Dabei wird die Idee des Organic Computings beschrieben, welches sich mit Selbstorganisationsprinzipien in IT-Systemen beschäftigt, und es werden aktuelle Forschungstrends dazu beschrieben.
Im zweiten Teil der Arbeit werden eigene Arbeiten im Feld von selbstorganisierenden eingebetteten Systemen vorgestellt. Sie behandeln verschiedene Aspekte eines künstlichen Hormonsystems (KHS), welches zur selbstorganisierten Verteilung von Tasks auf einer Menge von vernetzten Prozessoren genutzt werden kann. Dabei werden einerseits grundlegende Definitionen des Organic Computings im Bezug auf das KHS untersucht und bewertet. Andererseits werden neue Lerntechniken für das KHS untersucht, die sich am maschinellen Lernen orientieren. Außerdem wird ein mehrstufiges KHS entwickelt und evaluiert, um die Vergabe einer sehr großen Anzahl von Tasks (≥ 1000) auf einer sehr großen Anzahl von Prozessoren (≥ 10000) zu ermöglichen.
Die allgemein steigende Komplexität technischer Systeme macht sich auch in eingebetteten Systemen bemerkbar. Außerdem schrumpfen die Strukturgrößen der eingesetzten Komponenten, was wiederum die Auftrittswahrscheinlichkeit verschiedener Effekte erhöht, die zu Fehlern und Ausfällen dieser Komponenten und damit der Gesamtsysteme führen können. Da in vielen Anwendungsbereichen ferner Sicherheitsanforderungen eingehalten werden müssen, sind zur Gewährleistung der Zuverlässigkeit flexible Redundanzkonzepte nötig.
Ein Forschungsgebiet, das sich mit Methoden zur Beherrschung der Systemkomplexität befasst, ist das Organic Computing. In dessen Rahmen werden Konzepte erforscht, um in natürlichen Systemen beobachtbare Eigenschaften und Organisationsprinzipien auf technische Systeme zu übertragen. Hierbei sind insbesondere sogenannte Selbst-X-Eigenschaften wie Selbstorganisation, -konfiguration und -heilung von Bedeutung.
Eine konkrete Ausprägung dieses Forschungszweigs ist das künstliche Hormonsystem (artificial hormone system, AHS). Hierbei handelt es sich um eine Middleware für verteilte Systeme, welche es ermöglicht, die Tasks des Systems selbstständig auf seine Prozessorelemente (PEs) zu verteilen und insbesondere Ausfälle einzelner Tasks oder ganzer PEs automatisch zu kompensieren, indem die betroffenen Tasks auf andere PEs migriert werden. Hierbei existiert keine zentrale Instanz, welche die Taskverteilung steuert und somit einen Single-Point-of-Failure darstellen könnte. Entsprechend kann das AHS aufgrund seiner automatischen (Re)konfiguration der Tasks als selbstkonfigurierend und selbstheilend bezeichnet werden, was insbesondere die Zuverlässigkeit des realisierten Systems erhöht. Die Dauer der Selbstkonfiguration und Selbstheilung unterliegt zudem harten Zeitschranken, was den Einsatz des AHS auch in Echtzeitsystemen erlaubt.
Das AHS nimmt jedoch an, dass alle Tasks gleichwertig sind, zudem werden alle Tasks beim Systemstart in einer zufälligen Reihenfolge auf die einzelnen PEs verteilt. Häufig sind die in einem System auszuführenden Tasks jedoch für das Gesamtsystem von unterschiedlicher Wichtigkeit oder müssen gar in einer bestimmten Reihenfolge gestartet werden.
Um den genannten Eigenschaften Rechnung zu tragen, liefert diese Dissertation gegenüber dem aktuellen Stand der Forschung folgende Beiträge:
Zunächst werden die bisher bekannten Zeitschranken des AHS genauer betrachtet und verfeinert.
Anschließend wird das AHS durch die Einführung von Zuteilungsprioritäten erweitert: Mithilfe dieser Prioritäten kann eine Reihenfolge definiert werden, in welcher die Tasks beim Start des Systems auf die PEs verteilt beziehungsweise in welcher betroffene Tasks nach einem Ausfall auf andere PEs migriert werden.
Die Zeitschranken dieser AHS-Erweiterung werden im Detail analysiert.
Durch die Priorisierung von Tasks ist es möglich, implizit Teilmengen von Tasks zu definieren, die ausgeführt werden sollen, falls die Rechenkapazitäten des Systems nach einer bestimmten Anzahl von PE-Ausfällen nicht mehr ausreichen, um alle Tasks auszuführen: Die im Rahmen dieser Dissertation entwickelten Erweiterungen erlauben es in solchen Überlastsituationen, das System automatisch und kontrolliert zu degradieren, sodass die wichtigsten Systemfunktionalitäten lauffähig bleiben.
Überlastsituationen werden daher im Detail betrachtet und analysiert. In solchen müssen gegebenenfalls Tasks niedriger Priorität gestoppt werden, um auf den funktionsfähig verbleibenden PEs hinreichend viel Rechenkapazität zu schaffen, um Tasks höherer Priorität ausführen zu können und das System so in einen wohldefinierten Zustand zu überführen. Die Entscheidung, in welcher Reihenfolge hierbei Tasks gestoppt werden, wird von einer Task-Dropping-Strategie getroffen, die entsprechend einen großen Einfluss auf die Dauer einer solchen Selbstheilung nimmt.
Es werden zwei verschiedene Task-Dropping-Strategien entwickelt und im Detail analysiert: die naive Task-Dropping-Strategie, welche alle niedrigprioren Tasks auf einmal stoppt, sowie das Eager Task Dropping, das in mehreren Phasen jeweils höchstens eine Task pro PE stoppt. Im Vergleich zeigt sich, dass von letzterem fast immer weniger Tasks gestoppt werden als von der naiven Strategie, was einen deutlich schnelleren Abschluss der Selbstheilung ermöglicht. Lediglich in wenigen Sonderfällen ist die naive Strategie überlegen.
Es wird detailliert gezeigt, dass die entwickelte AHS-Erweiterung auch in Überlastsituationen die Einhaltung bestimmter harter Zeitschranken garantieren kann, was den Einsatz des erweiterten AHS in Echtzeitsystemen erlaubt.
Alle theoretisch hergeleiteten Zeitschranken werden durch umfassende Evaluationen vollumfänglich bestätigt.
Abschließend wird das erweiterte, prioritätsbasierten AHS mit verschiedenen verwandten Konzepten verglichen, um dessen Vorteile gegenüber dem Stand der Forschung herauszuarbeiten sowie zukünftige vertiefende Forschung zu motivieren.
