A Fast and Accurate Technique for Mapping
Parallel Applications on Stream-Oriented MPSoC Platforms with
Communication Awareness - Abstract
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
approximate or near-optimal solutions. This paper proposes a complete
allocation and scheduling framework, and deploys an MPSoC virtual
platform to validate the accuracy of modelling assumptions. The optimizer
implements an efficient and exact approach to the mapping problem based
on a decomposition strategy. The allocation subproblem is solved through
Integer Programming (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 significant 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.
