|
Abstract : |
This paper proposes a new lower bound on the number of processors and finish time for the problem of scheduling precedence graphs with communication costs.An algorithm (ETF) has been proposed by Hwang ]1[ for scheduling precedence graphs in systems with interprocessor communication times.In this paper the notion of the earliest starting time of a task is formulated for the context of lower bounds.A lower bound on the completion time is proposed.A task delay which does not increase the earliest completion time of a schedule is defined.Each task can then be scheduled within a time interval without affecting the lower bound performance on the finish time.This leads to definition of a new lower bound on the number of processors required to process the task graph.A derivation of the minimum time increase over the earliest completion time is also proposed for the case of smaller number of processors.Finally the paper proposes a lower bound on the minimum number of interprocessor communication links required to achieve optimum performance. Evaluation has been carried out by using a set of 360 small graphs.The bound on the finish time deviates at most by 5% from the optimum solution in 96% of the cases and performs well with respect to the minimum number of processors and communication links., |
