Enhancing the scalability of many-core systems towards utilizing fine-grain parallelism in task-based programming models
| dc.contributor.advisor | Juurlink, Ben | |
| dc.contributor.author | Dallou, Tamer | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Juurlink, Ben | |
| dc.contributor.referee | Labarta, Jesus | |
| dc.contributor.referee | Castrillon, Jeronimo | |
| dc.date.accepted | 2017-12-13 | |
| dc.date.accessioned | 2018-01-30T11:02:45Z | |
| dc.date.available | 2018-01-30T11:02:45Z | |
| dc.date.issued | 2017 | |
| dc.description.abstract | In the past few years, it has been foreseeable that Moore's law is coming to an end. This law, based on the observation that the number of transistors in an integrated chip doubles every 18-24 months, served as a roadmap for the semiconductors industry. On the verge of its end due to the huge increase in integrated chips power density, a new era in computing systems has begun. In this era, a core’s single performance is no longer the most important parameter, but the performance of the whole multicore system. It is an era where multiplicity and heterogeneity of computing units became the norm in state-of-the-art systems on chips (SoCs), not the exception. New programming models emerged trying to bridge the gap between programming complexity and well-utilization of the multicore systems, with their various available resources. One promising approach is the dataflow task-based programming model such as StarSs/OmpSs and OpenMP, where an application is broken down to smaller execution units called tasks, which will dynamically be scheduled to run on the available resources according to data dependences between those tasks. However, this approach has an overhead as its runtime system needs considerable amount of computational power to track dependences between tasks and build the task graph, decide on ready tasks, schedule them on idle cores, and upon task completion, kick off dependent tasks, all this performed dynamically at runtime. Although dataflow task-based programming provides a solution to the programmability problem of multicore systems, its runtime overhead, in practice, has limited the scalability of applications programmed using this programming model, especially when the tasks are fine-grain, and/or have complex task graphs. The main contribution of this thesis is to offload the heaviest part of the runtime system - task graph management - to a dedicated hardware accelerator, in order to accelerate the runtime system, as well as to save some conflicts on using the shared resources (microprocessor cores and memory system) by the runtime system and the user applications. The first prototype is presented in the form of the Nexus++ co-processor for the StarSs/OmpSs programming models. Using traces of applications written in StarSs/OmpSs from the StarBench benchmark suite, Nexus++ significantly improves the scalability of those applications. Nexus# is the successor of Nexus++, which has an improved execution pipeline compared to Nexus++, in addition to parallelizing the process of task graph management itself in a distributed fashion. For example, running an application with coarse-grain independent tasks such as "ray tracing" and where a software-only parallel solution achieves 31x speedup compared to the serial execution, Nexus# and Nexus++ achieve speedups of 194x and 60x respectively. For the case of fine-grain tasks with complex inter-task dependencies as in H.264 video decoding, the software-only parallel solution is slower than the serial execution due to runtime overhead, but Nexus# and Nexus++ achieve speedups of 7x and 2.2x respectively. Nexus# outperforms Nexus++ in terms of scalability, which opens the door to support even finer-grain tasks. As described in this work, through its extensive reconfigurability, Nexus# presents a suitable hardware accelerator for various multicore systems, ranging from embedded to complex high-performance systems. | en |
| dc.description.abstract | Seit einigen Jahren ist absehbar, dass die Gültigkeit von Moore’s Law nach fast 50 Jahren zu Ende geht. Dieses “Gesetz” basierte auf der Beobachtung, dass sich die Anzahl der Bauelemente auf einem Chip etwa alle 18 Monate verdoppelte und legte den Grundstein für die Roadmap der Halbleiterindustrie. Aufgrund der enormen Zunahme der Leistungsdichte von Mikroprozessoren steht diese Gesetz kurz vor dem Ende und ein neues Zeitalter in der Computerindustrie bricht an. In diesem Zeitalter ist die Single-Thread-Performance kein so wichtiger Faktor mehr, im Vergleich zur Leistung des gesamten Multicore-Systems. Es ist ein Zeitalter in dem die Vielfalt und Vielzahl von Prozessoren die Norm in aktuellen System on Chips (Soc) ist und nicht die Ausnahme. Seitdem sind neue Programmiermodelle entstanden, die versuchen, die Lücke zwischen algorithmischer Komplexität und einer effizienten Nutzung aller Ressourcen der SoC-Hardware zu überbrücken. Ein vielversprechender Ansatz ist das Datenfluss taskparallele Modell wie StarSs/OmpS und OpenMP. In diesem wird das Anwendungsprogramm in kleine Arbeitseinheiten, engl. Task, zerlegt. Diese Tasks werden dann unter Berücksichtigung der Datenabhängigkeiten dynamisch auf geeignete und verfügbare Ressourcen verteilt und parallel abgearbeitet. Dabei muss zwischen verschiedenen Laufzeitsystemen und Varianten dieses Programmiermodells abgewogen werden. Bei der Auswahl müssen folgende Punkte berücksichtigt werden, da diese eine nicht unerhebliche Rechenleistung benötigen: die interne Verwaltung des Taskgraphen, das Verfolgen der Datenabhängigkeiten zwischen Tasks, die Entscheidung wann ein Task bereit zur Bearbeitung ist, die Verteilung auf oder Zuteilung von Prozessoren und schließlich, nach der Abarbeitung der Aufgabe, die Rückmeldung an das Laufzeitsystem, die die Freigabe von weiteren Tasks nach sich zieht. Für Datenfluss taskparallele Programmiermodelle, in vielen Fällen wenigstens theoretisch eine sinnvolle Möglichkeit zur Programmierung von Multi- und Many-core Systemen, stellt der Overhead im Laufzeitsystem in der Praxis vielfach eine unüberwindbare Hürde dar. Dies gilt insbesondere für sehr fein unterteilte oder sehr komplexe Datenfluss- oder Taskgraphen. Der Hauptbeitrag dieser Dissertation ist es, den größten Teil eines Laufzeitsystems, das Task-Graph-Management, auf einen dedizierten Hardwarebeschleuniger auszulagern. Ziel dabei ist es, die Laufzeit des Systems zu steigern und gleichzeitig einigen Konflikten vorzubeugen, die entstehen, wenn das Laufzeitsystem oder Anwenderapplikationen geteilte Ressourcen (Mikroprozessorkerne und Speichersysteme) verwenden. Als erster Prototyp wird die Hardware-Unterstützung für das StarSs/OmpS Programmiermodell in Form des Nexus ++ Co-Prozessors eingeführt und der Einfluss auf Skalierbarkeit und Systemleistung gemessen. Für Traces von Anwendungen aus der StarBench Benchmarksuite zeigte Nexus++ eine erheblich verbesserte Skalierbarkeit dieser in StarSs/OmpSs geschriebenen Programme. Nexus# ist eine überarbeitete Version von Nexus++. Zusätzlich zur Parallelisierung der Prozesse für die Task-Graph-Verwaltung, welche verteilt erfolgt, besitzt die Version eine verbesserte Ausführungspipeline gegenüber dem Nexus++. Hierdurch ist es z.B. möglich, eine Applikation mit grobunterteilten unabhängigen Tasks, wie dem "ray tracing", um den Faktor 194x bzw. 60x mit Hilfe des Nexus# und Nexus++ zu beschleunigen verglichen mit der seriellen Ausführung. Durch eine reine Softwarelösung würde die Parallelisierung dagegen nur einen Geschwindigkeitszuwachs um den Faktor 31x erreichen. Hiervon profitieren Applikationen wie die H.264 Videodekodierung, welche feingranulare Task hat, die zusätzlich noch untereinander abhängig sind. Eine rein softwarebasierte Lösung zur Parallelisierung wäre aufgrund des Laufzeit-Overheads langsamer als die serielle Ausführung. Im Gegensatz dazu erzielen Nexus# bzw. Nexus++ jedoch ein Geschwindigkeitszuwachs um den Faktor 7x und 2.2x. Nexus# übertrumpft Nexus++ hinsichtlich der Skalierbarkeit, was eine feingranulare Unterteilung der Tasks ermöglicht. Wie in dieser Arbeit dargestellt, ist der Nexus# aufgrund seiner umfangreichen Rekonfigurierbarkeit ein zeitgemäßer Hardwarebeschleuniger. Er eignet sich für eine breite Palette von Mehrkernsystemen, angefangen bei eingebetteten Systemen bis hin zu komplexen Hochleistungssystemen. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/7387 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-6636 | |
| dc.language.iso | en | en |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | en |
| dc.subject.ddc | 000 Informatik, Informationswissenschaft, allgemeine Werke | de |
| dc.subject.ddc | 620 Ingenieurwissenschaften und zugeordnete Tätigkeiten | de |
| dc.subject.other | multicore systems | en |
| dc.subject.other | dataflow architecture | en |
| dc.subject.other | task-based programming | en |
| dc.subject.other | task superscalar | en |
| dc.subject.other | fine-grain parallelism | en |
| dc.subject.other | runtime system | en |
| dc.subject.other | scalability | en |
| dc.subject.other | Mehrkernsysteme | de |
| dc.subject.other | Datenflussarchitektur | de |
| dc.subject.other | taskparallele Programmierung | de |
| dc.subject.other | Task-Superskalarität | de |
| dc.subject.other | feingranulare Parallelität | de |
| dc.subject.other | Ausführungsumgebung | de |
| dc.subject.other | Skalierbarkeit | de |
| dc.title | Enhancing the scalability of many-core systems towards utilizing fine-grain parallelism in task-based programming models | en |
| dc.title.translated | Verbesserung der Skalierbarkeit von Mehrkernsystemen hinsichtlich der Verwendung von feingranularer Parallelität in task-basierten Programmiermodellen | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 4 Elektrotechnik und Informatik::Inst. Technische Informatik und Mikroelektronik | de |
| tub.affiliation.faculty | Fak. 4 Elektrotechnik und Informatik | de |
| tub.affiliation.institute | Inst. Technische Informatik und Mikroelektronik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |