SCHEDULING OF PARALLEL PROGRAMS ON CONFIGURABLE MULTIPROCESSORS BY GENETIC ALGORITHMS

The scheduling of programs on parallel hardware is investigated in ord er to minimize the response time of the resulting system. In particula r the scheduling problem considered in this paper includes - next to t he search for an optimal mapping of the tasks and their sequence of ex ecution - also the search for an optimal configuration of the parallel hardware. An approach for the simultaneous optimization of all three components using genetic algorithms is presented and its performance i s evaluated in comparison with an exact reference method based on an b ranch-and-bound-with-underestimates algorithm. The comparison is based on a large set of problem instances and includes regular task graphs with varying structure and scalable size, which had to be mapped onto a configurable parallel hardware consisting of 4-16 transputers, respe ctively. Small problem instances with less than eight tasks can be sol ved by both solution methods. For larger problem instances the referen ce method fails due to runtime complexity while the genetic algorithm can still find (suboptimal) solutions for problem instances with up to 120 tasks in an acceptable amount of time. (C) 1998 Elsevier Science Inc. All rights reserved.