R. Suda and S. Tomi (Japan)
Task Scheduling, Algorithm for Heterogeneous Systems, Load balancing, Communication Algorithm, Real-time scheduling, Divisible Load Theory
This paper proposes a scheduling algorithm for redis tribution of uniform independent divisible tasks on hetero geneous processors connected by a homogeneous network. The proposed algorithm is based on the multi-master di visible load model, which is an extension of the divisi ble load model from the master-worker framework. The schedule is asymptotically optimum, that is, the ratio of the makespan against the optimum one approaches to the unity when the amount of tasks grows infinitely. The computa tional complexity is so low that it can be used for run-time redistribution and/or rescheduling. In experiments it gives makespans very close to the optimums, and it is more effi cient compared to some existing methods.
Important Links:
Go Back
