| 带有分支结构OpenMp任务图的响应时间分析 |
| 来源：一起赢论文网 日期：2020-12-11 浏览数：1468 【 字体： 大 中 小 大 中 小 大 中 小 】 |
|
第４３ 卷 第１１ 期２０２０ 年１ １ 月计 算机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．４３Ｎｏ． １１Ｎｏｖ．２０２０带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析孙景昊Ｄ‘２）张利威ｕ池瑶瑶ｎ曹 蕾＇ １邓庆绪ｎ＂（ 东北大学计算机科学与工程学院 沈阳 １１０８１９）２ １（ 大连理工大学计算机科学与技术学院 辽宁大连 １１６０２４）摘 要 随着多核技术在实时系统中广泛应用， 实时程序的并行化成为当前的研究热点． 在实时领域， 有向无环图（ ＤＡＧ）是刻画并行实时程序的理论模型． 然而， 传统的ＤＡＧ任务图并不能刻画并行程序的实际特征（例如ｉｆ－ｅｌｓｅ控制流结构）． 于是， 能够同时反映程序的并行负载特征和ｉｆ－ｅｌｓｅ 控制流结构的分支并行任务图（ｃｏｎｄｉ ｔｉｏｎａｌＤＡＧ：ｃｏｎ－ＤＡＧ）应运而生． 目前， 实时领域通常假设ｃｏｎ－ＤＡＧ满足某种特殊结构， 即图中的并行子结构和分支子结构必须是单人口和单出口（简称为“单人单出”）．在这种约束下，ｃｏｎ－ＤＡＧ的响应时间分析问题具有多项式时间算法． 然而， 现实的ＯｐｅｎＭＰ程序具有更加灵活的结构 单人单出”假设一旦失效，ｃｏｎ－ＤＡＧ响应时间分析是否依然存在多项式时间算法为开放性问题． 本文针对一般情况下ＯｐｅｎＭＰ程序的分支结构开展研究． 对于非“单人单出”ｃｏｎ－ＤＡＧ图上响应时间分析问题， 基于动态规划理论， 提出了多项式时间的求解方法． 实验表明， 本文方法求得的ｃｏｎ－ＤＡＧ响应时间在之前方法的基础上能够提升３％， 为实时并行程序的可预测性提供更精确的理论支撑．关键词 ＯｐｅｎＭＰ； 有向无环图；ｉｆ－ｅｌｓｅ分支结构； 响应时间； 多项式时间中图法分类号ＴＰ３１１ＤＯＩ号１０．１ １８９７／ＳＰ． Ｊ．１０１６．２０２０． ０２１６６ＥｘａｃｔｌｙＡｎａｌｙｚｉｎｇＲｅｓｐｏｎｓｅＴｉｍｅｏｆＯｐｅｎＭＰＴａｓｋｓｗｉｔｈＣｏｎｄｉｔｉｏｎａｌＢｒａｎｃｈｅｓＳＵＮＪｉ ｎｇ－Ｈａｏ１ ， ＇ ２）ＺＨＡＮＧＬｉ－Ｗｅｉ１ １ＣＨＩＹａｏ－ＹａｏｎＣＡＯＬｅｉｎＤＥＮＧＱｉ ｎｇ－Ｘｕｕｎ（ ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ？ＮｏｒｔｈｅａｓｔｅｒｎＵｎｉ ｖｅｒｓｉ ｔｙ， Ｓｈｅｎｙａｎｇ１１０８１９）２）（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ ａｎｄＴｅｃｈｎｏｌｏｇｙ＾ＤａｌｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ＊Ｄａｌ ｉａｎ－，Ｌｉａｏｎｉ ｎｇ１１６０２４）ＡｂｓｔｒａｃｔＭｕｌ ｔｉ－ｃｏｒｅｓａｒｅｂｅｃｏｍｉ ｎｇｍａｉ ｎｓｔｒｅａｍｈａｒｄｗａｒｅｐｌａｔｆｏｒｍｓｆｏｒｅｍｂｅｄｄｅｄａｎｄｒｅａｌ－ｔｉ ｍｅｓｙｓｔｅｍｓ．Ｔｏｆｕｌ ｌｙｕｔｉｌｉｚｅｔｈｅｐｒｏｃｅｓｓｉ ｎｇｃａｐａｃｉｔｙｏｆｍｕｌｔｉ－ｃｏｒｅｓ，ｓｏｆｔｗａｒｅｓｈｏｕｌｄｂｅｐａｒａｌｌｅｌｉｚｅｄ．Ｒｅｃｅｎｔｌｙｍｕｃｈｗｏｒｋｈａｓｂｅｅｎｄｏｎｅｏｎｒｅａｌ－ｔｉ ｍｅｓｃｈｅｄｕｌ ｉ ｎｇｏｆｐａｒａｌｌｅｌｔａｓｋｓｍｏｄｅｌｅｄａｓｄｉｒｅｃｔｅｄａｃｙｃｌｉｃｇｒａｐｈｓ（ ＤＡＧ） ，ｍｏｔｉｖａｔｅｄｂｙｔｈｅｐａｒａｌ ｌ ｅｌｔａｓｋｓｔｒｕｃｔｕｒｅｓｓｕｐｐｏｒｔｅｄｂｙｐｏｐｕｌａｒｐａｒａｌｌｅｌｐｒｏｇｒａｍｍｉ ｎｇｆｒａｍｅｗｏｒｋｓｓｕｃｈａｓＯｐｅｎＭＰ．ＴｈｅＤＡＧ－ｂａｓｅｄｔａｓｋｍｏｄｅｌ ｓｉ ｎｅｘｉｓｔｉ ｎｇｒｅａｌ－ｔｉ ｍｅｓｃｈｅｄｕｌｉ ｎｇｒｅｓｅａｒｃｈｃａｎｎｏｔｆｕｌ ｌ ｙｃａｐｔｕｒｅｃｒｉｔｉｃａｌｆｅａｔｕｒｅｓｏｆｐａｒａｌｌｅｌｐｒｏｇｒａｍｓ，ｅ．ｇ．，ｉ ｆ－ｅｌ ｓｅｃｏｎｄｉｔｉｏｎａｌｓｔｒｕｃｔｕｒｅ．Ｒｅｃｅｎｔｌｙ，ｔｈｅｃｏｎｄｉｔｉｏｎａｌＤＡＧｍｏｄｅｌ ｓａｒｅｐｒｏｐｏｓｅｄｔｏｆｏｒｍｕｌａｔｅｔｈｅｒｅａｌ？ｔｉ ｍｅｓｙｓｔｅｍｓｃｏｍｐｏｓｅｄｂｙｐａｒａｌ ｌｅｌｗｏｒｋｌｏａｄａｎｄｃｏｎｄｉ ｔｉｏｎａｌｃｏｍｐｏｎｅｎｔｓ．Ｅｘｉ ｓｔｉ ｎｇＤＡＧ－ｂａｓｅｄｔａｓｋｍｏｄｅｌ ｓｉ ｎｒｅａｌ－ｔｉ ｍｅｓｃｈｅｄｕｌｉ ｎｇｒｅｓｅａｒｃｈａｓｓｕｍｅｓｐｅｃｉａｌｓｔｒｕｃｔｕｒｅｓｒｅｃｕｒｓｉ ｖｅｌｙｃｏｍｐｏｓｅｄｂｙｓｉ ｎｇｌ ｅ－ｓｏｕｒｃｅ－ｓｉ ｎｇｌｅ－ｓｉｎｋｐａｒａｌｌｅｌａｎｄｃｏｎｄｉ ｔｉｏｎａｌｃｏｍｐｏｎｅｎｔｓ．Ｗｉｔｈｔｈｉｓｓｐｅｃｉａｌａｓｓｕｍｐｔｉｏｎ，ｐｏｌｙｎｏｍｉａｌ－ｔｉｍｅｒｅｓｐｏｎｓｅｔｉｍｅａｎａｌｙｓｉｓｍｅｔｈｏｄｉｓｄｅｖｅｌｏｐｅｄ．Ｈｏｗｅｖｅｒ，ｒｅａｌｉｓｔｉｃＯｐｅｎＭＰｔａｓｋｓｙｓｔｅｍｓｉ ｎｇｅｎｅｒａｌｈａｖｅｍｏｒｅｆｌｅｘｉｂｌｅｓｔｒｕｃｔｕｒｅｓｔｈａｔｄｏｎｏｔｃｏｍｐｌｙｗｉｔｈｔｈｉｓａｓｓｕｍｐｔｉｏｎ．ＴｈｉｓｐａｐｅｒｓｔｕｄｉｅｓｇｅｎｅｒａｌＯｐｅｎＭＰｔａｓｋｓｙｓｔｅｍｓｗｉ ｔｈｇｅｎｅｒａｌｂｒａｎｃｈｉ ｎｇｓｔｒｕｃｔｕｒｅｓ，ａｎｄｄｅｖｅｌｏｐｓａｐｏｌｙｎｏｍｉａｌ－ｔｉｍｅｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉ ｎｇａｌｇｏｒｉｔｈｍｔｏｅｆｆｉｃｉｅｎｔ ｌｙｃａｌｃｕｌａｔｅｒｅｓｐｏｎｓｅｔｉｍｅｂｏｕｎｄｓｆｏｒ收稿日期：２０１９－０８－３０； 在线发布日期：２０２０－０７－０ １． 本课题得到国家自然科学基金（ ６１ ９７２０７６）、 兴辽英才计划（ ＸＬＹＣ１９０２０１７ ）、 ＮＳＦＣ－辽宁联合基金（ Ｕ１９０８２１２）资助． 孙景昊， 博士， 副教授， 中国计算机学会（ ＣＣＦ） 会员， 主要研究方向为实时系统调度、 并行程序分析． Ｅ－ｍａｉｌ：ｊｈｓｕｎ＠ｄｌ ｍ． ｅｄｕ． ｃｎ．张利威， 硕士研究生， 主要研究方向为ＯｐｅｎＭＰ并行程序分析．池瑶瑶， 硕士研究生， 主要研究方向为实时并行系统调度． 曹 蕾， 学士， 主要研究方向为实时系统、 优化算法． 邓庆绪（ 通信作者）， 博士， 教授， 主要研究领域为实时系统． Ｅ－ｍａｉｌ：ｄｅｎｇｑＸ＠ｍａｉ ｌ．ｎｅｕ．ｅｄｕ． ｃｎ．１１ 期 孙景昊等： 带有分支结构ＯｐｅｍＭＰ任务图的响应时间分析 ２１６ ７ＯｐｅｎＭＰｔａｓｋｓｙｓｔｅｍｓ．Ｆｉｒｓｔ ，ｔｈｉｓｐａｐｅｒｏｕｔｌｉ ｎｅｓＯｐｅｎＭＰｐｒｏｇｒａｍｓｅｍａｎｔｉｃｓ，ａｎｄｍｏｄｅｌｔｈｅｂｅｈａｖｉ ｏｒｓｏｆｇｅｎｅｒａｌＯｐｅｎＭＰｔａｓｋｓｙｓｔｅｍｓｗｉｔｈｇｅｎｅｒａｌｂｒａｎｃｈｉ ｎｇｓｔｒｕｃｔｕｒｅｓ， ｉ ｎｃｌ ｕｄｉ ｎｇｔａｓｋｍｏｄｅｌ ｓ，ｅｘｅｃｕｔｉｏｎｍｏｄｅｌｓａｎｄｓｃｈｅｄｕｌ ｉ ｎｇｍｏｄｅｌ ｓ．Ｓｅｃｏｎｄ，ｔ ｈｉｓｐａｐｅｒｄｅｅｐｌｙａｎａｌｙｚｅｓｔｈｅｒｅｌａｔ ｅｄｍｅｔｈｏｄｉ ｎｔｈｅｅｘｉｓｔｉ ｎｇｗｏｒｋ．Ｂｙｃｏｎｓｔｒｕｃｔｉ ｎｇａｃｏｕｎｔｅｒｅｘａｍｐｌ ｅ，ｗｅｆｉ ｎｄｔｈａｔｔｈｅｅｘｉｓｔｉ ｎｇｍｅｔｈｏｄｃａｎｎｏｔａｃｃｕｒａｔｅｌｙｃａｌ ｃｕｌａｔｅｔｈｅｒｅｓｐｏｎｓｅｔｉ ｍｅｂｏｕｎｄａｒｙｏｆｔｈｅｔａｓｋｇｒａｐｈｓ，ａｎｄｔｈｅｒｅｉ ｓａｃｅｒｔａｉ ｎｐｅｓｓｉ ｍｉｓｍ．Ｔｈｅｓｐｅｃｉｆｉｃｒｅａｓｏｎｉｓｔｈａｔａｌ ｔ ｈｏｕｇｈｔｈｅｅｘｉｓｔｉｎｇｍｅｔｈｏｄｃｏｎｓｉ ｄｅｒｓＯｐｅｎＭＰｔａｓｋｇｒａｐｈｓｗｉｔｈｍｕｌ ｔｉ－ｓｏｕｒｃｅ－ｍｕｌｔｉ－ｓｉ ｎｋｃｏｎｄｉ ｔｉ ｏｎａｌｂｒａｎｃｈｉｎｇｓｔｒｕｃｔｕｒｅｓ，ｉｔｃａｎｎｏｔｃｏｒｒｅｃｔｌｙａｎａｌｙｚｅｓｏｍｅｓｉｔｕａｔｉ ｏｎｓ，ｅ．ｇ．，ｔｈｅｐａｒａｍｅｔｅｒｓａｓｓｏｃｉａｔｅｄｗｉ ｔｈｔｈｅｔｗｏｂｒａｎｃｈｅｓｉ ｎｔｈｅｃｏｎｄｉｔｉ ｏｎａｌｂｒａｎｃｈｉ ｎｇｓｔｒｕｃｔｕｒｅａｒｅｑｕｉｔｅｄｉｆｆｅｒｅｎｔ． Ｔｈｉｒｄ，ｆｏｒｔｈｅａｎａｌｙｓｉｓｐｒｏｂｌｅｍｏｆｒｅｓｐｏｎｓｅｔｉ ｍｅｏｎｍｕｌ ｔｉ－ｓｏｕｒｃｅ－ｍｕｌ ｔｉ－ｓｉ ｎｋｃｏｎ－ＤＡＧｇｒａｐｈｓ，ｂａｓｅｄｏｎｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｔｈｅｏｒｙ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｎａｃｃｕｒａｔｅｓｏｌ ｕｔｉ ｏｎｍｅｔｈｏｄｏｆｐｏｌ ｙｎｏｍｉａｌｔｉ ｍｅ．Ｔｈｅｍａｉ ｎｉｄｅａｏｆｔｈｉ ｓｍｅｔｈｏｄｉ ｓａｓｆｏｌ ｌｏｗｓ．ＴｈｅＤＡＧｇｒａｐｈｉ ｓｔｒａｖｅｒｓｅｄｔｏｐｏｌ ｏｇｉｃａｌ ｌ ｙｉ ｎｒｅｖｅｒｓｅｏｒｄｅｒ，ｔｈｅｎｔｈｅｐａｒａｍｅｔｅｒｓａｓｓｏｃｉａｔｅｄｗｉｔｈｔｈｅｐｒｅｄｅｃｅｓｓｏｒｎｏｄｅｓａｒｅｃａｌ ｃｕｌａｔｅｄｂｙｕｓｉ ｎｇｔｈｅｃａｌｃｕｌａｔｉ ｏｎｒｅｓｕｌ ｔｓｏｆｔｈｅｓｕｃｃｅｓｓｏｒｎｏｄｅｓ，ａｎｄｆｉ ｎａｌ ｌｙｔｈｅｒｅｓｐｏｎｓｅｔｉｍｅｂｏｕｎｄｏｆｔｈｅＤＡＧｇｒａｐｈｉ ｓｃａｌｃｕｌａｔｅｄｂａｓｅｄｏｎｔｈｅｖａｌ ｕｅｓｏｆｔｈｅａｓｓｏｃｉａｔｅｄｖａｒｉａｂｌｅｓｏｆｔｈｅｓｏｕｒｃｅｎｏｄｅ．Ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｅｘｉｓｔｉ ｎｇａｌｇｏｒｉｔｈｍ，ｔｈｅａｌ ｇｏｒｉｔｈｍｉ ｎｔｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓｍｏｒｅｎｏｄｅ－ａｓｓｏｃｉａｔｅｄｖａｒｉａｂｌｅｓａｎｄｃｏｎｓｉ ｄｅｒｓｍｏｒｅｎｏｄｅｔｙｐｅｓ．Ｉｎｔｈｅｅｘｐｅｒｉｍｅｎｔｐａｒｔ，ｗｅｉ ｍｐｌｅｍｅｎｔｔｈｅａｌｇｏｒｉ ｔｈｍｏｆｅｘｉ ｓｔｉ ｎｇｗｏｒｋａｎｄｔｈｅａｌｇｏｒｉ ｔｈｍｉｎｔｈｉ ｓｐａｐｅｒ．Ｔｈｅｒｅｓｐｏｎｓｅｔｉ ｍｅｂｏｕｎｄｓｏｆｔｈｅｔｗｏａｌｇｏｒｉｔｈｍｓａｒｅｅｖａｌ ｕａｔｅｄｂｙｒａｎｄｏｍｌ ｙｇｅｎｅｒａｔｅｄＤＡＧｓ．Ｅｘｐｅｒｉｍｅｎｔａｌｗｏｒｋｓｈｏｗｓｔｈａｔｃｏｍｐａｒｅｄｔｏｔｈｅｔｒａｄｉ ｔｉ ｏｎａｌｍｅｔｈｏｄ，ｏｕｒｍｅｔｈｏｄｃａｎｅｆｆｅｃｔｉ ｖｅｌｙｉｍｐｒｏｖｅｔｈｅａｃｃｕｒａｃｙｏｆｔｈｅｒｅｓｐｏｎｓｅｔｉ ｍｅｂｏｕｎｄ． Ｕｎｄｅｒａｖｅｒａｇｅｃｏｎｄｉｔｉｏｎｓ，ｔｈｅａｃｃｕｒａｃｙｏｆｔｈｅｒｅｓｐｏｎｓｅｔｉ ｍｅｂｏｕｎｄｃａｎｂｅｉ ｎｃｒｅａｓｅｄｂｙ３％．Ｉｔｉｓｖｅｒｙｉ ｍｐｏｒｔａｎｔｆｏｒｒｅａｌ－ｔｉｍｅｓｙｓｔｅｍｔｏｉ ｍｐｒｏｖｅｔｈｅａｃｃｕｒａｃｙｏｆｒｅｓｐｏｎｓｅｔｉ ｍｅｂｏｕｎｄｅｆｆｅｃｔｉ ｖｅｌｙ．Ｉｎｒｅａｌ－ｔｉ ｍｅｓｙｓｔｅｍｓ，ｔｈｅｒｅｓｐｏｎｓｅｔｉ ｍｅｄｉ ｒｅｃｔｌｙａｆｆｅｃｔｓｔｈｅｓｃｈｅｄｕｌ ａｂｉ ｌｉ ｔｙｏｆｓｙｓｔｅｍｓ．Ｆｏｒｒｅａｌ－ｔｉｍｅｓｙｓｔｅｍｓｗｈｏｓｅｓｃｈｅｄｕｌａｂｉ ｌ ｉｔｙｉｓｉ ｎｃｒｉｔｉ ｃａｌｓｔａｔｅ，ｔｈｅａｃｃｕｒａｃｙｏｆｒｅｓｐｏｎｓｅｔ ｉ ｍｅｉ ｓｉ ｎｃｒｅａｓｅｄｂｙ１％，ｗｈｉｃｈｉｓｌｉ ｋｅｌ ｙｔｏｇｒｅａｔｌｙｉ ｎｃｒｅａｓｅｔｈｅｓｃｈｅｄｕｌａｂｉｌｉｔｙｏｆｓｙｓｔｅｍｓ．ＫｅｙｗｏｒｄｓＯｐｅｎＭＰ；ｄｉｒｅｃｔｅｄａｃｙｃｌ ｉｃｇｒａｐｈ；ｉｆ－ｅｌ ｓｅｂｒａｎｃｈｓｔｒｕｃｔｕｒｅ；ｒｅｓｐｏｎｓｅｔｉ ｍｅ；ｐｏｌｙｎｏｍｉａｌｔｉｍｅｉ 引 言近年来， 多核技术越来越广泛地应用于实时系统． 为了充分利用多核的计算资源， 实时软件并行化成为当前的研究热点和未来的发展趋势． ＯｐｅｎＭＰ？是多核系统最流行的并行编程框架之一． 近年来， 在实时嵌人式领域ＯｐｅｎＭＰ得到了广泛关注． 在实时领域中， 有向无环图（ＤｉｒｅｃｔｅｄＡｃｙｃｌｉｃＧｒａｐｈ，ＤＡＧ）是刻画ＯｐｅｎＭＰ程序的天然模型， 基于ＤＡＧ图的实时调度和分析的问题中涌现出大量研究工作［２＿１２：．然而， ＤＡＧ图并不能完全刻画ＯｐｅｎＭＰ的程序特征． ＯｐｅｎＭＰ程序的一个关键特征是： ＯｐｅｎＭＰ任务间不仅具有并行性， 而且在任务内还具有条件分支结构（ 例如ｉｆ－ｅｌ ｓｅ 语句）． 因此， 文献［１ ３－１ ８］研究了带有条件分支结构的ｃｏｎ－ＤＡＧ任务图．本文发现， 现有的ｃｏｎ－ＤＡＧ任务图模型仍然不能刻画实际的ＯｐｅｎＭＰ 程序． 例如， 在现有的ｃｏｎ－ＤＡＧ图中， 并行结构和条件分支结构具有单人口单出口的特征（ 以下简称为“单人单出”） ． 如图１所示， 该ｃｏｎ－ＤＡＧ图包含一个并行结构（ 黄色框） ，并行结构内嵌一个条件分支结构（ 绿色框）． 这些并行结构和条件分支结构都具有一个人口和一个出口， 不允许出现图中红色边（ 从条件分支结构外／内指向条件分支结构内／外） 的情况．然而， 在实际的ＯｐｅｎＭＰ程序中， 并行和条件分支结构可能不满足“单人单出”条件． 图２（ａ） 为一个ＯｐｅｎＭＰ程序， 其中条件分支结构内所触发的负载（ｃｏｄｅ３１） 与该条件分支结构外所触发的负载２１ ６８计 算机 学 报２０２０ 年（ｃｏｄｅｌ ４） 同步． 现有的实时调度研究并不能很好地描述和分析这种行为． 如果用类似于图１ 的方法对图２（ ａ） 中的ＯｐｅｎＭＰ程序进行建模， 将有两条边（ 在图２（ ｂ） 中标记为红色）， 从条件分支结构外／内部节点指向条件分支结构内／外部节点． 也就是说，图２（ ｂ） 的ＤＡＧ图中条件分支结构具有多个入口和出口． 当前研究［１ ＾］并不适用于图２ 中的任务模型．本文将对此类一般情况下ＯｐｅｎＭＰ任务进行建模与分析．１＃ｐｒａｇｍａｏｍｐｔａｓｋ｛２ｃｏｄｅｌ ｌ；３＃ｐｒａｇｍａｏｍｐｔａｓｋ｛ｃｏｄｅ２１； ｝４ｉｆ（ｅｘｐ）５＃ｐｒａｇｍａｏｍｐｔａｓｋｗａｉ ｔ；６ｃｏｄｅｌ２；７＃ｐｒａｇｍａｏｍｐｔａｓｋ｛ｃｏｄｅ３１； ｝８ｅｌｓｅ９ｃｏｄｅｌ ３；１ ０＃ｐｒａｇｍａｏｍｐｔａｓｋｗａｉ ｔ；１１ ｃｏｄｅｌ４；１２｝（ａ）ＯｐｅｎＭＰ程序＾ｏｄｅ２ｊ） （＾〇ｄｅ３ ｌ）ｖ＾八／（ｂ） 相应的ＤＡＧ任务图图２ＯｐｅｎＭＰ程序及相应的ＤＡＧ任务图本文旨在分析带有条件分支结构ＯｐｅｎＭＰ程序的响应时间． 文献［９］研究发现， 不带条件分支结构ＯｐｅｎＭＰ程序的响应时间， 可由经典Ｇｒａｈａｍ界［１ ９］来限定． 由于ｃｏｎ－ＤＡＧ图的执行流是一个非条件ＤＡＧ图， 所以文献［９］ 的结论可以扩展到ｃｏｎ－ＤＡＧ图中． 即首先枚举ｃｏｎ－ＤＡＧ图中所有可能的执行流， 然后求解每个执行流的Ｇｒａｈａｍ界， 并求取最大值． 然而， 这种枚举的方法， 在面对指数规模的执行流时， 其计算复杂度也是指数的． 为了规避枚举方法， 当前研究［１４ １８］基于动态规划给出了ｃｏｎ－ＤＡＧ图的响应时间界限的多项式时间计算方法． 但是， 这些方法均局限于带有“单人单出”约束的ｃｏｎ－ＤＡＧ图， 不适用于带有“多入多出”条件分支结构的一般性ＯｐｅｎＭＰ程序．本文针对一般性ＯｐｅｎＭＰ程序开展研究， 提出具有“多人多出”条件分支结构ｃｏｎ－ＤＡＧ任务图的响应时间算法． 在撰写本文之前， 文献［２０］也研究了“多人多出”条件分支结构的ＯｐｅｎＭＰ程序响应时间分析问题． 但是， 本文发现， 文献［２０］提出的算法并不能精确求解ｃｏｎ－ＤＡＧ的响应时间界， 具有相当的悲观性． 相比较而言， 本文提出的方法不但能够精确求解ｃｏｎ－ＤＡＧ的响应时间界， 而且还具有多项式时间的计算复杂度． 实验表明， 本文的算法在求解精度上， 优于文献［２０］中的方法． 与此同时， 本文实验表明， 文献［２０］方法具有较少的计算时间， 这说明在不要求较高求解精度的情况下， 文献［２０］方法具有易实现、 鲁棒的优点．本文第２ 节介绍ｃｏｎ－ＤＡＧ方面的相关研究工作； 第３ 节建立ＯｐｅｎＭＰ系统的形式化模型； 第４节介绍响应时间界； 第５ 节指出文献［２０］ 中的方法并不能精确求解响应时间界； 第６ 节提出伪多项式时间的精确算法； 第７ 节是实验结果； 最后是总结与展望．２ 相关工作文献［１０］首次将ＯｐｅｎＭＰ 程序建模为ＤＡＧ图． 文献［９］针对ＯｐｅｎＭＰ框架中已有的调度算法（例如， 宽度优先调度（ Ｂｒｅａｔｈ－Ｆｉ ｒｓｔ－Ｓｃｈｅｄｕｌｉｎｇ， ＢＦＳ）和负载优先调度（ Ｗｏｒｋ－Ｆｉ ｒｓｔ－Ｓｃｈｅｄｕｌｉ ｎｇ， ＷＦＳ） ） ， 基于文献［１０］ 中ＤＡＧ任务图模型， 首次为ＯｐｅｎＭＰ程序提出了响应时间界限分析． 在文献［９］ 中，ＯｐｅｎＭＰ任务分为两种类型： 绑定型任务和非绑定型任务．其中， 绑定型任务一旦在一个线程上开始执行， 就不能迁移到另一个线程． 另外， 非绑定型任务则不受此限制， 能够在不同的线程上迁移执行． 文献［９］指出， 绑定型任务的时序分析具有内在的复杂性， 这将导致响应时间分析的悲观性． 之后， 文献［１１］的研究发现， 绑定型任务不但会导致响应时间的悲观性， 还可能引起整个ＯｐｅｎＭＰ系统极差的时间行为（ 例如， 原本并行的程序， 由于绑定型任务的ｒｕｎｔｉ ｍｅ 约束， 被强制在单核上串行执行）． 上述工作均没有考虑ＯｐｅｎＭＰ中的条件分支结构．文献［１４－１７］研究了ｃｏｎ－ＤＡＧ模型， 主要提出了两类计算响应时间界限方法：一种方法将ｃｏｎ－ＤＡＧ转换为不包含条件节点的（ 非条件） ＤＡＧ图模型，然后直接应用非条件ＤＡＧ图的分析和计算方法求解ｃｏｎ－ＤＡＧ的响应时间界限＃１ ５３． 另一种方法则是基于动态规划思想， 在ｃｏｎ－ＤＡＧ图上直接计算响应时间［１Ｓ １ ７］． 这两种方法均具有多项式时间的计算复杂性， 也都局限于“单人单出”条件分支结构的ｃｏｎ－ＤＡＧ图模型． 最近， 文献［２０］研究了带有“多人多出”条件分支结构ｃｏｎ－ＤＡＧ的响应时间计算方法． 然而， 本文发现， 文献［２０］ 中的方法并不能精确求解ｃｏｎ－ＤＡＧ图响应时间界限， 存在一定的悲观孙景昊等： 带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析 ２１６９ １ １ 期性． 本文工作扩展自文献［２０］， 并在实验部分将本文提出的方法与文献［２０］的方法进行了定量分析和比对．此外， 文献［２１－２４］研究了ＯｐｅｎＭＰ程序的平均意义上的性能分析． 这与本文针对最坏情况下ＯｐｅｎＭＰ响应时间分析存在较大的差异： 文献［２１－２４］基于度量的方法， 不需要显式地构建条件分支结构． 与此相反， 本文最坏情况的响应时间分析显式地构建了ＯｐｅｎＭＰ程序条件分支结构和时序特性， 并根据这些信息形式化地推出响应时间的上界．３ 系统模型本节通过对ＯｐｅｎＭＰ程序语义进行简单介绍，建立ＯｐｅｎＭＰ系统的形式化模型， 具体包括任务模型、执行模型和调度模型．３． １ＯｐｅｎＭＰ程序与线程本文主要研究具有ｔａｓｋ语义的ＯｐｅｎＭＰ程序．ｔａｓｋ语义在ＯｐｅｎＭＰ３．０［１７：及以上版本中出现．图３ 给出了一个ＯｐｅｎＭＰ 程序示例． 该程序从ｐａｒａｌ ｌ ｅｌ 指令（ 第１ 行） 开始？ｐａｒａｌｌ ｅｌ 指令构造了一个并行域， 其包括ｐａｒａｌ ｌｅｌ 指令后面花括号中的所有代码（ 第２ 行至第２１ 行） ．１＃ｐｒ？ｉｇｍａｏｍｐｐａｒａｌｌ ｅｌ ｎｕｍ＿ｔｈｒｅａｄｓ（ ｍ）２｛ ＃ｊ）ｒａｇｍａｏｍｐｓｉ ｎｇｌｅ３｛＃ｐｒａｇｎｉａｏｍｐｔａｓｋＩｈ＇４｛ ｃｃｘＪｅｌ ｌ； ／／ｖ＼５＃ｐｒａｇｍａｏｍｐｔａｓｋ｛ｃｏｄｅ２１ ；／／ｖ２｝／／ｒ２６ｉｆＣ ｅｘｐｌ ）／／ｅｎｔｒｙ：Ｖｊ； ｅｘｉｔ ：７ｃｏｄｅｌ２； ／／ｖ＼８＃ｐｒａｇｍａｏｍｐｔａｓｋ／／ｒ３９｛ ｃｏｄｅ３ １ ；／／ｖｌ１０＃ｉ）ｒａｇｍａｏｍｐｔａｓｋ｛ｃｏｄｅ４１；／／ｖ＼）／／ｒ４１１ｃｃｘｄ ｅ３２； ／／ｖ＼１２｝／／ｅｎｄｏｆｒ３１３ｅｌｓｅ１４＃ｐｒａｇｍａｏｍｐｔａｓｋｗａｉｔ；１５ｃｏｄｅｌ３；／／ｖ＼１６ｐｒａｇｍａｏｍｐｔａｓｋｗａｉ ｔ；１７ｃｏｄｅｌ ６； ／／ｖ＼１８ｃｏｄｅｌ ７； ／／ｉＰｘ１９｝２０｝２１｝图３ＯｐｅｎＭＰ程序示例ｐａｒａｌ ｌｅｌ 指令创建；《 个ＯｐｅｎＭＰ线程， 其中ｗ由ｎｕｍｊｈｒｅａｄｓ 子句指定（第１ 行）？ＯｐｅｎＭＰ线程是指能够执行并行域内代码的实体（例如， 操作系统中的线程）． 与之前工作 类似． 本文假设每个线程独享一个内核的计算资源． 因此， 本文中“线程”的概念相当于一个物理内核．３．２ＯｐｅｎＭＰ任务模型并行域中的代码可以划分为一组并行任务ｒ＝＜ ｒｉ，…，ｒ？ ｝． 其中， 任务 对应第（ 个ｔａｓｋ 指令后面括号中所包含的代码域． 如图３ 所示， ｎ对应第４行的代码． 但是， 第９ 行的代码不包含在ｒｉ 的代码域中． 显然， 第９ 行的代码属于〇的代码域． 在ＯｐｅｎＭＰ任务系统ｒ中， 每个任务都有内部控制流结构， 任务之间存在依赖关系．本文将ＯｐｅｎＭＰ任务系统ｒ建模为ＤＡＧ图Ｇ＝（Ｖ， ￡） ． 其中， Ｖ表示节点集， 每个节点表示ｔａｓｋ指令中的顺序代码段． Ｅ表示边集． 每条边表示两个节点之间的前驱后继关系．图Ｇ可以分为ｎ个不相交的子图， 即Ｇ＝Ｇ， Ｕ…ＵＧ，，． 其中， 子图Ｇ，． ＝（Ｖ，， ￡：，＿） 是任务ｒ，．的控制流图（ Ｃｏｎｔｒｏｌ－Ｆｌ ｏｗＧｒａｐｈ， ＣＦＧ） ． 图４给出了图３ 中对应ＤＡＧ图的任务模型．在每个ＣＦＧＧ，＝（Ｖ，， ￡，） 中． Ｖ， 表示节点集， 节点＜表示ｒ， 的第ｘ个节点， 该节点的最坏情况执行时间（ ＷＣＥＴ） 定义为ｃ（ ＜） ．￡， 表示Ｆ－边集， 每条Ｆ－边（ 圹， ￡，（在图４ 中用点虚线箭头表示） 定义了节点＜和＜的时序关系， 即在节点＜完成执行之后， 节点Ｗ才能开始执行． 特殊地， 没有Ｆ－入边的节点称为Ｇ， 的源点， 没有Ｆ－出边的节点称为Ｇ， 的汇点， 分别定义为ｘＴ和 ． 本文假设每个Ｇ， 都有一个源点和一个汇点． 然而， 本文的方法也可以处理具有多个源／汇点的控制流图的情况： 只需在多个源点之前添加一个执行时间为零的虚拟源点， 在多个汇点之后添加一个执行时间为零的虚拟汇点．接下来， 分别介绍ＣＦＧ图的内部结构和ＣＦＧ间的依赖关系．３． ２． １ＣＦＧ图的内部结构每个任务ｒ， 是一个具有单人口和单出口的程序２１７０２０２０年 计 算机 学 报块（ｂｌｏｃｋ）． 程序块中包含条件分支结构， 如图３中第６？１５ 行所示．一般情况下， 每个条件分支结构包含一个进人点（ｉｆ指令） 和一个退出点（ ｅｎｄｉｆ 指令） ，以及ｉｆ和ｅｌｓｅ两个分支． 条件分支结构中只有一个分支会得到执行， 当该分支完成执行后， 条件分支结构退出执行． 本文允许嵌套条件分支结构， 即一个条件分支结构可以包含在另一个条件分支结构中．根据ＯｐｅｎＭＰ任务内结构， 可以把ＣＦＧ中的节点Ｖ， 分为两类： 条件节点和非条件节点．（１） 条件节点成对出现， 在图中用菱形和三角形表示， 它们分别表示条件分支结构的人口节点和出口节点． 如图４所示， ｚ；丨 是条件节点． 条件分支结构包含两个分支， 每个分支都是Ｇ， 的一个子图．（２） 非条件节点是除条件节点外的所有其它节点．一个非条件节点最多有一条Ｆ－出边， 最多有一条Ｆ－人边． 非条件节点又分为以下三种类型：①Ｔ－节点（Ｖ〖） 表示ｔａｓｋ指令前的代码段． 如图４所示， 以是Ｔ－节点， 对应于图３ 的第４行处的代码段ｃｏｄｅｌｌ．②Ｗ－节点（Ｖ，ｗ ） 表示ｔａｓｋｗａｉ ｔ 指令后的代码段． 如图４所示， ｔ；丨 是Ｗ－节点， 对应于图３ 的第１５行处的代码段ｃｏｄｅｌ３．③Ｎ－节点（Ｖｆ ）． 既非Ｔ类型又非Ｗ类型的非条件节点．３． ２． ２ＣＦＧ间的依赖关系任务之间有两种依赖关系： 任务创建和任务同步， 详细介绍如下：（１） 任务创建． ｔａｓｋ指令用于创建ＯｐｅｎＭＰ任务． 如图３ 所示， 任务ｒｉ 是由第３ 行的ｔａｓｋ指令创建的． ＯｐｅｎＭＰ支持任务嵌套， 例如，一个任务的代码域中还包含其它任务的ｔａｓｋ指令．一般地， 如果ｒ， 的代码域包含ｒ， 的ｔａｓｋ指令， 则称ｒ，？是 的父任务…是ｔ？， 的子任务． 如果ｒ， 是ｒ， 的父任务， 或者ｒ， 是５的父任务的父任务（ 可嵌套定义） ， 则称ｒ， 是ｑ的祖先任务， ｒ， 是ｒ， 的子孙任务． 令 为ｒ， 的任务图以及ｒ， 子孙任务图的并． 如图３ 所示，＾２ 是＾的孩子，〇是ｒｉ 的后代， 〇是ｒ４ 的祖先．一般地， 我们假设第一个任务ｎ没有父任务． 任何其它任务都只有一个父任务．相应地， ＣＦＧ之间也存在任务创建关系， 并由Ｔ－边来确定．Ｔ－边， 用半划线箭头表示． 父任务通过Ｔ－边指向其子任务． 准确地说， 如果（ｒ， 的）Ｔ－节点圹创建了ｒ， 的子任务ｑ， 则从＜到ｒ， 的源点有一条Ｔ－边． 在这种情况下， 只有＜完成执行后，ｒ， 才能够释放和执行． 在图４中， （ ４， ｘ４） 是一条Ｔ－边， 表示节点Ｚ；丨 创建任务ｒ２． 因为在ＯｐｅｎＭＰ中，一个ｔａｓｋ指令创建一个任务， 所以一个Ｔ－节点关联一条Ｔ－出边．规则１． 只有Ｔ－边能从任务（的Ｔ－节点）指向其子任务（ 的源点）．（２） 任务同步． ｔａｓｋｗａｉ ｔ 指令定义任务同步点，即任务可以在ｔａｓｋｗａｉｔ 指令处挂起并等待其它任务完成． 准确地说， 在ｔ 时刻， 任务〇在它自身的ｔａｓｋｗａｉｔ 指令处挂起， 直到所有在Ｚ 时刻之前创建的〇的子任务都完成， 任务＾才能继续执行． 如图３所示， 任务ｒｉ 在其ｔａｓｋｗａｉ ｔ 子句处挂起， 并等待其子任务 的完成．相应地， ＣＦＧ之间也存在任务同步关系， 并由Ｗ－边来确定．Ｗ－边， 用实线箭头表示． 子任务通过Ｗ－边指向其父任务． 准确地说， 对于任意Ｔ－节点＜以及Ｗ－节点＜， 其中，＜是ｗｆ的前驱…表示由＜创建的ｒ， 的子任务， 在这种情况下， 有一条Ｗ－边从＾的汇点指规则２． 只有Ｗ－边能从任务（ 的汇点） 指向其父任务（ 的Ｗ－节点）．Ｗ－边Ｏｆ， 〇定义ＯｐｅｎＭＰ中的父任务ｒ， 与其子任务ｒ，同步， 即父任务ｒ， 在Ｗ－节点Ｗ处挂起，等待其子任务Ｄ完成后， 可恢复执行． 如图４所示，由于ｒ２是由Ｗ的前驱节点Ｍ创建的且图中有一条从 丨 到４不经过任何中间Ｗ－节点的路径， 所以（ ｉ４，Ｗ） 是一条Ｗ－边， 该边从〇的汇点指向ｎ中的Ｗ－节点Ｗ． 从ｒ４ 到４没有Ｗ－边， 因为ｒ４ 不是由Ｍ的前驱节点创建的． 从ｒ２ 到ｎ有两条Ｗ－边， 即（ｔ４，以） 和（４，４）， 因为从Ｗ（ ｒｉ 的Ｔ－节点） 到Ｗ－节点４和４存在路径（ 不经过任何中间Ｗ－节点） ， 例如（ｗ！， ４） 和（Ｍ３． ３ＯｐｅｎＭＰ执行流模型Ｇ从第一个任务ｒ， 开始执行， 进而执行ｎ的子孙任务． Ｇ中的每个任务ｒ， 从源点 开始执行， 到汇点 执行结束． 在任务ｒ， 执行期间， 有两种可能的情况．（１） 当遇到条件节点圹时， 有且只有＜的一个后继节点得到执行．（２） 当遇到Ｎ－节点或Ｔ－节点圹时， 通过Ｆ－边或Ｔ－边连接的埒的所有后继节点都得到执行．根据以上执行语义， 由于Ｇ中存在条件分支结孙景昊等： 带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析 ２１７１１１ 期构， 通常情况下， 在Ｇ中只有部分任务和部分节点得到执行． 因此， Ｇ上的一次执行对应Ｇ的一个子图Ｇ、其包含执行中所遍历的所有节点． 称＾为Ｇ的一条执行流ｅ． 如图４ 所示， 执行流ｅ 中的节点和边用红色标记． 因为ｅ 没有遍历乂， 所以Ｗ－边（ｔ４， ｗ丨） 不包含在ｅ中．３． ４ＯｐｅｎＭＰ调度模型ＯｐｅｎＭＰ系统合理的任务调度满足以下两个约束：（１） 任务调度点（ ＴＳＰ） 包括任务创建点（ｔａｓｋ指令）、同步点（ ｔａｓｋｗａｉｔ 指令） 以及任务完成退出点．任务的执行只能在ＴＳＰ处中断和恢复．（２） 绑定型任务． ＯｐｅｎＭＰ任务分为两种类型：绑定型任务和非绑定型任务． 其中， 绑定型任务一旦在一个线程上开始执行， 就不能迁移到另一个线程．非绑定型任务则不受此限制， 能够在不同的线程上迁移执行．在ＯｐｅｎＭＰ任务模型中， ＯｐｅｎＭＰ调度是指将执行流ｅ 中的节点分配给线程， 直到ｅ 中的所有节点完成执行． 根据ＯｐｅｎＭＰ系统合理调度任务时满足的约束， 执行流ｅ 的合理调度必须满足以下约束条件：（ １） 对于执行流ｅ中任意节点＜， 只有当圹在ｅ中的所有前驱节点（ ＜是＜的前驱节点当且仅当（＜， ＜） £ ￡） 都完成执行， ＜才能执行． 特殊地， 对于执行流ｅ 中Ｗ－节点有两个前驱节点： ＜和法， 执行流ｅ 的调度满足ｗｏｒｋ－ｃｏｎｓｅｒｖｉ ｎｇ约束． 根据文献［１９］可知， 满足ｗｏｒｋ－ｃｏｎｓｅｒｖｉ ｎｇ 约束的调度具有良好的响应时间界， 如第４节所示．迁移开销． 由于本文考虑了非绑定型任务， 因此任务可能会在线程之间迁移． 任务迁移会产生系统开销． 注意到， 在ＯｐｅｎＭＰ调度算法（例如， ＷＦＳ和ＢＦＳ） 的调度下， 任务迁移仅发生在某些特定类型的节点上， 比如， Ｔ－节点和Ｗ－节点． 因此， 迁移开销可以限定如下． 我们用〇表示单个节点的迁移开销， 用ＮＣ表示ＤＡＧ图中Ｔ－节点的数目， 用ＮＷ表示ＤＡＧ图中Ｗ－节点的数目． 在ＷＦＳ的调度下，ＤＡＧ图的总迁移开销小于ＮＣＸＯ． 在ＢＦＳ的调度下， ＤＡＧ图的总迁移开销小于ＮＷＸＯ．４ 响应时间界在ｍ个线程上， 应用ＷＦＳ或ＢＦＳ算法调度， 任务图Ｇ的最坏情况响应时间（ ＷｏｒｓｔＣａｓｅＲｅｓｐｏｎｓｅＴｉｍｅ， ＷＣＲＴ）ｉ？（Ｇ） 定义如下：ｉ？（Ｇ）＝ｍａｘ｛ｉ？（ｅ）｜ｅ是Ｇ上的一条执行流｝（１）其中， ｉ？（ｅ） 是执行流ｅ 的ＷＣＲＴ． 由于一条执行流是一个非条件ＤＡＧ图， 根据文献［９］，Ｊ？（ ｅ） 可由以下引理限定．引理ｌｗ． 在ｍ个线程上， 应用ＷＦＳ或ＢＦＳ算法调度， 执行流ｅ 响应时间ｉ？（ｅ） 的界限如下：ｉ？（ｅ）＜／ｅ？（ｅ）ｖｏＫｅ）＿ｌｅｎ（ｅ）（２）Ｗ， 分别由Ｆ－边和Ｗ－边连接， 其中，ｘ；丨是ｒ， 的子任务ｒ， 的汇点． 根据执行语义， 在迖执行之前， 节点＜和任务ｒ， 必须完成执行．（２） 任务ｒ， 的执行在两个连续节点＜和＜之间发生中断， 仅当下列条件中至少有一个满足：①珥是Ｗ－节点；②＜是Ｔ－节点；中的任务允许在线程之间迁移．ＯｐｅｎＭＰ系统支持两种调度算法： 负载优先调度（ ＷＦＳ）［２５］和宽度优先调度（ ＢＦＳ）［２Ｓ］．ＷＦＳ优先执行新创建的任务， 而ＢＦＳ优先执行已经在线程上执行的任务． 在ＷＦＳ和ＢＦＳ的调度下， 非绑定型任务系统满足ｗｏｒｋ－ｃｏｎｓｅｒｖｉ ｎｇ 约束， 其响应时间可由Ｇｒａｈａｍ界保证． 本文考虑非绑定型ＯｐｅｎＭＰ任务， 并采用ＷＦＳ或ＢＦＳ调度算法．本文假设执行流ｅ 由ＷＦＳ或ＢＦＳ算法调度（详见３．３ 节） ． 根据文献［９］， 基于ＷＦＳ和ＢＦＳ算其中，Ｚｅ？（ｅ） 是ｅ 的最长路径长度， ｔｗＫｅ） 表示ｅ 中所有节点的最坏情况执行时间之和（ 即最大负载）．由于式（２） 是Ｇｒａｈａｍ在文献［１９］中首次提出的， 所以式（２） 又称为Ｇｒａｈａｍ界． 下面的定理表明，Ｇｒａｈａｍ界可以推广到带有条件分支结构的ＯｐｅｎＭＰ任务图．定理１． 在ｍ个线程上， 应用ＷＦＳ或ＢＦＳ算法调度， ＯｐｅｎＭＰ任务图Ｇ响应时间１？（Ｇ） 的界限如下：ｉ？（Ｇ） ＜ｍａｘ（ｚｅｗ（ｅ） ＋＾＾＾）（３）其中， ｅ 代表Ｇ中的执行流．证明． 根据引理１ 和式（１） ， 易知定理１成立．证毕．５ 已有工作存在的问题目前， 与本文最相近的工作是文献［２０］． 文献２１７２ 计 算机 学 报 ２０２０年［２０］ 同样解决带有（ 非“单人单出”） 条件分支结构ＯｐｅｎＭＰ任务图的响应时间分析问题， 给出了多项式时间算法． 然而． 文献［２０］的方法并不能精确求解式（３） 中的响应时间界， 存在一定的悲观性． 接下来，首先简单介绍文献［２０］中计算方法的相关概念和关键步骤． 然后， 通过构造反例， 揭示文献［２０］ 中方法的悲观性． 最后， 比较本文算法和文献［２０］中算法的异同点．５． １ 文献［２０］中算法简介文献［２０］中的算法应用动态规划技术， 按照图Ｇ的拓扑逆序对节点进行遍历． 在遍历过程中， 对于图中每个节点＜， 直接利用＜后继节点的计算结果， 推导出＜关联变量的值． 最后， 响应时间界即可由ｚ／ｒ的关联变量计算得出． 接下来， 首先介绍节点＜关联变量的相关概念． 然后， 给出＜关联变量的递推公式．定义１（Ｓ－图） ． 节点＜引导的３－图０！ ； （ １；＿／）包含节点＜及＜的后继节点， ｓｐＧｓ０；■）＝｛ ｗｆ｝ＵＳＵＣＣ（〇． 其中， ＳＵＣＣ（〇为＜的所有后继节点．例如， 在图４中， Ｇｓ（＾４）＝ （ｙ， ｗ丨， Ｗ ）？定义２（Ｓ－执行流） ． 对于Ｇ中任意执行流ｅ ，以及ｅ 中的节点 引导的Ｓ－执行流ｅｓ（ ＜） 为子图ｅｎＧｓ （ｉ；ｆ） ．定义３（Ｄ－图） ． 节点＜引导的Ｄ－图Ｇｄ（ ＜）包含＜及＜在ｒ，？（ 和 的子孙任务） 中的后继节点，即ＧＤ？）＝｛ ＜｝ Ｕ＾Ｕ＾（ ＜）． 其中，＝ＳＵＣＣ（＜） 门Ａ，？ 〇， 为ｒ， 的任务图以及ｒ， 子孙任务图的并．例如， 在图４ 中， Ｇｄ（ ４）＝（ ４） ．定义４（Ｄ－执行流）． 对于Ｇ中任意的执行流￡ ， 以及￡ 中的节点 引导的Ｄ－执行流 为子图ｅＡＧＤＷ）．节点＜关联的变量定义如下．定义５（Ｓ－图Ｇｓ （ ｗｆ） 的Ｌｅｎｇｔｈ） ．Ｇｓ（ ｘｒ； ） 中最长路径的长度， 即ｌｅｎ＾Ｘｖｘｉ）＝ｍ．ａ． ｙ．ｌｅｎｓｅ｛ ｖ１：＇）（ ４）ｅ ６Ｇ其中， 是Ｓ－执行流ｅｓ（＜） 中最长路径长度．定义６（Ｄ－图ＧＤ（ｖｐ的Ｖｏｌ ｕｍｅ）．Ｇｄ（ ｔ＾） 中Ｄ－执行流的最大负载， 即ｖｏｌ＾（ｖｆ ）＝ｍａｘｖｏｌ°（ｖｊ）（５）ｅ６Ｇ其中，ｔＷｆ（ ｗｆ） 是Ｄ－执行流ｅＤ（ ｉｆ） 中所有节点的响应时间之和， 即ｖ＜（ ｖｆ）＝Ｊ］ｃ（ｖ－；）（ ６）定义７（３－图６５（＜） 的界）． Ｇｓ（〇中Ｓ－执行流的最大界＊即ｇｒａ＾Ｃｖｆ）＝ ｍａｘｇｒａｆ（ ｖｆ）ｅ ６Ｇ其中，ｇｒａｆ（ ｖｆ ） 是Ｓ－执行流ｅｓ（ ｗｆ） 的界，即ｇｒａｆ（ｖｆ）＝ｌｅｎｆ（ ｖ－）＋ｖｏＩｆ（， ｖ＇ｊ）—ｌｅｎｔ（ａ（７）（８）节点圹关联变量的计算分以下两种情况：（１） 若＜是条件分支结构的人口节点， 设＃和冲是ｔｒ； 的直接后继， 那么，ｇｒａ Ｖ）＝ｃ （ ）＋ｍａ ｘ ｛ ｇｒａ Ｖｗｆ１） ，ｇｒａｆ；（ ｗｆＯＫ９ ）（ ２） 若＜是Ｔ－节点， 设＾是＜所创建的ｒ， 的子任务，＜‘是ｒ，的源点， Ｖ是（ 通过Ｆ－边连接的） ＜的后继节点， 则ｇｒａ＊（ ｔ；ｆ）＝ｃ（Ｔ；；ｒ） ＋ｍａｘ｛ ｒｉ， Ｔ２ ｝（１ ０）其中，ｒ＿ｓｒｒｉ—ｇｒａＧ（Ｖｊ ） Ｈ－’ｒ２＝ｇｒ〇ｆ）ｖｏｌ＾Ｃｖ＇＾）ｍ５． ２ 文献［２０］中算法的悲观性本节通过构造反例（ 如图５ 所示）， 说明文献［２０］中的算法不能精确求解式（３） 中的响应时间界．在图５ 中， 最外层的任务ｒ， 包含一个Ｔ－节点＜和一个以＜为人口的条件分支结构． 其中， Ｔ－节点＜创建了ｒ， 的子任务ｒ，． 另外， 条件分支结构包含两个分支． 其中， 第一个分支包含一个执行时间为Ｌ的Ｗ－节点， 第二个分支包含ｗＬ个Ｔ－节点， 每个节点创建一个执行时间为１ 的任务， 分别定义为ｎ， ｒ２，…，ＤＡＧ图中其它节点执行时间均为０．图５ 文献［２０］的反例根据式（１ ０） ， 为计算＜的关联变量 （ 圹） ，需要预先计算出＜的关联变量 （＜）和 （＾）以及认＇＇的关联变量＃４（ ＜） 和 其中，是＜所创建任务ｒ７的源点， Ｗ是＜的后继节点． 如图５ 所示， 根据定义６， 可以计算两个参数１１ 期 孙景昊等： 带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析 ２１７３训６（＜）＝０和 ？ 根据定义７， 可以计算两个参数（＜）＝Ｌ（１—１／ｍ） 和Ｗ）＝Ｌ＋（ ｌ—ｌ／ｍ） ． 进一步地， 可计算得出式（１０） 中的中间变量Ａ＝■Ｌ＋Ｌ（ｌ＿ｌ／ｗ＾） ， Ａ＝Ｌ＋（ｌ－ｌ／ｍ） ？因此， Ｗ＜＾（ ＾＾ｆ）＝Ｌ＋Ｌ（ｌ—ｌ／ＯＴ）？另一方面， 图５ 中ＤＡＧ任务图实际包含两条执行流ｅｉ 和ｅ２． 其中， 执行流ｅｉ 包含 ，邙丨 （ 如图５ 中红色和蓝色轨迹的组合） ． 执行流ｅ２包含｛ ｗｆ， ｗｆ ， ｆ， ｗ，！， ｗｆ，…， ， ｎ， ｒ２ ，…，｝（如图５中红色和绿色轨迹的组合） ｅｉ 关联的变量（〇＝Ｌ，ｅ２ 关联的变量炉＜２（＜）＝Ｌ＋（１—１／ｍ） ． 因此， 以上两者取大， 可得ｇｒ４（ ＜）＝Ｌ＋（ｌ—１／ｍ） ？ 文献［２０］中算法的误差为（Ｌ＿ｌ） （ｌ＿＼／ｒｎ） ．５． ３ 本文算法和文献［２０］中算法的异同由上述反例可以看出， 文献［２０］中的算法存在一定的悲观性． 本文在第６ 节将提出能够精确求解式（３） 中响应时间界的算法． 本文算法与文献［２０］中算法的异同如下：相同点． 两个算法都采用了动态规划技术， 为图中的节点关联一定数量的变量， 按照ＤＡＧ图的拓扑逆序对节点进行遍历， 计算各节点关联的变量．在计算过程中， 图中每个节点＜的关联变量， 可直接利用＜后继节点的计算结果得出． 最后， 响应时间界即为源点关联的相关变量．不同点． 本文的算法能够精确求解式（３） 中的响应时间界，然而， 文献［２０］中的算法仅能得到近似解． 具体的原因是： 文献［２０］虽然考虑了带有“多入多出”条件分支结构的ＤＡＧ图， 但是不能正确分析条件分支结构中两个分支所关联的参数差异较大的情况． 例如，一个分支关联较小的 和较长的＆？，另一个分支关联较大的 和较短的＾？（ 详见图５所示） ． 在这种情况下， 文献［２０］中的算法把ＤＡＧ任务图中实际没有包含的路径（如图５中＜） 纳入了响应时间计算， 从而导致了响应时间界的悲观估计． 为了解决这个问题， 本文算法引人更多的节点关联变量（详见第６．１ 节表１）， 并对节点关联变量的计算情况进行更加细致地划分（ 详见第６．２ 节）．６ 多项式时间精确算法由第５ 节可知， 已有工作中的算法存在悲观性，不能精确求解式（３） 中的响应时间界． 本节将给出能够精确求解式（３） 中响应时间界的多项式时间算法．与文献［２０］中方法类似， 本文依然采用动态规划技术． 如算法１ 所示， 对图Ｇ进行拓扑逆序遍历， 利用后继节点的计算结果来计算前驱节点关联的参数．最后， 由源点 的关联变量值计算出图Ｇ的响应时间界．算法１．ＯｐｅｎＭＰ任务图响应时间界的精确算法．输人： 带有条件分支结构的有向无环图输出： 最坏情况响应时间界１． 按照Ｇ的拓扑逆序＜７ 遍历节点；２． 对于Ｇ的拓扑逆序 中的每个节点ｘ；ｆ ：３．按照６．２ 节方法计算＜关联的变量；４． 由＜的关联变量计算Ｇ的响应时间界（详见式（３） ）；相较于文献［２０］方法， 本文方法为图Ｇ中的节点关联了更多的变量． 这些变量对于式（３）的精确求解起到关键作用． 接下来， 首先介绍节点关联的变量． 然后， 给出响应时间界的精确求解方法． 最后， 比较文献［２０］方法与本文方法的精确度．６．１ 节点关联的变置图Ｇ中每个节点＜的关联变量如表１ 所示．表１ 图Ｇ中节点关联的变置定义变量名称变量的形式化定义＾ｕｏ／Ｄ（ｖｆ）ｖｏｌＤ（． ｖ＾） — ｍａｘ｛ｖｏｌｆ（ ｖｆ）｝１ｅ ６Ｇ／ｅｎＤ（ｖｆ）／ｅｎＤＣｖｆ） ＝ ｍａｘ｛ｌｅｎ＾（ ｖｆ）｝ｇｒａＤ（ｖ＾）ｇｒａＤ （ｕｐ＝ ｒｍｉ ｘ ｛ｖｏｌ＾（ｖｆ）／ｍ＋（ｌ—ｌ／７ｗ）ｌｅｎｆ（Ｔ／ｆ）｝ｇｒａｆ（ｖｆ）ｇｒａｅ（ｖｆ）＝ ｍａｘ｛ｖｏｌｆ（ｖｆ）／ｍ－ｂ（ｌ￣￣ｌ／ｍ）ｌｅｎ＾（ｖｆ）｝）＝ ｎ＾｛ ｗ／ｆ（ｕｆ）／ｍ＋（ｌ—１／ｍ）ｌｅｎ＾（ ｖｊ）｝ｇｒａ“ （ｖｆ）ｇｒａｔｌ（ｖｆ）＝ ｍａＬ ｘ｛ｖｏｌ＾＞（ｖｆ）／ｍ＇ｂ（ ｌ￣ｌ／ｍ）ｌ ｅｎ＾（ ｖｆ）｝在表１ 的各个公式中， 对于给定的执行流ｅ，根据定义４， 节点＜引导的Ｄ－执行流为￡。（ 〇．＾＾？（ ＜） 为〇－执行流￡１３（ ＜）的负载量． ＾＾（ 〇为Ｄ－执行流ｅＤ？） 中最长路径的长度． 为Ｄ－执行流ｅＤ（ ＜）中以＜为起点且以 为终点的最长路径长度． ＆＜（ ＜） 为Ｄ－执行流ｅＤ （＜） 中以Ｗ－节点为起点的最长路径长度 为Ｄ－执行流ｅＤ（ 圹） 中以Ｗ－节点为起点且以 为终点的最长路径长度．６． ２ 节点变量的递推公式下面介绍表１ 中节点关联变量的计算方法． 根据第３ 节的任务模型可知，一个节点＜可能有零个后继、一个后继和两个后继三种情况． 因此， 将按照这三种可能， 分情况讨论：２１７４ 计 算机 学 报２０２０年（ １ ） 如果节点圹没有后继节点， 则可按以下方法计算各参数．ｖｏｌＤ（ｖｊ）＝ｃ（ ｖｆ） （１１）ｌｅｎＤ（ ｖｆ ）＝ｃ（ｖｐ （１２）ｇｒａＤ（ｖｐ＝ｃ（ ｖＪ） （１３）ｇｒａｅ （ｖ－）＝ｃ（ ｖｆ）（ １４）（ｃ（ｖ〇，ｌ—〇〇，若＜是Ｗ－节点否则（１５）（ｃ（ｖ〇９ 若＜是ｗ－节点（１６）［—〇〇， 否则ｇｒａｕＸｖｆ）ｇｒａｕ｛ｖ－）其中，一〇〇表示“负无穷大”， 即对于任意实数？—＜Ｄ〇－＼￣ａ＝ —〇〇．（２） 如果节点＜仅有一个直接后继节点， 则考虑以下三种情况：①如果＜的后继节点＜与ｔ；「 同属于任务ｒ，，则可按以下方法计算各参数．ｖｏｌＤＣ ｖｆ）＝ｃＯｉ〇＋ ｖｏｌＤ（ ｖＤ（１７）ｌｅｎＤ（ｖ〇＝ｃ（ｖ〇＋ｌｅｎＤ（ｖ｝）（１８）ｇ－ｒａＤ（ ｉ；／）＝ｃ（ｕｆ） ＋ｇｒａＤＣ ｖ＇Ｊ ）（１９）ｇｒａｅ（ｖ＾）＝ｃ（ｖＪｆ） ＋ｇｒａｒ ｛ ｖ＾）（２０）ｇｒａｕ．｛ ｖｘｉ）＜＾ｇｒａｅ（， ｖｒｉ） ，｛ ｇｒａｕＣ ｖｆ＇） ，图６ 给出了式（ １ ７）？ｇｒａ？ｇｒａＤ＾ｖＪ）， 若＜是Ｗ－节点否则若＜是Ｗ－节点否则（２２） 的解释． 如图６ 所示，（２１）（２２）最外层的任务 包含一个以＜为人口的条件分支结构． 该条件分支结构包含两个分支． 其中， 第一个分支包含一个Ｎ－节点， 第二个分支包含一个Ｔ－节点坪， 节点＜创建了ｒ， 的子任务 ＤＡＧ图中所有节点的执行时间均为１ ．式（１ ７） 的含义为， ＜的关联变量 等于＜的执行时间加上＜的关联变量 其中，乂是＜的后继节点． 例如， 在图６ 中， ＜的关联变量ｉｙ〇／Ｄ（ｚ）ｆ＞＝１＋５＝６．式（１８） 的含义为， 圹的关联变量 等于＜的执行时间加上Ｗ的关联变量Ｄ（Ｗ） ． 其中，＜是＜的后继节点． 例如， 在图６ 中， ＜的关联变量ｌｅｎＤ（． ｖ＾）＝１＋ ４＝５．式（ １９） 的含义为， ＜的关联变量ｇｒａＤ（ ＜） 等于＜的执行时间加上＜的关联变量 ） ． 其中，＜是＜的后继节点． 例如， 在图６ 中， ＜的关联变量ｇ＊ｒａＤ（ ｉｉｆ）＝１ ＋４＋１／ｔｗ＝５＋１／ｗ．式（ ２０） 的含义为， ＜的关联变量 ） 等于＜的执行时间加上ｗｆ 的关联变量ｇｒａ，（＜） ． 其中，＜是＜的后继节点． 例如， 在图６ 中， ＜的关联变量ｇｒａ，（ ｕｆ）＝ｌ ＋４＋ｌ／ｍ＝５＋ｌ／ｍ．式（２１） 的含义为， 若＜是Ｗ－节点， 则＜的关联变量等于ｇｒａｕ （＜） ． 否则，ｇｒａｔ．（Ｔ／；‘） 等于认＇的关联变量ｇｒａＷ） ． 其中， Ｗ是＜的后继节点．例如， 在图６ 中， 圹的关联变量ｇｒａ？．（＾）＝５／ｍ．式（２２） 的含义为， 若＜是Ｗ－节点， 则＜的关联变量ｇｒａ？ 〇ｆ） 等于ｇｖａｆ（ ＜）． 否则，ｇｒａ？（ ｔ／ｆ） 等于＜的关联变量 其中， ￥是＜的后继节点．例如， 在图６中， ＜的关联变量＾７＾？（ 〇＝５／？１ ．②如果＜是Ｔ－节点， 则可按以下方法计算各参数． 其中…是Ｔ－节点＜所创建的任务 是任务的源点， 也即＜的后继节点．ｖｏｌＤ（ｖ〇＝ｃ（ ｖｆ） ＋ｖｏｌＤ（ｖｊｒｃ） （２３）ｌｅｎＤ（： ＾）＝ｆ（ ＾）＋Ｚｅ？Ｄ（ ｖ７ｒ） （２４）ｇｒａＤ（ ｖｆ）＝ｃＣ ｖｆ）＋ｇｒａＤ（ｖｊＫ） （２５）ｇｒａｅ（ ｖｐ＝＝ｃ（ｖｆ） （２６）ｇｒａｕＸｖ＾）］＾＼ｇｒａＤ（ｖＪ） ，［—〇〇，若＊＾是ｗ－节点否则（２７）ｇｒａｕ（ ｖ〇＾＼ｇｒａｅ｛ ｖｘ｛） ，Ｌ—〇〇，若Ｗ是Ｗ－节点否则（２８）图７ 给出了式（２３）？（２８） 的解释． 如图７ 所示，最外层的任务ｒ， 包含一个Ｔ－节点＜， ｗｆ创建了的子任务 任务ｒ， 包含一个以ｗｊ为人口的条件分支结构． 该条件分支结构包含两个分支． ＤＡＧ图中所有节点的执行时间均为１．式（２３） 的含义为， ＜的关联变量ｗＺＤ（ ｔ；；ｒ） 等于＜的执行时间加上 的关联变量Ｄ（％〃）． 其中，是节点＜所创建任务ｒ， 的源点．例如， 在图７ 中，孙景昊等： 带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析 ２１ ７５ １１ 期Ｖ， 的关联变量ｗ／Ｄ（＜）＝ｌ＋６＝７．式（２４） 的含义为， ＜的关联变量 等于＜的执行时间加上 的关联变量 其中，是节点＜所创建任务＾的源点． 例如， 在图７ 中，ｖ厂 的关联变量／ｅｎＤ（ ｖ／）＝ｌ＋６＝７．式（２５） 的含义为， ＜的关联变量 等于＜的执行时间加上 的关联变量ｇｒａＤ（Ｗ：；＂＇） ． 其中，＜＂是＜所创建任务ｒ，的源点． 例如， 在图７ 中，＜的关联变量ｇ＂ｒａＤ（ｚ；ｆ）＝ １＋６＝７．式（２６） 的含义为， ＜的关联变量 等于＜的执行时间． 例如， 在图７ 中， 的关联变量ｇｒａｅ（ｖｆ）＝ｌ．式（２７） 的含义为， 若＜是＼＾－节点， 则＜的关联变量ｇｒａｕ．（ｗｆ） 等于ｇｒａＤ（ ｖ；＇） ． 否则，ｇｒａ？．（ｕｆ） 等于＿〇〇． 例如， 在图７ 中， ｖ；■的关联变量ｇｒａ？．（ ｗｆ）＝＿〇〇．式（２８） 的含义为， 若＜是Ｗ－节点， 则＜的关联变量ｇｒａ？（ ｗｆ）等于ｇｒａ，（＜）． 否则， 等于＿〇〇． 例如， 在图７ 中， ＜的关联变量ｇｒｕ？（ ｖ；＂）＝③如果＜的后继是Ｗ－节点％＇？（ 任务ｒ， 即为ｒ，的父任务）， 则可按以下方法计算各参数．ｖｏｌｎ｛ｖｘｉ）＝ｃ｛ ｖｘｉ）（ ２９）Ｗ５（ ＾）＝ｃ（＾） ＋／ｅｎＤ（ ｕ；）（３０）ｇｒａＤ（ ｖｆ）＝ｃ（ｖｆ）＋ｇｒａＤ（ ｖＪ）（３１）ｇｒａ， （ｖｆ）＝ｃ（ ｖｆ）（３２）ｇｒａｕ，（ｖｆ）ｊｇｒａＤ（ ｖｆ） ，ｌ—ｏｏ，若＜是Ｗ－节点否则（３３）ｇｒａｕ｛ｖｘｉ）Ｉ ｇｒａＡｖＤ＾ 若＜是Ｗ－节点否则图８ 给出了式（２９）？（３４） 的解释． 如图８ 所示，最外层的任务ｒ， 包含一个Ｗ－节点＜、一个Ｔ－节点＜和一个以＜为入口的条件分支结构． 其中， Ｔ－节点＜创建了ｒ７ 的子任务＾． ０八＆图中所有节点的执行时间均为１．式（２９） 的含义为， ＜的关联变量ｗＺＤ（ ＜） 等于＜的执行时间． 例如， 在图８ 中， Ｍ的关联变量ｖｏｌＤ（ ｖ－）＝＼ ．式（３０） 的含义为， Ｚ；「 的关联变量ＺｍＤ（ ＜） 等于＜的执行时间加上＜的关联变量＾ 其中，＜是Ｗ－节点且为＜的后继节点． 例如， 在图８ 中，＜的关联变量ＺｒａＤ（ｚ；ｆ）＝ｌ＋５＝６．式（ ３１ ） 的含义为， ＜的关联变量ｇｒｆｌＤ（ ＜） 等于＜的执行时间加上ｖ丨的关联变量ｇｖａＤ（ ＜） ． 其中，＜是Ｗ－节点且为＜的后继节点． 例如， 在图８ 中，＜的关联变量ｇｒａＤ（ ｚ；ｆ）＝ １＋５＝６．式（ ３２） 的含义为， ＜的关联变量ｇｒａｆ（ ＜） 等于＜的执行时间． 例如， 在图８中， ｔ／ｆ 的关联变量ｇｒａｒ ＾）＝ｌ．式（３３） 的含义为， 若圹是Ｗ－节点， 则＜的关联变量 （＜） 等于 （＜）． 否则， （＜） 等于—〇〇． 例如， 在图８ 中， ＜的关联变量ｇｒａ？（＜）＝—〇〇？式（３４） 的含义为， 若＜是Ｗ－节点， 则＜的关联变量ｇｒａ？（ｔ／「） 等于ｇｒａｆ〇丨）． 否则， 等于＿〇〇．例如， 在图８ 中， ＜的关联变量ｇｒａ？（ ＜）＝（３） 如果节点＜有两个直接后继节点， 则考虑以下三种情况：①如果＜是条件分支结构的人口节点（ 假设Ｗ的两个后继节点分别为＜和Ｗ）， 则可按以下方法计算各参数．ｔｉ〇／ｒ，（ Ｔｙｆ）＝ｃ（ｗ／） ４－ｍａｘ｛ ＴＯ／Ｄ（ ＾；＇）， ｖｏｌＤ（ｖｚｉ） ｝（３５）ｌｅｎＤ（． ｖ＇ｌ）＝ｃ（ｖｆ）￣ｈｍａｘ｛ｌｅｎＤ（ ｖ＇）， ｌｅｎＤ（ｖ＾）｝（ ３６）ｇｒａＤ（ｔ；ｐ＝ｃ（ｗｆ） ＋ｍａｘ｛ ｇ＇ｒａＤ（ｔ；；＇），ｇｒａＤ（Ｔｙ；）｝（３７）ｇｒａｅ（． ｖｊ）＝ｃ（ ｖｌ） ＋ｍａｘ｛ ｇｒａｒ（ Ｖｉ）， ｇｒａ，Ｘｖ］）｝（３８）（ｇｒａｏｉ ｖｌ），若ｖ；■是Ｗ－节点ｇｒａｗ｛ｖ］）＜ｍａｘ｛ ＾ｒａ？，（ｗｆ），ｇｒａｖｌ ，Ｘｖｚ，＇） ｝， 否则（ ３９）ｇｒａｕ （ ｖ＾）＝ｍａｘ｛ ｇｒａ？（ ｗ；＇），ｇｒａｕ（ｄ；）｝（ ４０）图９ 给出了式（３５）？（ ４０） 的解释． 如图９ 所示，最外层的任务ｒ， 包含一个Ｔ－节点＜和一个以＜为入口的条件分支结构． 其中， Ｔ－节点＜创建ｒ， 的子任务 另外， 条件分支结构的第一个分支包含一个２１７６ 计 算机 学 报 ２０２０年节点＜， 第二个分支包含一个节点ＤＡＧ图中所有节点的执行时间均为１ ．式（３５） 的含义为， 节点圹的关联变量等于的执行时间加上ｍａｘ｛ ｘ；ｏＺＤ（ｔ；ｆ） ，ｔ；ｏＺＤ（ｚ＾） ｝．其中， Ｗ和Ｗ是条件节点＜的两个后继节点． 另外，ｍａｘ｛ ｒｏ／Ｄ（ ｔ；；ｖ） ， ｔ；ｏＺＤ（ Ｗ） ｝ 表示在Ｉ；＇的关联变量ｗ／ Ｗ） 和Ｗ的关联变量ｔ＾Ｄ（ 〇中取最大值． 例如， 在图９中， １＾０（ 〇＝３，１＾０（ ？＾）＝４． 因此， ＜的关联变量＾〇ＺＤ（ｉ；ｆ）＝１＋４＝＝５．式（３６） 的含义为， 节点圹的关联变量＾７２Ｄ（ 〇等于＜的执行时间加上ｍａｘ｛ＺｅｗＤ（ｔ；ｆ） ， ＾＃（ １；丨）｝．其中， Ｗ和Ｗ是条件节点＜的两个后继节点． 另外，ｍａｘ｛Ｗ） ， ＾７２Ｄ（＜）｝ 表示在Ｗ的关联变量＾／ｚＤ（ ｚ；ｆ） 和＜的关联变量／ｍＤ（ ＜） 中取最大值． 例如， 在图９中“ｅ７ｚＤ（ｔ；？）＝３，＾ｎＤ（ｔ；ｐ＝３？ 因此， ＜的关联变量Ｚｗｄ（＜）＝１＋３＝４．式（３７） 的含义为， ＜的关联变量 （圹） 等于奴ｆ的执行时间加上ｎｉａｘ｛ ｇｒａＤ（ ｚ；ｆ） ，尽？－＜２０（ ＜）｝． 其中， ＜和Ｗ是条件节点＜的两个后继节点． 另外，ｍａｘ｛ ｇｒａＤ（ｔ；『） ，ｇｒａＤ（ ｔ＾）｝ 表示在节点＜的关联变量ｇｒａＤ（ ｔ；；ｖ） 和＜的关联变量ｇｒａＤ（＜） 中取最大值． 例如， 在图９中，ｇｒａＤ？）＝３， ｇｒａＤ（ ｚ；ｆ）＝ ３ ＋ ｌ／ｍ． 因此， ＜的关联变量ｇＴａＤ（ 〇＝ｌ＋３＋ｌ／ｍ＝Ａ＋ｌ／ｍ．式（３８） 的含义为， ＜的关联变量 等于＜的执行时间加上ｍａｘ｛（Ｖ） ， ｇｒａ，（Ｗ）｝？ 其中， ＜和＜是条件节点＜的两个后继节点． 另外，ｍａｘ｛ｇｒａ， （Ｖ），ｇｒａ，（＜） 丨 表示在ｚ；；ｖ的关联变量ｎ〇；＇） 和＊＾的关联变量 ） 中取最大值． 例如， 在图９中，容ｒａｅ（ｚ；；ｖ）＝３，ｇｒａｆ（ ＜）＝３＋１／７Ｗ？ 因此， 的关联变量ｇｒａｅ（ ｚ；ｆ）＝ｌ＋ ３ ＋ ｌ／ｍ＝４＋ｌ／ｍ．式（ ３９） 的含义为， 若＜是Ｗ－节点， 则＜的关联变量ｇｒａｔ， （＜） 等于ｇｒａＤ（＜） ？ 否则，ｇｒａｗ（ ｚ／ｆ）等于ｍａｘ｛（ ｉ；；ｖ） ，ｇｎ２ｕ〇；）｝？ 其中， Ｉ；：； 和ｔ；『 是条件节点＜的两个后继节点． 另夕卜， ｍａｘ｛ｇｒａｕ， （Ｖ ） ，ｇｒａｕ．（ ＜）｝ 表示在节点Ｉ；；＇的关联变量ｇｒａ＿ａ．〇；＇） 和Ｗ的关联变量 中取最大值． 例如， 在图９中， Ｗ的关联变量 ｕ，（＜）＝４／ｍ．式（４０） 的含义为， 圹的关联变量 等于ｍａｘ｛ ｇｎ２？（ Ｗ）， ｗａＭ（ｔ；〖） ｝ ． 其中， Ｚ；；＇和ｔ；『是条件节点＜的两个后继节点． 另夕卜？ｍａｘ｛ｇｒａｕ（Ｖ） ，表示在节点ｔ；？ 的关联变量ｇｒａ？（＜） 和＜的关联变量ｇｒａＪＯ中取最大值． 例如， 在图９ 中，＜的关联变量ｇｒａ？（ ＜）＝４／ｍ．②如果圹创建任务ｒ， 且有后继节点Ｗ（ 如图１０所示） ， 则按以下方法计算各参数．ｖｏｌｌ）（ｖ－）＝ｃ（ ｖｆ）￣ｈｍａｘ｛ ｖｏｌＤ（ ｖ＇ｉ）， ｖｏｌＤ（ｖＳｊｎ）｝（４１ ）Ｚ＾Ｄ（ ｔ；；ｒ）＝ｃ（ｔ；；ｒ）＋ ｍａｘ｛／＾Ｄ（ｔ；；ｖ） ，／＾Ｄ（ｚ；；ｒｆ） ｝（４２）ｇｒａＤ（ ｖｆ）＝ｃ（ｖｆ） ＋ｍａｘ｛ ｒ］ ， ｒ２， ｒ３ ｝ （４３）其中，Ｆｊ＝ｖｏｌＤ｛ｖ＇）ｎ） ／ ｇｒａ＾ｖ）） ，ｒ２＝ｇｒａＤ（ｖＪｃ） ＋ｖｏｌＤ（ｖ） ／ｍ，ｒ３＝ｇｒａｅ （ ｖｓ／ｃ） ＋ｇｒａｕＸｖｙ， ），ｇｒａｅ｛ｖｘｉ）＝ｃ｛ ｖｘｉ）Ｊｒｍｄ．ｘ｛ 〇ｔ＼ ９ 〇２）（４４）其中，ｎ，＼：Ｑｚｇｒａ＾Ｘｖ＾）■ｕｏＺＤ（ ｗ＊ｒｒ）／ｍ ＋ｇｒａ，（－ｙ；ｖ） ，ｇｒａ，（ ｖ＂ ）＋ ｇｒａｕ（ｕ；＇） ，｜＾ｍＤ（ｔ；ｆ）， 若■是Ｗ－节点Ｕｒａ？．（＜）， 否则（４５）ｇｒａ？（ｖｊ）（ｇｒａｒ（ ｖｆ） ，＼ｇｒａ？（ｖｎ＾若＜是Ｗ－节点（４６）否则图１０ 给出了式（４１）？（４６） 的解释． 如图１０ 所示， 最外层的任务ｒ， 包含一个Ｔ－节点＜和一个以＜为入口的条件分支结构． 其中， Ｔ－节点埒创建了ｒ，的子任务ｒ，．ＤＡＧ图中所有节点执行时间均为１．图１０ 式（４１）？（４６） 的解释示例式（４１） 的含义为， ＜的关联变量 等于Ｖ；■的执行时间加上ｍａｘ｛ ｗｃ＾Ｄ（ ｗ；ｖ） ，ｉ；ｏＺＤ（＇￡；７ｖ） ｝ ． 其中， Ｗ是＜的后继节点，＜是节点＜所创建任务ｒ，的源点？ 另夕卜， ｍａｘ｛ ｗ／Ｗ））｝ 表示在＜的关联变量Ｄ） 和的关联变量Ｄ（） 中取最大值． 例如， 在图１０ 中， ｗ／Ｗ） ＝４，ｔＷｕ（ｉ；厂） ＝１． 因此，＜的关联变量ｘＷＤ（ｔ；ｆ）＝ｌ ＋４＝５．式（ ４２） 的含义为， ＜的关联变量Ｚｅｎｕ（ 〇等于「的执行时间加上ｍａｘ｛ＺｅｗＤ（（ｗ厂） ｝． 其中￥是＜的后继节点， ＜■‘是节点＜所创建任务ｆ，的源点． 另外， ｍａｘ｛＆？Ｄ（＜），（＜＂） ｝ 表示在＜１ １ 期 孙景昊等： 带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析 ２１７７的关联变量＆ＤＵＶ） 和＜的关联变量＆°（＜） 中取最大值． 例如， 在图１０ 中，／ｅｗＷ）＝ ４， （ ＜）＝１． 因此， ＜的关联变量 （ 圹）＝ｌ ＋４＝５．式（４３） 的含义为， ＜的关联变量＾ 等于＜的执行时间加上ｍａｘｌｒ！， ｒ２， ｒ３ ｝． 其中， ｍａｘ｛ ｒｉ，Ａ， ｒ３ ｝ 表示在ｒ， 、 ｒ２ 和ａ中取最大值． 令＜■‘是＜所创建任务ｒ， 的源点， Ｖ是＜的后继节点， 参数＾（： ＾： ＾以的含义表示如下： ／＾等于＾的关联变量ｕｏ／Ｄ（ｔ＾）／ｗ加上Ｔ；＇的关联变量ｇｒａ丨 ＾（ｖｆ ）； ｒ２等于 的关联变量 Ｄ（） 加上＜的关联变量ｗＺＤ（ ｔ；；ｖ）／ｍ； ｒ．， 等于 的关联变量＃？（＜）加上Ｗ的关联变量ｇｒａ？．（ｚ；；＇）． 例如， 在图１０ 中， ｒｉ＝４＋１／所， 乃＝１＋４／？２ ， １＼＝１＋４／；＾因此，圹的关联变量）＝ １ ＋４＋１／ｗ＝５＋１／７ｋ．式（ ４４） 的含义为， ＜的关联变量 等于＜的执行时间加上ｍａｘ｛Ｘ２ｉ， 仏｝ ． 其中， ｍａｘ｛ ，仏｝ 表示在辽和仏中取最大值． 令节点 是＜ 所创建任务巧的源点， 节点＜是＜的后继节点， 参数认（ １＝１，２） 的含义表示如下： 仏等于＜＂的关联变量ＷＤ（ｔ；ｐ／ｍ加上＜的关联变量 办等于的关联变量 “） 加上Ｗ的关联变量ｇｒｆｌ？（Ｖ；）． 例如， 在图１０中， ■０！＝４＋ １／ｍ， 從＝１＂Ｉ＂＂４／ｗｉ． 因此， ｗｆ的关联变量ｇｒａ，（ ｗｆ）＝１＋ ４＋ １／ｍ＝５＋１／ｍ．式（ ４５） 的含义为， 若＜是Ｗ－节点， 则＜的关联变量ｇｒａ？． Ｏｆ） 等于ｇｒａ＾（ｚ／ｆ） ． 否则，ｇｒａ？， （＜） 等于＜的关联变量 其中， 认＇是＜的后继节点．例如， 在图１ ０ 中， Ｖ； 的关联变量ｇｒａ？．（＜）＝４／Ｗ．式（ ４６）的含义为， 若＜是Ｗ－节点， 则＜的关联变量ｇｒａ？（＜） 等于 （ｕｆ） ． 否则，ｇｒａ？（＜） 等于切＇的关联变量 （Ｗ） ． 其中， 认＇是＜的后继节点．例如， 在图１ ０ 中， 的关联变量ｇｒａ？（ 〇＝４／ｗ．③如果＜创建任务ｒ， 且有后继Ｗ－节点＜（ ｎ是ｒ， 的父任务） ， 如图１ １ 所示， 则按以下方法计算各参数．ｗＺＤ（〇＝ｃ（＾） ＋ｚ＾Ｄ（ ｚ；厂）（４７）ｌｅｎｎ（ ｖ＾）＝ｃ（ ｖｆ） ＋ｍａｘ｛ ｌｅｎｕ（ ｖ］＇ ｃ）Ｕｅｎ＇ ＾ｉｖ＾）｝（４８）ｇｒａＤ（ ｖｆ）＝ｃ（ｚ）／） ４－ｍａｘ＜ ｒｉ ，ｇｒａＢ｛ｖ］ｒｃ）｝（４９）其中，ｇｒａｕＸｖＪ）［ｇｒａＤ（ｖ－） ， 若ｚ；ｆ是Ｗ－节点否则（ ５１）ｇｒａ？（ ｖｊ）－＼ ｇｒａｒ（． ｖ＾）， 若 是Ｗ－节点否则图１ １ 给出了式（ ４７）？（ ５２） 的解释． 如图１１ 所示， 最外层的任务ｎ包含一个Ｔ－节点Ｗ和一个Ｗ－节点其中， Ｔ－节点Ｘ；丨 创建了ｒ， 的子任务ｒ，．ｒ， 包含一个Ｔ－节点＜， Ｔ－节点＜创建了ｒ， 的子任务ｒ；．包含一个以＇ｕ＇为人口的条件分支结构． ＤＡＧ图中所有节点的执行时间均为１ ．图１ １式（４７）？（５２） 的解释示例式（４７） 的含义为，ｔ；； 的关联变量ｔＷＤ（ 〇等于＜的执行时间加上＜的关联变量 ）． 其中，是＜所创建任务ｒ，的源点． 例如， 在图１ １ 中， ＜的关联变量ｗｏ／！Ｄ（ ｔ＾）＝ｌ＋４＝５．式（ ４８） 的含义为， ＜的关联变量／ｅ？Ｄ（ 〇等于＜的执行时间加上ｍａｘ｛ ／ｅｗＤ（）， ／ｅ？Ｄ（幻丨）｝ ． 其中， 幻厂是＾所创建任务ｒ，的源点，Ｉ；丨是Ｗ－节点且为＜的后继节点． 另外， ｍａｘ｛Ｚ？； ＫＤ（ ｙ）， ＺｅｗＤ（ｔ；ｐ｝ 表示在＜‘的关联变量＾？Ｄ（＜‘） 和＜的关联变量ＺｅｗＤ（＜） 中取最大值． 例如， 在图１１ 中，＝１． 因此， 的关联变量ＺｅＺＯｆ）＝１＋ ４＝５．式（ ４９）的含义为， ｔ；； 的关联变量ｇｒａ［）（ ＜） 等于＜的执行时间加上ｍａｘ｛ｒ！，ｇｒａＤ（■？厂） ｝ ． 其中，ｍａｘ＾ ｒ，， ＾％（＜）｝ 表示在厂， 和节点＜‘的关联变量ｇｒａＤ（ ｆ） 中取最大值． 令 是ｘｒ；■所创建任务ｒ，的源点，＜是Ｗ－节点且为Ｘ；「的后继节点， 参数Ａ等于＜‘的关联变量Ｄ（＜ｆ） ／ｍ加上ｔ；丨的关联变量ＺｅｎＤ（ ＜）？ 例如， 在图１ １中， ｒ，＝１＋４／ｍ， ｇｘａＤ（ｔ；ｐ＝４． 因此，＜的关联变量ｇｎｚＤ（＜）＝ ｌ＋４＝５．式（ ５０） 的含义为， ＜的关联变量ｇｒａ，（ ＜） 等于＜的执行时间． 例如， 在图１ １中，）＝１ ．式（５１） 的含义为， 若＜是１－节点， 则＜的关联变量ｇｒａａ．（＜）等于ｇｒａＤ（＜） ． 否则，ｇｒａ？． （＜）等于—〇〇． 例如， 在图１ １ 中， ＜的关联变量ｇｒａ？．（ ＾）＝Ｆ］＝ ｖｏｌＤ（ ｖｓ ＂）／ｍ－＼－ｌｅｎｕ（ｖ＼） ，ｇｒａ，ＸｖＪ：）＝ｃ｛ ｖ－） （５０）２１７８ 计 报 ２０２０年 算式（５２） 的含义为， 若＜是Ｗ－节点， 则＜的关联变量Ｏｆ） 等于ａ，Ｏｆ）． 否则， （ ｔ；ｆ） 等于＿〇〇． 例如， 在图１１中， ｖｆ的关联变量ｇｒａ？（ ＜）＝—〇〇？时间复杂度分析． 本节的算法具有多项式时间计算复杂度， 其理由如下： 首先， 本节算法为图Ｇ中的每个节点计算６ 个参数， 故需要计算的参数总个数为６ｎ（ ｎ为图Ｇ中的节点个数） ． 其次， 每个节点上参数的计算直接利用该节点后继节点的参数计算结果． 根据式（１ １）？（ ５２） ， 每个参数的计算时间为ＣＫ５）， 其中 为节点的最大出度． 综上， 本节算法总的计算复杂度为ＯＧ５）．６． ３ 算法１ 的误差分析本节介绍算法１ 在图５ 示例上响应时间的计算过程， 并比较文献［２０］算法与算法１的精确度．如图５ 所示， ＜有两个直接后继节点和＜．其中， 是＜所创建任务ｒ，的源点． 根据式（４ ３） ，为了计算＜的关联变量＾ 需要预先计算ｗ广的关联变量ｗＺＤ（） 、ｇｒａＤ（） 和ｇｒａ，（ Ｉ）厂）以及Ｗ的关联变量ｗＺＤ（ｗ；ｖ）、ｇｒａＤ（〇 和ｇｒａｕ．（Ｔ；；ｖ） ．如图５ 所示， 仅有一个直接后继节点Ｗ， 并且＜为Ｗ－节点． 根据式（２９）、（３１） 、 （３２） ， 可以计算以下三个参数ｗＺＤ（ 取厂）＝０、ｙａＤ（ｘ；厂）＝０和ｇｒａ， （）＝０． 如图５ 所示， ｚ；；＇有两个直接后继节点且为条件分支结构的人口节点． 根据式（ ３５） 、 （３７）、 （３９）， 可以计算以下三个参数ＴＯ３ＺＤ（ｚ；；ｖ）＝７ＷＬ、 ｇ＂ｒａＤ（ ｗ；ｖ）＝Ｌ＋（ １一１／ｍ） 和 Ｕｆ）＝Ｌ？ 进一步地， 可计算式（４３）中的中间变量ｆ＂ｉ＝Ｌ ＋１＿ｌ／？ｉ ， ＾二！＾ 和ｊＰ３＝Ｌ？ 因此， ｇｒａＤ（ ｕｆ）＝Ｌ＋（ｌ＿ｌ／ｍ） ．根据５．２ 节可知， 相较于图５ 的真实响应时间界ａ＋（ｌ— ｌ／ｍ） ） ， 文献［２０］算法求得的响应时间界误差为（ Ｌ—ｌ） （ｌ＿ｌ ／ｍ）． 根据上文可知， 本文算法求得的响应时间界为Ｌ＋（ｌ—１／ｍ） ， 即真实响应时间界． 因而， 文献［２０］算法仅能求得近似解， 而本文算法能够得到精确解．７ 实验结果本节实现了文献［２０］的算法（ 记为ＡｌｇＯ） 和本文第６ 节的算法（ 记为Ａｌｇｌ） ． 实验所使用的微型计算机为ＤＥＬＬＯｐｔｉＰｌｅｘ３０５０ 台式机， 硬件配置为Ｉｎｔｅｌ （ Ｒ）Ｃｏｒｅ（ ＴＭ）ｉ５－７５００ＣＰＵ＠３．４０ＧＨｚ， ８ＧＢ机 学ＤＤＲ４ 内存（７．８９ＧＢ可用）， 操作系统为ＭｉｃｒｏｓｏｆｔＷｉ ｎｄｏｗｓｌＯ６４ 位？ 利用Ｐｙｔｈｏｎ语言进行编程， 程序运行环境为Ｐｙｔｈｏｎ３．７， 并利用Ｐｙｔｈｏｎ模块ｍａｔｐｌ ｏｔｌｉ ｂ绘制实验图． 通过随机生成的算例， 对算法求得的响应时间界和计算时间进行了评估． 随机算例的生成程序描述如下．随机生成《个ｃｏｎ－ＤＡＧ任务图｛ Ｇ， ，…， Ｇ，，｝ ．每个任务图在［１０ ， ４０］范围内随机选择非条件节点个数． 每个非条件节点的最坏情况执行时间的取值范围为［１ ， １ ００］． 此外， 每个任务图中条件节点的执行时间为〇．对于每个任务图， 按照从源点到汇点的顺序生成图中的节点． 每个新生成的节点＜以Ｐｉ ｆ 的概率确定为条件节点． 如果＜为条件节点， 则生成＜对应的条件分支结构． 该条件分支结构包含一个人口节点（ 即节点＜） 、 两个条件分支和一个出口节点．如果＜不是条件节点， 则将其随机插人到任务图现有的条件分支中． 对于每个非条件节点＜， 以 的概率将珥确定为Ｔ－节点， 以 ， 的概率将＜确定为Ｗ－节点， 以 的概率将＜确定为Ｎ－节点， 并且保证Ｐｎ＜＞ｒ＋＋Ｐ仰ｉ ， ＝ １ ？对于ｒ， 中任意的Ｔ－节点＜， 在任务集｛ ｒ，＋丨，…，中选择一个尚未分配父任务的 确定ｒ， 是ｒ， 的父任务， 即构造从＜到ｑ源点 的Ｔ－边． 如果不存在这样的ｒ，， 则调整＜为Ｎ－节点．对于Ｗ－节点＜， 设＜为＜的前驱Ｔ－节点， 假设ｒ；是由＜创建的任务， 从巧的汇点到Ｗ－节点＜添加Ｗ－边？图１２？图１６ 针对不同的参数组合进行实验，参数配置如图例所示． 其中， ｍ表示线程数， ｎ表示任务数， Ｐｉ ， 表示条件节点的生成概率，， 表示Ｗ－节点的生成概率， 表示Ｔ－节点的生成概率．图１ ２？图１ ６ 的（ ａ） 中， 灰色柱状图代表ＡｌｇＯ求得的响应时间界的平均值ｉ？。 ； 白色柱状图代表Ａｌｇｌ求得的响应时间界的平均值 箱型图展示了ＡｌｇＯ和Ａｌｇｌ 的响应时间界差值（Ｇａｐ） 的分布． 具体来说， 箱型图对响应时间界的差值按照从小到大排序， 箱型图的顶表示第７５％的数据； 箱型图的底表示第２５％的数据； 箱型图顶和底之间的区域表示２５％？７５％的数据； 中间浅线表示中位数， 即第５０％的数据； 上须线表示Ｇａｐ 的最大值； 下须线表示Ｇａｐ 的最小值？ 图１２？图１６ 的（ｂ） 中， 实折线代孙景昊等： 带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析 ２１７９２５０５００８０４８１２１ ６２０２４２８３２３６４０（ ａ ） 线程数４８１２１６２０２４２８３２３６４０（ ｂ） 线程数图１２ｗ＝１０，Ｐｉｆ＝ ０．３，Ｐｗａｉ ｔ＝〇－３，Ｐｃｒｅ＝ ０．３０．０５０．１００．１５０．２００．２５０．３００．３５０．４００．４５０．５０（ ａ ） Ｐｌｆ０．０５０．１００．１５０．２００．２５０．３００． ３５０．４００．４５０．５０（ｂ）Ｐｉ ｔ１ １期表ＡｌｇＯ 求得的计算时间； 虚折线代表Ａｌｇｌ 求得的计算时间； 箱型图展示了Ａｌｇｌ 和ＡｌｇＯ 的计算时间比值的分布． 具体来说， 箱型图对计算时间的比值按照从小到大排序， 箱型图的顶表示第７５％的数据；箱型图的底表示第２５％的数据； 箱型图顶和底之间的区域表示２５％？７５％的数据； 中间浅线表示中位４０１１６０１ ． ． １ Ｒ０１ ｌ ｉ？１数， 即第５０％的数据； 上须线表示计算时间比值的最大值； 下须线表示计算时间比值的最小值． 对于每种参数组合， 进行１〇〇〇 次随机实验． 实验表明，Ａｌｇｌ 能够改进响应时间界的精度， 与ＡｌｇＯ 的平均界差可达１７６． 另外， 针对所有算例， Ａｌｇｌ 的计算时间在１４．３ ｍｓ 之内， 略高于ＡｌｇＯ．８ ｉ ，６（ ａ） 任务数（ ｂ） 任务数图１３ｍ＝４，Ｐｉｆ＝ ０．３，Ｐｗａｉｔ ＝０．３，Ｐｃｒｅ＝ ０．３１６０ｌ－ １ １ ６０４０． —＝＝＝—１７ｂｉ ． ． ． ． １ Ｒ０１ ＼ Ｒｌｊ＿＾＿Ｔ〇ｌｏｏ９０８０７０６０５０ ４０３０２０ １０ｏｏｏ６４２ｗｓ／匣宮埏４４＞ｏｏｏ＞ｏｏｏｕ８０７０６０５０ ４０３０２０１０２０１５０００５０鰣４－１１２８０４０３０２０１ ０（ＯＩＸＶ蜍Ｒｌｆｅ＾ｉ＃５４３２１３｜阳１２鰣４４１Ｇ（＆ｏ）猢昧叵宏闼晋２００１８４８０（ＯＩＸ）／虼匣宏闼昏１２１４０图１４ｍ＝ｉ，ｎ＝１０，Ｐｗａｈ＝〇．３，Ｐｃｒｃ＝０．３２１ ８０ 计 ２０２０年０． ０５０．１ ００．１５０．２００．２５０．３００．３５０．４００．４５０．５０ ０．０５０．１ ００．１５０．２００．２５０．３００．３５０．４００．４５０．５０（ ｂ） ＰＯＴ图１５：４，７２＝１０，Ｐｉ ｆ ＝０？３，Ｐｗａｉ ， ＝０？３０．０５０．１ ００．１５０．２００．２５０．３００．３５０．４００．４５０．５００．０５０．１００．１５０．２００．２５０．３００．３５０．４００．４５０． ５０Ｃａ） Ｐｗａｉ ｔ（ｂ） Ｐｗａｉ ｔ图１６ｍ＝４，７２ ＝１ ０，Ｐｊ ｆ＝０．３，Ｐｃ ｒｅ＝ ０．３如图１２ 所示， 实验数据表明， 硬件平台上处理器核数会影响Ａｌ ｇＯ 与Ａｌ ｇｌ 求得的Ｇａｐ？ 在一般情况下， 随着核数的增多， 两个算法求得的Ｇａｐ越小．根据Ｇｒａｈａｍ界式（ ３） ， 核数越多， ＤＡＧ图的最大负载对于响应时间的影响越弱． 因此， 该实验现象表明， 相对于提升ＤＡＧ图最长路径长度的评估精度而言， Ａｌｇｌ 能够更有效地改善ＤＡＧ图最大负载的评估精度． 另外， Ａｌｇｌ 与ＡｌｇＯ 的计算时间比值不超过３．５．如图１３ 所示， Ｇａｐ随着任务数的增长而增大．具体原因如下： 随着任务数的增多， 有向无环图的总负载增大． 由于Ａｌ ｇｌ 能够更加精确地估计有向无环图的最大负载量（ 如图１２ 所示） ， 因此， Ｇａｐ 随着任务数增长呈递增趋势． 另外， Ａｌｇｌ 与ＡｌｇＯ 的计算时间的比值略微减少．如图Ｕ所示， 随着Ｐｉｆ 的增大， Ｇａｐ具有増大的趋势． 具体原因如下： 心的值越大， 有向无环图中条件分支嵌套结构越复杂， 越有可能产生有利于Ａｌｇｌ的子结构（ 如５．２ 节中的反例）． 另外， Ａｌｇｌ 与ＡｌｇＯ的计算时间比值呈递减趋势．如图１５ 所示， 随着厂？的增大， Ｇａｐ 呈现递增趋势． 具体原因如下： 根据随机算例程序， 越大，单个任务的子任务就越多， 这导致了较大的任务并行度． 在高并行度的算例（如５． ２ 节的反例） 中更能体现Ａｌｇｌ 的优越性． 另外， Ａｌｇｌ 与ＡｌｇＯ 的计算时间呈现线性增长趋势．如图１６ 所示， 随着尸＿的增大， Ｇａｐ略微减少．具体原因如下： Ｐｗａｉ， 的值越大， 有向无环图的最长路径长度越长． 根据Ｇｒａｈａｍ界式（ ３） ， 最长路径长度越长， ＤＡＧ图的最长路径长度对响应时间的影响越强． 因此， 实验现象表明， 对于响应时间精度的影响而言， 提升ＤＡＧ图最长路径长度的评估精度并没有改善ＤＡＧ图的最大负载精度明显（ 如图１２ 所示）． 另外， Ａｌｇｌ 与ＡｌｇＯ 的计算时间呈现线性增长的趋势．实验数据表明，一方面， 与Ａｌｇｌ 相比， ＡｌｇＯ 需要更少的计算时间（ 平均意义下， ＡｌｇＯ 能够节省２．５ 倍的计算时间） ， 并且能够尽可能高地保障响Ｒｂ？－Ｍ１ｂｉｓ４４３２１２１（２ＸＶ酴叵宏遏＃孙景昊等： 带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析 ２１８１ １ １ 期应时间界的精度． 这说明Ａｌ ｇＯ 具有易实现、 鲁棒的优点．另一方面， 相较于ＡｌｇＯ ， Ａｌｇｌ 能够有效提高响应时间界精度． 在平均情况下， 响应时间界精度能够提高３％． 能够有效改善响应时间界精度， 对实时系统是至关重要的． 原因如下： 在实时系统里， 响应时间直接影响着系统的可调度性． Ａｌｇｌ 在平均响应时间界精度上提高３％， 这会增强系统可调度的概率．值得注意的是， 在实际系统中， 通常存在多个ＤＡＧ任务并行工作的情况． 尽管对于单个ＤＡＧ任务，Ａｌｇｌ带来的精度提升有限（通常是原响应时间界的３％） ， 但是， 对于包含多个ＤＡＧ任务的实时系统而言， 如果每个ＤＡＧ任务的响应时间界精度提升３％， 其积累的精度也是很可观的．另外， 与ＡｌｇＯ 相比， Ａｌｇｌ 的计算时间有所增加． 但是， 这种增加并不会破坏实时系统的实时性．具体原因如下： 在实时系统里， 系统计算性能和运行时间是非常重要的． 其中， 系统运行时间指的是在系统部署之后运行时的时间． 本文方法应用于系统部署之前， 对系统进行离线分析和验证． 因此， Ａｌ ｇｌ 的计算时间与系统部署之后实际运行的时间没有必然联系．综上所述， 尽管Ａｌｇｌ 增加了计算时间， 但是提升了响应时间界的分析精度． 这对于保障系统的安全性来说是值得的： 对于可调度性处于临界状态的实时系统而言， 响应时间精度有１％的提升， 都有可能极大地增加系统可调度的概率．８ 总结与展望ＯｐｅｎＭＰ是实时系统最有希望的多核并行编程框架之一． 近年来， 实时系统领域的研究热点围绕ＯｐｅｎＭＰ的ＤＡＧ任务图展开． 当前， ＤＡＧ任务图的研究很少考虑ＯｐｅｎＭＰ程序的条件分支特征． 尚未有研究能够精确计算出带有条件分支结构ＯｐｅｎＭＰ任务图的响应时间界． 本文致力于研究ＯｐｅｎＭＰ的并行结构和分支结构特征， 基于动态规划技术提出了能够求解带有条件分支ＯｐｅｎＭＰ任务图响应时间界的精确算法． 并且， 本文方法具有多项式时间的计算复杂度． 下一步的工作将围绕ＯｐｅｎＭＰ程序更复杂的实际特征展开， 例如， 程序中的循环和递归特征． 为带有条件分支和循环递归结构ＯｐｅｎＭＰ程序的响应时间分析提供新的理论和方法．参 考 文 献［１ ］ＢｏａｒｄＯＡＲ．ＯｐｅｎＭＰａｐｐｌｉｃａｔ ｉｏｎｐｒｏｇｒａｍｉｎｔ ｅｒｆａｃｅｖｅｒｓｉｏｎ３． ０． Ｂａｒｃｅｌｏｎａ，Ｓｐａｉｎ；ＢａｒｃｅｌｏｎａＳｕｐｅｒｃｏｍｐｕｔｉｎｇＣｅｎｔｅｒ，ＴｅｃｈｎｏｌｏｇｙＲｅｐｏｒｔ：０１ ，２００８［２］ＳａｉｆｕｌｌａｈＡ？ＬｉＪ？ＡｇｒａｗａｌＫ？ｅｔａｌ．Ｍｕｌｔｉ－ｃｏｒｅｒｅａｌ－ｔ ｉｍｅｓｃｈｅｄｕｌｉｎｇｆｏｒｇｅｎｅｒａｌｉｚｅｄｐａｒａｌｌｅｌｔ ａｓｋｍｏｄｅｌｓ． Ｒｅａｌ－ＴｉｍｅＳｙｓｔｅｍｓ，２０１ ３，４９（ ４ ） ：４０４－４３５［３］Ｌｉ Ｊ，ＬｕｏＺ， ＦｅｒｒｙＤ，ｅｔａｌ．ＧｌｏｂａｌＥＤＦｓｃｈｅｄｕｌｉ ｎｇｆｏｒｐａｒａｌｌｅｌｒｅａｌ－ｔｉ ｍｅｔａｓｋｓ．Ｒｅａｌ－ＴｉｍｅＳｙｓｔｅｍｓ ，２０１５，５ １（４） ：３９５－４３９［４］ＦｅｒｒｙＤ， ＬｉＪ， ＭａｈａｄｅｖａｎＭ，ｅｔａｌ．Ａｒｅａｌ－ｔｉ ｍｅｓｃｈｅｄｕｌｉ ｎｇｓｅｒｖｉｃｅｆｏｒｐａｒａｌ ｌｅｌ ｔａｓｋｓ／／Ｐｒｏｃｅｅｄｉ ｎｇｓ ｏｆ ｔｈｅ２０１３ＩＥＥＥ１９ｔ ｈＲｅａｌ－ＴｉｍｅａｎｄＥｍｂｅｄｄｅｄＴｅｃｈｎｏｌｏｇｙａｎｄＡｐｐｌｉｃａｔｉｏｎｓＳｙｍｐｏｓｉｕｍ（ ＲＴＡＳ）．Ｐｈｉｌａｄｅｌｐｈｉａ，ＵＳＡ，２０１３ ：２６１－２７２［５］Ｓａｉ ｆｕｌｌａｈＡ，ＦｅｒｒｙＤ，ＬｉＪ，ｅｔａｌ．Ｐａｒａｌｌｅｌｒｅａｌ－ｔｉｍｅｓｃｈｅｄｕｌｉｎｇｏｆＤＡＧｓ． ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｒａｌｌｅｌａｎｄＤｉ ｓｔｒｉｂｕｔｅｄＳｙｓｔ ｅｍｓ，２０１４？２５（ １２ ） ：３２４２－３２５ ２［６］ＢａｒｕａｈＳ． Ｉ ｍｐｒｏｖｅｄｍｕｌｔｉｐｒｏｃｅｓｓｏｒｇｌｏｂａｌｓｃｈｅｄｕｌａｂｉｌｉｔｙａｎａｌｙｓｉｓｏｆｓｐｏｒａｄｉｃＤＡＧｔａｓｋｓｙｓｔｅｍｓ／ ／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２０１４２６ｔｈＥｕｒｏｍｉ ｃｒｏＣｏｎｆｅｒｅｎｃｅｏｎＲｅａｌ－ＴｉｍｅＳｙｓｔｅｍｓ．Ｍａｄｒｉ ｄ＊Ｓｐａｉｎ，２０１４：９７－１０５［７］ＱａｍｈｉｅｈＭ？Ｆａｕｂｅｒｔ ｅａｕＦ，ＧｅｏｒｇｅＬ？ＭｉｄｏｎｎｅｔＳ． ＧｌｏｂａｌＥＤＦｓｃｈｅｄｕｌｉ ｎｇｏｆｄｉｒｅｃｔｅｄａｃｙｃｌ ｉｃｇｒａｐｈｓｏｎｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｙｓｔ ｅｍｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔ ｈｅ２ １ｓｔＩｎｔ ｅｒｎａｔｉ ｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＲｅａｌ－Ｔｉ ｍｅＮｅｔｗｏｒｋｓａｎｄＳｙｓｔｅｍｓ．ＮｅｗＹｏｒｋ，ＵＳＡ，２０１３ ：２８７－２９６［８］ＱａｍｈｉｅｈＭ，ＧｅｏｒｇｅＬ？ＭｉｄｏｎｎｅｔＳ． Ａｓｔｒｅｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｐａｒａｌｌｅｌｒｅａｌ－ｔｉｍｅＤＡＧｔａｓｋｓｏｎｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｙｓｔｅｍｓ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆ ｔ ｈｅ２２ ｎｄＩｎｔｅｒｎａｔ ｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ ｏｎＲｅａｌ－ＴｉｍｅＮｅｔｗｏｒｋｓａｎｄＳｙｓｔｅｍｓ．ＮｅｗＹｏｒｋ，ＵＳＡ，２０１４：１３［９］ＳｅｒｒａｎｏＭＡ，ＭｅｌａｎｉＡ，ＶａｒｇａｓＲ？ｅｔａｌ．Ｔｉｍｉｎｇｃｈａｒａｃｔｅｒ？ｉｚａｔｉｏｎｏｆ ＯｐｅｎＭＰ４ｔａｓｋｉｎｇｍｏｄｅｌ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２０１５Ｉｎｔｅｒｎａｔｉ ｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｉｌｅｒｓ，Ａｒｃｈｉ ｔ ｅｃｔｕｒｅａｎｄＳｙｎｔｈｅｓｉ ｓｆｏｒＥｍｂｅｄｄｅｄＳｙｓｔ ｅｍｓ（ ＣＡＳＥＳ）．Ａｍｓｔｅｒｄａｍ，Ｎｅｔ ｈｅｒｌａｎｄｓ，２０１５ ：１５７－１６６［１０］ＶａｒｇａｓＲ， ＱｕｉｎｏｎｅｓＥ？ＭａｒｏｎｇｉｕＡ． ＯｐｅｎＭＰａｎｄｔｉｍｉｎｇｐｒｅｄｉｃｔａｂｉｌｉｔｙ： Ａｐｏｓｓｉ ｂｌｅｕｎｉｏｎ？／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２０１５Ｄｅｓｉｇｎ， ＡｕｔｏｍａｔｉｏｎＴｅｓｔ ｉ ｎＥｕｒｏｐｅＣｏｎｆｅｒｅｎｃｅ＆？Ｅｘｈｉｂｉ ｔ ｉ ｏｎ． ＳａｎＪｏｓｅｔＵＳＡ？２０ Ｘ５ ： ６１７－６２０［１１］ＳｕｎＪｉｎｇｈａｏ， ＧｕａｎＮａｎ，ＷａｎｇＹａｎｇ，ｅｔａｌ． Ｒｅａｌ－ｔ ｉ ｍｅｓｃｈｅｄｕｌｉｎｇａｎｄａｎａｌｙｓｉ ｓｏｆＯｐｅｎＭＰｔａｓｋｓｙｓｔ ｅｍｓｗｉ ｔ ｈｔ ｉ ｅｄｔａｓｋｓ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＲｅａｌ－Ｔｉ ｍｅＳｙｓｔｅｍｓＳｙｍｐｏｓｉ ｕｍ（ＲＴＳＳ） ． Ｐａｉｒｓ，Ｆｒａｎｃｅ，２０１７ ： ９２－１ ０３［１２］ＺｈｏｕＪｉａ－Ｘｉａｎｇ，ＺｈｅｎｇＷｅｉ－Ｍｉｎ． Ａｓｔａｔｉｃｓｃｈｅｄｕｌｉ ｎｇａｌｇｏｒｉｔ ｈｍｏｎＤＡＧｐａｒｔ ｉｔｉｏｎ－ｒｅｃｏｎｆ ｉｇｕｒａｔｉｏｎｉ ｎｔ ｈｅｎｅｔ ｗｏｒｋｏｆｗｏｒｋｓｔａｔｉｏｎｓ．ＪｏｕｒｎａｌｏｆＳｏｆｔ ｗａｒｅ ？２０００ ？１ １ （ ８） ：１０９７－１１０４（ ｉｎＣｈｉｎｅｓｅ）（周佳祥， 郑纬民． 基于ＤＡＧ图解一重构的机群系统静态调度算法．软件学报， ２０００，１ １ （ ８） ：１０９７－１ １０４）２１８２ 计 报 ２０２０年 算 机 学／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆｔ ｈｅ２０１９ＩＥＥＥＲｅａｌ－ＴｉｍｅａｎｄＥｍｂｅｄｄｅｄＴｅｃｈｎｏｌｏｇｙａｎｄＡｐｐｌｉｃａｔｉｏｎｓＳｙｍｐｏｓｉ ｕｍ（ ＲＴＡＳ）．Ｍｏｎｔｒｅａｌ ，Ｃａｎａｄａ，２０１ ９ ：１６９－１８１［１３ ］ＦｏｎｓｅｃａＪＣ？ＮｅｌｉｓＶ？ＲａｒａｖｉＧ，ＰｉｎｈｏＬＭ． Ａｍｕｌｔｉ－ＤＡＧｍｏｄｅｌｆｏｒｒｅａｌ－ｔ ｉ ｍｅｐａｒａｌｌ ｅｌａｐｐｌｉ ｃａｔ ｉｏｎｓｗｉ ｔ ｈｃｏｎｄｉｔ ｉ ｏｎａｌｅｘｅｃｕｔ ｉ ｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆ ｔｈｅ ３０ｔｈＡｎｎｕａｌＡＣＭＳｙｍｐｏｓｉ ｕｍｏｎＡｐｐｌｉ ｅｄＣｏｍｐｕｔｉｎｇ．ＮｅｗＹｏｒｋ， ＵＳＡ，２０１５ ： １ ９２ ５－１ ９３２［１ ４］ＢａｒｕａｈＳ， Ｂｏｎｉｆ ａｃｉＶ， Ｍａｒｃｈｅｔｔ ｉ－ＳｐａｃｃａｍｅｌａＡ．Ｔｈｅｇｌ ｏｂａｌＥＤＦｓｃｈｅｄｕｌｉ ｎｇｏｆｓｙｓｔｅｍｓｏｆｃｏｎｄｉｔｉｏｎａｌｓｐｏｒａｄｉｃＤＡＧｔａｓｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔ ｈｅ２０１５２７ｔ ｈＲｅａｌ－ＴｉｍｅＳｙｓｔ ｅｍｓ（ ＥＣＲＴＳ）．Ｌｕｎｄ，Ｓｗｅｄｅｎ，２０１５ ：２２２－２３１［１ ５］ＢａｒｕａｈＳ．Ｔｈｅｆ ｅｄｅｒａｔ ｅｄｓｃｈｅｄｕｌ ｉ ｎｇｏｆｓｙｓｔ ｅｍｓ ｏｆ ｃｏｎｄｉ ｔ ｉ ｏｎａｌｓｐｏｒａｄｉ ｃＤＡＧｔａｓｋｓ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆ ｔｈｅ１ ２ｔｈＩ ｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆ ｅｒｅｎｃｅｏｎＥｍｂｅｄｄｅｄＳｏｆｔ ｗａｒｅ．ＮＪ，ＵＳＡ，２０１ ５：１－１ ０［１６］Ｍｅｌ ａｎｉＡ．ＢｅｒｔｏｇｎａＭ，Ｂｏｎｉ ｆ ａｃｉＶ， ｅｔａｌ ． Ｒｅｓｐｏｎｓｅ－ｔｉ ｍｅａｎａｌｙｓｉ ｓｏｆｃｏｎｄｉｔｉ ｏｎａｌＤＡＧｔａｓｋｓｉ ｎｍｕ ｌｔｉｐｒｏｃｅｓｓｏｒｓｙｓｔｅｍｓ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆｔ ｈｅ２０１５２７ｔ ｈＥｕｒｏｍｉｃｒｏＣｏｎｆｅｒｅｎｃｅｏｎＲｅａｌ－ＴｉｍｅＳｙｓｔｅｍｓ． Ｌｕｎｄ， Ｓｗｅｄｅｎ，２０１５ ：２１１－２２１［ １７］Ｍｅｌ ａｎｉＡ，Ｂｅｒｔ ｏｇｎａＭ，ＢｏｎｉｆａｃｉＶ，ｅｔａｌ．Ｓｃｈｅｄｕ ｌａｂｉｌｉｔｙａｎａｌｙｓｉｓｏｆｃｏｎｄｉｔｉｏｎａｌ ｐａｒａｌ ｌｅｌｔａｓｋｇｒａｐｈｓｉ ｎｍｕｌｔｉｃｏｒｅｓｙｓｔｅｍｓ． ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＣｏｍｐｕｔｅｒｓ ？２０１７ ， ６ ６ （ ２ ） ：３３９－３ ５３［１８］ＳｕｎＪ，ＧｕａｎＮ， ＷａｎｇＹ，ｅｔａｌ．Ｆｅａｓｉｂｉｌｉｔｙｏｆｆｏｒｋ－ｊｏｉｎｒｅａｌ－ｔ ｉｍｅｔ ａｓｋｇｒａｐｈｍｏｄｅｌｓ：Ｈａｒｄｎｅｓｓａｎｄ ａｌｇｏｒｉｔ ｈｍｓ． ＡＣＭＴｒａｎｓａｃｔｉ ｏｎｓｏｎＥｍｂｅｄｄｅｄＣｏｍｐｕｔｉｎｇＳｙｓｔｅｍｓ，２０１６ ，１５（ １） ：１４匸１９］ＧｒａｈａｍＲＬ． Ｂｏｕｎｄｓｆｏｒｃｅｒｔａｉ ｎｍｕｌｔｉｐｒｏｃｅｓｓｉｎｇａｎｏｍａｌ ｉ ｅｓ．ＢｅｌｌＳｙｓｔｅｍＴｅｃｈｎｉｃａｌＪｏｕｒｎａｌ ，１ ９６６， ４５ （ ９ ） ： １５６３－１ ５８１［２０］ＳｕｎＪ， ＧｕａｎＮ，ＳｕｎＪ， ＣｈｉＹ． Ｃａｌｃｕｌａｔｉ ｎｇｒｅｓｐｏｎｓｅ－ｔｉ ｍｅｂｏｕｎｄｓｆｏｒＯｐｅｎＭＰｔａｓｋｓｙｓｔｅｍｓｗｉｔｈｃｏｎｄｉｔｉｏｎａｌｂｒａｎｃｈｅｓ［２１］ＬｉｕＸ， Ｍｅｌｌ ｏｒ－ＣｒｕｍｍｅｙＪ， ＦａｇａｎＭ． Ａｎｅｗａｐｐｒｏａｃｈｆｏｒｐｅｒｆ ｏｒｍａｎｃｅａｎａｌｙｓｉｓｏｆＯｐｅｎＭＰｐｒｏｇｒａｍｓ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆｔｈｅ２ ７ｔ ｈＩ ｎｔｅｒｎａｔｉｏｎａｌＡＣＭＣｏｎｆｅｒｅｎｃｅｏｎＩｎｔ ｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＳｕｐｅｒｃｏｍｐｕｔｉｎｇ． ＮｅｗＹｏｒｋ，ＵＳＡ， ２０１ ３：６９－８０［２ ２］Ｅｉ ｃｈｅｎｂｅｒｇｅｒＡＥ，Ｍｅｌ ｌｏｒ－ＣｒｕｍｍｅｙＪ？ＳｃｈｕｌｚＭ，ｅｔａｌ．ＯＭＰＴ：ＡｎＯｐｅｎＭＰｔｏｏｌｓａｐｐｌｉ ｃａｔｉｏｎｐｒｏｇｒａｍｍｉ ｎｇｉ ｎｔｅｒｆａｃｅｆｏｒｐｅｒｆ ｏｒｍａｎｃｅａｎａｌｙｓｉ ｓ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆｔｈｅＩ ｎｔ ｅｒｎａｔｉ ｏｎａｌＷｏｒｋｓｈｏｐｏｎＯｐｅｎＭＰ． Ｃａｎｂｅｒｒａ ，Ａｕｓｔｒａｌ ｉ ａ，２０１３ ：１７１－１８５［２３］ＨｕｃｋＫＡ，Ｍａｌ ｏｎｙＡＤ， ＳｈｅｎｄｅＳ， ＪａｃｏｂｓｅｎＤＷ．Ｉ ｎｔｅｇｒａｔ ｅｄｍｅａｓｕｒｅｍｅｎｔｆ ｏｒｃｒｏｓｓ－ｐｌａｔｆ ｏｒｍＯｐｅｎＭＰｐｅｒｆｏｒｍａｎｃｅａｎａｌｙｓｉｓ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩｎｔｅｒｎａｔｉｏｎａｌ ＷｏｒｋｓｈｏｐｏｎＯｐｅｎＭＰ． Ｓａｌｖａｄｏｒ，Ｂｒａｓｉｌ ，２０１４： １４６－１６０［２４］Ｄｉ ｅｔｒｉｃｈＲ， Ｓｃｈｍｉｔ ｔＦ， ＧｒｕｎｄＡ， Ｓｃｈｍｉｄｌ Ｄ． Ｐｅｒｆｏｒｍａｎｃｅｍｅａｓｕｒｅｍｅｎｔｆｏｒ ｔｈｅ ＯｐｅｎＭＰ４． ０ ｏｆｆｌｏａｄｉｎｇｍｏｄｅｌ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆｔ ｈｅＥｕｒｏｐｅａｎＣｏｎｆ ｅｒｅｎｃｅｏｎＰａｒａｌｌｅｌＰｒｏｃｅｓｓｉｎｇ． Ｐｏｒｔｏ，Ｐｏｒｔｕｇａｌ，２０１４：２ ９１－３０１［２５］ＦｒｉｇｏＭ，Ｌｅｉ ｓｅｒｓｏｎＣＥ．ＲａｎｄａｌｌＫＨ．Ｔｈｅｉ ｍｐｌｅｍｅｎｔ ａｔ ｉｏｎｏｆｔｈｅＣｉｌｋ－５ｍｕｌｔｉｔｈｒｅａｄｅｄｌａｎｇｕａｇｅ． ＡＣＭＳＩＧＰＬＡＮＮｏｔｉｃｅｓ ，１９９８，３３（５）：２１２－２２３［２６］ＮａｒｌｉｋａｒＧＪ．Ｓｃｈｅｄｕｌ ｉｎｇｔｈｒｅａｄｓｆ ｏｒｌｏｗｓｐａｃｅｒｅｑｕｉ ｒｅｍｅｎｔａｎｄｇｏｏｄｌｏｃａｌｉｔｙ．ＴｈｅｏｒｙｏｆＣｏｍｐｕｔｉｎｇＳｙｓｔｅｍｓ，２００２，３５（ ２） ：１ ５１－１８７ＳＵＮＪｉ ｎｇ－Ｈａｏ， Ｐｈ．Ｄ． ， ａｓｓｏｃｉａｔｅｐｒｏｆｅｓｓｏｒ．Ｈｉｓｒｅｓｅａｒｃｈｉ ｎｔ ｅｒｅｓｔｓｉｎｃｌ ｕｄｅｒｅａｌ－ｔｉ ｍｅｓｙｓｔｅｍｓｃｈｅｄｕｌｉｎｇａｎｄｐａｒａｌｌｅｌｐｒｏｇｒａｍａｎａｌｙｓｉｓ．ＺＨＡＮＧＬｉ－Ｗｅｉ，Ｍ． Ｓ．ｃａｎｄｉｄａｔｅ．ＨｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅＯｐｅｎＭＰｐａｒａｌｌ ｅｌｐｒｏｇｒａｍａｎａｌｙｓｉｓ．ＣＨＩＹａｏ－Ｙａｏ，Ｍ．Ｓ．ｃａｎｄｉｄａｔ ｅ．Ｈｅｒｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｒｅａｌ－ｔｉ ｍｅｐａｒａｌｌ ｅｌｓｙｓｔｅｍｓｃｈｅｄｕｌｉｎｇ．ＣＡＯＬｅｉ ，Ｂ．Ｓ．Ｈｅｒｒｅｓｅａｒｃｈｉ ｎｔｅｒｅｓｔｓｉｎｃｌ ｕｄｅｒｅａｌ－ｔｉｍｅｓｙｓｔｅｍａｎｄｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ．ＤＥＮＧＱｉｎｇ－ＸｕｔＰｈ．Ｄ．？ｐｒｏｆｅｓｓｏｒ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｉｓｒｅａｌ－ｔ ｉ ｍｅｓｙｓｔｅｍ．ＢａｃｋｇｒｏｕｎｄＮｏｗａｄａｙｓ，ｗｉｔｈｔ ｈｅｄｅｖｅｌ ｏｐｍｅｎｔｏｆｍｕｌ ｔｉｃｏｒｅｓ，ｈｉｇｈ－ｐｅｒｆｏｒｍａｎｃｅａｎｄｒｅａｌ－ｔｉ ｍｅｏｆｓｏｆｔ ｗａｒｅｈａｖｅｄｒａｗｎｉｎｃｒｅａｓｉｎｇｉｎｔｅｒｅｓｔｓｉ ｎｅｍｂｅｄｄｅｄａｎｄｒｅａｌ－ｔ ｉｍｅｃｏｍｐｕｔｉｎｇｓｙｓｔｅｍｓ．ＯｐｅｎＭＰｃａｎｆｕｌ ｌｙｒｅｆｌ ｅｃｔｔｈｅｐａｒａｌｌ ｅｌｎａｔｕｒｅｏｆｒｅａｌ－ｔｉ ｍｅｃｏｍｐｕｔｉｎｇ，ａｎｄｉｓｏｎｅｏｆｔｈｅｍｏｓｔｐｒｏｍｉ ｓｉｎｇｔｈｅｄｅｆａｃｔ ｏｓｔａｎｄａｒｄｆｏｒｂｕｉｌ ｄｉ ｎｇｎｅｘｔ－ｇｅｎｅｒａｔｉｏｎｒｅａｌ－ｔｉｍｅｅｍｂｅｄｄｅｄｓｙｓｔｅｍｓ． ＯｐｅｎＭＰｒｅａｌ－ｔｉｍｅｓｃｈｅｄｕｌｉｎｇｔｈｅｏｒｙｂｒｅａｋｓｔｈｒｏｕｇｈｔｈｅｙｈａｖｅｎｏｔｂｅｅｎｒｅｓｏｌ ｖｅｄ．Ｔｈｉ ｓｓｕｂｊｅｃｔｉｓｔｏｓｔｕｄｙｔｈｅｄｉ ｆｆｉｃｕｌｔｐｒｏｂｌ ｅｍｓｉｎＯｐｅｎＭＰｒｅａｌ－ｔｉｍｅｓｃｈｅｄｕｌｉｎｇ． Ｉｎｔｈｅｒｅａｌ－ｔｉｍｅｆｉｅｌ ｄ，ａｄｉｒｅｃｔ ｅｄａｃｙｃｌｉｃｇｒａｐｈ（ ＤＡＧ）ｉｓｔｈｅｎａｔ ｕｒａｌｍｏｄｅｌｆｏｒｃｈａｒａｃｔｅｒｉｚｉ ｎｇＯｐｅｎＭＰｐｒｏｇｒａｍｓ．Ｈｏｗｅｖｅｒ，ＤＡＧｓｃａｎｎｏｔａｃｃｕｒａｔ ｅｌｙｄｅｓｃｒｉｂｅＯｐｅｎＭＰｐｒｏｇｒａｍｓｂｅｃａｕｓｅＯｐｅｎＭＰｐｒｏｇｒａｍｓａｒｅｎｏｔ ｏｎｌｙｐａｒａｌ ｌｅｌ， ｂｕｔａｌｓｏｉ ｎｃｌ ｕｄｅｃｏｎｄｉｔｉｏｎａｌｂｒａｎｃｈｅｓ（ｓｕｃｈａｓｉｆ－ｅｌ ｓｅｓｔ ａｔｅｍｅｎｔ） ．Ｔｈｅｒｅｆｏｒｅ，ｒｅｓｅａｒｃｈｏｎｔｈｅｃｏｎｄｉｔｉｏｎａｌＤＡＧ（ｃｏｎ－ＤＡＧ）ｔ ａｓｋｇｒａｐｈｉｓｓｔｉｌ ｌｏｐｅｎ．ＥｘｉｓｔｉｎｇＤＡＧｔ ａｓｋｍｏｄｅｌｓａｓｓｕｍｅｗｅｌ ｌ－ｎｅｓｔ ｅｄｓｔ ｒｕｃｔｕｒｅｓｒｅｃｕｒｓｉｖｅｌｙｃｏｍｐｏｓｅｄｂｙｓｉｎｇｌｅ－ ｓｏｕｒｃｅ－ ｓｉｎｇｌｅ－ ｓｉｎｋｐａｒａｌ ｌ ｅｌａｎｄｃｏｎｄｉｔ ｉｏｎａｌｃｏｍｐｏｎｅｎｔｓ．Ｈｏｗｅｖｅｒ，ｃｏｎ－ＤＡＧｓｉｎｇｅｎｅｒａｌｄｏｎｏｔｃｏｍｐｌｙｗｉｔｈｔｈｉｓａｓｓｕｍｐｔｉｏｎ， ａｎｄｅｘｉｓｔ ｉｎｇｗｏｒｋ孙景昊等： 带有分支结构ＯｐｅｎＭＰ任务图的响应时间分析 ２１８３ １１ 期ｃａｎｎｏｔｆｕｌ ｌｙｄｅｓｃｒｉｂｅａｎｄａｎａｌｙｚｅｔｈｅｂｅｈａｖｉｏｒｓｏｆｒｅａｌｉｓｔｉｃＯｐｅｎＭＰｐｒｏｇｒａｍｓ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｗｉｌ ｌｍｏｄｅｌ ａｎｄａｎａｌｙｚｅｔｈｅｂｅｈａｖｉｏｒｓｏｆＯｐｅｎＭＰｔａｓｋｓｙｓｔｅｍｓｗｉｔｈｇｅｎｅｒａｌｂｒａｎｃｈｉｎｇｓｔｒｕｃｔｕｒｅｓ．Ｔｈｉｓｐａｐｅｒ ａｉｍｓｔｏａｎａｌｙｚｅｔｈｅｒｅｓｐｏｎｓｅｔｉｍｅｏｆＯｐｅｎＭＰｐｒｏｇｒａｍｓｗｉｔｈｃｏｎｄｉ ｔｉｏｎａｌｂｒａｎｃｈｓｔｒｕｃｔｕｒｅ．Ａｎａｉｖｅｓｏｌ ｕｔｉ ｏｎｉｓｃａｌｃｕｌ ａｔｉｎｇｔｈｅｒｅｓｐｏｎｓｅｔｉｍｅｂｙｅｎｕｍｅｒａｔｉｎｇａｌｌｐｏｓｓｉ ｂｌ ｅｅｘｅｃｕｔｉｏｎｆｌｏｗｓｉｎｔｈｅｃｏｎ－ＤＡＧｓ，ｂｕｔｉｔｈａｓｅｘｐｏｎｅｎｔｉａｌｔｉ ｍｅｃｏｍｐｌ ｅｘｉｔｙ．Ｔｈｅｒｅｆｏｒｅ ？ｅｘｉｓｔｉｎｇｗｏｒｋｓｄｅｖｅｌｏｐｐｏｌｙｎｏｍｉａｌ？ｔｉｍｅｄｙｎａｍｉ ｃｐｒｏｇｒａｍｍｉｎｇａｌ ｇｏｒｉ ｔｈｍｓｔｏｃａｌ ｃｕｌａｔｅｒｅｓｐｏｎｓｅｔｉ ｍｅｂｏｕｎｄｓｏｆｃｏｎ－ＤＡＧｓ．Ｈｏｗｅｖｅｒ，ｔｈｅｓｅｍｅｔｈｏｄｓａｓｓｕｍｅｓｔｒｕｃｔｕｒｅｓｒｅｃｕｒｓｉｖｅｌｙｃｏｍｐｏｓｅｄｂｙｓｉ ｎｇｌｅ－ｓｏｕｒｃｅ－ｓｉｎｇｌ ｅ－ｓｉｎｋｐａｒａｌ ｌｅｌａｎｄｃｏｎｄｉｔｉｏｎａｌｃｏｍｐｏｎｅｎｔｓ，ｓｏｔｈｅｙｃａｎｎｏｔａｎａｌｙｚｅｇｅｎｅｒａｌ ＯｐｅｎＭＰｔａｓｋｓｙｓｔｅｍｓｔｈａｔｄｏｎｏｔｃｏｍｐｌ ｙｗｉｔｈｔｈｉｓａｓｓｕｍｐｔｉｏｎ．Ｔｈｉｓｐａｐｅｒｓｔｕｄｉｅｓｇｅｎｅｒａｌ ＯｐｅｎＭＰｔａｓｋｓｙｓｔｅｍｓ，ａｎｄｐｒｏｐｏｓｅｓａｎａｌｇｏｒｉ ｔｈｍｆｏｒｃａｌｃｕｌａｔｉｎｇｔｈｅｒｅｓｐｏｎｓｅｔｉ ｍｅｏｆｃｏｎ－ＤＡＧｔａｓｋｇｒａｐｈｗｉｔｈ‘‘ｍｕｌｔｉ－ｓｏｕｒｃｅ－ｍｕｌ ｔｉ－ｓｉｎｋ”ｃｏｎｄｉｔｉｏｎａｌｓｔｒｕｃｔｕｒｅｓ．Ｃｏｍｐａｒｅｄｗｉｔｈｅｘｉｓｔｉｎｇｍｅｔｈｏｄｓ，Ｔｈｅａｌｇｏｒｉｔｈｍｉｎｔｈｉｓｐａｐｅｒｎｏｔｏｎｌｙｃａｎａｃｃｕｒａｔｅｌｙｃａｌ ｃｕｌａｔｅｔｈｅｒｅｓｐｏｎｓｅｔｉｍｅｂｏｕｎｄｓｏｆｃｏｎ－ＤＡＧｔａｓｋｓ，ｂｕｔａｌｓｏｈａｓｐｏｌｙｎｏｍｉａｌｔｉｍｅｃｏｍｐｌｅｘｉｔｙ．Ｔｈｉ ｓｗｏｒｋｗａｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉ ｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（Ｎｏ．６１９７２０７６） ，ｗｈｉｃｈａｉｍｓｔｏａｎａｌｙｚｅｔｈｅｔｈｅｏｒｙ， ｍｏｄｅｌｓ，ａｌｇｏｒｉｔｈｍｓ，ａｎｄａｐｐｌ ｉｃａｔｉｏｎｓｏｆｒｅａｌ－ｔｉｍｅｓｃｈｅｄｕｌｉｎｇｆｏｒＯｐｅｎＭＰｔａｓｋｇｒａｐｈ．Ｏｕｒｒｅｓｅａｒｃｈｇｒｏｕｐｈａｓｂｅｅｎｗｏｒｋｉ ｎｇｏｎｒｅａｌ－ｔｉｍｅｅｍｂｅｄｄｅｄｓｙｓｔｅｍｓ＊ｍｕｌｔｉ－ｃｏｒｅｒｅａｌ－ｔｉｍｅｓｃｈｅｄｕｌｉ ｎｇ，ｎｅｔｗｏｒｋｏｐｔｉｍｉｚａｔｉｏｎ，ａｎｄｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ．Ｒｅｌａｔｅｄｗｏｒｋｓｈａｖｅｂｅｅｎｐｕｂｌｉｓｈｅｄｉｎｒｅｐｕｔａｂｌｅ ｊｏｕｒｎａｌ ｓａｎｄｃｏｎｆｅｒｅｎｃｅｓ，ｓｕｃｈａｓＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒｓ，ＩＥＥＥＴｒａｎｓｏｎＣｏｍｐｕｔｅｒｓ，ＩＥＥＥＴｒａｎｓｏｎＣＡＤ，ＡＣＭＴｒａｎｓｏｎＥＣＳ， ＲＴＳＳ， ＤＡＣ，ＲＴＡＳ，ＥＭＳＯＦＴ，ＤＡＴＥ，ｅｔｃ． |
| [返回] |
下一篇：一种基于领域适配的跨项目软件缺陷预测方法