K. Dussazieger et M. Schwehm, SCHEDULING OF PARALLEL PROGRAMS ON CONFIGURABLE MULTIPROCESSORS BY GENETIC ALGORITHMS, International journal of approximate reasoning, 19(1-2), 1998, pp. 23-38
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.