Suboptimal solutions using integer approximation techniques for schedulingdivisible loads on distributed bus networks

The problem of optimal divisible load distribution in distributed bus netwo rks employing a heterogeneous cluster of processors is addressed, The objec tive is to minimize the total processing time of the entire load subject to the communication and computation delays, In the mathematical model we ado pt, both the granularity of the load fractions and all the associated overh eads (also referred to as start-up costs) in the process of communication a nd computation, are considered explicitly in the problem formulation. We in troduce 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 p ropose an integer approximation algorithm and derive ultimate performance b ounds for the class of homogeneous networks. We then extend the problem to a special class of application problems in which the data partitioning is r estricted to a finite number of partitions, For this case, we present a rec ursive procedure to obtain optimal processing time. We then present two dif ferent integer approximation algorithms-PIA and IIA that could generate int eger load fractions and yield suboptimal solutions. The choice of these alg orithms are also analyzed. All the results are extended to a class of homog eneous networks to obtain ultimate performance bounds, Several illustrative examples are provided for ease of explanation.