Title :
Lower and upper bounds on time for multiprocessor optimal schedules
Author :
Jain, Kamal Kumar ; Rajaraman, V.
Author_Institution :
Dept. of Comput. Sci. & Autom., Indian Inst. of Sci., Bangalore, India
fDate :
8/1/1994 12:00:00 AM
Abstract :
The lower and upper bounds on the minimum time needed to process a given directed acyclic task graph for a given number of processors are derived. It is proved that the proposed lower bound on time is not only sharper than the previously known values but also easier to calculate. The upper bound on time, which is useful in determining the worst case behavior of a given task graph, is presented. The lower and upper bounds on the minimum number of processors required to process a given task graph in the minimum possible time are also derived. It is seen with a number of randomly generated dense task graphs that the lower and upper bounds we derive are equal, thus giving the optimal time for scheduling directed acyclic task graphs on a given set of processors
Keywords :
directed graphs; minimisation; parallel algorithms; scheduling; directed acyclic task graph; lower time bound; minimum processing time; minimum processor number; multiprocessor optimal schedules; parallel processing; performance evaluation; randomly generated dense task graphs; upper time bound; worst case behavior; Concurrent computing; NP-complete problem; Optimal scheduling; Parallel algorithms; Parallel processing; Processor scheduling; Random number generation; Scheduling algorithm; Tree graphs; Upper bound;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
