Task Allocation in Distributed Embedded Systems by Genetic Programming

In this paper we describe a task allocation method, that utilizes genetic programming to find a suitable solution in an adequate time for this NP-complete combinatorial optimization problem. The underlying distributed embedded system is heterogenous, consisting of different processors with different properties such as core type, clock frequency, available memory, and I/O interfaces, interconnected with different communication media. In our applications, which are described as dataflow graphs, the number of tasks to be placed is much larger than the number of processors available. We highlight the difficulties when applying genetic programming to this problem and present our solutions and enhancements, accompanied with some simulation results.