带时间约束实时任务图模型上可调度性分析算法研究

作者：孙景昊; 关楠; 邓庆绪

来源：计算机学报, 2015, 1-13.

• 时间约束
• 实时任务图
• 可调度性分析
• 需求上界函数
• 动态规划

带时间约束的实时任务图(TCDRT)模型具有接近于时间自动机的丰富表达性,但是其关联的可调度性分析(SA)问题却是强NP困难的.目前的研究仅关注一类约束个数为常数K的易解模型:K-TCDRT,且局限于SA问题的图转换求解方法.这种间接求法使得问题的计算复杂度随约束宽度指数倍增长.本文研究TCDRT模型上可调度性分析问题的直接求解方法,为两个核心子问题给出新的理论结果.第一,针对需求上界函数(DBF)的计算问题,提出了考虑时间约束的路径需求结构,并据此设计了新的动态规划算法,其时间复杂度与约束宽度无关.第二,对于可调度分析上界T的限定问题,从理论上证明了该问题是伪多项式时间可解的,且计算复杂度不再与K指数相关,这使得本文算法性能较已有结果有指数级提升.更进一步地,本文方法还蕴含着一类新的TCDRT易解模型.该类模型突破了约束个数必须为常数的局限,其分析难度也较K-TCDRT有指数倍地下降.

• 出版日期2015-7-22
• 单位东北大学