The computing power of single-core computers, which has previously been boosted by techniques such as pipelining, super-scalar execution units and out-of-order execution, can no longer keep up with the advances of microchip manufacturing. The acceleration of sequential execution in increasingly complex computing cores is becoming less and less efficient as it causes very high power density, which in turn limits the achievable clock frequency. Microprocessors that pack lots of simpler, more efficient cores onto one chip pose a possible solution to this dilemma. Instead of spending the additional resources gained by each new generation of chip technology on trying to speed up sequential execution, many-core systems leverage the massively parallel execution of control flows to achieve a high computing throughput.

Compared to single-core computers, many-core systems require application software to follow a fundamentally different approach: Software must formulate its application problem as a parallel program so that there are enough control flows to utilise the parallel hardware. Avoiding serial parts of execution is of particular importance as it directly limits the achievable speedup that can be gained through parallelisation.

Invasive Computing is a programming paradigm that has explicitly been designed for the execution of parallel applications on many-core systems. It is based on a notion of cooperative contest between applications to divide up the many-core system among them. The applications formulate their resource demand in an abstract way and act resource aware when dealing with resource assignment. This implies that they do not strictly insist on the exact amount of resources they initially demanded, but instead act flexibly and deal with deviating resource allocations, so that they are still able to fulfil their original purpose. This process is carried out continuously during the whole runtime of an invasive application and enables it to update its resource demand depending on its current need, which may vary between different computing phases.

The invasive hardware architecture serves as a basis for invasive computing. It is a tiled many-core architecture whose primary building block is a tile consisting of a number of computing cores and local memory. Each tile is relatively independent of its peers and the whole system is formed by a loose coupling employing a meshed network on chip. Communication between tiles is performed using special operations supplied by the network-on-chip hardware that enables the software to exchange messages between tiles. This loose coupling allows to increase the total number of cores by adding additional tiles to the system.

The goal of this thesis is to provide lightweight operating-system support for such invasive applications running on the invasive hardware architecture. The foundation of OctoPOS, the operating system developed specifically for that purpose, is laid by designing an application model explicitly tailored towards executing invasive applications. The resource awareness of the applications enables OctoPOS to divide a many-core system into spatially separated partitions. Within these partitions, the applications can in turn gain full control over their computing resources. As part of the cooperative contest, applications can vary the size of their own partition by trying to add or subtract further resources depending on their own demand.

Spatial partitioning with the resulting direct access to the execution resources enables OctoPOS to provide a lightweight execution environment for the execution of the invasive applications themselves. The goal is to make the generation of new potentially parallel control flows as efficient as possible. This enables applications to benefit even from the parallelisation of short sections of possible parallel execution. To achieve this also on a global scale on the tiled invasive hardware architecture, OctoPOS employs a strategy of co-design between hardware and system software. The resulting interfaces and mechanisms enable OctoPOS to scale, even when creating additional control flows outside of the local tile. The co-design brings down the additional overhead imposed by such operations to the mere latency caused by the network-on-chip hardware and prevents disturbing already running programs on the target tile.

Die Rechenleistung von Einkernrechensystemen, welche in der Vergangenheit durch den Einsatz von Techniken wie Fließbandverarbeitung, superskalaren Ausführungseinheiten oder das Umordnen von Befehlssequenzen zur Laufzeit immer weiter gesteigert werden konnte, kann dem Fortschritt bei der Fertigung von Mikroprozessoren nicht mehr folgen. Die Beschleunigung der sequenziellen Ausführung durch immer komplexere Rechenkerne wirft dabei immer weniger Ertrag ab und die dadurch verursachte hohe Leistungsdichte bildet eine Grenze für die Steigerung der Taktfrequenzen. Einen möglichen Ausweg bilden Mikroprozessoren, welche aus einer Vielzahl von einfacher gehaltenen aber dafür effizienteren Rechenkernen bestehen. Anstatt die zusätzlichen Ressourcen, welche mit jeder neuen Generation der Chipfertigung freigesetzt werden, in die immer ineffizienter werdende Beschleunigung der sequenziellen Ausführung zu investieren, setzen solche Vielkernrechner auf eine massiv parallele Ausführung von Kontrollflüssen, um eine hohe Rechenleistung zu erhalten.

Im Vergleich zu sequenziell arbeitenden Rechnern stellen Vielkernrechner an die Software fundamental andere Anforderungen: Die Software muss ihr Problem als paralleles Programm derart formulieren, dass genügend ausführbare Kontrollflüsse bereitstehen, um die parallele Hardware mit Aufgaben versorgen zu können. Insbesondere die Vermeidung von seriellen Anteilen ist von großer Wichtigkeit, da diese die Effizienz bei der Beschleunigung der Ausführung grundlegend begrenzen.

Invasives Rechnen ist ein Programmierparadigma, welches explizit im Hinblick auf die Ausführung paralleler Anwendungen auf einem Vielkernrechner entworfen ist. Es basiert auf einem Modell des kooperativen Wettstreites der Anwendungen untereinander, um zu einer Aufteilung des parallelen Rechensystems zu gelangen. Die Anwendungen bringen ihren Ressourcenbedarf dabei in abstrakter Form zum Ausdruck und verhalten sich im Rahmen des Wettstreites ressourcengewahr. Dies bedeutet, dass sie nicht starr auf ihren Ressourcenforderungen bestehen, sondern flexibel auf die tatsächlich erfolgte Zuteilung reagieren und sich an diese anpassen können, um ihren eigentlichen Anwendungszweck zu erfüllen. Dieser Prozess begleitet eine invasive Anwendung während ihrer gesamten Laufzeit, so dass sie in unterschiedlichen Phasen ihrer Ausführung einen wechselnden Ressourcenbedarf zum Ausdruck bringen kann.

Als Basis des invasiven Rechnens dient die invasive Hardwarearchitektur, welche einen gekachelt aufgebauten Vielkernrechner beschreibt. Den Grundbaustein bildet die Kachel, welche ein in sich abgeschlossenes Rechensystem aus einer Anzahl von Rechenkernen und lokalem Speicher darstellt. Die einzelnen Kacheln sind lose miteinander über ein vermaschtes Netzwerk verbunden. Die Kommunikation zwischen den Kacheln wird dabei über vom Netzwerk bereitgestellte dedizierte Operationen abgewickelt, welche es erlauben Nachrichten zwischen den Kacheln auszutauschen. Diese lose Kopplung ermöglicht es über die Anzahl der Kacheln auch die insgesamt verfügbare Anzahl an Rechenkernen zu steigern.

Ziel dieser Arbeit ist es, eine leichtgewichtige Betriebssystemunterstützung für Anwendungen nach dem Modell des invasiven Rechnens auf der invasiven Hardwarearchitektur bereitzustellen. Die Grundlage für das zu diesem Zweck entwickelte Betriebssystem OctoPOS bildet der Entwurf eines explizit für die Ausführung von invasiven Anwendungen vorgesehenen Applikationsmodells. Die Ressourcengewahrheit der Anwendungen ermöglicht es hier, den Vielkernrechner in einzelne, räumlich getrennte Partitionen aufzuteilen und innerhalb dieser den Anwendungen direkte Kontrolle über die enthaltenen Rechenressourcen zu gewähren. Als Teil des kooperativen Wettstreites um Ressourcen können die Anwendungen dabei ihre eigene Partition im Laufe der Ausführung entsprechend vergrößern oder verkleinern.

Die räumliche Aufteilung und der damit verbundene direkte Zugriff auf die Ausführungsressourcen ermöglichen es OctoPOS, innerhalb der Partitionen ein leichtgewichtiges Ablaufmodell für die eigentliche Programmausführung der invasiven Anwendungen bereitzustellen. Ziel hierbei ist es, die Erzeugung von potentiell parallel ausführbaren Kontrollflüssen so effizient wie möglich zu gestalten. So kann auch aus kurzen Abschnitten paralleler Ausführung eine Beschleunigung durch Parallelisierung erreicht werden. Um dies auch für die gekachelt aufgebaute invasive Hardwarearchitektur zu ermöglichen, wird ein Ansatz zum Co-Design zwischen Hardware und Systemsoftware gewählt. Die dabei entworfenen Schnittstellen und Mechanismen versetzen OctoPOS in die Lage, die Erzeugung zusätzlicher paralleler Kontrollflüsse auch über die Grenzen der jeweiligen lokalen Kachel hinaus skalierbar zu halten. Dabei kann der Mehraufwand im Vergleich zur Erzeugung von Kontrollflüssen innerhalb der eigenen Kachel auf den reinen, durch das vermaschte Netzwerk verursachten Kommunikationsmehraufwand begrenzt und eine Störung der laufenden Ausführung am Zielort vermieden werden.