Measuring Efficiency and Executability of Allocation and Scheduling in Multi-Processor Systems-on-Chip
Luca Benini, Davide Bertozzi, Alessio Guerri, Michela Milano, Francesco Poletti · 2005
Multi-Processor Systems-on-Chips (MPSoCs) are be- coming increasingly complex, and mapping and scheduling of multi-task applications on computa- tional units is key to meeting performance constraints and power budgets. Abstract models of system com- ponents and deployment of advanced algorithmic tech- niques for the optimization problem can provide for fast design space exploration and for optimal solu- tions. We exploit Constraint Programming (CP) from Artificial Intelligence and Integer Programming from Operations Research (OR) as a means to capture dif- ferent aspects of the same problem (optimality and feasibility), and prove the effectiveness of this hybrid approach. Moreover, we exploit an accurate MPSoC virtual platform for capturing mismatches between problem formulation and real-life systems, and for as- sessing their impact on expected performance. We introduce the notion of execution constraints in the model of the problem, thus making the solution ex- pressible and implementable in the real world. The model without execution constraints is a relaxation of the real problem and therefore provides a super- optimal solution. We compare the effectiveness of this latter solution with the one provided by the simulator, and try to refine our models as well as our optimiza- tion techniques accordingly.