This paper describes an efficient, complete approach for solving a complex
allocation and scheduling problem for Multi-Processor System-on-Chip (MPSoC).
Given a throughput constraint for a target application characterized as a
task graph annotated with computation, communication and storage
requirements, we compute an allocation and schedule which minimizes
communication cost first, and then the makespan given the minimal
communication cost. Our approach is based on problem decomposition where the
allocation is solved through an Integer Programming solver, while the
scheduling through a Constraint Programming solver. The two solvers are interleaved
and their interaction regulated by no-good generation.
Experimental results show speedups of orders of magnitude w.r.t. pure IP and
CP solution strategies.