Optimal multi-installments algorithm for divisible load scheduling
Shang Mingsheng, Sun Shi-xin · 2005
In this paper, we study optimal algorithms for scheduling divisible load on a star network in multi-installments, with the objective to minimize the processing time. Firstly, we consider approach based on linear programming. We found that optimal load sizes of each installment are determined by the number of processor and the rate of processor power to the communication speed. If the number of processor is given, we derive the optimal installments. And for achieving optimal processing time it is preferable to use more processors rather than more installments. Next, we consider optimal parameters of periodic multi-installment algorithm. For a given computation system, we derive the analytic expression of optimal installments. We further prove that, for large-scale workloads, any algorithm which keeps the communication link busy is asymptotically optimal, which gives a way to determine how many processors should be involved in processing.