Toward Minimum WCRT Bound for DAG Tasks Under Prioritized List Scheduling Algorithms
Toward Minimum WCRT Bound for DAG Tasks Under Prioritized List Scheduling Algorithms
复制标题
DOI：
10.1109/tcad.2022.3197532
复制
发表时间：
2022-11
影响因子：
2.9
通讯作者：
Shuangshuang Chang;Ran Bi;Jinghao Sun;Weichen Liu;Qi Yu;Qingxu Deng;Zonghua Gu
中科院分区：
文献类型：
--
作者：
Shuangshuang Chang;Ran Bi;Jinghao Sun;Weichen Liu;Qi Yu;Qingxu Deng;Zonghua Gu
许多现代实时并行应用可以建模为有向无环图（DAG）任务。最近的研究表明，最坏情况下的响应时间（WCRT）界的DAG任务可以显着减少时，顶点的执行顺序是由分配给每个顶点的优先级的DAG。如何获得最优的顶点优先级分配，以及从DAG任务的最佳WCRT界到最小WCRT界的距离仍然是开放的问题。在这篇文章中，我们的目标是构建最佳的顶点优先级分配，并推导出最小的WCRT界的DAG任务。我们编码的优先级分配问题成一个整数线性规划（ILP）制定。为了有效地求解ILP模型，我们不涉及所有的变量或约束。相反，我们迭代地求解ILP模型，即，我们最初仅用几个主要变量和约束来求解ILP模型，然后在每次迭代中，我们用更可能导出最优优先级分配的变量和约束来递增ILP模型。实验表明，该方法能够在不涉及太多变量或约束的情况下最优地求解ILP模型，对于50个顶点的实例，我们平均在几分钟内通过涉及12.67%的变量找到最优优先级分配。
Many modern real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Recent studies show that the worst-case response time (WCRT) bound of a DAG task can be significantly reduced when the execution order of the vertices is determined by the priority assigned to each vertex of the DAG. How to obtain the optimal vertex priority assignment, and how far from the best-known WCRT bound of a DAG task to the minimum WCRT bound are still open problems. In this article, we aim to construct the optimal vertex priority assignment and derive the minimum WCRT bound for the DAG task. We encode the priority assignment problem into an integer linear programming (ILP) formulation. To solve the ILP model efficiently, we do not involve all variables or constraints. Instead, we solve the ILP model iteratively, i.e., we initially solve the ILP model with only a few primary variables and constraints, and then at each iteration, we increment the ILP model with the variables and constraints which are more likely to derive the optimal priority assignment. Experimental work shows that our method is capable of solving the ILP model optimally without involving too many variables or constraints, e.g., for instances with 50 vertices, we find the optimal priority assignment by involving 12.67% variables on average and within several minutes on average.