Pre-scheduling and Scheduling of Task Graph on Homogeneous Multiprocessor Systems

Task graph scheduling is a multi-objective optimization and NP-hard problem.In this paper a new algorithm on homogeneous multiprocessors systems is proposed.Basically, scheduling algorithms are targeted to balance the two parameters of timeand energy consumption. These two parameters are up to a certain limit in contrastwith each other and improvement of one causes reduction in the other one. Theproblem is to achieve the trade-off between these two parameters. Pre-schedulingalgorithms are mainly aimed at modifying the structure of task graph to gainoptimal scheduling.In the proposed algorithm the suitable number of processors for scheduling thetask graph is computed. The idea of Nash equilibrium is mainly applied to computethe appropriate number of processors in such a way that the idle time of theprocessors is reduced while their processing power is increased. Also, consideringthe communication costs and interdependencies, the tasks are merged as theirearliest start time is reduced. In this way, the length of the critical path is reducedwhile the degree of parallelism is increased and ultimately the completion time isreduced. Our experimental result on a number of known benchmark graphsdemonstrates the effect of our proposed algorithm.

کلیدواژه ها:

schedule ، pre-schedule ، task graph ، game theory ، optimization ، Nash equilibrium