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.