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

Response Time Analysis for Prioritized DAG Task

作　　者：李峰 毕冉 马野 孙景昊[1] 李西盛 邓庆绪 LI Feng;BI Ran;MA Ye;SUN Jing-Hao;LI Xi-Sheng;DENG Qing-Xu(School of Computer Science and Technology,Dalian University of Technology,Dalian,Liaoning 116024;School of Computer and Communication Engineering,Northeastern University at Qinhuangdao,Qinhuangdao,Hebei 066004;Hebei Key Laboratory of Marine Perception Network and Data Processing,Northeastern University at Qinhuangdao,Qinhuangdao,Hebei 066004;School of Computer Science and Engineering,Northeastern University,Shenyang 110819)

机构地区：[1]大连理工大学计算机科学与技术学院,辽宁大连116024 [2]东北大学秦皇岛分校计算机与通信工程学院,河北秦皇岛066004 [3]东北大学秦皇岛分校河北省海洋感知网络与数据处理重点实验室,河北秦皇岛066004 [4]东北大学计算机科学与工程学院,沈阳110819

出　　处：《计算机学报》2024年第12期2909-2924,共16页Chinese Journal of Computers

基　　金：国家自然科学基金(62472063,62072085);河北省自然科学基金(F2024501037)资助.

摘　　要：随着多核技术在实时嵌入式系统中的广泛应用,多核处理器已经成为主流的硬件平台,充分发挥多核处理器的计算能力需要实现对实时程序进行全面的并行化.有向无环图(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.

关 键 词：响应时间 可满足性模理论 优先级调度 有向无环图 并行调度 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]