Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5653
Main Title: A dynamic and component-based process scheduler framework for heterogeneous many-core systems
Translated Title: Ein dynamisches und komponenten-basiertes Prozessablaufplanungs-Framework für heterogene Many-Core Systeme
Author(s): Busse, Anselm
Advisor(s): Heiß, Hans-Ulrich
Referee(s): Heiß, Hans-Ulrich
Mühl, Gero
De Rose, César
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: Since the first decade of the 21st century, improvements in computer performance are no longer achieved through increasing clock rates but parallelization and specialization. As a result, heterogeneous many-core systems are becoming more and more common. Leaving their niche in highly specialized computing, they have to be supported by a general purpose operating system. A major part of the support that has to be delivered will be done by the process scheduler as it has to tailor the task order and placement to those systems. Current approaches to scheduler architecture are not capable of coping with the resulting challenges. In particular, the state of the art falls short to provide ways and means to react to new developments in hardware technology quickly and lacks the capability to enable the adaptation of the scheduler to the changed environment. Therefore, the original contribution to the knowledge of this dissertation is a new approach to the architecture of the operating system's process scheduler. This dissertation introduces a component-based approach to the process scheduler architecture that allows the decomposition of the scheduling problem into distinct parts rather than the monolithic approach as it is state of the art. Components are connected through Pipes that are an advanced form of runqueues suitable for the component-based approach. Besides Pipes, information is distributed among the components through a publish–subscribe-based message system. Components can change the order of tasks and distribute or merge tasks from or to several pipes. This allows a flexible scheduler design both during development and runtime: The developer can reuse existing components and build new schedulers from existing implementations. Through the explicit layout of the components code-paths, possible bottlenecks become easier to identify compared to a monolithic approach. Through the separation, it is also feasible to change the entire scheduling policy during runtime. This enables an optimal shaping of the scheduler to the needs of the current working set and the properties of the underlying hardware architecture. The components are embedded into a framework that allows a comprehensible development of schedulers that scale even in many-core systems. The framework approach permits the integration into several runtime systems without changing the actual scheduler implementation. This dissertation proves the feasibility through integrating the framework into major open source kernels: Linux and FreeBSD. Based on this exemplary implementation, the properties of the approach are evaluated. The studies show that the component-based scheduler framework is scalable for hundreds of cores, the overhead is quantified and the benefits of having well-defined interfaces are demonstrated. Finally, the advantages of a dynamic adaptation of scheduling strategies at runtime are shown.
Leistungssteigerungen in Computern werden seit dem ersten Jahrzehnt des 21. Jahrhunderts nicht mehr durch fortlaufende Erhöhung der Taktfrequenzen erreicht, sondern durch zunehmende Parallelisierung und Spezialisierung. Auf Grund dessen gewinnen heterogene Many-Core-Systeme zunehmend an Bedeutung. Somit müssen auch zunehmend Betriebssysteme Unterstützung bieten. Eine wichtige Rolle hierbei wird die Prozessablaufplanung und -zuordnung spielen, die für diese Systeme angepasst werden müssen. Aktuelle Architekturen für die Implementierung der Prozessablaufplanung können mit den resultierenden Herausforderungen nicht Schritt halten. Insbesondere ist es beim aktuellen Stand der Technik nicht möglich, auf Innovationen im Hardwarebereich rasch zu reagieren und die Prozessablaufplanung an die neuen Gegebenheiten anzupassen. Aus diesem Grund besteht der Beitrag zur Wissenschaft dieser Dissertation in einer neuartigen Architektur für die Prozessablaufplanung. Diese Arbeit präsentiert einen neuen komponenten-basierten Ansatz zur Architektur der Prozessablaufplanung, welcher die Aufteilung des Planungsalgortithmuses in Komponenten erlaubt. Komponenten werden durch Pipes verbunden, welche eine Weiterentwicklung der bisher verwendeten Runqueues darstellen. Ferner werden Informationen unter den Komponenten durch ein publish-subscribe-basiertes Nachrichtensystem verbreitet. Komponenten können die Reihenfolge und die Verteilung der eingehenden Prozesse auf die ausgehenden Pipes bestimmen. Der Entwickler kann bestehende Komponenten wiederverwenden und neue Prozessablaufplanungsimplementierungen aus bestehenden erzeugen. Die vorgestellte Architektur erlaubt das einfache Auffinden von Flaschenhälsen durch ein expliziteres Layout des Prozessplaners verglichen zum monolithischen Ansatz. Ferner erlaubt die Architektur durch ihre expliziten Schnittstellen die Änderung der Planungsimplementierung zur Laufzeit. Der Prozessablaufplaner wird hierdurch optimal auf die Gegebenheiten des Systems angepasst. Die Komponenten sind in ein Framework eingebettet, welches die transparente Entwicklung von Prozessplanungsimplementierungen ermöglicht. Der framework-basierte Ansatz erlaubt die einfache Einbindung bestehender Implementierungen ohne größere Änderungen in verschiedenen Laufzeitumgebungen. Diese Dissertation demonstriert die Machbarkeit des Ansatzes durch die Integration in zwei der größten offenen Betriebssystemkerne: Linux und FreeBSD. Basierend auf dieser Beispielimplementierung werden im Verlauf dieser Arbeit die Eigenschaften des Ansatzes evaluiert und diskutiert. Die Arbeit zeigt, dass der Ansatz für hunderte von Rechenkernen skaliert, sie quantifiziert den Overhead des Ansatzes und stellt die Vorteile wohl definierter Schnittstellen in diesem Anwendungsbereich am Beispiel vor. Schlussendlich werden die Vorzüge des Wechselns der Planungsstrategie zur Laufzeit dargestellt.
URI: http://depositonce.tu-berlin.de/handle/11303/6072
http://dx.doi.org/10.14279/depositonce-5653
Exam Date: 13-Dec-2016
Issue Date: 2016
Date Available: 27-Dec-2016
DDC Class: DDC::000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::000 Informatik, Informationswissenschaft, allgemeine Werke
Subject(s): process scheduling
operating systems
many-core systems
heterogeneous systems
Prozessablaufplanung
Betriebssysteme
Many-Core Systeme
heterogene Systeme
Creative Commons License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Telekommunikationssysteme » Publications

Files in This Item:
File Description SizeFormat 
busse_anselm.pdf2.69 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.