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.