Optimal algorithms for scheduling large scale application on heterogeneous systems

This paper studies optimal algorithms for scheduling large-scale application on heterogeneous systems using Divis ible Load Theory.A more realistic and general model,i.e.,both processors and communication links may have different speeds and arbitrary start-up costs,and communication is in non-blocking mode,is introduced.Under such environment, the following results are obtained:①Mathematic model and closed-form expressions both for the processing time and the fraction of load for each processor are derived;②the influence of start-up costs on the optimal processing time is analyzed;③for a given heterogeneous systems and a large-scale computing problem,optimal algorithms are proposed.