GENETIC ALGORITHM FOR MAPPING TASKS ONTO TO RECONFIGURABLE PARALLEL PROCESSOR

The authors describe a genetic algorithm for a difficult optimisation problem which arises in the context of parallel processing. The proble m is to assign each task in the given task graph T to a processor, so as to minimise the total overall execution time of the tasks. Total ex ecution time is computed with the knowledge of individual run times of tasks and the communication requirements among tasks. The intertask c ommunication time is dependent on the interconnection network which co nnects the processors. No prior knowledge of the interconnection topol ogy is assumed. The algorithm finds the interconnection architecture t hat is best suited for the task graph T; this makes sense when the tar get architecture is reconfigurable through programmable switches, e.g. transputer-based parallel processors. The algorithm is also extended to add heterogeneous platforms, where each task t can be executed on a particular class of processors. The optimisation technique is based o n the genetic paradigm. The authors describe an efficient chromosome r epresentation, genetic operators and a fitness measure suitable for th e application.