GENETICAS: a multi-DSP scheduling technique based on genetic algorithms
Peter M. Koch, Nicklas Larsen, Tobias Valentin Bauer, O. Ejlersen · 2002
Genetic algorithms (GA) is an emerging technique for solving combinatorial optimization problems, e.g., the NP-hard static multiprocessor scheduling problem which is of particular importance when mapping data independent algorithms onto multiple DSP processor architectures. In this paper we present a new GA-based multi-DSP scheduler, GENETICAS, which employs simple genetic operators and an efficient genotype encoding of the schedule. We show that GENETICAS significantly outperforms one of the few existing GA-based scheduling strategies (to be denoted GAMS). As compared to GAMS, GENETICAS furthermore generates realistic schedules which takes into account the inevitable and sometimes significant inter processor communication (IPC) cost.