Generate-map-reduce: An extension to map-reduce to support shared data and recursive computations

摘要

It is difficult to express the parallelism present in complex computations by using existing higher levelrnabstractions such as MapReduce and Dryad. These computations include applications from wide variety ofrndomains, like Artificial Intelligence, Decision Tree Algorithms, Association Rule Mining, RecommenderrnSystems, Graph Algorithms, Clustering Algorithms, Compute Intensive Scientific Workflows, OptimizationrnAlgorithms, and so forth. Their execution graphs introduce new challenges in terms of programmerrnexpressibility and runtime performance such as iterative and recursive computations, shared communicationrnmodel, and so forth.We propose an extension to MapReduce, called Generate-Map-Reduce (GMR), targetedrntowards modeling these applications. GMR introduces a new Generate abstraction into the MapReducernframework that captures recursive computations. The runtime also supports iterative jobs and a distributedrncommunication model by using shared data structures. We illustrate recursive computations with GMR byrnmodeling complex applications such as simulated annealing, A* search, and adaptive quadrature computationrnthat require recursive spawning of new tasks to handle variable degree of parallelism. GMR runtimernsupports caching of common data across iterations in memory and local disks.We illustrate how this cachingrnhelps in achieving significant speedup for iterative computations by modeling k-means clustering.