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

Task flow scheduling method with throughput constraint and resource thrift

作　　者：周航[1] 王希敏[1] 蔡志明[1] 虢应华 

机构地区：[1]海军工程大学电子工程学院,湖北武汉430033 [2]水声对抗国防科技重点实验室,广东湛江524022

出　　处：《华中科技大学学报（自然科学版）》2015年第9期35-40,共6页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(51009146)

摘　　要：根据实时信号处理应用中嵌入式计算硬件的资源受限特点,提出一种新的适合计算任务流的实时任务调度算法,以满足吞吐率为调度约束条件、以最小化流水线时延为调度目标并兼顾资源节约原则.算法为两层结构,首先采用任务插入策略得到满足吞吐率约束的中间结果;再通过基于任务复制的优化调度,分析了影响调度长度的关键任务并按照所定义的优先级构造关键边的决策树以确定需复制的关键父任务,充分利用了处理器的空闲时间片以减少时延.另外还设计了检测任务复制后出现的冗余处理器的方法.通过随机任务图仿真分析,说明该算法能以较小的处理器使用量获得满足吞吐率约束的调度结果.Aiming to the features of limited space and easily damaged of embedded hardwares in real‐time signal processing systems ,a new real‐time scheduling algorithm for computational pipelines was proposed ,which was a trade‐off between computational latency and resource thrift under throughput constraint .The algorithm had two levels .First ,insertion technique was adopted to generate partial schedule under throughput constraint .Second ,the duplication‐based optimization was used to find out the key task w hich influenced the total makespan and decided the father task to be duplicated by con‐structing a deciding‐tree .The idle time slot was sufficiently utilized in used processors .Moreover ,a method for detecting the redundant processors was also proposed .Experimental results on random di‐rected acyclic graphs （DAGs） show that the proposed algorithm can meet throughput constraint using less number of processors .

关 键 词：并行计算 任务调度 吞吐率 计算流水线 任务复制 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]