MapReduce for the Cell B.E. Architecture
Minds at UW (University of Wisconsin)Published 1 January 2007Open access
Marc de Kruijf, Karthikeyan Sankaralingam
Citations40
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is found that the simplicity of the model and the efficiency of the MapReduce implementation make it an attractive choice for the Cell specifically and more generally to distributed memory systems and software-exposed memories.
Abstract
MapReduce is a simple and flexible parallel programming model proposed by Google for large scale data processing in a distributed computing environment [4]. In this paper, we present a design and implementation of MapReduce for the Cell architecture. This model provides a simple machine abstraction to users, hiding parallelization and hardware primitives. Our runtime automatically manages parallelization, scheduling, partitioning and memory transfers. We study the basic characteristics of the model and evaluate our runtime’s performance, scalability, and efficiency for micro-benchmarks and complete applications. We show that the model is well suited for many applications that map well to the Cell architecture, and that the runtime sustains high performance on these applications. For other applications, we analyze runtime performance and describe why performance is less impressive. Overall, we find that the simplicity of the model and the efficiency of our MapReduce implementation make it an attractive choice for the Cell platform specifically and more generally to distributed memory systems and software-exposed memories.
Keywords
Computer Science
Communications of the ACMMapReduce
18,538 Citations2008Jay B. Dean, Sanjay Ghemawat
This presentation explains how the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules inter-machine communication to make efficient use of the network and disks.
Evaluating MapReduce for Multi-core and Multiprocessor Systems
968 Citations2007Colby Ranger, R. Raghuraman +3 more
It is established that, given a careful implementation, MapReduce is a promising model for scalable performance on shared-memory systems with simple parallel code.
IBM Journal of Research and DevelopmentIntroduction to the Cell multiprocessor
941 Citations2005J. Kahle, Michael Day +4 more
This paper discusses the history of the project, the program objectives and challenges, the disign concept, the architecture and programming models, and the implementation of the Cell multiprocessor.
Map-reduce-merge
716 Citations2007Hung‐Chih Yang, Ali Dasdan +2 more
A Merge phase is added to Map-Reduce a Merge phase that can efficiently merge data already partitioned and sorted by map and reduce modules, and it is demonstrated that this new model can express relational algebra operators as well as implement several join algorithms.
Scientific ProgrammingInterpreting the Data: Parallel Analysis with Sawzall
616 Citations2005Rob Pike, Sean Dorward +2 more
The design -- including the separation into two phases, the form of the programming language, and the properties of the aggregators -- exploits the parallelism inherent in having data and computation distributed across many machines.
Science of Computer ProgrammingGoogle’s MapReduce programming model — Revisited
491 Citations2007Ralf Lämmel
This work reverse-engineers the seminal papers on MapReduce and Sawzall, and captures the findings as an executable specification, using typed functional programming (specifically Haskell) as a tool for design recovery and executable specification.
Memory---Sequoia
463 Citations2006Kayvon Fatahalian, William J. Dally +9 more
This work has implemented a complete programming system, including a compiler and runtime systems for cell processor-based blade systems and distributed memory clusters, and demonstrates efficient performance running Sequoia programs on both of these platforms.
IEEE MicroSynergistic Processing in Cell's Multicore Architecture
403 Citations2006Michael Gschwind, H. Peter Hofstee +4 more
The streamlined architecture provides an efficient multithreaded execution environment for both scalar and SIMD threads and represents a reaffirmation of the RISC principles of combining leading edge architecture and compiler optimizations.
IEEE MicroImagine: media processing with streams
350 Citations2001Brucek Khailany, William J. Dally +7 more
The power-efficient Imagine stream processor achieves performance densities comparable to those of special-purpose embedded processors and can sustain 18.3 gops on mpeg-2 encoding.
Dynamic management of scratch-pad memory space
253 Citations2001Mahmut Kandemir, J. Ramanujam +4 more
A compiler-controlled dynamic on-chip scratch-pad memory (SPM) management framework that uses both loop and data transformations is proposed that indicates significant reductions in data transfer activity between SPM and off-chip memory.
Optimizing Compiler for the CELL Processor
173 Citations2005Alexandre E. Eichenbergert, Kathryn O’Brien +12 more
Several compiler techniques that aim at automatically generating high quality codes over a wide range of heterogeneous parallelism available on the CELL processor are described and results indicate that significant speedup can be achieved with a high level of support from the compiler.
Ray Tracing on the Cell Processor
118 Citations2006Carsten Benthin, Ingo Wald +2 more
Using a combination of low-level optimized kernel routines, a streaming software architecture, explicit caching, and a virtual software-hyperthreading approach to hide DMA latencies, for a single cell a pure ray tracing performance of nearly one order of magnitude over that achieved by a commodity CPU is achieved.
IBM Systems JournalMPI microtask for programming the Cell Broadband Engine™ processor
93 Citations2006Maureen O’Hara, Hiroshi Inoue +3 more
A new programming model, MPI microtask, based on the standard Message Passing Interface (MPI) programming model for distributed-memory parallel machines is proposed, and the preprocessor and runtime in the microtask system optimize the execution of microtasks by exploiting explicit communications in the MPI model.
Compilation for explicitly managed memory hierarchies
87 Citations2007Timothy J. Knight, Ji Young Park +7 more
A compiler for machines with an explicitly managed memory hierarchy is presented and it is suggested that a primary role of any compiler for such architectures is to manipulate and schedule a hierarchy of bulk operations at varying scales of the application and of the machine.
Dynamic multigrain parallelization on the cell broadband engine
77 Citations2007Filip Blagojević, Dimitrios S. Nikolopoulos +2 more
This paper presents a scheduler for applications with layered parallelism on Cell and investigates its performance with RAxML, an application which infers large phylogenetic trees, using the Maximum Likelihood (ML) method.
IBM Journal of Research and DevelopmentCell/B.E. blades: Building blocks for scalable, real-time, interactive, and digital media servers
29 Citations2007A.K. Nanda, J. Randal Moulic +5 more
The Cell Broadband Engine™ (Cell/B.E.) processor, developed jointly by Sony, Toshiba, and IBM primarily for next-generation gaming consoles, packs a level of floating-point, vector, and integer streaming performance in one chip that is an order of magnitude greater than that of traditional commodity microprocessors.
IBM Journal of Research and DevelopmentSpeech recognition systems on the Cell Broadband Engine processor
9 Citations2007Yingchun Liu, Henry E. Jones +4 more
From the initial performance timings, it is observed that a single Cell/B.E. E. processor can recognize speech from thousands of simultaneous voice channels in real time-a channel density that is orders of magnitude greater than the capacity of existing software speech recognizers based on CPUs.
Programming and performance evaluation of the cell processor
6 Citations2005Ryuji Sakai, Seiji Maeda +11 more