Please use this identifier to cite or link to this item:
Title: On the influence of start-up costs in scheduling divisible loads on bus networks
Authors: Veeravalli, B. 
Li, X.
Ko, C.C. 
Issue Date: Dec-2000
Citation: Veeravalli, B., Li, X., Ko, C.C. (2000-12). On the influence of start-up costs in scheduling divisible loads on bus networks. IEEE Transactions on Parallel and Distributed Systems 11 (12) : 1288-1305. ScholarBank@NUS Repository.
Abstract: Optimal distribution of divisible loads in bus networks is considered in this paper. The problem of minimizing the processing time is investigated by including all the overhead components that could penalize the performance of the system, in addition to the inherent communication and computation delays. These overheads are considered to be constant additive factors to the respective communication and computation components. Closed-form solution for the processing time is derived and the influence of overheads on the optimal processing time is analyzed. We derive a necessary and sufficient condition for the existence of the optimal processing time. We then study the effect of changing the load distribution sequence on the time performance. Through rigorous analysis, an optimal sequence to distribute the load among the processors is identified, whenever it exists. In case such an optimal sequence fails to exist, we present a greedy algorithm to obtain a suboptimal 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 time 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 our algorithm lies within a radius given by the sum of the computation and communication delays. Several numerical examples are presented to illustrate the concepts.
Source Title: IEEE Transactions on Parallel and Distributed Systems
ISSN: 10459219
DOI: 10.1109/71.895794
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.