One of the main issues in distributed computing systems is to determine an optimal task-scheduling method. In this paper, we present an effective algorithm to schedule a directed acyclic graph onto a heterogeneous distributed system, called the Earliest Starting and Finishing time Duplication based (ESFD) algorithm. Our proposed algorithm considers all parameters associated with the processors, the task, and its immediate predecessors to perform an effective task allocation. The ESFD algorithm is a three-phase algorithm with a dynamic phase to assign a priority to each task. Simulation results on both random graphs and real application graphs show that the network storage link, speedup, and efficiency generated by ESFD algorithm are better than those generated by the well-known Heterogeneous Critical Parent Trees, Heterogeneous Earliest Finish Time, and Levelized Heavily Communicating Node First algorithms.
HagrasTJanecekJ. A static task scheduling heuristic for homogeneous computing environments. In: Proceedings of the 12th Euromicro Conference on Parallel Distributed and Network-Based Processing, 2004, pp. 192–198.
2.
DutotPFN’takpéTSuterFCasanovaH. Scheduling parallel task graphs on (almost) homogeneous multi-cluster platforms. IEEE Trans Parallel and Distrib Syst2009; 20: 940–952.
3.
BenoitACasanovaHRhen-SonigoVRobertY. Resource allocation strategies for constructive in-network stream processing. In: Proceedings of the 10th Workshop on Advances on Parallel and Distributed Processing Symposium (APDCM), 2009.
4.
StavrinidesGLKaratzaHD. Scheduling multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing imprecise computations. J Syst Software2010; 83: 1004–1014.
5.
HosseinzadehMShahhoseiniHS. Earliest starting and finishing time duplication-based algorithm. In: Proceedings of the 2009 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS’09), Istanbul, Turkey, 2009, pp. 47–53.
6.
HargrasTJanecekJ. A near lower-bound complexity algorithm for compile-time task-scheduling in heterogeneous computing systems. In: Proceedings of the 3rd International Symposium on Models and Tools for Parallel Computing on Heterogeneous Networks, 2004, pp. 106–113.
7.
ShiZJeannotEDongarraJJ. Robust task scheduling in non-deterministic heterogeneous computing systems. In: Proceedings of the IEEE International Conference on Cluster Computing, 2006, pp. 25–28.
8.
QinXXieT. An availability-aware task scheduling strategy for heterogeneous systems. IEEE Trans Parallel Distrib Syst2008; 57: 188–199.
9.
ChuangPWeiC. An efficient optimization technique for task matching and scheduling in heterogeneous computing systems. In: Proceedings of the International Conference on Parallel and Distributed Systems, 2002, pp. 419–424.
10.
SinnenOSousaLASandnesFE. Toward a realistic task scheduling model. IEEE Trans Parallel Distrib Syst2006; 17: 263–275.
11.
BoeresCRiosEOchiL. Hybrid evolutionary static scheduling for heterogeneous systems. IEEE Trans Evol Comput2005; 3: 1929–1936.
12.
ChenYWangLHuangS. A novel task scheduling algorithm for real-time multiprocessor systems. In: Proceedings of the IEEE International Conference on Control and Automation (ICCA), 2007, pp. 271–275.
13.
FingFLiK. An improved task scheduling algorithm for heterogeneous systems. In: Proceedings of the International Joint Conference on Computational Sciences and Optimization (CSO), 2009, pp. 90–94.
14.
AgarwalAKumarP. Heterogeneity-aware task scheduling using critical path in grid environment. In: Proceedings of the International Conference on Signal Processing Systems, 2009, pp. 479–483.
15.
ParhamiB. Introduction to parallel processing. London: Kluwer Academic, 2002, pp. 347–367.
16.
BajajRArawalDP. Improving scheduling of tasks in a heterogeneous environment. IEEE Trans Parallel Distrib Syst2004; 15: 107–118.
17.
TsuchiyaTOsadaTKikunoT. A new heuristic algorithm based on GAs for multiprocessor scheduling with task duplication. In: Proceedings of the 3rd International Conference on Algorithms and Architectures for Parallel Processing (ICAPP), 1997, pp. 295–308.
18.
AuluckN. Duplication based integrated task and message scheduling on a heterogeneous network of workstations. In: Proceedings of the 10th IEEE high Assurance Systems Engineering Symposium (HASE’07), 2007, pp. 429–430.
19.
YeYDuZHaoS. Optimizing message passing programs based on task section duplication. In: Proceedings of the IEEE International Symposium on Parallel and Distributed Processing with Applications, 2009, pp. 673–678.
20.
LotfifarFShahhoseiniHS. A low complexity task scheduling algorithm for heterogeneous computing systems. In: Proceedings of the 3rd Asia International Conference on Modelling and Simulation (AMS ’09), 2009, pp. 596–601.
21.
AgarwalAKumarP. Economical duplication based task scheduling for heterogeneous and homogeneous computing systems. In: Proceedings of the IEEE International Conference on Advance Computing Conference (IACC), 2009, pp. 87–93.
22.
ChoeTParkC. A task duplication based scheduling algorithm with optimality condition in heterogeneous systems. In: Proceedings of the International Conference on Parallel Processing Workshops (ICPPW), 2002, pp. 531–536.
23.
ShenLChoeTY. Posterior task scheduling algorithms for heterogeneous computing systems. In: Proceedings of the 7th International Conference on High Performance Computing for Computational Science (VECPAR’06), Springer, vol. 4395, 2007, pp. 172–183.
24.
BaskiyarSDickinsonC. Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication. J Parallel Distrib Comput2005; 65: 911–921.
25.
TopcuogluHHaririSWuMY. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst2002; 13: 260–274.
26.
HagrasTJanecekJ. A simple scheduling heuristic for heterogeneous computing environments. In: Proceedings of the 2nd International Conference on Parallel and Distributed Computing (ISPDC’03), 2003, pp. 104–110.
27.
IlavarasanEThambiduraiP. Levelized scheduling of directed A-cyclic precedence constrained task graphs onto heterogeneous computing system. In: Proceedings of the 1st IEEE International Conference on Distributed Frameworks of Multimedia Applications (DFMA ’05), 2005, pp. 262–269.
28.
LiuChHLiChFLaiKChWuChCh. A dynamic critical path duplication task scheduling algorithm for distributed heterogeneous computing systems. In: Proceedings of the 12th International Conference on Parallel and Distributed Systems (ICPADS ’06), vol. 1, 2006, pp. 365–374.
29.
RadulescuAGemundAJ. Fast and effective task scheduling in heterogeneous systems. In: Proceedings of the 9th Heterogeneous Computing Workshop (HCW ’00), 2000, p.29.
