Mapping and scheduling of parallel C applications with Ant Colony Optimization onto heterogeneous reconfigurable MPSoCs

Efficient mapping and scheduling of partitioned applications are crucial to improve the performance on today´s reconfigurable multiprocessor systems-on-chip (MPSoCs) platforms. Most of existing heuristics adopt the directed acyclic (task) Graph as representation, that unfortunately, is not able to represent typical embedded applications (e.g., real-time and loop-partitioned). In this paper we propose a novel approach, based on Ant Colony Optimization, that explores different alternative designs to determine an efficient hardware-software partitioning, to decide the task allocation and to establish the execution order of the tasks, dealing with different design constraints imposed by a reconfigurable heterogeneous MPSoC. Moreover, it can be applied to any parallel C application, represented through Hierarchical Task Graphs. We show that our methodology, addressing a realistic target architecture, outperforms existing approaches on a representative set of embedded applications.