|
Identifier |
000378811 |
Title |
Implementing Scalable Parallel Programming Models with Hybrid Address Spaces |
Alternative Title |
Υλοποίηση κλιμακώσιμων παράλληλων προγραμματιστικών μοντέλων με υβριδικούς χώρους διευθύνσεων |
Author
|
Παπαγιάννης, Αναστάσιος Ελευθέριος.
|
Thesis advisor
|
Κατεβαίνης, Μανόλης
|
Abstract |
This thesis introduces hybrid address spaces as a design methodology
for implementing scalable runtime systems on many-core architectures without
hardware support for cache coherence. We demonstrate hybrid address
spaces in an implementation of MapReduce, a well-established programming
model for large-scale, fault-tolerant data processing. Using the Intel Single-
Chip Cloud Computer as an experimental testbed, we present HyMR, a
staged MapReduce runtime system whereby different stages alternate between
a distributed memory address space and a shared memory address
space to improve performance and scalability. In exploring hybrid address
spaces, we introduce four improvements in the implementation of MapReduce:
(1) Lock-free data distribution algorithms, using user-defined splitter
functions. (2) A scalable, interrupt-less implementation of work-stealing for
non-coherent architectures using exclusively on-chip communication to minimize
latency. (3) Optimized implementation for on-chip barrier algorithms
for non-coherent many-core processors. (4) A new mechanism to enable fast
access from a core to the private memory of another core on-chip, which
accelerates global exchange operations.
We compare HyMR to an optimized reference implementation using exclusively
distributed address spaces and find that hybrid address spaces improve
performance by a factor of 1.71 x (geometric mean). We also compare
HyMR with Phoenix++, a state-of-art implementation for systems with
hardware-managed cache coherence in terms of scalability and sustained to
peak data processing bandwidth, where HyMR demonstrates improvements
of a factor of 3.1x and 3.2x (geometric mean) respectively.
|
Language |
English |
Subject |
MapReduce |
|
Parallel Progmamming Models |
|
Runtime Systems |
|
Single-Chip-Cloud |
|
Εκτίμηση πόζας |
|
Παράλληλα προγραμματιστικά μοντέλα |
|
Συστήματα χρόνου εκτέλεσης |
Issue date |
2013-03-15 |
Collection
|
School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses
|
|
Type of Work--Post-graduate theses
|
Views |
783 |