The increasing levels of system integration in Multi-Processor SoCs (MPSoCs)
emphasize the need for new design flows for efficient mapping of multi-task
applications onto hardware platforms. The problem of allocating and scheduling
precedence-constrained tasks on processors in 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, where an
MPSoC virtual platform is used to accurately
derive input parameters, validate abstract models of system components and
assess constraint satisfaction and objective function optimization.
The optimizer implements an efficient and exact approach
to allocation and scheduling based on problem decomposition. The allocation
subproblem is solved through Integer Programming while the scheduling one through
Constraint Programming. The two solvers can interact by means of
no-good generation, thus building an iterative procedure which is proved to
converge to the optimal solution. Experimental results show significant speedups
w.r.t. pure IP and CP exact solution strategies as well as high accuracy with
respect to cycle accurate functional simulation.
A case study further demostrates the practical viability of our framework for real-life systems and applications.
