Coscheduling in the multicore era
| dc.contributor.advisor | Heiß, Hans-Ulrich | |
| dc.contributor.author | Schönherr, Jan Hendrik | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Heiß, Hans-Ulrich | |
| dc.contributor.referee | Richling, Jan | |
| dc.contributor.referee | Polze, Andreas | |
| dc.date.accepted | 2019-06-19 | |
| dc.date.accessioned | 2019-10-07T09:57:53Z | |
| dc.date.available | 2019-10-07T09:57:53Z | |
| dc.date.issued | 2019 | |
| dc.description.abstract | In its most general definition, coscheduling refers to a deliberate simultaneous execution of certain tasks on multiple CPUs. The concepts of coscheduling and gang scheduling have been introduced in the early eighties and nineties, respectively. At that time, the first massively parallel systems were developed and became more widely used. The guarantee of simultaneous execution of certain tasks allows to make use of fine-grained synchronization efficiently: it is impossible for a currently executing task to wait for another task that does not make progress. Compared to batch processing and partitioning in space, coscheduling allows to preempt a running parallel application in favor of another more important application. This context switch at application level offers more flexibility for schedulers. Since then, there have been thorough changes in the computing landscape: (non-parallel) personal computers have penetrated the market, and with it, parallelism had become a second-class citizen. Parallelism has only recently become important again, after single-thread performance could not be increased by the usual margins anymore. However, parallelism today differs from parallelism back then, mostly because of the following two reasons: 1. The reintroduction of parallel systems happened not overnight but as a gradual process. Due to this, existing software was adapted to run on parallel systems instead of being rewritten. This adapted software handles contemporary multicore systems as if they were distributed systems instead of the parallel systems they are: current operating systems have no concept of a parallel application; they do not know about coscheduling or other management approaches, hampering real parallel applications. To make matter worse, budding software developers (outside of the HPC niche) are seldom taught the subtleties of parallel software development. 2. The properties of today’s multicore architectures differ substantially from early parallel systems and clusters. For this reason it is not always possible to reuse once valid solutions. In particular, CPUs in today’s system have to share a multitude of resource, such as memory bandwidth of caches. This results in resource contention with a more or less noticeable impact on performance of individual tasks. In most cases research suggests to avoid or reduce resource contentions by grouping tasks skillfully – which is basically a form of coscheduling. However, an integration of these research ideas into existing systems is impractical more often than not, because individual ideas – while solving their specific use case – are difficult to combine with their rather narrow focus. This thesis is ports the concept coscheduling to contemporary multicore architectures. Advantages and disadvantages known from other parallel architectures are reevaluated, and a catalog of use cases – old and new – is compiled. The combined requirements of these use cases form the basis for a versatile coscheduling model. A flexible coscheduling approach is devised, which measures up to today’s expectations of application and operating system developers alike. In particular, a method is included that allows to integrate coscheduling functionality into existing general purpose schedulers without changing their characteristic traits substantially. Newly enabled management opportunities within the operating system are discussed and their influence on the design of upcoming parallel applications and operating systems are explored. | en |
| dc.description.abstract | Der Begriff Coscheduling bezeichnet in seiner weitesten Definition die bewusst gleichzeitige Ausführung ausgewählter Tasks auf mehreren CPUs. Coscheduling und der verwandte Begriff Gang Scheduling wurden in den 80er bzw. 90er Jahren geprägt, als die ersten Mehrprozessorsysteme entwickelt wurden, bzw. sie weitere Verbreitung fanden. Die garantierte gleichzeitige Ausführung von bestimmten Tasks erlaubt die effiziente Realisierung von feingranularer Synchronisation und Kommunikation, ohne dass es zu möglicherweise langen Wartezeiten kommt, weil auf einen gerade nicht laufenden Task gewartet werden muss. Im Vergleich zu beispielsweise Stapelverarbeitung oder der Partitionierung des Systems im Raum erlaubt es Coscheduling, die gerade laufende parallele Anwendung zu Gunsten einer anderen zu unterbrechen, wodurch Schedulingverfahren nun nicht mehr auf einzelnen sequentiellen Tasks operieren, sondern auf ganzen parallelen Anwendungen. Seitdem hat sich die IT-Landschaft deutlich weiterentwickelt: aufgrund des Siegeszugs des (nicht parallelen) PCs ist die Thematik Parallelität zunächst in den Hintergrund getreten. Erst als weitere Taktsteigerungen nicht mehr möglich waren, wurde Parallelität wieder interessant. Im Vergleich zu früher gibt es allerdings zwei bedeutende Unterschiede: 1. Durch die vergleichsweise langsame Wiedereinführung von parallelen Systemen fand keine Neuentwicklung von Software statt, sondern eine Adaption. Damit werden aktuelle Mehrkernsysteme eher als verteiltes System denn als paralleles System behandelt: aktuelle Betriebssysteme kennen das Konzept einer parallelen Anwendung nicht; Coscheduling und andere Managementansätze sind ihnen fremd, worunter die Ausführung tatsächlich paralleler Anwendungen leidet. Zudem wird herangehenden Softwareentwicklern (außerhalb der HPC-Nische) die Entwicklung entsprechender Software selten nahe gebracht. 2. Aktuelle Mehrkernsysteme unterscheiden sich in ihrer Architektur stark von frühen parallelen Systemen und Clustern. Dies führt dazu, dass sich die Lösungen von damals nicht ohne weiteres auf heutige Systeme übertragen lassen. Inbesondere gibt es in heutigen Systemen diverse Ressourcen, die sich mehrere CPUs teilen müssen, wie z. B. Speicherbandbreite oder Caches. Dies führt zu Ressourcenengpässen, die zu mehr oder weniger starken Leistungseinbußen individueller Tasks führen können. Die Forschung schlägt hier zumeist ein geschicktes Gruppieren von Tasks vor, so dass Ressourcenengpässe nach Möglichkeit minimiert werden – im Prinzip eine andere Form von Coscheduling. Während jeder Vorschlag für sich seine Daseinsberechtigung hat, ist eine Integration in bestehende Systeme meist unpraktikabel, da der Fokus oft eingeschränkt ist und die verschiedenen Ideen in Konflikt miteinander stehen. In dieser Dissertation wird das Konzept Coscheduling auf heutige Mehrkernsysteme übertragen und adaptiert. Die früher gültigen Vor- und Nachteile werden neu bewertet und alte wie neue Anwendungsszenarien betrachtet. Aus einem Anforderungskatalog heraus wird ein Coschedulingverfahren konzipiert, das den heutigen Erwartungen von Anwendungs- und Betriebssystementwicklern gerecht wird. Es wird eine Methode dargelegt, wie besagtes Verfahren in bestehende Betriebssysteme integriert werden kann, ohne dass es zu einer wesentlichen Verhaltensänderung des ursprünglichen Schedulers kommt. Es wird gezeigt, welche neuen Managementmöglichkeiten sich dadurch für das Betriebssystem ergeben und welchen Einfluss dies in Zukunft auf die Entwicklung paralleler Anwendungen und Betriebssysteme haben wird. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/9896 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-8908 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 004 Datenverarbeitung; Informatik | de |
| dc.subject.other | coscheduling | en |
| dc.subject.other | multicore | en |
| dc.subject.other | scheduling | en |
| dc.subject.other | operating systems | en |
| dc.subject.other | Coscheduling | de |
| dc.subject.other | Multicore | de |
| dc.subject.other | Scheduling | de |
| dc.subject.other | Betriebssysteme | de |
| dc.title | Coscheduling in the multicore era | en |
| dc.title.subtitle | the art of doing things simultaneously | en |
| dc.title.translated | Coscheduling im Multicore-Zeitalter | de |
| dc.title.translatedsubtitle | die Kunst, Dinge gleichzeitig zu tun | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | domain | en |
| tub.affiliation | Fak. 4 Elektrotechnik und Informatik::Inst. Telekommunikationssysteme::FG Kommunikations- und Betriebssysteme | de |
| tub.affiliation.faculty | Fak. 4 Elektrotechnik und Informatik | de |
| tub.affiliation.group | FG Kommunikations- und Betriebssysteme | de |
| tub.affiliation.institute | Inst. Telekommunikationssysteme | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |