2012 · 30 citations · 23 references
ComputingComputer EngineeringComputer ScienceFault-tolerant ComputingParallel ComputingSchedulingData ParallelismFault Tolerance In Parallel SystemsJob SchedulingParallel Computing SystemsResource SchedulingTask SchedulingFault Tolerance MechanismsFault-tolerant MapreduceIdle ResourcesLarge-scale Data ProcessingMapreduceMapreduce AlgorithmsParallel Task ExecutionSpeculative Task Execution
MapReduce has been adopted widely in both academia and industry to run large-scale data parallel applications. In MapReduce, each slave node hosts a number of task slots to which tasks can be assigned. So they limit the maximum number of tasks that can execute concurrently on each node. When all task slots of a node are not used, the resources “reserved” for idle slots are unutilized. To improve resource utilization, we propose resource stealing to enable running tasks to steal resources reserved for idle slots and give them back proportionally whenever new tasks are assigned. Resource stealing makes the otherwise wasted resources get fully utilized without interfering with normal job scheduling. MapReduce uses speculative execution to improve fault tolerance. Current Hadoop implementation decides whether to run speculative tasks based on the progress rates of running tasks, which does not take into consideration the absolute progress of each task. We propose Benefit Aware Speculative Execution which evaluates the potential benefit of speculative tasks and eliminates unnecessary runs. We implement the proposed algorithms in Hadoop, and our experiments show that our algorithms can significantly shorten job execution time and reduce the number of non-beneficial speculative tasks.
23
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
The Case for Energy-Proportional Computing
Luiz André Barroso, Urs Hölzle · Computer · 2007 · 2.5K citations
Michael Isard, Mihai Budiu, Yuan Yu et al. · 2007 · 2.5K citations
An improved algorithm for matching biological sequences
Osamu Gotoh · Journal of Molecular Biology · 1982 · 1.8K citations