Stochastic allocation and scheduling for conditional task graphs in multi-processor systems-on-chip

Abstract Embedded systems designers are turning to multicore architectures to satisfy the ever-growing computational needs of applications within a reasonable power envelope. One of the most daunting challenges for MultiProcessor System-on-Chip (MPSoC) platforms is the development of tools for efficient mapping multi-task applications onto hardware platforms. Software mapping can be formulated as an optimal allocation and scheduling problem, where the application is modeled as a task graph, the target hardware is modeled as a set of heterogeneous resources, and the objective function represents a design goal α (e.g. minimum execution time, minimum usage of communication resources, etc.). Conditional task graphs, where inter-task edges represent data as well as control dependencies, are a well-known computational model to describe complex real-life applications where alternative execution paths, guarded by conditionals, can be specified. Each condition has a probability associated with each possible outcome. Mapping conditional task graphs is significantly more challenging than mapping pure data-flow graphs (where edges only represent data dependencies). Approaches based on general-purpose complete solvers (e.g. Integer Linear Programming solvers) are limited both by computational blowup and by the fact that the objective is a stochastic functional. The main contribution of our work is an efficient and complete approach to allocation and scheduling of conditional task graphs, based on (i) an exact analytic formulation of the stochastic objective function exploiting task graph analysis and (ii) an extension of the timetable constraint for conditional activities. Moreover, our solver is integrated in a complete application development environment which produces executable code for target multicore platforms. This integrated framework allows us to validate modeling assumptions and to assess constraint satisfaction and objective function optimization. Extensive validation results demonstrate not only that our approach can handle nontrivial instances efficiently, but also that our models are accurate and lead to optimal and highly predictable execution.