期刊
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
卷 31, 期 11, 页码 -出版社
WILEY
DOI: 10.1002/cpe.5060
关键词
clustering; DAG scheduling; multiprocessors; task graphs
In multiprocessor environments, the scheduling algorithms play a significant role in maximizing system performance. In this paper, we propose a clustering-based task scheduling algorithm called Edge Priority Scheduling (EPS) for multiprocessor environments. The proposed algorithm extends the idea of edge zeroing heuristic and uses the concept of edge priority to minimize the makespan of the task graph. The complexity of the EPS algorithm is O(|V||E|(|V| + |E|)), where |E| represents the number of edges and |V| denotes the number of nodes in the task graph. The experiments are performed for random task graphs and the task graphs generated from some representative real-world applications such as Gaussian Elimination and Fast Fourier Transform. The performance of the EPS algorithm is compared with six well-known algorithms such as EZ (Edge Zeroing), LC (Linear Clustering), CPPS (Cluster Pair Priority Scheduling), DCCL (Dynamic Computation Communication Load), RDCC (Randomized Dynamic Computation Communication), and LOCAL. The results show that the EPS algorithm outperforms the compared algorithms in terms of the normalized schedule length and speedup.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据