Utilization of map-reduce for parallelization of resource scheduling using MPI: PRS

Abstract

Scheduling for speculative parallelization is a problem that remained unsolved despite its importance [2]. In the previous work scheduling was done based on Fixed-Size Chunking (FSC) technique which needed several'dry-runs' before an acceptable finalized chunk size that will be scheduled to each processors is found. There are many other scheduling methods which were originally designed for loops with no dependences, but they were primarily focused in the problem of load balancing. In this work we address the problem of scheduling tasks with and without dependences for speculative execution. We have found that a complexity between minimizing the number of re-executions and reducing overheads can be found if the size of the scheduled block of iterations is calculated at runtime. We introduce here a scheduling method called Parallelization of Resource scheduling (PRS) in which we first analyze the processing speed of each worker based on that further division of the actual task will be done. The result shows a 5% to 10% speedup improvement in real applications with dependences with respect to a carefully tuned PRS strategy. Copyright � 2011 ACM.