A hierarchical LST-based task scheduler for NoC-based MPSoCs with slack-time monitoring support

Emerging large-scale MPSoCs can have hundreds of PEs (Processing Elements), and scalable real-time support is necessary. Current proposals in MPSoCs scheduling have static behaviors or lack accurate validation, from a clock cycle model of the system. This paper proposes a hierarchical scheduling algorithm. At the bottom level, each PE executes a local LST-based scheduler algorithm with extended features to handle with inter-task communication and interruption overheads. At the top level, a global scheduler manages at run-time task mapping and real-time adaptation by using task migration and monitored information. The run-time adaptation is supported by a slack time monitoring that notifies the global scheduler the slack time of the PEs. The monitoring data, combined with traditional real-time metrics, provide a powerful real-time management that, as demonstrated by a clock cycle validation, can be implemented in large scale MPSoCs.