A Scheduling Algorithm for Fork-Join DAG in Bus-based and Heterogeneous Environment

DOI

10.2991/iccasm.2012.178How to use a DOI?

Keywords

Task scheduling, Task duplication, Heterogeneous, Bus-based, Fork-join task graph

Abstract

The Fork-Join task graph is one of the basic modeling structures for parallel processing. However, many previous scheduling algorithms ignore to economize processors and minimize the total completion time. What’s more, many algorithms don’t consider the competition caused by bus-based clusters and the heterogeneous of processors in real applications. This paper presents a new algorithm for Fork- Join task graph, considering economy of processors and minimization of the total completion time, the non-parallel communication, and heterogeneous environment as well. We propose a task scheduling algorithm based on task duplication which randomly generated a number of Fork-Join task graphs by producing the task execution time and communication time. Simulation results show that the proposed algorithm has less total completion time and less number of processors than other compared algorithms for more practical applications.

Copyright

© 2012, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Lisheng Wang
AU  - Liguo Chen
AU  - Kete Wang
PY  - 2012/08
DA  - 2012/08
TI  - A Scheduling Algorithm for Fork-Join DAG in Bus-based and Heterogeneous Environment
BT  - Proceedings of the 2012 International Conference on Computer Application and System Modeling (ICCASM 2012)
PB  - Atlantis Press
SP  - 702
EP  - 705
SN  - 1951-6851
UR  - https://doi.org/10.2991/iccasm.2012.178
DO  - 10.2991/iccasm.2012.178
ID  - Wang2012/08
ER  -