An MILP-Based Performance Analysis Technique for Non-Preemptive Multitasking MPSoC
Hoeseok Yang, Sungchan Kim, Soonhoi Ha · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2010
For real-time applications, it is necessary to estimate the worst-case performance early in the design process without actual hardware implementation. While the non-preemptive task scheduling is pertinent to multi-core platforms because of easy implementation and high performance, its scheduling anomaly behavior makes the worst-case performance estimation extremely difficult. In this paper, we propose an analysis technique based on mixed integer linear programming (MILP) to estimate the worst-case performance of each task in a non-preemptive multitask application on multi-processor system-on-chip architecture. MILP provides a systematic way to describe the complex interaction among task scheduling, communication architecture, and task execution, which affects the worst-case behavior dynamically. The proposed analysis technique overcomes several limitations that previous work usually has; it allows multiple tasks with different periods and models contention on the communication architecture. We show that the proposed analysis takes affordable computation time to make it of practical value even though it has exponential complexity in theory. The proposed technique estimates a safe bound on task latency statistically, which is demonstrated by extensive random simulations.