A Fast andAccurateTechnique for Mapping Parallel Applications on Stream-Oriented MPSoC Platforms

The problem of allocating and scheduling precedence-constrained tasks on the processors of a distributed real-time system is NP-hard. As such, it has been traditionally tackled by means of heuristics, which provide only approx-imate or near-optimal solutions. This paper proposes a complete allocation and scheduling framework, and deploys an MPSoC virtual platform to val-idate the accuracy of modelling assumptions. The optimizer implements an efficient and exact approach to the mapping problem based on a decomposi-tion strategy. The allocation subproblem is solved through Integer Program-ming (IP) while the scheduling one through Constraint Programming (CP). The two solvers interact by means of an iterative procedure which has been proven to converge to the optimal solution. Experimental results show sig-nificant speed-ups w.r.t. pure IP and CP exact solution strategies as well as high accuracy with respect to cycle-accurate functional simulation. Two case studies further demonstrate the practical viability of our framework for real-life applications