Please use this identifier to cite or link to this item: https://doi.org/10.1109/3468.895891
Title: Suboptimal solutions using integer approximation techniques for scheduling divisible loads on distributed bus networks
Authors: Veeravalli, B. 
Viswanadham, N. 
Issue Date: Nov-2000
Source: Veeravalli, B.,Viswanadham, N. (2000-11). Suboptimal solutions using integer approximation techniques for scheduling divisible loads on distributed bus networks. IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans. 30 (6) : 680-691. ScholarBank@NUS Repository. https://doi.org/10.1109/3468.895891
Abstract: The problem of optimal divisible load distribution in distributed bus networks employing a heterogeneous cluster of processors is addressed. The objective is to minimize the total processing time of the entire load subject to the communication and computation delays. In the mathematical model we adopt, both the granularity of the load fractions and all the associated overheads (also referred to as start-up costs) in the process of communication and computation, are considered explicitly in the problem formulation. We introduce a directed flow graph model for representing the load distribution process. This representation is novel to this literature. With this model, we first derive a closed-form solution for an optimal processing time. We propose an integer approximation algorithm and derive ultimate performance bounds for the class of homogeneous networks. We then extend the problem to a special class of application problems in which the data partitioning is restricted to a finite number of partitions. For this case, we present a recursive procedure to obtain optimal processing time. We then present two different integer approximation algorithms - PIA and IIA that could generate integer load fractions and yield suboptimal solutions. The choice of these algorithms are also analyzed. All the results are extended to a class of homogeneous networks to obtain ultimate performance bounds. Several illustrative examples are provided for ease of explanation.
Source Title: IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.
URI: http://scholarbank.nus.edu.sg/handle/10635/50602
ISSN: 10834427
DOI: 10.1109/3468.895891
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

14
checked on Dec 4, 2017

Page view(s)

39
checked on Dec 8, 2017

Google ScholarTM

Check

Altmetric


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