欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:15327302358
邮箱:peter.lyz@163.com

Q Q:
910330594  
微信paperwinner
工作时间:9:00-24:00

博士论文
当前位置:首页 > 博士论文
带有分支结构OpenMp任务图的响应时间分析
来源:一起赢论文网     日期:2020-12-11     浏览数:79     【 字体:

 第43 第11 2020 年1 1 月计 算机 学 报CHINESEJOURNALOFCOMPUTERSVol.43No. 11Nov.2020带有分支结构OpenMP任务图的响应时间分析孙景昊D‘2)张利威u池瑶瑶n曹 蕾' 1邓庆绪n"( 东北大学计算机科学与工程学院 沈阳 110819)2 1( 大连理工大学计算机科学与技术学院 辽宁大连 116024)摘 要 随着多核技术在实时系统中广泛应用, 实时程序的并行化成为当前的研究热点. 在实时领域, 有向无环图( DAG)是刻画并行实时程序的理论模型. 然而, 传统的DAG任务图并不能刻画并行程序的实际特征(例如if-else控制流结构). 于是, 能够同时反映程序的并行负载特征和if-else 控制流结构的分支并行任务图(condi tionalDAG:con-DAG)应运而生. 目前, 实时领域通常假设con-DAG满足某种特殊结构, 即图中的并行子结构和分支子结构必须是单人口和单出口(简称为“单人单出”).在这种约束下,con-DAG的响应时间分析问题具有多项式时间算法. 然而, 现实的OpenMP程序具有更加灵活的结构 单人单出”假设一旦失效,con-DAG响应时间分析是否依然存在多项式时间算法为开放性问题. 本文针对一般情况下OpenMP程序的分支结构开展研究. 对于非“单人单出”con-DAG图上响应时间分析问题, 基于动态规划理论, 提出了多项式时间的求解方法. 实验表明, 本文方法求得的con-DAG响应时间在之前方法的基础上能够提升3%, 为实时并行程序的可预测性提供更精确的理论支撑.关键词 OpenMP; 有向无环图;if-else分支结构; 响应时间; 多项式时间中图法分类号TP311DOI号10.1 1897/SP. J.1016.2020. 02166ExactlyAnalyzingResponseTimeofOpenMPTaskswithConditionalBranchesSUNJi ng-Hao1 , ' 2)ZHANGLi-Wei1 1CHIYao-YaonCAOLeinDENGQi ng-Xuun( SchoolofComputerScienceandEngineering?NortheasternUni versi ty, Shenyang110819)2)(SchoolofComputerScience andTechnology^DalianUniversityofTechnology*Dal ian-,Liaoni ng116024)AbstractMul ti-coresarebecomi ngmai nstreamhardwareplatformsforembeddedandreal-ti mesystems.Toful lyutilizetheprocessi ngcapacityofmulti-cores,softwareshouldbeparallelized.Recentlymuchworkhasbeendoneonreal-ti meschedul i ngofparalleltasksmodeledasdirectedacyclicgraphs( DAG) ,motivatedbytheparal l eltaskstructuressupportedbypopularparallelprogrammi ngframeworkssuchasOpenMP.TheDAG-basedtaskmodel si nexisti ngreal-ti mescheduli ngresearchcannotful l ycapturecriticalfeaturesofparallelprograms,e.g.,i f-el seconditionalstructure.Recently,theconditionalDAGmodel sareproposedtoformulatethereal?ti mesystemscomposedbyparal lelworkloadandcondi tionalcomponents.Exi sti ngDAG-basedtaskmodel si nreal-ti mescheduli ngresearchassumespecialstructuresrecursi velycomposedbysi ngl e-source-si ngle-sinkparallelandcondi tionalcomponents.Withthisspecialassumption,polynomial-timeresponsetimeanalysismethodisdeveloped.However,realisticOpenMPtasksystemsi ngeneralhavemoreflexiblestructuresthatdonotcomplywiththisassumption.ThispaperstudiesgeneralOpenMPtasksystemswi thgeneralbranchi ngstructures,anddevelopsapolynomial-timedynamicprogrammi ngalgorithmtoefficient lycalculateresponsetimeboundsfor收稿日期:2019-08-30; 在线发布日期:2020-07-0 1. 本课题得到国家自然科学基金( 61 972076)、 兴辽英才计划( XLYC1902017 )、 NSFC-辽宁联合基金( U1908212)资助. 孙景昊, 博士, 副教授, 中国计算机学会( CCF) 会员, 主要研究方向为实时系统调度、 并行程序分析. E-mail:jhsun@dl m. edu. cn.张利威, 硕士研究生, 主要研究方向为OpenMP并行程序分析.池瑶瑶, 硕士研究生, 主要研究方向为实时并行系统调度. 曹 蕾, 学士, 主要研究方向为实时系统、 优化算法. 邓庆绪( 通信作者), 博士, 教授, 主要研究领域为实时系统. E-mail:dengqX@mai l.neu.edu. cn.11 期 孙景昊等: 带有分支结构OpemMP任务图的响应时间分析 216 7OpenMPtasksystems.First ,thispaperoutli nesOpenMPprogramsemantics,andmodelthebehavi orsofgeneralOpenMPtasksystemswithgeneralbranchi ngstructures, i ncl udi ngtaskmodel s,executionmodelsandschedul i ngmodel s.Second,t hispaperdeeplyanalyzestherelat edmethodi ntheexisti ngwork.Byconstructi ngacounterexampl e,wefi ndthattheexisti ngmethodcannotaccuratelycal culatetheresponseti meboundaryofthetaskgraphs,andtherei sacertai npessi mism.Thespecificreasonisthatal t houghtheexistingmethodconsi dersOpenMPtaskgraphswithmul ti-source-multi-si nkcondi ti onalbranchingstructures,itcannotcorrectlyanalyzesomesituati ons,e.g.,theparametersassociatedwi ththetwobranchesi ntheconditi onalbranchi ngstructurearequitedifferent. Third,fortheanalysisproblemofresponseti meonmul ti-source-mul ti-si nkcon-DAGgraphs,basedondynamicprogrammingtheory,thispaperproposesanaccuratesol uti onmethodofpol ynomialti me.Themai nideaofthi smethodi sasfol lows.TheDAGgraphi straversedtopol ogical l yi nreverseorder,thentheparametersassociatedwiththepredecessornodesarecal culatedbyusi ngthecalculati onresul tsofthesuccessornodes,andfi nal lytheresponsetimeboundoftheDAGgraphi scalculatedbasedontheval uesoftheassociatedvariablesofthesourcenode.Comparedwiththeexisti ngalgorithm,theal gorithmi nthispaperintroducesmorenode-associatedvariablesandconsi dersmorenodetypes.Intheexperimentpart,wei mplementthealgori thmofexi sti ngworkandthealgori thminthi spaper.Theresponseti meboundsofthetwoalgorithmsareeval uatedbyrandoml ygeneratedDAGs.Experimentalworkshowsthatcomparedtothetradi ti onalmethod,ourmethodcaneffecti velyimprovetheaccuracyoftheresponseti mebound. Underaverageconditions,theaccuracyoftheresponseti meboundcanbei ncreasedby3%.Itisveryi mportantforreal-timesystemtoi mprovetheaccuracyofresponseti meboundeffecti vely.Inreal-ti mesystems,theresponseti medi rectlyaffectstheschedul abi li tyofsystems.Forreal-timesystemswhoseschedulabi l ityisi ncriti calstate,theaccuracyofresponset i mei si ncreasedby1%,whichisli kel ytogreatlyi ncreasetheschedulabilityofsystems.KeywordsOpenMP;directedacycl icgraph;if-el sebranchstructure;responseti me;polynomialtimei 引 言近年来, 多核技术越来越广泛地应用于实时系统. 为了充分利用多核的计算资源, 实时软件并行化成为当前的研究热点和未来的发展趋势. OpenMP?是多核系统最流行的并行编程框架之一. 近年来, 在实时嵌人式领域OpenMP得到了广泛关注. 在实时领域中, 有向无环图(DirectedAcyclicGraph,DAG)是刻画OpenMP程序的天然模型, 基于DAG图的实时调度和分析的问题中涌现出大量研究工作[2_12:.然而, DAG图并不能完全刻画OpenMP的程序特征. OpenMP程序的一个关键特征是: OpenMP任务间不仅具有并行性, 而且在任务内还具有条件分支结构( 例如if-el se 语句). 因此, 文献[1 3-1 8]研究了带有条件分支结构的con-DAG任务图.本文发现, 现有的con-DAG任务图模型仍然不能刻画实际的OpenMP 程序. 例如, 在现有的con-DAG图中, 并行结构和条件分支结构具有单人口单出口的特征( 以下简称为“单人单出”) . 如图1所示, 该con-DAG图包含一个并行结构( 黄色框) ,并行结构内嵌一个条件分支结构( 绿色框). 这些并行结构和条件分支结构都具有一个人口和一个出口, 不允许出现图中红色边( 从条件分支结构外/内指向条件分支结构内/外) 的情况.然而, 在实际的OpenMP程序中, 并行和条件分支结构可能不满足“单人单出”条件. 图2(a) 为一个OpenMP程序, 其中条件分支结构内所触发的负载(code31) 与该条件分支结构外所触发的负载21 68计 算机 学 报2020 年(codel 4) 同步. 现有的实时调度研究并不能很好地描述和分析这种行为. 如果用类似于图1 的方法对图2( a) 中的OpenMP程序进行建模, 将有两条边( 在图2( b) 中标记为红色), 从条件分支结构外/内部节点指向条件分支结构内/外部节点. 也就是说,图2( b) 的DAG图中条件分支结构具有多个入口和出口. 当前研究[1 ^]并不适用于图2 中的任务模型.本文将对此类一般情况下OpenMP任务进行建模与分析.1#pragmaomptask{2codel l;3#pragmaomptask{code21; }4if(exp)5#pragmaomptaskwai t;6codel2;7#pragmaomptask{code31; }8else9codel 3;1 0#pragmaomptaskwai t;11 codel4;12}(a)OpenMP程序^ode2j) (^〇de3 l)v^八/(b) 相应的DAG任务图图2OpenMP程序及相应的DAG任务图本文旨在分析带有条件分支结构OpenMP程序的响应时间. 文献[9]研究发现, 不带条件分支结构OpenMP程序的响应时间, 可由经典Graham界[1 9]来限定. 由于con-DAG图的执行流是一个非条件DAG图, 所以文献[9] 的结论可以扩展到con-DAG图中. 即首先枚举con-DAG图中所有可能的执行流, 然后求解每个执行流的Graham界, 并求取最大值. 然而, 这种枚举的方法, 在面对指数规模的执行流时, 其计算复杂度也是指数的. 为了规避枚举方法, 当前研究[14 18]基于动态规划给出了con-DAG图的响应时间界限的多项式时间计算方法. 但是, 这些方法均局限于带有“单人单出”约束的con-DAG图, 不适用于带有“多入多出”条件分支结构的一般性OpenMP程序.本文针对一般性OpenMP程序开展研究, 提出具有“多人多出”条件分支结构con-DAG任务图的响应时间算法. 在撰写本文之前, 文献[20]也研究了“多人多出”条件分支结构的OpenMP程序响应时间分析问题. 但是, 本文发现, 文献[20]提出的算法并不能精确求解con-DAG的响应时间界, 具有相当的悲观性. 相比较而言, 本文提出的方法不但能够精确求解con-DAG的响应时间界, 而且还具有多项式时间的计算复杂度. 实验表明, 本文的算法在求解精度上, 优于文献[20]中的方法. 与此同时, 本文实验表明, 文献[20]方法具有较少的计算时间, 这说明在不要求较高求解精度的情况下, 文献[20]方法具有易实现、 鲁棒的优点.本文第2 节介绍con-DAG方面的相关研究工作; 第3 节建立OpenMP系统的形式化模型; 第4节介绍响应时间界; 第5 节指出文献[20] 中的方法并不能精确求解响应时间界; 第6 节提出伪多项式时间的精确算法; 第7 节是实验结果; 最后是总结与展望.2 相关工作文献[10]首次将OpenMP 程序建模为DAG图. 文献[9]针对OpenMP框架中已有的调度算法(例如, 宽度优先调度( Breath-Fi rst-Scheduling, BFS)和负载优先调度( Work-Fi rst-Scheduli ng, WFS) ) , 基于文献[10] 中DAG任务图模型, 首次为OpenMP程序提出了响应时间界限分析. 在文献[9] 中,OpenMP任务分为两种类型: 绑定型任务和非绑定型任务.其中, 绑定型任务一旦在一个线程上开始执行, 就不能迁移到另一个线程. 另外, 非绑定型任务则不受此限制, 能够在不同的线程上迁移执行. 文献[9]指出, 绑定型任务的时序分析具有内在的复杂性, 这将导致响应时间分析的悲观性. 之后, 文献[11]的研究发现, 绑定型任务不但会导致响应时间的悲观性, 还可能引起整个OpenMP系统极差的时间行为( 例如, 原本并行的程序, 由于绑定型任务的runti me 约束, 被强制在单核上串行执行). 上述工作均没有考虑OpenMP中的条件分支结构.文献[14-17]研究了con-DAG模型, 主要提出了两类计算响应时间界限方法:一种方法将con-DAG转换为不包含条件节点的( 非条件) DAG图模型,然后直接应用非条件DAG图的分析和计算方法求解con-DAG的响应时间界限#1 53. 另一种方法则是基于动态规划思想, 在con-DAG图上直接计算响应时间[1S 1 7]. 这两种方法均具有多项式时间的计算复杂性, 也都局限于“单人单出”条件分支结构的con-DAG图模型. 最近, 文献[20]研究了带有“多人多出”条件分支结构con-DAG的响应时间计算方法. 然而, 本文发现, 文献[20] 中的方法并不能精确求解con-DAG图响应时间界限, 存在一定的悲观孙景昊等: 带有分支结构OpenMP任务图的响应时间分析 2169 1 1 期性. 本文工作扩展自文献[20], 并在实验部分将本文提出的方法与文献[20]的方法进行了定量分析和比对.此外, 文献[21-24]研究了OpenMP程序的平均意义上的性能分析. 这与本文针对最坏情况下OpenMP响应时间分析存在较大的差异: 文献[21-24]基于度量的方法, 不需要显式地构建条件分支结构. 与此相反, 本文最坏情况的响应时间分析显式地构建了OpenMP程序条件分支结构和时序特性, 并根据这些信息形式化地推出响应时间的上界.3 系统模型本节通过对OpenMP程序语义进行简单介绍,建立OpenMP系统的形式化模型, 具体包括任务模型、执行模型和调度模型.3. 1OpenMP程序与线程本文主要研究具有task语义的OpenMP程序.task语义在OpenMP3.0[17:及以上版本中出现.图3 给出了一个OpenMP 程序示例. 该程序从paral l el 指令( 第1 行) 开始?parall el 指令构造了一个并行域, 其包括paral lel 指令后面花括号中的所有代码( 第2 行至第21 行) .1#pr?igmaompparall el  num_threads( m)2{ #j)ragmaompsi ngle3{#pragniaomptaskIh'4{ ccxJel l; //v\5#pragmaomptask{code21 ;//v2}//r26ifC expl )//entry:Vj; exit :7codel2; //v\8#pragmaomptask//r39{ code3 1 ;//vl10#i)ragmaomptask{code41;//v\)//r411ccxd e32; //v\12}//endofr313else14#pragmaomptaskwait;15codel3;//v\16pragmaomptaskwai t;17codel 6; //v\18codel 7; //iPx19}20}21}图3OpenMP程序示例paral lel 指令创建;《 个OpenMP线程, 其中w由numjhreads 子句指定(第1 行)?OpenMP线程是指能够执行并行域内代码的实体(例如, 操作系统中的线程). 与之前工作 类似. 本文假设每个线程独享一个内核的计算资源. 因此, 本文中“线程”的概念相当于一个物理内核.3.2OpenMP任务模型并行域中的代码可以划分为一组并行任务r=< ri,…,r? }. 其中, 任务 对应第( 个task 指令后面括号中所包含的代码域. 如图3 所示, n对应第4行的代码. 但是, 第9 行的代码不包含在ri 的代码域中. 显然, 第9 行的代码属于〇的代码域. 在OpenMP任务系统r中, 每个任务都有内部控制流结构, 任务之间存在依赖关系.本文将OpenMP任务系统r建模为DAG图G=(V, £) . 其中, V表示节点集, 每个节点表示task指令中的顺序代码段. E表示边集. 每条边表示两个节点之间的前驱后继关系.图G可以分为n个不相交的子图, 即G=G, U…UG,,. 其中, 子图G,. =(V,, £:,_) 是任务r,.的控制流图( Control-Fl owGraph, CFG) . 图4给出了图3 中对应DAG图的任务模型.在每个CFGG,=(V,, £,) 中. V, 表示节点集, 节点<表示r, 的第x个节点, 该节点的最坏情况执行时间( WCET) 定义为c( <) .£, 表示F-边集, 每条F-边( 圹, £,(在图4 中用点虚线箭头表示) 定义了节点<和<的时序关系, 即在节点<完成执行之后, 节点W才能开始执行. 特殊地, 没有F-入边的节点称为G, 的源点, 没有F-出边的节点称为G, 的汇点, 分别定义为xT和 . 本文假设每个G, 都有一个源点和一个汇点. 然而, 本文的方法也可以处理具有多个源/汇点的控制流图的情况: 只需在多个源点之前添加一个执行时间为零的虚拟源点, 在多个汇点之后添加一个执行时间为零的虚拟汇点.接下来, 分别介绍CFG图的内部结构和CFG间的依赖关系.3. 2. 1CFG图的内部结构每个任务r, 是一个具有单人口和单出口的程序21702020年 计 算机 学 报块(block). 程序块中包含条件分支结构, 如图3中第6?15 行所示.一般情况下, 每个条件分支结构包含一个进人点(if指令) 和一个退出点( endif 指令) ,以及if和else两个分支. 条件分支结构中只有一个分支会得到执行, 当该分支完成执行后, 条件分支结构退出执行. 本文允许嵌套条件分支结构, 即一个条件分支结构可以包含在另一个条件分支结构中.根据OpenMP任务内结构, 可以把CFG中的节点V, 分为两类: 条件节点和非条件节点.(1) 条件节点成对出现, 在图中用菱形和三角形表示, 它们分别表示条件分支结构的人口节点和出口节点. 如图4所示, z;丨 是条件节点. 条件分支结构包含两个分支, 每个分支都是G, 的一个子图.(2) 非条件节点是除条件节点外的所有其它节点.一个非条件节点最多有一条F-出边, 最多有一条F-人边. 非条件节点又分为以下三种类型:①T-节点(V〖) 表示task指令前的代码段. 如图4所示, 以是T-节点, 对应于图3 的第4行处的代码段codell.②W-节点(V,w ) 表示taskwai t 指令后的代码段. 如图4所示, t;丨 是W-节点, 对应于图3 的第15行处的代码段codel3.③N-节点(Vf ). 既非T类型又非W类型的非条件节点.3. 2. 2CFG间的依赖关系任务之间有两种依赖关系: 任务创建和任务同步, 详细介绍如下:(1) 任务创建. task指令用于创建OpenMP任务. 如图3 所示, 任务ri 是由第3 行的task指令创建的. OpenMP支持任务嵌套, 例如,一个任务的代码域中还包含其它任务的task指令.一般地, 如果r, 的代码域包含r, 的task指令, 则称r,?是 的父任务…是t?, 的子任务. 如果r, 是r, 的父任务, 或者r, 是5的父任务的父任务( 可嵌套定义) , 则称r, 是q的祖先任务, r, 是r, 的子孙任务. 令 为r, 的任务图以及r, 子孙任务图的并. 如图3 所示,^2 是^的孩子,〇是ri 的后代, 〇是r4 的祖先.一般地, 我们假设第一个任务n没有父任务. 任何其它任务都只有一个父任务.相应地, CFG之间也存在任务创建关系, 并由T-边来确定.T-边, 用半划线箭头表示. 父任务通过T-边指向其子任务. 准确地说, 如果(r, 的)T-节点圹创建了r, 的子任务q, 则从<到r, 的源点有一条T-边. 在这种情况下, 只有<完成执行后,r, 才能够释放和执行. 在图4中, ( 4, x4) 是一条T-边, 表示节点Z;丨 创建任务r2. 因为在OpenMP中,一个task指令创建一个任务, 所以一个T-节点关联一条T-出边.规则1. 只有T-边能从任务(的T-节点)指向其子任务( 的源点).(2) 任务同步. taskwai t 指令定义任务同步点,即任务可以在taskwait 指令处挂起并等待其它任务完成. 准确地说, 在t 时刻, 任务〇在它自身的taskwait 指令处挂起, 直到所有在Z 时刻之前创建的〇的子任务都完成, 任务^才能继续执行. 如图3所示, 任务ri 在其taskwai t 子句处挂起, 并等待其子任务 的完成.相应地, CFG之间也存在任务同步关系, 并由W-边来确定.W-边, 用实线箭头表示. 子任务通过W-边指向其父任务. 准确地说, 对于任意T-节点<以及W-节点<, 其中,<是wf的前驱…表示由<创建的r, 的子任务, 在这种情况下, 有一条W-边从^的汇点指规则2. 只有W-边能从任务( 的汇点) 指向其父任务( 的W-节点).W-边Of, 〇定义OpenMP中的父任务r, 与其子任务r,同步, 即父任务r, 在W-节点W处挂起,等待其子任务D完成后, 可恢复执行. 如图4所示,由于r2是由W的前驱节点M创建的且图中有一条从 丨 到4不经过任何中间W-节点的路径, 所以( i4,W) 是一条W-边, 该边从〇的汇点指向n中的W-节点W. 从r4 到4没有W-边, 因为r4 不是由M的前驱节点创建的. 从r2 到n有两条W-边, 即(t4,以) 和(4,4), 因为从W( ri 的T-节点) 到W-节点4和4存在路径( 不经过任何中间W-节点) , 例如(w!, 4) 和(M3. 3OpenMP执行流模型G从第一个任务r, 开始执行, 进而执行n的子孙任务. G中的每个任务r, 从源点 开始执行, 到汇点 执行结束. 在任务r, 执行期间, 有两种可能的情况.(1) 当遇到条件节点圹时, 有且只有<的一个后继节点得到执行.(2) 当遇到N-节点或T-节点圹时, 通过F-边或T-边连接的埒的所有后继节点都得到执行.根据以上执行语义, 由于G中存在条件分支结孙景昊等: 带有分支结构OpenMP任务图的响应时间分析 217111 期构, 通常情况下, 在G中只有部分任务和部分节点得到执行. 因此, G上的一次执行对应G的一个子图G、其包含执行中所遍历的所有节点. 称^为G的一条执行流e. 如图4 所示, 执行流e 中的节点和边用红色标记. 因为e 没有遍历乂, 所以W-边(t4, w丨) 不包含在e中.3. 4OpenMP调度模型OpenMP系统合理的任务调度满足以下两个约束:(1) 任务调度点( TSP) 包括任务创建点(task指令)、同步点( taskwait 指令) 以及任务完成退出点.任务的执行只能在TSP处中断和恢复.(2) 绑定型任务. OpenMP任务分为两种类型:绑定型任务和非绑定型任务. 其中, 绑定型任务一旦在一个线程上开始执行, 就不能迁移到另一个线程.非绑定型任务则不受此限制, 能够在不同的线程上迁移执行.在OpenMP任务模型中, OpenMP调度是指将执行流e 中的节点分配给线程, 直到e 中的所有节点完成执行. 根据OpenMP系统合理调度任务时满足的约束, 执行流e 的合理调度必须满足以下约束条件:( 1) 对于执行流e中任意节点<, 只有当圹在e中的所有前驱节点( <是<的前驱节点当且仅当(<, <) £ £) 都完成执行, <才能执行. 特殊地, 对于执行流e 中W-节点有两个前驱节点: <和法, 执行流e 的调度满足work-conservi ng约束. 根据文献[19]可知, 满足work-conservi ng 约束的调度具有良好的响应时间界, 如第4节所示.迁移开销. 由于本文考虑了非绑定型任务, 因此任务可能会在线程之间迁移. 任务迁移会产生系统开销. 注意到, 在OpenMP调度算法(例如, WFS和BFS) 的调度下, 任务迁移仅发生在某些特定类型的节点上, 比如, T-节点和W-节点. 因此, 迁移开销可以限定如下. 我们用〇表示单个节点的迁移开销, 用NC表示DAG图中T-节点的数目, 用NW表示DAG图中W-节点的数目. 在WFS的调度下,DAG图的总迁移开销小于NCXO. 在BFS的调度下, DAG图的总迁移开销小于NWXO.4 响应时间界在m个线程上, 应用WFS或BFS算法调度, 任务图G的最坏情况响应时间( WorstCaseResponseTime, WCRT)i?(G) 定义如下:i?(G)=max{i?(e)|e是G上的一条执行流}(1)其中, i?(e) 是执行流e 的WCRT. 由于一条执行流是一个非条件DAG图, 根据文献[9],J?( e) 可由以下引理限定.引理lw. 在m个线程上, 应用WFS或BFS算法调度, 执行流e 响应时间i?(e) 的界限如下:i?(e)</e?(e)voKe)_len(e)(2)W, 分别由F-边和W-边连接, 其中,x;丨是r, 的子任务r, 的汇点. 根据执行语义, 在迖执行之前, 节点<和任务r, 必须完成执行.(2) 任务r, 的执行在两个连续节点<和<之间发生中断, 仅当下列条件中至少有一个满足:①珥是W-节点;②<是T-节点;中的任务允许在线程之间迁移.OpenMP系统支持两种调度算法: 负载优先调度( WFS)[25]和宽度优先调度( BFS)[2S].WFS优先执行新创建的任务, 而BFS优先执行已经在线程上执行的任务. 在WFS和BFS的调度下, 非绑定型任务系统满足work-conservi ng 约束, 其响应时间可由Graham界保证. 本文考虑非绑定型OpenMP任务, 并采用WFS或BFS调度算法.本文假设执行流e 由WFS或BFS算法调度(详见3.3 节) . 根据文献[9], 基于WFS和BFS算其中,Ze?(e) 是e 的最长路径长度, twKe) 表示e 中所有节点的最坏情况执行时间之和( 即最大负载).由于式(2) 是Graham在文献[19]中首次提出的, 所以式(2) 又称为Graham界. 下面的定理表明,Graham界可以推广到带有条件分支结构的OpenMP任务图.定理1. 在m个线程上, 应用WFS或BFS算法调度, OpenMP任务图G响应时间1?(G) 的界限如下:i?(G) <max(zew(e) +^^^)(3)其中, e 代表G中的执行流.证明. 根据引理1 和式(1) , 易知定理1成立.证毕.5 已有工作存在的问题目前, 与本文最相近的工作是文献[20]. 文献2172 计 算机 学 报 2020年[20] 同样解决带有( 非“单人单出”) 条件分支结构OpenMP任务图的响应时间分析问题, 给出了多项式时间算法. 然而. 文献[20]的方法并不能精确求解式(3) 中的响应时间界, 存在一定的悲观性. 接下来,首先简单介绍文献[20]中计算方法的相关概念和关键步骤. 然后, 通过构造反例, 揭示文献[20] 中方法的悲观性. 最后, 比较本文算法和文献[20]中算法的异同点.5. 1 文献[20]中算法简介文献[20]中的算法应用动态规划技术, 按照图G的拓扑逆序对节点进行遍历. 在遍历过程中, 对于图中每个节点<, 直接利用<后继节点的计算结果, 推导出<关联变量的值. 最后, 响应时间界即可由z/r的关联变量计算得出. 接下来, 首先介绍节点<关联变量的相关概念. 然后, 给出<关联变量的递推公式.定义1(S-图) . 节点<引导的3-图0! ; ( 1;_/)包含节点<及<的后继节点, spGs0;■)={ wf}USUCC(〇. 其中, SUCC(〇为<的所有后继节点.例如, 在图4中, Gs(^4)= (y, w丨, W )?定义2(S-执行流) . 对于G中任意执行流e ,以及e 中的节点 引导的S-执行流es( <) 为子图enGs (i;f) .定义3(D-图) . 节点<引导的D-图Gd( <)包含<及<在r,?( 和 的子孙任务) 中的后继节点,即GD?)={ <} U^U^( <). 其中,=SUCC(<) 门A,? 〇, 为r, 的任务图以及r, 子孙任务图的并.例如, 在图4 中, Gd( 4)=( 4) .定义4(D-执行流). 对于G中任意的执行流£ , 以及£ 中的节点 引导的D-执行流 为子图eAGDW).节点<关联的变量定义如下.定义5(S-图Gs ( wf) 的Length) .Gs( xr; ) 中最长路径的长度, 即len^Xvxi)=m.a. y.lense{ v1:')( 4)e 6G其中, 是S-执行流es(<) 中最长路径长度.定义6(D-图GD(vp的Vol ume).Gd( t^) 中D-执行流的最大负载, 即vol^(vf )=maxvol°(vj)(5)e6G其中,tWf( wf) 是D-执行流eD( if) 中所有节点的响应时间之和, 即v<( vf)=J]c(v-;)( 6)定义7(3-图65(<) 的界). Gs(〇中S-执行流的最大界*即gra^Cvf)= maxgraf( vf)e 6G其中,graf( vf ) 是S-执行流es( wf) 的界,即graf(vf)=lenf( v-)+voIf(, v'j)—lent(a(7)(8)节点圹关联变量的计算分以下两种情况:(1) 若<是条件分支结构的人口节点, 设#和冲是tr; 的直接后继, 那么,gra V)=c ( )+ma x { gra Vwf1) ,graf;( wfOK9 )( 2) 若<是T-节点, 设^是<所创建的r, 的子任务,<‘是r,的源点, V是( 通过F-边连接的) <的后继节点, 则gra*( t;f)=c(T;;r) +max{ ri, T2 }(1 0)其中,r_srri—graG(Vj ) H-’r2=gr〇f)vol^Cv'^)m5. 2 文献[20]中算法的悲观性本节通过构造反例( 如图5 所示), 说明文献[20]中的算法不能精确求解式(3) 中的响应时间界.在图5 中, 最外层的任务r, 包含一个T-节点<和一个以<为人口的条件分支结构. 其中, T-节点<创建了r, 的子任务r,. 另外, 条件分支结构包含两个分支. 其中, 第一个分支包含一个执行时间为L的W-节点, 第二个分支包含wL个T-节点, 每个节点创建一个执行时间为1 的任务, 分别定义为n, r2,…,DAG图中其它节点执行时间均为0.图5 文献[20]的反例根据式(1 0) , 为计算<的关联变量 ( 圹) ,需要预先计算出<的关联变量 (<)和 (^)以及认''的关联变量#4( <) 和 其中,是<所创建任务r7的源点, W是<的后继节点. 如图5 所示, 根据定义6, 可以计算两个参数11 期 孙景昊等: 带有分支结构OpenMP任务图的响应时间分析 2173训6(<)=0和 ? 根据定义7, 可以计算两个参数(<)=L(1—1/m) 和W)=L+( l—l/m) . 进一步地, 可计算得出式(10) 中的中间变量A=■L+L(l_l/w^) , A=L+(l-l/m) ?因此, W<^( ^^f)=L+L(l—l/OT)?另一方面, 图5 中DAG任务图实际包含两条执行流ei 和e2. 其中, 执行流ei 包含 ,邙丨 ( 如图5 中红色和蓝色轨迹的组合) . 执行流e2包含{ wf, wf , f, w,!, wf,…, , n, r2 ,…,}(如图5中红色和绿色轨迹的组合) ei 关联的变量(〇=L,e2 关联的变量炉<2(<)=L+(1—1/m) . 因此, 以上两者取大, 可得gr4( <)=L+(l—1/m) ? 文献[20]中算法的误差为(L_l) (l_\/rn) .5. 3 本文算法和文献[20]中算法的异同由上述反例可以看出, 文献[20]中的算法存在一定的悲观性. 本文在第6 节将提出能够精确求解式(3) 中响应时间界的算法. 本文算法与文献[20]中算法的异同如下:相同点. 两个算法都采用了动态规划技术, 为图中的节点关联一定数量的变量, 按照DAG图的拓扑逆序对节点进行遍历, 计算各节点关联的变量.在计算过程中, 图中每个节点<的关联变量, 可直接利用<后继节点的计算结果得出. 最后, 响应时间界即为源点关联的相关变量.不同点. 本文的算法能够精确求解式(3) 中的响应时间界,然而, 文献[20]中的算法仅能得到近似解. 具体的原因是: 文献[20]虽然考虑了带有“多入多出”条件分支结构的DAG图, 但是不能正确分析条件分支结构中两个分支所关联的参数差异较大的情况. 例如,一个分支关联较小的 和较长的&?,另一个分支关联较大的 和较短的^?( 详见图5所示) . 在这种情况下, 文献[20]中的算法把DAG任务图中实际没有包含的路径(如图5中<) 纳入了响应时间计算, 从而导致了响应时间界的悲观估计. 为了解决这个问题, 本文算法引人更多的节点关联变量(详见第6.1 节表1), 并对节点关联变量的计算情况进行更加细致地划分( 详见第6.2 节).6 多项式时间精确算法由第5 节可知, 已有工作中的算法存在悲观性,不能精确求解式(3) 中的响应时间界. 本节将给出能够精确求解式(3) 中响应时间界的多项式时间算法.与文献[20]中方法类似, 本文依然采用动态规划技术. 如算法1 所示, 对图G进行拓扑逆序遍历, 利用后继节点的计算结果来计算前驱节点关联的参数.最后, 由源点 的关联变量值计算出图G的响应时间界.算法1.OpenMP任务图响应时间界的精确算法.输人: 带有条件分支结构的有向无环图输出: 最坏情况响应时间界1. 按照G的拓扑逆序<7 遍历节点;2. 对于G的拓扑逆序 中的每个节点x;f :3.按照6.2 节方法计算<关联的变量;4. 由<的关联变量计算G的响应时间界(详见式(3) );相较于文献[20]方法, 本文方法为图G中的节点关联了更多的变量. 这些变量对于式(3)的精确求解起到关键作用. 接下来, 首先介绍节点关联的变量. 然后, 给出响应时间界的精确求解方法. 最后, 比较文献[20]方法与本文方法的精确度.6.1 节点关联的变置图G中每个节点<的关联变量如表1 所示.表1 图G中节点关联的变置定义变量名称变量的形式化定义^uo/D(vf)volD(. v^) — max{volf( vf)}1e 6G/enD(vf)/enDCvf) = max{len^(  vf)}graD(v^)graD (up= rmi x {vol^(vf)/m+(l—l/7w)lenf(T/f)}graf(vf)grae(vf)= max{volf(vf)/m-b(l ̄ ̄l/m)len^(vf)})= n^{ w/f(uf)/m+(l—1/m)len^( vj)}gra“ (vf)gratl(vf)= maL x{vol^>(vf)/m'b( l ̄l/m)l en^( vf)}在表1 的各个公式中, 对于给定的执行流e,根据定义4, 节点<引导的D-执行流为£。( 〇.^^?( <) 为〇-执行流£13( <)的负载量. ^^( 〇为D-执行流eD?) 中最长路径的长度. 为D-执行流eD( <)中以<为起点且以 为终点的最长路径长度. &<( <) 为D-执行流eD (<) 中以W-节点为起点的最长路径长度 为D-执行流eD( 圹) 中以W-节点为起点且以 为终点的最长路径长度.6. 2 节点变量的递推公式下面介绍表1 中节点关联变量的计算方法. 根据第3 节的任务模型可知,一个节点<可能有零个后继、一个后继和两个后继三种情况. 因此, 将按照这三种可能, 分情况讨论:2174 计 算机 学 报2020年( 1 ) 如果节点圹没有后继节点, 则可按以下方法计算各参数.volD(vj)=c( vf) (11)lenD( vf )=c(vp (12)graD(vp=c( vJ) (13)grae (v-)=c( vf)( 14)(c(v〇,l—〇〇,若<是W-节点否则(15)(c(v〇9 若<是w-节点(16)[—〇〇, 否则grauXvf)grau{v-)其中,一〇〇表示“负无穷大”, 即对于任意实数?—<D〇-\ ̄a= —〇〇.(2) 如果节点<仅有一个直接后继节点, 则考虑以下三种情况:①如果<的后继节点<与t;「 同属于任务r,,则可按以下方法计算各参数.volDC vf)=cOi〇+ volD( vD(17)lenD(v〇=c(v〇+lenD(v})(18)g-raD( i;/)=c(uf) +graDC v'J )(19)grae(v^)=c(vJf) +grar { v^)(20)grau.{ vxi)<^grae(, vri) ,{ grauC vf') ,图6 给出了式( 1 7)?gra?graD^vJ), 若<是W-节点否则若<是W-节点否则(22) 的解释. 如图6 所示,(21)(22)最外层的任务 包含一个以<为人口的条件分支结构. 该条件分支结构包含两个分支. 其中, 第一个分支包含一个N-节点, 第二个分支包含一个T-节点坪, 节点<创建了r, 的子任务 DAG图中所有节点的执行时间均为1 .式(1 7) 的含义为, <的关联变量 等于<的执行时间加上<的关联变量 其中,乂是<的后继节点. 例如, 在图6 中, <的关联变量iy〇/D(z)f>=1+5=6.式(18) 的含义为, 圹的关联变量 等于<的执行时间加上W的关联变量D(W) . 其中,<是<的后继节点. 例如, 在图6 中, <的关联变量lenD(. v^)=1+ 4=5.式( 19) 的含义为, <的关联变量graD( <) 等于<的执行时间加上<的关联变量 ) . 其中,<是<的后继节点. 例如, 在图6 中, <的关联变量g*raD( iif)=1 +4+1/tw=5+1/w.式( 20) 的含义为, <的关联变量 ) 等于<的执行时间加上wf 的关联变量gra,(<) . 其中,<是<的后继节点. 例如, 在图6 中, <的关联变量gra,( uf)=l +4+l/m=5+l/m.式(21) 的含义为, 若<是W-节点, 则<的关联变量等于grau (<) . 否则,grat.(T/;‘) 等于认'的关联变量graW) . 其中, W是<的后继节点.例如, 在图6 中, 圹的关联变量gra?.(^)=5/m.式(22) 的含义为, 若<是W-节点, 则<的关联变量gra? 〇f) 等于gvaf( <). 否则,gra?( t/f) 等于<的关联变量 其中, ¥是<的后继节点.例如, 在图6中, <的关联变量^7^?( 〇=5/?1 .②如果<是T-节点, 则可按以下方法计算各参数. 其中…是T-节点<所创建的任务 是任务的源点, 也即<的后继节点.volD(v〇=c( vf) +volD(vjrc) (23)lenD(: ^)=f( ^)+Ze?D( v7r) (24)graD( vf)=cC vf)+graD(vjK) (25)grae( vp==c(vf) (26)grauXv^)]^\graD(vJ) ,[—〇〇,若*^是w-节点否则(27)grau( v〇^\grae{ vx{) ,L—〇〇,若W是W-节点否则(28)图7 给出了式(23)?(28) 的解释. 如图7 所示,最外层的任务r, 包含一个T-节点<, wf创建了的子任务 任务r, 包含一个以wj为人口的条件分支结构. 该条件分支结构包含两个分支. DAG图中所有节点的执行时间均为1.式(23) 的含义为, <的关联变量wZD( t;;r) 等于<的执行时间加上 的关联变量D(%〃). 其中,是节点<所创建任务r, 的源点.例如, 在图7 中,孙景昊等: 带有分支结构OpenMP任务图的响应时间分析 21 75 11 期V, 的关联变量w/D(<)=l+6=7.式(24) 的含义为, <的关联变量 等于<的执行时间加上 的关联变量 其中,是节点<所创建任务^的源点. 例如, 在图7 中,v厂 的关联变量/enD( v/)=l+6=7.式(25) 的含义为, <的关联变量 等于<的执行时间加上 的关联变量graD(W:;"') . 其中,<"是<所创建任务r,的源点. 例如, 在图7 中,<的关联变量g"raD(z;f)= 1+6=7.式(26) 的含义为, <的关联变量 等于<的执行时间. 例如, 在图7 中, 的关联变量grae(vf)=l.式(27) 的含义为, 若<是\^-节点, 则<的关联变量grau.(wf) 等于graD( v;') . 否则,gra?.(uf) 等于_〇〇. 例如, 在图7 中, v;■的关联变量gra?.( wf)=_〇〇.式(28) 的含义为, 若<是W-节点, 则<的关联变量gra?( wf)等于gra,(<). 否则, 等于_〇〇. 例如, 在图7 中, <的关联变量gru?( v;")=③如果<的后继是W-节点%'?( 任务r, 即为r,的父任务), 则可按以下方法计算各参数.voln{vxi)=c{ vxi)( 29)W5( ^)=c(^) +/enD( u;)(30)graD( vf)=c(vf)+graD( vJ)(31)gra, (vf)=c( vf)(32)grau,(vf)jgraD( vf) ,l—oo,若<是W-节点否则(33)grau{vxi)I graAvD^ 若<是W-节点否则图8 给出了式(29)?(34) 的解释. 如图8 所示,最外层的任务r, 包含一个W-节点<、一个T-节点<和一个以<为入口的条件分支结构. 其中, T-节点<创建了r7 的子任务^. 0八&图中所有节点的执行时间均为1.式(29) 的含义为, <的关联变量wZD( <) 等于<的执行时间. 例如, 在图8 中, M的关联变量volD( v-)=\ .式(30) 的含义为, Z;「 的关联变量ZmD( <) 等于<的执行时间加上<的关联变量^ 其中,<是W-节点且为<的后继节点. 例如, 在图8 中,<的关联变量ZraD(z;f)=l+5=6.式( 31 ) 的含义为, <的关联变量grflD( <) 等于<的执行时间加上v丨的关联变量gvaD( <) . 其中,<是W-节点且为<的后继节点. 例如, 在图8 中,<的关联变量graD( z;f)= 1+5=6.式( 32) 的含义为, <的关联变量graf( <) 等于<的执行时间. 例如, 在图8中, t/f 的关联变量grar ^)=l.式(33) 的含义为, 若圹是W-节点, 则<的关联变量 (<) 等于 (<). 否则, (<) 等于—〇〇. 例如, 在图8 中, <的关联变量gra?(<)=—〇〇?式(34) 的含义为, 若<是W-节点, 则<的关联变量gra?(t/「) 等于graf〇丨). 否则, 等于_〇〇.例如, 在图8 中, <的关联变量gra?( <)=(3) 如果节点<有两个直接后继节点, 则考虑以下三种情况:①如果<是条件分支结构的人口节点( 假设W的两个后继节点分别为<和W), 则可按以下方法计算各参数.ti〇/r,( Tyf)=c(w/) 4-max{ TO/D( ^;'), volD(vzi) }(35)lenD(. v'l)=c(vf) ̄hmax{lenD( v'), lenD(v^)}( 36)graD(t;p=c(wf) +max{ g'raD(t;;'),graD(Ty;)}(37)grae(. vj)=c( vl) +max{ grar( Vi), gra,Xv])}(38)(graoi vl),若v;■是W-节点graw{v])<max{ ^ra?,(wf),gravl ,Xvz,') }, 否则( 39)grau ( v^)=max{ gra?( w;'),grau(d;)}( 40)图9 给出了式(35)?( 40) 的解释. 如图9 所示,最外层的任务r, 包含一个T-节点<和一个以<为入口的条件分支结构. 其中, T-节点<创建r, 的子任务 另外, 条件分支结构的第一个分支包含一个2176 计 算机 学 报 2020年节点<, 第二个分支包含一个节点DAG图中所有节点的执行时间均为1 .式(35) 的含义为, 节点圹的关联变量等于的执行时间加上max{ x;oZD(t;f) ,t;oZD(z^) }.其中, W和W是条件节点<的两个后继节点. 另外,max{ ro/D( t;;v) , t;oZD( W) } 表示在I;'的关联变量w/ W) 和W的关联变量t^D( 〇中取最大值. 例如, 在图9中, 1^0( 〇=3,1^0( ?^)=4. 因此, <的关联变量^〇ZD(i;f)=1+4==5.式(36) 的含义为, 节点圹的关联变量^72D( 〇等于<的执行时间加上max{ZewD(t;f) , ^#( 1;丨)}.其中, W和W是条件节点<的两个后继节点. 另外,max{W) , ^72D(<)} 表示在W的关联变量^/zD( z;f) 和<的关联变量/mD( <) 中取最大值. 例如, 在图9中“e7zD(t;?)=3,^nD(t;p=3? 因此, <的关联变量Zwd(<)=1+3=4.式(37) 的含义为, <的关联变量 (圹) 等于奴f的执行时间加上niax{ graD( z;f) ,尽?-<20( <)}. 其中, <和W是条件节点<的两个后继节点. 另外,max{ graD(t;『) ,graD( t^)} 表示在节点<的关联变量graD( t;;v) 和<的关联变量graD(<) 中取最大值. 例如, 在图9中,graD?)=3, graD( z;f)= 3 + l/m. 因此, <的关联变量gTaD( 〇=l+3+l/m=A+l/m.式(38) 的含义为, <的关联变量 等于<的执行时间加上max{(V) , gra,(W)}? 其中, <和<是条件节点<的两个后继节点. 另外,max{gra, (V),gra,(<) 丨 表示在z;;v的关联变量n〇;') 和*^的关联变量 ) 中取最大值. 例如, 在图9中,容rae(z;;v)=3,graf( <)=3+1/7W? 因此, 的关联变量grae( z;f)=l+ 3 + l/m=4+l/m.式( 39) 的含义为, 若<是W-节点, 则<的关联变量grat, (<) 等于graD(<) ? 否则,graw( z/f)等于max{( i;;v) ,gn2u〇;)}? 其中, I;:; 和t;『 是条件节点<的两个后继节点. 另夕卜, max{grau, (V ) ,grau.( <)} 表示在节点I;;'的关联变量gra_a.〇;') 和W的关联变量 中取最大值. 例如, 在图9中, W的关联变量 u,(<)=4/m.式(40) 的含义为, 圹的关联变量 等于max{ gn2?( W), waM(t;〖) } . 其中, Z;;'和t;『是条件节点<的两个后继节点. 另夕卜?max{grau(V) ,表示在节点t;? 的关联变量gra?(<) 和<的关联变量graJO中取最大值. 例如, 在图9 中,<的关联变量gra?( <)=4/m.②如果圹创建任务r, 且有后继节点W( 如图10所示) , 则按以下方法计算各参数.voll)(v-)=c( vf) ̄hmax{ volD( v'i), volD(vSjn)}(41 )Z^D( t;;r)=c(t;;r)+ max{/^D(t;;v) ,/^D(z;;rf) }(42)graD( vf)=c(vf) +max{ r] , r2, r3 } (43)其中,Fj=volD{v')n) / gra^v)) ,r2=graD(vJc) +volD(v) /m,r3=grae ( vs/c) +grauXvy, ),grae{vxi)=c{ vxi)Jrmd.x{ 〇t\ 9 〇2)(44)其中,n,\:Qzgra^Xv^)■uoZD( w*rr)/m +gra,(-y;v) ,gra,( v" )+ grau(u;') ,|^mD(t;f), 若■是W-节点Ura?.(<), 否则(45)gra?(vj)(grar( vf) ,\gra?(vn^若<是W-节点(46)否则图10 给出了式(41)?(46) 的解释. 如图10 所示, 最外层的任务r, 包含一个T-节点<和一个以<为入口的条件分支结构. 其中, T-节点埒创建了r,的子任务r,.DAG图中所有节点执行时间均为1.图10 式(41)?(46) 的解释示例式(41) 的含义为, <的关联变量 等于V;■的执行时间加上max{ wc^D( w;v) ,i;oZD('£;7v) } . 其中, W是<的后继节点,<是节点<所创建任务r,的源点? 另夕卜, max{ w/W))} 表示在<的关联变量D) 和的关联变量D() 中取最大值. 例如, 在图10 中, w/W) =4,tWu(i;厂) =1. 因此,<的关联变量xWD(t;f)=l +4=5.式( 42) 的含义为, <的关联变量Zenu( 〇等于「的执行时间加上max{ZewD((w厂) }. 其中¥是<的后继节点, <■‘是节点<所创建任务f,的源点. 另外, max{&?D(<),(<") } 表示在<1 1 期 孙景昊等: 带有分支结构OpenMP任务图的响应时间分析 2177的关联变量&DUV) 和<的关联变量&°(<) 中取最大值. 例如, 在图10 中,/ewW)= 4, ( <)=1. 因此, <的关联变量 ( 圹)=l +4=5.式(43) 的含义为, <的关联变量^ 等于<的执行时间加上maxlr!, r2, r3 }. 其中, max{ ri,A, r3 } 表示在r, 、 r2 和a中取最大值. 令<■‘是<所创建任务r, 的源点, V是<的后继节点, 参数^(: ^: ^以的含义表示如下: /^等于^的关联变量uo/D(t^)/w加上T;'的关联变量gra丨 ^(vf ); r2等于 的关联变量 D() 加上<的关联变量wZD( t;;v)/m; r., 等于 的关联变量#?(<)加上W的关联变量gra?.(z;;'). 例如, 在图10 中, ri=4+1/所, 乃=1+4/?2 , 1\=1+4/;^因此,圹的关联变量)= 1 +4+1/w=5+1/7k.式( 44) 的含义为, <的关联变量 等于<的执行时间加上max{X2i, 仏} . 其中, max{ ,仏} 表示在辽和仏中取最大值. 令节点 是< 所创建任务巧的源点, 节点<是<的后继节点, 参数认( 1=1,2) 的含义表示如下: 仏等于<"的关联变量WD(t;p/m加上<的关联变量 办等于的关联变量 “) 加上W的关联变量grfl?(V;). 例如, 在图10中, ■0!=4+ 1/m, 從=1"I""4/wi. 因此, wf的关联变量gra,( wf)=1+ 4+ 1/m=5+1/m.式( 45) 的含义为, 若<是W-节点, 则<的关联变量gra?. Of) 等于gra^(z/f) . 否则,gra?, (<) 等于<的关联变量 其中, 认'是<的后继节点.例如, 在图1 0 中, V; 的关联变量gra?.(<)=4/W.式( 46)的含义为, 若<是W-节点, 则<的关联变量gra?(<) 等于 (uf) . 否则,gra?(<) 等于切'的关联变量 (W) . 其中, 认'是<的后继节点.例如, 在图1 0 中, 的关联变量gra?( 〇=4/w.③如果<创建任务r, 且有后继W-节点<( n是r, 的父任务) , 如图1 1 所示, 则按以下方法计算各参数.wZD(〇=c(^) +z^D( z;厂)(47)lenn( v^)=c( vf) +max{ lenu( v]' c)Uen' ^iv^)}(48)graD( vf)=c(z)/) 4-max< ri ,graB{v]rc)}(49)其中,grauXvJ)[graD(v-) , 若z;f是W-节点否则( 51)gra?( vj)-\ grar(. v^), 若 是W-节点否则图1 1 给出了式( 47)?( 52) 的解释. 如图11 所示, 最外层的任务n包含一个T-节点W和一个W-节点其中, T-节点X;丨 创建了r, 的子任务r,.r, 包含一个T-节点<, T-节点<创建了r, 的子任务r;.包含一个以'u'为人口的条件分支结构. DAG图中所有节点的执行时间均为1 .图1 1式(47)?(52) 的解释示例式(47) 的含义为,t;; 的关联变量tWD( 〇等于<的执行时间加上<的关联变量 ). 其中,是<所创建任务r,的源点. 例如, 在图1 1 中, <的关联变量wo/!D( t^)=l+4=5.式( 48) 的含义为, <的关联变量/e?D( 〇等于<的执行时间加上max{ /ewD(), /e?D(幻丨)} . 其中, 幻厂是^所创建任务r,的源点,I;丨是W-节点且为<的后继节点. 另外, max{Z?; KD( y), ZewD(t;p} 表示在<‘的关联变量^?D(<‘) 和<的关联变量ZewD(<) 中取最大值. 例如, 在图11 中,=1. 因此, 的关联变量ZeZOf)=1+ 4=5.式( 49)的含义为, t;; 的关联变量gra[)( <) 等于<的执行时间加上max{r!,graD(■?厂) } . 其中,max^ r,, ^%(<)} 表示在厂, 和节点<‘的关联变量graD( f) 中取最大值. 令 是xr;■所创建任务r,的源点,<是W-节点且为X;「的后继节点, 参数A等于<‘的关联变量D(<f) /m加上t;丨的关联变量ZenD( <)? 例如, 在图1 1中, r,=1+4/m, gxaD(t;p=4. 因此,<的关联变量gnzD(<)= l+4=5.式( 50) 的含义为, <的关联变量gra,( <) 等于<的执行时间. 例如, 在图1 1中,)=1 .式(51) 的含义为, 若<是1-节点, 则<的关联变量graa.(<)等于graD(<) . 否则,gra?. (<)等于—〇〇. 例如, 在图1 1 中, <的关联变量gra?.( ^)=F]= volD( vs ")/m-\-lenu(v\) ,gra,XvJ:)=c{ v-) (50)2178 计 报 2020年 算式(52) 的含义为, 若<是W-节点, 则<的关联变量Of) 等于a,Of). 否则, ( t;f) 等于_〇〇. 例如, 在图11中, vf的关联变量gra?( <)=—〇〇?时间复杂度分析. 本节的算法具有多项式时间计算复杂度, 其理由如下: 首先, 本节算法为图G中的每个节点计算6 个参数, 故需要计算的参数总个数为6n( n为图G中的节点个数) . 其次, 每个节点上参数的计算直接利用该节点后继节点的参数计算结果. 根据式(1 1)?( 52) , 每个参数的计算时间为CK5), 其中 为节点的最大出度. 综上, 本节算法总的计算复杂度为OG5).6. 3 算法1 的误差分析本节介绍算法1 在图5 示例上响应时间的计算过程, 并比较文献[20]算法与算法1的精确度.如图5 所示, <有两个直接后继节点和<.其中, 是<所创建任务r,的源点. 根据式(4 3) ,为了计算<的关联变量^ 需要预先计算w广的关联变量wZD() 、graD() 和gra,( I)厂)以及W的关联变量wZD(w;v)、graD(〇 和grau.(T;;v) .如图5 所示, 仅有一个直接后继节点W, 并且<为W-节点. 根据式(29)、(31) 、 (32) , 可以计算以下三个参数wZD( 取厂)=0、yaD(x;厂)=0和gra, ()=0. 如图5 所示, z;;'有两个直接后继节点且为条件分支结构的人口节点. 根据式( 35) 、 (37)、 (39), 可以计算以下三个参数TO3ZD(z;;v)=7WL、 g"raD( w;v)=L+( 1一1/m) 和 Uf)=L? 进一步地, 可计算式(43)中的中间变量f"i=L +1_l/?i , ^二!^ 和jP3=L? 因此, graD( uf)=L+(l_l/m) .根据5.2 节可知, 相较于图5 的真实响应时间界a+(l— l/m) ) , 文献[20]算法求得的响应时间界误差为( L—l) (l_l /m). 根据上文可知, 本文算法求得的响应时间界为L+(l—1/m) , 即真实响应时间界. 因而, 文献[20]算法仅能求得近似解, 而本文算法能够得到精确解.7 实验结果本节实现了文献[20]的算法( 记为AlgO) 和本文第6 节的算法( 记为Algl) . 实验所使用的微型计算机为DELLOptiPlex3050 台式机, 硬件配置为Intel ( R)Core( TM)i5-7500CPU@3.40GHz, 8GB机 学DDR4 内存(7.89GB可用), 操作系统为MicrosoftWi ndowslO64 位? 利用Python语言进行编程, 程序运行环境为Python3.7, 并利用Python模块matpl otli b绘制实验图. 通过随机生成的算例, 对算法求得的响应时间界和计算时间进行了评估. 随机算例的生成程序描述如下.随机生成《个con-DAG任务图{ G, ,…, G,,} .每个任务图在[10 , 40]范围内随机选择非条件节点个数. 每个非条件节点的最坏情况执行时间的取值范围为[1 , 1 00]. 此外, 每个任务图中条件节点的执行时间为〇.对于每个任务图, 按照从源点到汇点的顺序生成图中的节点. 每个新生成的节点<以Pi f 的概率确定为条件节点. 如果<为条件节点, 则生成<对应的条件分支结构. 该条件分支结构包含一个人口节点( 即节点<) 、 两个条件分支和一个出口节点.如果<不是条件节点, 则将其随机插人到任务图现有的条件分支中. 对于每个非条件节点<, 以 的概率将珥确定为T-节点, 以 , 的概率将<确定为W-节点, 以 的概率将<确定为N-节点, 并且保证Pn<>r++P仰i , = 1 ?对于r, 中任意的T-节点<, 在任务集{ r,+丨,…,中选择一个尚未分配父任务的 确定r, 是r, 的父任务, 即构造从<到q源点 的T-边. 如果不存在这样的r,, 则调整<为N-节点.对于W-节点<, 设<为<的前驱T-节点, 假设r;是由<创建的任务, 从巧的汇点到W-节点<添加W-边?图12?图16 针对不同的参数组合进行实验,参数配置如图例所示. 其中, m表示线程数, n表示任务数, Pi , 表示条件节点的生成概率,, 表示W-节点的生成概率, 表示T-节点的生成概率.图1 2?图1 6 的( a) 中, 灰色柱状图代表AlgO求得的响应时间界的平均值i?。 ; 白色柱状图代表Algl求得的响应时间界的平均值 箱型图展示了AlgO和Algl 的响应时间界差值(Gap) 的分布. 具体来说, 箱型图对响应时间界的差值按照从小到大排序, 箱型图的顶表示第75%的数据; 箱型图的底表示第25%的数据; 箱型图顶和底之间的区域表示25%?75%的数据; 中间浅线表示中位数, 即第50%的数据; 上须线表示Gap 的最大值; 下须线表示Gap 的最小值? 图12?图16 的(b) 中, 实折线代孙景昊等: 带有分支结构OpenMP任务图的响应时间分析 21792505008048121 6202428323640( a ) 线程数481216202428323640( b) 线程数图12w=10,Pif= 0.3,Pwai t=〇-3,Pcre= 0.30.050.100.150.200.250.300.350.400.450.50( a ) Plf0.050.100.150.200.250.300. 350.400.450.50(b)Pi t1 1期表AlgO 求得的计算时间; 虚折线代表Algl 求得的计算时间; 箱型图展示了Algl 和AlgO 的计算时间比值的分布. 具体来说, 箱型图对计算时间的比值按照从小到大排序, 箱型图的顶表示第75%的数据;箱型图的底表示第25%的数据; 箱型图顶和底之间的区域表示25%?75%的数据; 中间浅线表示中位4011601 . . 1 R01 l i?1数, 即第50%的数据; 上须线表示计算时间比值的最大值; 下须线表示计算时间比值的最小值. 对于每种参数组合, 进行1〇〇〇 次随机实验. 实验表明,Algl 能够改进响应时间界的精度, 与AlgO 的平均界差可达176. 另外, 针对所有算例, Algl 的计算时间在14.3 ms 之内, 略高于AlgO.8 i ,6( a) 任务数( b) 任务数图13m=4,Pif= 0.3,Pwait =0.3,Pcre= 0.3160l- 1 1 6040. —===—17bi . .  . . 1 R01 \ Rlj_^_T〇loo9080706050 403020 10ooo642ws/匣宮埏44>ooo>ooou80706050 40302010201500050鰣4-112804030201 0(OIXV蜍Rlfe^i#543213|阳12鰣441G(&o)猢昧叵宏闼晋20018480(OIX)/虼匣宏闼昏12140图14m=i,n=10,Pwah=〇.3,Pcrc=0.321 80 计 2020年0. 050.1 00.150.200.250.300.350.400.450.50 0.050.1 00.150.200.250.300.350.400.450.50( b) POT图15:4,72=10,Pi f =0?3,Pwai , =0?30.050.1 00.150.200.250.300.350.400.450.500.050.100.150.200.250.300.350.400.450. 50Ca) Pwai t(b) Pwai t图16m=4,72 =1 0,Pj f=0.3,Pc re= 0.3如图12 所示, 实验数据表明, 硬件平台上处理器核数会影响Al gO 与Al gl 求得的Gap? 在一般情况下, 随着核数的增多, 两个算法求得的Gap越小.根据Graham界式( 3) , 核数越多, DAG图的最大负载对于响应时间的影响越弱. 因此, 该实验现象表明, 相对于提升DAG图最长路径长度的评估精度而言, Algl 能够更有效地改善DAG图最大负载的评估精度. 另外, Algl 与AlgO 的计算时间比值不超过3.5.如图13 所示, Gap随着任务数的增长而增大.具体原因如下: 随着任务数的增多, 有向无环图的总负载增大. 由于Al gl 能够更加精确地估计有向无环图的最大负载量( 如图12 所示) , 因此, Gap 随着任务数增长呈递增趋势. 另外, Algl 与AlgO 的计算时间的比值略微减少.如图U所示, 随着Pif 的增大, Gap具有増大的趋势. 具体原因如下: 心的值越大, 有向无环图中条件分支嵌套结构越复杂, 越有可能产生有利于Algl的子结构( 如5.2 节中的反例). 另外, Algl 与AlgO的计算时间比值呈递减趋势.如图15 所示, 随着厂?的增大, Gap 呈现递增趋势. 具体原因如下: 根据随机算例程序, 越大,单个任务的子任务就越多, 这导致了较大的任务并行度. 在高并行度的算例(如5. 2 节的反例) 中更能体现Algl 的优越性. 另外, Algl 与AlgO 的计算时间呈现线性增长趋势.如图16 所示, 随着尸_的增大, Gap略微减少.具体原因如下: Pwai, 的值越大, 有向无环图的最长路径长度越长. 根据Graham界式( 3) , 最长路径长度越长, DAG图的最长路径长度对响应时间的影响越强. 因此, 实验现象表明, 对于响应时间精度的影响而言, 提升DAG图最长路径长度的评估精度并没有改善DAG图的最大负载精度明显( 如图12 所示). 另外, Algl 与AlgO 的计算时间呈现线性增长的趋势.实验数据表明,一方面, 与Algl 相比, AlgO 需要更少的计算时间( 平均意义下, AlgO 能够节省2.5 倍的计算时间) , 并且能够尽可能高地保障响Rb?-M1bis4432121(2XV酴叵宏遏#孙景昊等: 带有分支结构OpenMP任务图的响应时间分析 2181 1 1 期应时间界的精度. 这说明Al gO 具有易实现、 鲁棒的优点.另一方面, 相较于AlgO , Algl 能够有效提高响应时间界精度. 在平均情况下, 响应时间界精度能够提高3%. 能够有效改善响应时间界精度, 对实时系统是至关重要的. 原因如下: 在实时系统里, 响应时间直接影响着系统的可调度性. Algl 在平均响应时间界精度上提高3%, 这会增强系统可调度的概率.值得注意的是, 在实际系统中, 通常存在多个DAG任务并行工作的情况. 尽管对于单个DAG任务,Algl带来的精度提升有限(通常是原响应时间界的3%) , 但是, 对于包含多个DAG任务的实时系统而言, 如果每个DAG任务的响应时间界精度提升3%, 其积累的精度也是很可观的.另外, 与AlgO 相比, Algl 的计算时间有所增加. 但是, 这种增加并不会破坏实时系统的实时性.具体原因如下: 在实时系统里, 系统计算性能和运行时间是非常重要的. 其中, 系统运行时间指的是在系统部署之后运行时的时间. 本文方法应用于系统部署之前, 对系统进行离线分析和验证. 因此, Al gl 的计算时间与系统部署之后实际运行的时间没有必然联系.综上所述, 尽管Algl 增加了计算时间, 但是提升了响应时间界的分析精度. 这对于保障系统的安全性来说是值得的: 对于可调度性处于临界状态的实时系统而言, 响应时间精度有1%的提升, 都有可能极大地增加系统可调度的概率.8 总结与展望OpenMP是实时系统最有希望的多核并行编程框架之一. 近年来, 实时系统领域的研究热点围绕OpenMP的DAG任务图展开. 当前, DAG任务图的研究很少考虑OpenMP程序的条件分支特征. 尚未有研究能够精确计算出带有条件分支结构OpenMP任务图的响应时间界. 本文致力于研究OpenMP的并行结构和分支结构特征, 基于动态规划技术提出了能够求解带有条件分支OpenMP任务图响应时间界的精确算法. 并且, 本文方法具有多项式时间的计算复杂度. 下一步的工作将围绕OpenMP程序更复杂的实际特征展开, 例如, 程序中的循环和递归特征. 为带有条件分支和循环递归结构OpenMP程序的响应时间分析提供新的理论和方法.参 考 文 献[1 ]BoardOAR.OpenMPapplicat ionprogramint erfaceversion3. 0. Barcelona,Spain;BarcelonaSupercomputingCenter,TechnologyReport:01 ,2008[2]SaifullahA?LiJ?AgrawalK?etal.Multi-corereal-t imeschedulingforgeneralizedparallelt askmodels. Real-TimeSystems,201 3,49( 4 ) :404-435[3]Li J,LuoZ, FerryD,etal.GlobalEDFscheduli ngforparallelreal-ti metasks.Real-TimeSystems ,2015,5 1(4) :395-439[4]FerryD, LiJ, MahadevanM,etal.Areal-ti mescheduli ngserviceforparal lel tasks//Proceedi ngs of the2013IEEE19t hReal-TimeandEmbeddedTechnologyandApplicationsSymposium( RTAS).Philadelphia,USA,2013 :261-272[5]Sai fullahA,FerryD,LiJ,etal.Parallelreal-timeschedulingofDAGs. IEEETransactionsonParallelandDi stributedSyst ems,2014?25( 12 ) :3242-325 2[6]BaruahS. I mprovedmultiprocessorglobalschedulabilityanalysisofsporadicDAGtasksystems/ /Proceedingsofthe201426thEuromi croConferenceonReal-TimeSystems.Madri d*Spain,2014:97-105[7]QamhiehM?Faubert eauF,GeorgeL?MidonnetS. GlobalEDFscheduli ngofdirectedacycl icgraphsonmultiprocessorsyst ems//Proceedingsoft he2 1stInt ernati onalConferenceonReal-Ti meNetworksandSystems.NewYork,USA,2013 :287-296[8]QamhiehM,GeorgeL?MidonnetS. Astretchingalgorithmforparallelreal-timeDAGtasksonmultiprocessorsystems//Proceedi ngsof t he22 ndInternat ionalConference onReal-TimeNetworksandSystems.NewYork,USA,2014:13[9]SerranoMA,MelaniA,VargasR?etal.Timingcharacter?izationof OpenMP4taskingmodel//Proceedingsofthe2015Internati onalConferenceonCompilers,Archi t ectureandSynthesi sforEmbeddedSyst ems( CASES).Amsterdam,Net herlands,2015 :157-166[10]VargasR, QuinonesE?MarongiuA. OpenMPandtimingpredictability: Apossi bleunion?//Proceedingsofthe2015Design, AutomationTest i nEuropeConference&?Exhibi t i on. SanJosetUSA?20 X5 : 617-620[11]SunJinghao, GuanNan,WangYang,etal. Real-t i meschedulingandanalysi sofOpenMPtasksyst emswi t ht i edtasks//ProceedingsoftheReal-Ti meSystemsSymposi um(RTSS) . Pairs,France,2017 : 92-1 03[12]ZhouJia-Xiang,ZhengWei-Min. Astaticscheduli ngalgorit hmonDAGpart ition-reconf igurationi nt henet workofworkstations.JournalofSoft ware ?2000 ?1 1 ( 8) :1097-1104( inChinese)(周佳祥, 郑纬民. 基于DAG图解一重构的机群系统静态调度算法.软件学报, 2000,1 1 ( 8) :1097-1 104)2182 计 报 2020年 算 机 学//Proceedi ngsoft he2019IEEEReal-TimeandEmbeddedTechnologyandApplicationsSymposi um( RTAS).Montreal ,Canada,201 9 :169-181[13 ]FonsecaJC?NelisV?RaraviG,PinhoLM. Amulti-DAGmodelforreal-t i meparall elappli cat ionswi t hcondit i onalexecut i on//Proceedingsof the 30thAnnualACMSymposi umonAppli edComputing.NewYork, USA,2015 : 1 92 5-1 932[1 4]BaruahS, Bonif aciV, Marchett i-SpaccamelaA.Thegl obalEDFscheduli ngofsystemsofconditionalsporadicDAGtasks//Proceedingsoft he201527t hReal-TimeSyst ems( ECRTS).Lund,Sweden,2015 :222-231[1 5]BaruahS.Thef ederat edschedul i ngofsyst ems of condi t i onalsporadi cDAGtasks//Proceedi ngsof the1 2thI nternationalConf erenceonEmbeddedSoft ware.NJ,USA,201 5:1-1 0[16]Mel aniA.BertognaM,Boni f aciV, etal . Response-ti meanalysi sofconditi onalDAGtasksi nmu ltiprocessorsystems//Proceedi ngsoft he201527t hEuromicroConferenceonReal-TimeSystems. Lund, Sweden,2015 :211-221[ 17]Mel aniA,Bert ognaM,BonifaciV,etal.Schedu labilityanalysisofconditional paral leltaskgraphsi nmulticoresystems. IEEETransactionsonComputers ?2017 , 6 6 ( 2 ) :339-3 53[18]SunJ,GuanN, WangY,etal.Feasibilityoffork-joinreal-t imet askgraphmodels:Hardnessand algorit hms. ACMTransacti onsonEmbeddedComputingSystems,2016 ,15( 1) :14匸19]GrahamRL. Boundsforcertai nmultiprocessinganomal i es.BellSystemTechnicalJournal ,1 966, 45 ( 9 ) : 1563-1 581[20]SunJ, GuanN,SunJ, ChiY. Calculati ngresponse-ti meboundsforOpenMPtasksystemswithconditionalbranches[21]LiuX, Mell or-CrummeyJ, FaganM. Anewapproachforperf ormanceanalysisofOpenMPprograms//Proceedi ngsofthe2 7t hI nternationalACMConferenceonInt ernationalConferenceonSupercomputing. NewYork,USA, 201 3:69-80[2 2]Ei chenbergerAE,Mel lor-CrummeyJ?SchulzM,etal.OMPT:AnOpenMPtoolsappli cationprogrammi ngi nterfaceforperf ormanceanalysi s//Proceedi ngsoftheI nt ernati onalWorkshoponOpenMP. Canberra ,Austral i a,2013 :171-185[23]HuckKA,Mal onyAD, ShendeS, JacobsenDW.I ntegrat edmeasurementf orcross-platf ormOpenMPperformanceanalysis//ProceedingsoftheInternational WorkshoponOpenMP. Salvador,Brasil ,2014: 146-160[24]Di etrichR, Schmit tF, GrundA, Schmidl D. Performancemeasurementfor the OpenMP4. 0 offloadingmodel//Proceedi ngsoft heEuropeanConf erenceonParallelProcessing. Porto,Portugal,2014:2 91-301[25]FrigoM,Lei sersonCE.RandallKH.Thei mplement at ionoftheCilk-5multithreadedlanguage. ACMSIGPLANNotices ,1998,33(5):212-223[26]NarlikarGJ.Schedul ingthreadsf orlowspacerequi rementandgoodlocality.TheoryofComputingSystems,2002,35( 2) :1 51-187SUNJi ng-Hao, Ph.D. , associateprofessor.Hisresearchi nt erestsincl udereal-ti mesystemschedulingandparallelprogramanalysis.ZHANGLi-Wei,M. S.candidate.HisresearchinterestsincludeOpenMPparall elprogramanalysis.CHIYao-Yao,M.S.candidat e.Herresearchinterestsincludereal-ti meparall elsystemscheduling.CAOLei ,B.S.Herresearchi nterestsincl udereal-timesystemandoptimizationalgorithm.DENGQing-XutPh.D.?professor.Hisresearchinterestisreal-t i mesystem.BackgroundNowadays,witht hedevel opmentofmul ticores,high-performanceandreal-ti meofsoft warehavedrawnincreasinginterestsi nembeddedandreal-t imecomputingsystems.OpenMPcanful lyrefl ecttheparall elnatureofreal-ti mecomputing,andisoneofthemostpromi singthedefact ostandardforbuil di ngnext-generationreal-timeembeddedsystems. OpenMPreal-timeschedulingtheorybreaksthroughtheyhavenotbeenresol ved.Thi ssubjectistostudythedi fficultprobl emsinOpenMPreal-timescheduling. Inthereal-timefiel d,adirect edacyclicgraph( DAG)isthenat uralmodelforcharacterizi ngOpenMPprograms.However,DAGscannotaccurat elydescribeOpenMPprogramsbecauseOpenMPprogramsarenot onlyparal lel, butalsoi ncl udeconditionalbranches(suchasif-el sest atement) .Therefore,researchontheconditionalDAG(con-DAG)t askgraphisstil lopen.ExistingDAGt askmodelsassumewel l-nest edst ructuresrecursivelycomposedbysingle- source- single- sinkparal l elandcondit ionalcomponents.However,con-DAGsingeneraldonotcomplywiththisassumption, andexist ingwork孙景昊等: 带有分支结构OpenMP任务图的响应时间分析 2183 11 期cannotful lydescribeandanalyzethebehaviorsofrealisticOpenMPprograms.Therefore,thispaperwil lmodel andanalyzethebehaviorsofOpenMPtasksystemswithgeneralbranchingstructures.Thispaper aimstoanalyzetheresponsetimeofOpenMPprogramswithcondi tionalbranchstructure.Anaivesol uti oniscalcul atingtheresponsetimebyenumeratingallpossi bl eexecutionflowsinthecon-DAGs,butithasexponentialti mecompl exity.Therefore ?existingworksdeveloppolynomial?timedynami cprogrammingal gori thmstocal culateresponseti meboundsofcon-DAGs.However,thesemethodsassumestructuresrecursivelycomposedbysi ngle-source-singl e-sinkparal lelandconditionalcomponents,sotheycannotanalyzegeneral OpenMPtasksystemsthatdonotcompl ywiththisassumption.Thispaperstudiesgeneral OpenMPtasksystems,andproposesanalgori thmforcalculatingtheresponseti meofcon-DAGtaskgraphwith‘‘multi-source-mul ti-sink”conditionalstructures.Comparedwithexistingmethods,Thealgorithminthispapernotonlycanaccuratelycal culatetheresponsetimeboundsofcon-DAGtasks,butalsohaspolynomialtimecomplexity.Thi sworkwassupportedbytheNationalNaturalSci enceFoundationofChina(No.61972076) ,whichaimstoanalyzethetheory, models,algorithms,andappl icationsofreal-timeschedulingforOpenMPtaskgraph.Ourresearchgrouphasbeenworki ngonreal-timeembeddedsystems*multi-corereal-timescheduli ng,networkoptimization,andparallelcomputing.Relatedworkshavebeenpublishedinreputable journal sandconferences,suchasChineseJournalofComputers,IEEETransonComputers,IEEETransonCAD,ACMTransonECS, RTSS, DAC,RTAS,EMSOFT,DATE,etc.

[返回]
上一篇:基于本地差分隐私的键_值数据精确收集方法_张啸剑
下一篇:一种基于领域适配的跨项目软件缺陷预测方法