Publication

@article{179,
title = {Orchestrating an Ensemble of MapReduce Jobs for Minimizing Their Makespan},
author = {Verma, Abhishek and Cherkasova, Ludmila and Campbell, Roy H.},
isbn = {1545-5971},
year = {2013},
date = {2013-00-01},
journal = {IEEE Transactions on Dependable and Secure ComputingIEEE Transactions on Dependable and Secure ComputingIEEE Transactions on Dependable and Secure Computing},
volume = {10},
number = {5},
pages = {314-327},
publisher = {IEEE},
abstract = {Cloud computing offers an attractive option for businesses to rent a suitable size MapReduce cluster, consume resources as a service, and pay only for resources that were consumed. A key challenge in such environments is to increase the utilization of MapReduce clusters to minimize their cost. One way of achieving this goal is to optimize the execution of Mapreduce jobs on the cluster. For a set of production jobs that are executed periodically on new data, we can perform an offline analysis for evaluating performance benefits of different optimization techniques. In this work, we consider a subset of production workloads that consists of MapReduce jobs with no dependencies. We observe that the order in which these jobs are executed can have a significant impact on their overall completion time and the cluster resource utilization. Our goal is to automate the design of a job schedule that minimizes the completion time (makespan) of such a set of MapReduce jobs. We introduce a simple abstraction where each MapReduce job is represented as a pair of map and reduce stage durations. This representation enables us to apply the classic Johnson algorithm that was designed for building an optimal two-stage job schedule. We evaluate the performance benefits of the constructed schedule through an extensive set of simulations over a variety of realistic workloads. The results are workload and cluster-size dependent, but it is typical to achieve up to 10-25 percent of makespan improvements by simply processing the jobs in the right order. However, in some cases, the simplified abstraction assumed by Johnsontextquoterights algorithm may lead to a suboptimal job schedule. We design a novel heuristic, called BalancedPools, that significantly improves Johnsontextquoterights schedule results (up to 15-38 percent), exactly in the situations when it produces suboptimal makespan. Overall, we observe up to 50 percent in the makespan improvements with the new BalancedPools algorithm. The results of our simulation study are validated through experiments on a 66-node Hadoop cluster.},
note = {217UE<br/>Times Cited:0<br/>Cited References Count:33},
keywords = {Algorithm design and analysis, batch workloads, Business, Clustering algorithms, Computational modeling, Hadoop, MapReduce, minimized makespan, optimized schedule, Production, Schedules, Upper bound},
pubstate = {published},
tppubtype = {article}
}

@conference{198,
title = {PIC: Partitioned Iterative Convergence for Clusters},
author = {Farivar, Reza and Raghunathan, Anand and Chakradhar, Srimat and Kharbanda, Harshit and Campbell, Roy H.},
isbn = {978-0-7695-4807-4},
year = {2012},
date = {2012-01-01},
booktitle = {2012 IEEE International Conference on Cluster Computing},
pages = {391-401},
publisher = {IEEE},
organization = {IEEE},
abstract = {Iterative-convergence algorithms are frequently used in a variety of domains to build models from large data sets. Cluster implementations of these algorithms are commonly realized using parallel programming models such as MapReduce. However, these implementations suffer from significant performance bottlenecks, especially due to large volumes of network traffic resulting from intermediate data and model updates during the iterations. To address these challenges, we propose partitioned iterative convergence (PIC), a new approach to programming and executing iterative convergence algorithms on frameworks like MapReduce. In PIC, we execute the iterative-convergence computation in two phases - the best-effort phase, which quickly produces a good initial model and the top-off phase, which further refines this model to produce the final solution. The best-effort phase iteratively performs the following steps: (a) partition the input data and the model to create several smaller, model-building sub-problems, (b) independently solve these sub-problems using iterative convergence computations, and (c) merge solutions of the sub-problems to create the next version of the model. This partitioned, loosely coupled execution of the computation produces a model of good quality, while drastically reducing network traffic due to intermediate data and model updates. The top-off phase further refines this model by employing the original iterative-convergence computation on the entire (un-partitioned) problem until convergence. However, the number of iterations executed in the top-off phase is quite small, resulting in a significant overall improvement in performance. We have implemented a library for PIC on top of the Hadoop MapReduce framework, and evaluated it using five popular iterative-convergence algorithms (Page Rank, K-Means clustering, neural network training, linear equation solver and image smoothing). Our evaluations on clusters ranging from 6 nodes to 256 nodes demonstrate a 2.5X-4X speedup compared to conventional implementations using Hadoop.},
keywords = {Clustering algorithms, Computational modeling, Convergence, Data models, Integrated circuit modeling, Partitioning algorithms},
pubstate = {published},
tppubtype = {conference}
}