Asynchronous Algorithms in MapReduce
Authors:
- Karthik KambatlaKKKarthik Kambatla
- Naresh RapoluNRNaresh Rapolu
- Suresh JagannathanSJSuresh Jagannathan
- Ananth GramaAGAnanth Grama
- 1 September 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 245-254
Abstract
Asynchronous algorithms have been demonstrated to improve scalability of a variety of applications in parallel environments. Their distributed adaptations have received relatively less attention, particularly in the context of conventional execution environments and associated overheads. One such framework, MapReduce, has emerged as a commonly used programming framework for large-scale distributed environments. While the MapReduce programming model has proved to be effective for data-parallel applications, significant questions relating to its performance and application scope remain unresolved. The strict synchronization between map and reduce phases limits expression of asynchrony and hence, does not readily support asynchronous algorithms. This paper investigates the notion of partial synchronizations in iterative MapReduce applications to overcome global synchronization overheads. The proposed approach applies a locality-enhancing partition on the computation. Map tasks execute local computations with (relatively) frequent local synchronizations, with less frequent global synchronizations. This approach yields significant performance gains in distributed environments, even though their serial operation counts are higher. We demonstrate these performance gains on asynchronous algorithms for diverse applications, including pagerank, shortestpath, and kmeans. We make the following specific contributions in the paper(i) we motivate the need to extend MapReduce with constructs for asynchrony, (ii) we propose an API to facilitate partial synchronizations combined with eager scheduling and locality enhancing techniques, and (iii) demonstrate performance improvements from our proposed extensions through a variety of applications from different domains.Keywords
This publication has 8 references indexed in Scilit:
- Improving parallelism and locality with asynchronous algorithms2010
- Distributed aggregation for data-parallel computing2009
- MapReduce optimization using regulated dynamic prioritization2009
- Parallel Pairwise Clustering2009
- Evaluating MapReduce for Multi-core and Multiprocessor Systems2007
- Asynchronous Iterative Algorithms for Nonexpansive Linear SystemsJournal of Parallel and Distributed Computing, 2000
- A new class of asynchronous iterative algorithms with order intervalsMathematics of Computation, 1998
- A general theory of bibliometric and other cumulative advantage processesJournal of the American Society for Information Science, 1976