同构计算环境中一种快速有效的静态任务调度算法

快速有效的调度任务是多处理器计算环境中的一个关键问题. 目前任务调度算法中刻画任务依赖关系最流行的模型是DAG. 在以前的文献中, 提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境). 延伸了TTIG模型, 并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2). GBHA以组的形式尽量消除图中回路，因而能获得任务图的全局信息，具有更好的调度性能. 在模拟实验中，将此算法与MATE和其他同构环境中基于DAG的有效调度算法，在不同测试条件下进行了比较，结果显示GBHA在性能上明显优于MATE，与基于DAG模型的调度算法比较而言，在性能方面各有千秋，但在算法时间复杂度方面具有显著的优势.

A Fast and Effective Static Task Scheduling Algorithm in Homogeneous Computing Environments

Efficient scheduling of tasks is a key issue for achieving high performance in multiprocessor systems. At present the most popular model characterizing dependencies between tasks is DAG (directed acyclic graph) . In previous reference, a novel model called TTIG (temporal task in interaction graph) that is more realistic and universal than DAG, and its corresponding algorithm called MATE (mapping algorithm based on task dependencies) were presented. This paper extends TTIG model, and proposes a new static scheduling algorithm called GBHA (group-based hybrid algorithm) and two heuristic methods. GBHA tries to collect the tasks that interact with each other into a group so that it can capture global information about almost all dependence relationship between tasks in task graph. Moreover, GBHA ranks the tasks based on groups from bottom to top in graph, and maps the tasks onto processors according to their earliest finish time or earliest start time on each processor. In this work, the algorithms are compared with MATE and some well-known scheduling algorithms based on DAG in homogeneous systems, such as FCP. The results of simulation experiment and analyses of time complexity show that scheduling performance of our algorithms not only outperforms MATE significantly but also can be comparable to efficient scheduling algorithms based on DAG but with much lower time complexity.