Game theoretic approach for run-time task scheduling on an multi-processor system on chip

Multi-processor system on chip (MPSoC) consists of multiple cores communicating via an on-chip communication backplane. An application to be executed on an MPSoC is represented using a task graph where a node represents an operation to be scheduled on a core and the edges represent the communication between these operations. Typically task graph scheduling on MPSoC is done statically during hardware-software co-design, based on estimated execution times. Static scheduling makes a program non-portable, hence dynamic scheduling is preferred. In this study, the authors present hardware-based dynamic feedback-driven task rescheduling heuristic that executes in real time. This task scheduling heuristic is based on the observation that during the course of execution, an application goes through a phase where a sub-graph (phase graph) of the application task graph repeatedly executes for a very large number of times. The proposed approach is iterative, where the schedule length of a phase graph converges to a smaller value in subsequent iterations. Experimental results show (i) real-time scheduling can be performed using proposed game theoretic approach which converges to a minimum in fewer than 100 iterations (ii) reducing the schedule length ranging 3-16% as compared with greedy heuristic.