An Efficient Parallel Scheduling Algorithm of Dependent Task Graphs
t Optimal scheduling of tasks of a directed acyclic graph (DAG) onto a set of processors is a strong NP-hard problem. Because list scheduling has shown good performance and is less difficult to design, it has been studied and used widely. In this paper we present a new list scheduling scheme to schedule tasks of a DAG onto a homogeneous multi-processors system. The primary objective of this scheme is to minimize schedule length and scheduling time itself. We analyzed three typical list scheduling algorithms-MCP algorithm, ETF algorithm and BDCP algorithm, and find that they all can not guarantee the earliest schedules of the CPNs. In this paper, we propose a better list scheduling algorithm based on critical path, and its time-complexity is O(pv2). This algorithm always it is the most important purpose that schedule CPN as soon as it is a ready task, which makes the nodes that have the greatest influence to the scheduling length of the task graph be scheduled first. This greatly shortens the scheduling length of the task graph. We compare the performance of this algorithm with existing scheduling scheme through analysis and the result of experiments. The scheduling length generated by this algorithm is shorter than that of other scheduling algorithm.
s list scheduling critical path parallel algorithm system
Shang Mingsheng Sun Shixin Wang Qingxian
Department of Computer Science, UESTC, Chengdu 610054
国际会议
成都
英文
595-598
2003-08-27（万方平台首次上网日期，不代表论文的发表时间）