Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4903
Main Title: Automatic task and data mapping in shared memory architectures
Translated Title: Automatisches Mapping von Tasks und Daten in Shared Memory Architekturen
Author(s): Diener, Matthias
Advisor(s): Navaux, Philippe O. A.
Heiß, Hans-Ulrich
Referee(s): Heiß, Hans-Ulrich
Richling, Jan
Schneider Beck Filho, Antonio Carlos
Navaux, Philippe O. A.
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: Reducing the cost of memory accesses, both in terms of performance and energy consumption, is a major challenge in shared-memory architectures. Modern systems have deep and complex memory hierarchies with multiple cache levels and memory controllers, leading to a Non-Uniform Memory Access (NUMA) behavior. In such systems, there are two ways to improve the memory affinity: First, by mapping tasks that share data (communicate) to cores with a shared cache, cache usage and communication performance are improved. Second, by mapping memory pages to memory controllers that perform the most accesses to them and are not overloaded, the average cost of accesses is reduced. We call these two techniques task mapping and data mapping, respectively. For optimal results, task and data mapping need to be performed in an integrated way. Previous work in this area performs the mapping only separately, which limits the gains that can be achieved. Furthermore, most previous mechanisms require expensive operations, such as communication or memory access traces, to perform the mapping, require changes to the hardware or to the parallel application, or use a simple static mapping. These mechanisms can not be considered generic solutions for the mapping problem. In this thesis, we make two contributions to the mapping problem. First, we introduce a set of metrics and a methodology to analyze parallel applications in order to determine their suitability for an improved mapping and to evaluate the possible gains that can be achieved using an optimized mapping. Second, we propose two automatic mechanisms that perform task mapping and combined task/data mapping, respectively, during the execution of a parallel application. These mechanisms work on the operating system level and require no changes to the hardware, the applications themselves or their runtime libraries. An extensive evaluation with parallel applications from multiple benchmark suites as well as real scientific applications shows substantial performance and energy efficiency improvements that are significantly higher than simple mechanisms and previous work, while maintaining a low overhead.
Moderne parallele Architekturen haben komplexe Speicherhierarchien, die aus mehreren Ebenen von privaten und gemeinsam genutzten Caches, sowie einem Non-Uniform Memory Access (NUMA) Verhalten aufgrund mehrerer Speichercontroller bestehen. Eine der größten Herausforderungen in diesen Architekturen ist die Verbesserung der Lokalität und Balance von Speicherzugriffen, so dass die Latenz der Speicherzugriffe reduziert wird, da dies die Performance und Energieeffizienz von parallelen Anwendungen verbessern kann. Zwei Typen von Verbesserungen existieren: (1) Tasks die auf gemeinsame Daten zugreifen, sollen nah beieinander in der Speicherhierarchie ausgeführt werden, um die Nutzung der Caches zu verbessern. Wir bezeichnen diese Technik als Task Mapping. (2) Speicherseiten sollen den Speichercontrollern zugeordnet werden, von denen die meisten Zugriffe kommen und die nicht überlastet sind, um die durchschnittliche Speicherzugriffszeit zu reduzieren. Wir nennen diese Technik Data Mapping. Für optimale Ergebnisse müssen Task und Data Mapping in integrierter Form durchgeführt werden. Frühere Arbeiten in diesem Bereich führt das Mapping nur getrennt aus, wodurch die Vorteile, die erzielt werden können, begrenzt werden. Außerdem erfordern die meisten früheren Mechanismen teure Operationen um das Mapping durchzuführen, wie etwa Traces der Kommunikation oder von Speicherzugriffen. Andere Arbeiten erfordern Änderungen an der Hardware oder an der parallelen Anwendung, oder erzeugen nur ein einfaches statisches Mapping. Diese Mechanismen können nicht als generische Lösungen für das Mapping-Problem betrachtet werden. In dieser Arbeit präsentieren wir zwei Beiträge für das Mapping-Problem. Zuerst führen wir eine Reihe von Metriken und eine Methodologie zur Bestimmung der Eignung von parallelen Anwendungen für die verschiedenen Arten von Mapping. Das Ziel ist es, die möglichen Gewinne, die durch eine optimiertes Mapping erreicht werden können, vorherzusagen. Zweitens stellen wir zwei Mechanismen vor, die Task und Data Mapping automatisch während der Laufzeit der parallelen Applikation ausführen. Diese Mechanismen funktionieren auf der Betriebssystemebene und erfordern keine Änderungen an der Hardware, den Anwendungen oder deren Laufzeit-Bibliotheken. Eine umfangreiche Auswertung mit einer großen Auswahl paralleler Applikationen zeigen signifikante Verbesserungen der Performance und der Energieeffizienz.
URI: http://depositonce.tu-berlin.de/handle/11303/5206
http://dx.doi.org/10.14279/depositonce-4903
Exam Date: 28-Oct-2015
Issue Date: 2015
Date Available: 15-Dec-2015
DDC Class: DDC::000 Informatik, Informationswissenschaft, allgemeine Werke
Subject(s): task mapping
data mapping
shared memory
multicore
NUMA
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Publications

Files in This Item:
File Description SizeFormat 
diener_matthias.pdf2.66 MBAdobe PDFThumbnail
View/Open


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