On runtime task graph extraction in MPSoC

In a Multi Processor System on Chip (MPSoC), an application executes on multiple processor cores connected by a Network on Chip (NoC). An application is represented in the form of a Task Graph consisting of nodes and edges which correspond to operations (tasks) and communication between these nodes, respectively. The task graph is scheduled on an MPSoC platform by generating a task to core assignment so as to minimize the total execution time. Static scheduling of a task graph is optimized based on estimated execution times on the MPSoC hardware platforms. Dynamic scheduling is challenging because the task graph must be available during runtime while making scheduling decisions. However, dynamic scheduling offers the benefits of portability and adaptability. Runtime discovery of task graph is one of the main challenges faced by dynamic scheduling due to unavailability of application task graph. In this work, we present a novel mechanism for runtime task graph extraction based on the observation that an application goes through several phases during its execution. During a stable phase, the same task graph (Phase Graph) repeatedly executes for a very large number of iterations. Experimental results show that task graphs can be extracted within as few as 200 iterations during a program phase.