摘要
现代并行系统的复杂调度问题可以转化为Fork-join图的任务调度问题。然而在实际计算环境中,两个处理节点之间的通信大多以独占方式进行,现有的大多数任务调度算法往往忽略了对通信信道独占性的考虑。提出了一种带通信限制的Fork-join图调度算法CCTD。该算法引入了实际环境中的通信独占性限制,同时保证了Fork-join图的基于复制的优化调度,而且尽可能地减少了对处理器占用。实验结果表明,CCTD算法是一种适应性强的、高效的Fork-join图调度算法。
All the complicated scheduling problems in modern parallel systems can be converted to the basic scheduling problem for Fork-Join task graphs. However, the communication between two processing nodes is carried on exclusively in real computation environment,which are normally ignored by most task scheduling algorithms. This paper presentsed a scheduling algorithm under communication constraints for Fork-Join task graphs. The algorithm provided a duplication based approach to schedule Fork-Join task graph while introducing the constraints of exclusive communications in reality. The number of processing nodes was also minimized compared to other scheduling algorithms. The experimental results show that CCTD is an efficient Fork-Join task graph scheduling algorithm, and fit for a broad range of scheduling problems.
出处
《计算机科学》
CSCD
北大核心
2009年第6期282-285,共4页
Computer Science
关键词
任务调度
任务复制
fork-join
通信限制
Task scheduling, Task duplication, Fork-join task graph, Communication constraint
