基于树状线性规划搜索的单调速率优化设计

• 作者: 吕荫润 吴敬征 王永吉 陈力
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 实时系统 单调速率 最优化 搜索算法 线性规划 可满足性模定理
• 年，卷（期）: 2015,（12）
• 所属期刊栏目: 操纵系统
• 页码范围: 3223-3241
• 页数: 19页
• 分类号: TP316
• 字数: 13464字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004853

摘要

改善单调速率(rate monotonic,称RM)可调度性判定算法的效率,是过去40年计算机实时系统设计的重要问题.最近,研究人员把可调度性判定问题扩展到了更一般的优化设计问题,即,如何调节在区间可选择情况下的任务运行时间,使得:(1)系统RM可调度;(2)系统的某个性能(如CPU利用率)达到最优.在已有的求解实时系统RM优化设计问题的方法中,都是先把原问题建模成广义约束优化问题,然后再对广义约束优化问题进行求解.但现有方法的求解速度较慢,任务数较多时不再适用.提出一种求解优化问题的方法一一基于树状的线性规划搜索(linear programming search,简称LPS)方法.该方法先将实时系统RM优化设计问题建模成广义约束优化问题,再将其分拆成若干线性规划子问题,然后构造线性规划搜索树,利用剪枝搜索算法求解部分线性规划子问题,最后得到优化解.实验结果表明:LPS方法相比于已有的方法能够节省20％～70％的求解时间,任务数越多,节省时间越多.该研究成果可以与计算机可满足性模定理(satisfiability modulo theories,简称SMT)领域的多个研究热点问题联系起来,并可望改善SMT问题的求解效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈力	中国科学院软件研究所基础软件国家工程研究中心	45	868	15.0	29.0