带优先级DAG实时任务图模型的响应时间分析

Response Time Analysis for Prioritized DAG Task

随着多核技术在实时嵌入式系统中的广泛应用,多核处理器已经成为主流的硬件平台,充分发挥多核处理器的计算能力需要实现对实时程序进行全面的并行化.有向无环图(DAG)是用于描述并行实时程序的理论模型,可描绘复杂任务的细粒度并行性.任务内优先级分配可以减少DAG任务运行时行为的不确定性,获得更小的最坏情况响应时间(WCRT).现有优先级DAG任务的响应时间分析都是关于DAG任务最坏情况响应时间界限的研究,因其与实际的最坏情况响应时间存在较大差距而存在悲观性,限制了实时嵌入式系统的计算性能,使其占用更多计算资源以确保任务在截止时间内完成.本文针对具有优先级的DAG任务的响应时间分析问题,提出了一种基于可满足性模理论(SMT)的方法来计算DAG任务精确的最坏情况响应时间.尽管已有研究给出关于DAG任务精确的WCRT,但并不适用于具有优先级的DAG.本文将带有优先级DAG任务的响应时间分析问题形式化为混合逻辑公式的可满足性问题,从而获得精确的最坏情况响应时间.实验结果表明,本文提出的方法不仅能够保证WCRT的精度,而且与现有DAG任务精确WCRT的计算方法相比,本文方法的计算效率平均提升了50%.

With the widespread application of multi-core technology in real-time embedded systems,multi-core processors have become the mainstream hardware platform.To fully utilize the powerful computational capabilities of multi-cores,comprehensive parallelization must be implemented in real-time programs.Directed Acyclic Graph(DAG)describes the parallelism of real-time programs which can effectively depict the fine-grained parallel characteristics of complex tasks.Intra-task Priority Assignment can reduce the uncertainty in the runtime behavior of DAG tasks,resulting in a smaller Worst-Case Response Time(WCRT).Existing response time analyses for priority-based DAG tasks focus on the upper bound of the WCRT.However,these analyses tend to be pessimistic due to the gap between the upper bound and the exact WCRT.This pessimism limits the computational performance of real-time embedded systems,causing them to occupy more computational resources to ensure tasks are completed within their deadlines.This paper focuses on response time analysis of prioritized DAG tasks and proposes an improved method that employs Satisfiability Modulo Theories(SMT)to compute a more accurate upper bound for DAG task response time.Although previous studies have provided exact WCRT analysis for DAG tasks,these findings do not extend to DAGs with priorities,and existing methods still exhibit pessimism.This paper formalizes the response time analysis of prioritybased DAG tasks into a satisfiability problem of mixed logical formulas and gets the exact WCRT.Experimental work shows that the method proposed in this paper not only guarantees the precision of the obtained bounds but also improves the average computational efficiency by 50% compared to existing methods for accurately calculating the WCRT of DAG tasks.