航电系统计算平台多核处理器的DAG可调度性分析优化  

DAG Schedulability Analysis and Optimization of Multicore Processors in Avionics System Computing Platform

作　　者：杨欢[1,3] 王晓东 何佩 刘尊[1,3] 姚红静 郭阳明[2,3] YANG Huan;WANG Xiaodong;HE Pei;LIU Zun;YAO Hongjing;GUO Yangming(School of Computer Science,Northwestern Polytechnical University,Xi′an 710072,China;School of Cybersecurity,Northwestern Polytechnical University,Xi′an 710072,China;Research Center of Intelligent Industry Detection and Robot Safety Control Engineering Technology in Shaanxi Province,Xi′an 710072,China)

机构地区：[1]西北工业大学计算机学院,西安710072 [2]西北工业大学网络安全空间学院,西安710072 [3]陕西省智能工业检测与机器人安全控制工程技术研究中心,西安710072

出　　处：《小型微型计算机系统》2025年第3期759-768,共10页Journal of Chinese Computer Systems

基　　金：国家某重点科研项目(MJ-2018-S-34)资助.

摘　　要：随着高性能的多核处理器在客机航空电子系统中被应用,并且有向无环图(Directed Acyclic Graph,DAG)被用于模型功能依赖,本文研究运行在同构多处理器平台上的单周期非抢占式DAG,致力于减少DAG的完成时间并提供一个紧密而安全的界限,充分利用DAG拓扑节点的两个关键因素:并行性和依赖性.首先,引入了一个并发父子模型(Concurrent Parent and Children Model,CPCM),它精确地捕捉了上述两个因素,并且可以在解析DAG时递归地应用.在CPCM基础上,提出了一种新的调度方法减少最大完工时间,节点按以下顺序排列:1)关键路径;2)关键路径的早期前驱路径;3)更长的路径.其次,提出了一种新的响应时间分析,它为非关键节点的任何执行顺序提供了一个通用的界限,并为固定的执行顺序提供了一个特定的界限.实验表明该可调度性分析方法优于其他方法.With the application of high-performance multi-core processors in the avionics system of passenger aircraft,and the Directed Acyclic Graph(DAG)is used for model functional dependence,this paper studies the one-cycle nonpreemptive DAG running on the homogeneous multi-processor platform.In order to reduce the completion time of DAG and provide a tight and safe boundary,the parallelism and dependence of nodes are used,which are two key factors of DAG topology.Firstly,a Concurrent Parent and Child Model(CPCM)is introduced,which accurately captures the above two factors and can be applied recursively when parsing DAG.Based on CPCM,a new scheduling method is proposed,which focuses on reducing the maximum completion time and arranging nodes in the following order:1)critical path;2)early predecessor path of critical path;3)longer path.Secondly,a new response time analysis is proposed,which provides a general boundary for any execution order of non-critical nodes and a specific boundary for a fixed execution order.Experiments show that this schedulability analysis method is superior to other methods.

关 键 词：多核 并行 有限无环图 父子模型 响应时间分析 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]