EZDCP:A new static task scheduling algorithm with edge-zeroing based on dynamic critical paths

来源期刊：中南大学学报(英文版)2003年第2期

论文作者：陈志刚 华强胜

文章页码：140 - 144

Key words：EZDCP; directed acyclic graph; dynamic critical path; task scheduling algorithm

Abstract:

A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.