同构环境中基于通信竞争的任务调度算法  

Novel Contention-aware Task Scheduling Algorithm in Homogeneous System

作　　者：韩建军[1] 阮幼林[2] 李庆华[1] 缪天鹏[1] Abbas A.Essa 

机构地区：[1]华中科技大学计算机科学与技术学院 [2]武汉理工大学信息学院 [3]南京大学电子工程与科学系,江苏南京210093

出　　处：《小型微型计算机系统》2007年第4期678-682,共5页Journal of Chinese Computer Systems

基　　金：基于网格环境的实时应用中任务调度算法及机制的研究(60503048)资助.

摘　　要：基于DAG的静态任务调度算法已有深入的研究及应用.目前的调度算法大多假定处理器之间可以并行接收数据,而没有考虑实际应用中通信链路的竞争及延迟,进而导致调度算法在具体应用中效率较低.侧重研究同构计算环境下具有依赖关系任务的边调度问题,结合传统任务调度问题中的有效策略,提出基于优化插入的调度算法(OISA).OISA根据实际问题的具体特征,采用改进的路由算法选择负载较少的数据链路,并通过形式化的证明以优化通信数据在链路的开始传输时间,以达到降低调度长度的目的.通过试验测试表明,OISA在性能上明显优于目前已有的相关算法.Many research works has been done in the domain of static scheduling algorithms based on DAG. However, most of these work assumes that each processor can receive communication data concurrently, while ignoring the contention and delay on data links in real applications, which leads to low efficiency. This paper focuses on the issue of edge scheduling for dependent tasks in homogeneous environment. Combined with classically efficient heuristics, the proposed algorithm, OISA （Optimal Insertion Scheduling Algorithm）, starts from the basic characteristic of the problem, selects route paths with relatively low load to transfer data by modified routing algorithm, and optimizes the start time of communication data transferred on links in form of theorems. Thus, the schedule length of our algorithm is reduced efficiently. The experiment result indicates that the proposed algorithm obviously outperforms other algorithms so far.

关 键 词：同构计算环境 调度算法 通信竞争 边调度 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]