Please use this identifier to cite or link to this item:
|Title:||Suboptimal solutions using integer approximation techniques for scheduling divisible loads on distributed bus networks|
|Authors:||Veeravalli, B. |
|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.|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 4, 2017
checked on Dec 8, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.