Based On Dynamic Communication Contention List Scheduling Algorithm For Arbitrary Network System

The rapid growth of the technology of computing and network mostly promotes the scientific research and commercial application based on Internet. In many areas, there are more and more higher request for the computing capacity and it is difficult for a single computer to undertake calculation task. When the number of processing units is more than 2,scheduling arbitrary task graph in order to obtain an optimizing solution is a NP-complete problem.As a heuristic scheduling algorithm,list scheduling algorithm has better performance and lower time complexity. But, most heuristics for this NP-hard problem assume fully connected homogeneous processors and ignore contention on the communication links. However, as arbitrary network topology heterogeneous system, communication contention have a strong influence on the execution time of a parallel application.This paper investigates the incorporation of contention awareness into task scheduling. The innovation is the idea of dynamic scheduling edges to links, which we use the earliest communication finish path search algorithm based on shortest-path search algorithm. The other novel idea proposed in this paper is scheduling priority based on recursive rank computation on heterogeneous arbitrary architectures. In the end, to reduce execute time of algorithm, a parallel algorithm use OpenMP is proposed and achieve speedup O(PPE).The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithm significantly surpass classic and static communication contention awareness algorithm, especially for high data transmission rate parallel application.