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. [ABSTRACT FROM AUTHOR]