On the influence of start-up costs in scheduling divisible loads on bus networks

Optimal distribution of divisible loads in bus networks is considered in th is paper. The problem of minimizing the processing time is investigated by including all the overhead components that could penalize the performance o f the system, in addition to the inherent communication and computation del ays. These overheads are considered to be constant additive factors to the respective communication and computation components. Closed-form solution f or the processing time is derived and the influence of overheads on the opt imal processing time is analyzed. We derive a necessary and sufficient cond ition for the existence of the optimal processing time. We then study the e ffect of changing the load distribution sequence on the time performance. T hrough rigorous analysis, an optimal sequence to distribute the load among the processors is identified, whenever it exists. In case such an optimal s equence fails to exist, we present a greedy algorithm to obtain a suboptima l sequence based on some important properties of the overhead factors. Then , the effect of granularity of the data that is divisible is considered in the analysis for the case of homogeneous networks. An integer approximation algorithm capable of generating integer values of the load fractions in ti me O(m), where m, is the number of processors in the network, is proposed. We then show that the upper bound on the suboptimal solution generated by o ur algorithm lies within a radius given by the sum of the computation and c ommunication delays. Several numerical examples are presented to illustrate the concepts.