中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Title:
基于树状线性规划搜索的单调速率优化设计
Alternative Title: Rate-Monotonic Optimal Design Based on Tree-Like Linear Programming Search
Author: 陈力 ; 王永吉 ; 吴敬征 ; 吕荫润
Keyword: 实时系统 ; 单调速率 ; 最优化 ; 搜索算法 ; 线性规划 ; 可满足性模定理
Source: 软件学报
Issued Date: 2015
Volume: 26, Issue:12, Pages:3223-3241
Indexed Type: CSCD
Department: 陈力, 中国科学院软件研究所, 基础软件国家工程研究中心, 北京 100190, 中国;王永吉, 中国科学院软件研究所, 基础软件国家工程研究中心;;计算机科学国家重点实验室, 北京 100190, 中国;吴敬征, 中国科学院软件研究所, 基础软件国家工程研究中心;;计算机科学国家重点实验室, 北京 100190, 中国;吕荫润, 中国科学院软件研究所, 基础软件国家工程研究中心;;计算机科学国家重点实验室, 北京 100190, 中国;
Abstract: 改善单调速率(rate monotonic,简称RM)可调度性判定算法的效率,是过去40年计算机实时系统设计的重要问题.最近,研究人员把可调度性判定问题扩展到了更一般的 优化设计问题,即,如何调节在区间可选择情况下的任务运行时间,使得:(1)系统RM可调度;(2)系统的某个性能(如CPU利用率)达到最优.在已有的 求解实时系统RM优化设计问题的方法中,都是先把原问题建模成广义约束优化问题,然后再对广义约束优化问题进行求解.但现有方法的求解速度较慢,任务数较 多时不再适用.提出一种求解优化问题的方法基于树状的线性规划搜索(linear programming search,简称LPS)方法.该方法先将实时系统RM优化设计问题建模成广义约束优化问题,再将其分拆成若干线性规划子问题,然后构造线性规划搜索树 ,利用剪枝搜索算法求解部分线性规划子问题,最后得到优化解.实验结果表明:LPS方法相比于已有的方法能够节省20%~70%的求解时间,任务数越多, 节省时间越多.该研究成果可以与计算机可满足性模定理(satisfiability modulo theories,简称SMT)领域的多个研究热点问题联系起来,并可望改善SMT问题的求解效率.
English Abstract: Over the last four decades, a critical problem in real-time system is to improve the efficiency of the decision algorithm for the rate-monotonic(RM) scheduling. Nowadays researchers extend the decision problem to a generalized optimal design problem, that is,how to adjust the task execution time in the corresponding interval such that(1) the system is schedulable and(2) certain system performance(e.g. CPU utilization) is optimized. All the existing methods for solving this problem are to formulate the problem as the generalized constrained optimization problem(GCOP). However, these methods run very slowly and cannot be applied to the systems with large numbers of tasks. In this paper, a new method for solving the optimization problem is proposed. The method is called tree-like linear programming search(LPS). First, the problem is transformed into a GCOP. Next, the GCOP is partitioned into several linear programming sub-problems. Then, a linear programming search tree is constructed and the node of linear programming is solved by depth-first-search as the optimal solution. The experimental results illustrate that the new method can save 20%~70% of runtime comparing with other existing methods. This work also relates to the research areas of satisfiability modulo theories(SMT), and is expected to improve the efficiency for solving SMT problems.
Language: 中文
Citation statistics:
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/17392
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:
File Name/ File Size Content Type Version Access License
基于树状线性规划搜索的单调速率优化设计.pdf(1553KB)----限制开放 联系获取全文

Recommended Citation:
陈力,王永吉,吴敬征,等. 基于树状线性规划搜索的单调速率优化设计[J]. 软件学报,2015-01-01,26(12):3223-3241.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[陈力]'s Articles
[王永吉]'s Articles
[吴敬征]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[陈力]‘s Articles
[王永吉]‘s Articles
[吴敬征]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace