Please use this identifier to cite or link to this item: https://doi.org/10.1109/71.895794
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
Source: 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. https://doi.org/10.1109/71.895794
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
URI: http://scholarbank.nus.edu.sg/handle/10635/62536
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.

SCOPUSTM   
Citations

65
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

30
checked on Nov 23, 2017

Page view(s)

22
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


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