Stochastic allocation and scheduling for conditional task graphs in multi-processor systems-on-chip
Stochastic allocation and scheduling for conditional task graphs in multi-processor systems-on-chip
复制标题
多处理器片上系统中条件任务图的随机分配和调度
DOI：
10.1007/s10951-010-0184-y
复制
发表时间：
2010
影响因子：
2
通讯作者：
L. Benini
中科院分区：
文献类型：
--
作者：
M. Lombardi;M. Milano;M. Ruggiero;L. Benini
嵌入式系统设计人员正在转向多核架构，以在合理的功率范围内满足应用程序不断增长的计算需求。对于多处理器片上系统（MPSoC）平台来说，最艰巨的挑战之一是开发工具，将多任务应用程序有效地映射到硬件平台上。软件映射可以表述为最优分配和调度问题，其中应用程序被建模为任务图，目标硬件被建模为一组异构资源，目标函数表示设计目标α(例如。最小的执行时间，最小的通信资源使用，等等)。条件任务图是一种众所周知的计算模型，用于描述复杂的现实应用程序，其中可以指定由条件保护的替代执行路径。每种情况都有与每种可能结果相关联的概率。映射条件任务图比映射纯数据流图（其中的边仅表示数据依赖关系）更具挑战性。基于通用完全解算器（如整数线性规划解算器）的方法受到计算膨胀和目标是随机泛函这一事实的限制。我们工作的主要贡献是一种高效和完整的方法来分配和调度条件任务图，基于(i)利用任务图分析的随机目标函数的精确解析公式和（ii）对条件活动的时间表约束的扩展。此外，我们的求解器集成在一个完整的应用程序开发环境中，该环境为目标多核平台生成可执行代码。这个集成的框架允许我们验证建模假设，并评估约束满足和目标函数优化。大量的验证结果表明，我们的方法不仅可以有效地处理重要的实例，而且我们的模型是准确的，并导致最佳和高度可预测的执行。
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 non-trivial instances efficiently, but also that our models are accurate and lead to optimal and highly predictable execution.