满足吞吐约束与资源节约的任务流调度方法

发布时间：2019-05-29 20:41

【摘要】：根据实时信号处理应用中嵌入式计算硬件的资源受限特点,提出一种新的适合计算任务流的实时任务调度算法,以满足吞吐率为调度约束条件、以最小化流水线时延为调度目标并兼顾资源节约原则.算法为两层结构,首先采用任务插入策略得到满足吞吐率约束的中间结果;再通过基于任务复制的优化调度,分析了影响调度长度的关键任务并按照所定义的优先级构造关键边的决策树以确定需复制的关键父任务,充分利用了处理器的空闲时间片以减少时延.另外还设计了检测任务复制后出现的冗余处理器的方法.通过随机任务图仿真分析,说明该算法能以较小的处理器使用量获得满足吞吐率约束的调度结果.
[Abstract]:According to the resource constraints of embedded computing hardware in real-time signal processing applications, a new real-time task scheduling algorithm suitable for computing task flow is proposed, which satisfies the throughput as the scheduling constraint. The scheduling goal is to minimize pipeline delay and the principle of resource saving is taken into account. The algorithm is a two-tier structure. Firstly, the task insertion strategy is used to obtain the intermediate results that meet the throughput constraints. Then through the optimal scheduling based on task replication, the key tasks that affect the scheduling length are analyzed, and the decision tree of the key edge is constructed according to the defined priority to determine the key parent task to be replicated. The idle time slice of the processor is fully utilized to reduce the delay. In addition, a method to detect redundant processors after task replication is designed. Through the simulation analysis of random task diagram, it is shown that the algorithm can obtain the scheduling results which meet the throughput constraints with a small processor usage.
【作者单位】： 海军工程大学电子工程学院;水声对抗国防科技重点实验室;
【基金】：国家自然科学基金资助项目(51009146)
【分类号】：TP332

【参考文献】

相关期刊论文 前4条

1 叶朝谋;丁建江;俞志强;蔡轶;;基于周期分区的相控阵雷达任务交叉调度研究[J];电子与信息学报;2014年02期

2 任磊;王永良;陈辉;陈建文;;STAP并行处理系统的调度问题研究[J];系统工程与电子技术;2009年04期

3 艾锐峰;蔡志明;王希敏;陈宝柱;;声纳并行处理系统的设计方法与调度策略[J];系统工程与电子技术;2011年08期

4 尤涛;杨凯;杜承烈;钟冬;朱怡安;;基于动态关键路径与边消除的任务复制分配算法[J];西北工业大学学报;2013年06期

【共引文献】

相关期刊论文 前10条

1 王超;刘伟;袁培苑;;基于细粒度任务分配的空时自适应并行处理算法研究[J];电子与信息学报;2012年06期

2 任磊;陈风波;吴永刚;程晓涛;;异构STAP系统的多层次数据通信研究[J];空军预警学院学报;2013年01期

3 ZHAI GuoWei;TIAN Lin;ZHOU YiQing;SHI JingLin;;Load diversity based optimal processing resource allocation for super base stations in centralized radio access networks[J];Science China(Information Sciences);2014年04期

4 田国忠;肖创柏;谢军奇;;有期限约束的多DAG共享资源的调度及公平费用优化方法[J];计算机学报;2014年07期

5 朱荣;袁朝晖;曹义亲;;面向系统级能耗优化的无线实时网络系统任务调度机制[J];华东交通大学学报;2014年06期

6 石伟;张明;郭御风;龚锐;;实时微处理器体系结构综述[J];计算机工程与科学;2015年05期

7 彭浩;韩江洪;陆阳;张建军;;多处理器硬实时系统的抢占阈值调度研究[J];计算机研究与发展;2015年05期

8 代声馨;洪玫;郭兵;杨秋辉;黄蔚;徐保平;;多处理器实时系统可调度性分析的UPPAAL模型[J];软件学报;2015年02期

9 邓钰;陈辉;何雅晶;王婧;;多通道STAP并行处理系统设计与实现[J];微计算机信息;2010年35期

10 艾锐峰;蔡志明;王希敏;陈宝柱;;声纳并行处理系统的设计方法与调度策略[J];系统工程与电子技术;2011年08期

相关博士学位论文 前5条

1 敬思远;面向绿色虚拟数据中心资源管理的若干关键技术研究[D];电子科技大学;2013年

2 任慰;以实时操作系统为中心的嵌入式系统平台化设计研究[D];华中科技大学;2013年

3 田国忠;多DAG共享资源调度的若干问题研究[D];北京工业大学;2013年

4 周正勇;实时系统的容错调度技术研究[D];华中科技大学;2014年

5 盖文妹;含硫气田井喷事故公共报警理论及系统开发的研究[D];北京科技大学;2015年

相关硕士学位论文 前4条

1 沈案;异构分布式系统中基于DVS的节能调度算法研究与实现[D];湖南大学;2013年

2 崔浩鑫;基于实时操作系统的任务调度算法研究及硬件实现[D];哈尔滨理工大学;2015年

3 李莹;基于任务分裂的多核平台实时任务调度研究[D];大连理工大学;2014年

4 权彦清;基于BWDSP104X系统的嵌入式操作系统内存管理和上下文切换的实时性研究[D];中国科学技术大学;2015年

【二级参考文献】

相关期刊论文 前10条

1 王希敏;蔡志明;;水声信息系统仿真软件构架模型[J];兵工学报;2007年04期

2 保铮,廖桂生,吴仁彪,张玉洪,王永良;相控阵机载雷达杂波抑制的时-空二维自适应滤波[J];电子学报;1993年09期

3 邵银波;王永良;李强;陈辉;肖奚安;;一种用于空时自适应处理的并行计算模型[J];电子学报;2006年03期

4 张云泉,孙家昶,迟学斌,唐志敏;数值计算程序的存储复杂性分析[J];计算机学报;2000年04期

5 邱卫东,陈燕,李洁萍,彭澄廉;一种实时异构嵌入式系统的任务调度算法[J];软件学报;2004年04期

6 蔡志明;王希敏;;软件声纳的概念与趋势[J];声学技术;2007年05期

7 ;Novel radar dwell scheduling algorithm based on pulse interleaving[J];Journal of Systems Engineering and Electronics;2009年02期

8 许勇,王秀坛,彭应宁,汤俊;一种适于软件雷达系统数据结构的设计和实现[J];系统工程与电子技术;2001年02期

9 周颖;王国玉;王雪松;肖顺平;;基于启发式混合遗传算法的相控阵雷达最优化调度[J];系统工程与电子技术;2006年07期

10 任磊;王永良;陈辉;陈建文;;STAP并行处理系统的调度问题研究[J];系统工程与电子技术;2009年04期

相关博士学位论文 前2条

1 卢建斌;相控阵雷达资源优化管理的理论与方法[D];国防科学技术大学;2007年

2 张爱清;可扩展数据驱动并行算法研究及应用[D];中国工程物理研究院;2009年

，

本文编号：2488212