Task Scheduling on Configurable Parallel Systems by Genetic Algorithms

. Computing the schedule on a configurable parallel system adds one dimension to the traditional scheduling problem. Besides determining the spatial mapping of tasks to processors and their execution orderon the respective processors, additionally the topology of the parallel system has to be configured to best suite the application program. In order to acknowledge the mutual influence between schedule and topology, we present a genetic algorithm that optimizes them at the same time. The genetic algorithm is used here as stochastic searchalgorithm. It takes into accountprecedenceconstraintsbetween tasks and considers communication costs. The genetic algorithm has been implemented and evaluated in terms of runtime behavior and optimality of the solution. 1. Introduction The goal of most scheduling algorithms is to minimize the execution time of an application program on a given parallel hardware. The execution time consists of the pure computation time of the tasks and of the time it t..