W.F. Boyer and G.S. Hura (USA)
Distributed heterogeneous computing; dynamic scheduling; dependent task scheduling.
Two new algorithms are proposed for scheduling tasks in heterogeneous distributed systems where tasks may have arbitrary dependencies and estimates of execution time are imperfect. A new Dynamic Adaptive Random Scheduler (DARS) algorithm is proposed. DARS uses a randomized ordering technique to search for a near optimum schedule while monitoring the status of each previously dispatched task such that tasks are migrated according to the current estimates of task execution time. A proposed new Load Balancing (LB) algorithm distributes tasks initially by a heuristic that accounts for heterogeneity and dependencies, and while tasks are executing it migrates tasks to rebalance the load whenever a host becomes idle such that the number of migrations is minimized and each migration accounts for dependencies. The algorithms were evaluated by simulation of various scenarios and for various levels of uncertainty in execution time estimated values. The best algorithm is highly dependent on the nature of the load and the level of uncertainty in the execution time estimates.
Important Links:
Go Back
