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

基于DAG的静态任务调度算法已有深入的研究及应用.目前的调度算法大多假定处理器之间可以并行接收数据,而没有考虑实际应用中通信链路的竞争及延迟,进而导致调度算法在具体应用中效率较低.侧重研究同构计算环境下具有依赖关系任务的边调度问题,结合传统任务调度问题中的有效策略,提出基于优化插入的调度算法(OISA).OISA根据实际问题的具体特征,采用改进的路由算法选择负载较少的数据链路,并通过形式化的证明以优化通信数据在链路的开始传输时间,以达到降低调度长度的目的.通过试验测试表明,OISA在性能上明显优于目前已有的相关算法.

Novel Contention-aware Task Scheduling Algorithm in Homogeneous System

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.