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

发布时间：2018-12-24 08:55

【摘要】：改善单调速率(rate monotonic,简称RM)可调度性判定算法的效率,是过去40年计算机实时系统设计的重要问题.最近,研究人员把可调度性判定问题扩展到了更一般的优化设计问题,即,如何调节在区间可选择情况下的任务运行时间,使得:(1)系统RM可调度;(2)系统的某个性能(如CPU利用率)达到最优.在已有的求解实时系统RM优化设计问题的方法中,都是先把原问题建模成广义约束优化问题,然后再对广义约束优化问题进行求解.但现有方法的求解速度较慢,任务数较多时不再适用.提出一种求解优化问题的方法——基于树状的线性规划搜索(linear programming search,简称LPS)方法.该方法先将实时系统RM优化设计问题建模成广义约束优化问题,再将其分拆成若干线性规划子问题,然后构造线性规划搜索树,利用剪枝搜索算法求解部分线性规划子问题,最后得到优化解.实验结果表明:LPS方法相比于已有的方法能够节省20%~70%的求解时间,任务数越多,节省时间越多.该研究成果可以与计算机可满足性模定理(satisfiability modulo theories,简称SMT)领域的多个研究热点问题联系起来,并可望改善SMT问题的求解效率.
[Abstract]:Improving the efficiency of monotone rate (rate monotonic, (RM) schedulability decision algorithm is an important problem in the design of computer real-time system in the past 40 years. Recently, researchers extended the schedulability decision problem to the more general optimization design problem, that is, how to adjust the task running time under the condition of interval selection, which makes: (1) system RM schedulable; (2) the performance of the system (such as CPU utilization) is optimized. In the existing methods for solving the RM optimization design problem of real-time systems, the original problem is modeled as a generalized constrained optimization problem, and then the generalized constrained optimization problem is solved. However, the existing methods are slow to solve the problem and are no longer applicable when the number of tasks is more. In this paper, a method for solving optimization problems is presented, which is based on a tree-like linear programming search method called (linear programming search, (LPS). In this method, the RM optimization design problem of real-time system is modeled as a generalized constrained optimization problem, then it is divided into several linear programming subproblems, and then the linear programming search tree is constructed, and the pruning search algorithm is used to solve the partial linear programming subproblem. Finally, the optimal solution is obtained. The experimental results show that the LPS method can save 20% 70% of the solving time compared with the existing methods, the more tasks, the more time is saved. The research results can be related to many hot problems in the field of computer satisfiability modulus theorem (satisfiability modulo theories, (SMT), and it is expected to improve the efficiency of solving SMT problem.
【作者单位】：中国科学院软件研究所基础软件国家工程研究中心;中国科学院大学;计算机科学国家重点实验室(中国科学院软件研究所);中国科学院软件研究所互联网软件技术实验室;
【基金】：国家自然科学基金(61170072) 国家青年科学基金(61303057) 中国科学院、国家外国专家局创新团队国际合作伙伴计划~~
【分类号】：TP301.6;TP302

【参考文献】