Dynamic Task Flow Scheduling for Heterogeneous Distributed Computing: Algorithm and Strategy

Wei SUN; Yuanyuan ZHANG; Yasushi INOGUCHI

doi:10.1093/ietisy/e90-d.4.736

Dynamic Task Flow Scheduling for Heterogeneous Distributed Computing: Algorithm and Strategy

Wei SUN, Yuanyuan ZHANG, Yasushi INOGUCHI

Full Text Views

0

Share
Cite this

Summary :

Heterogeneous distributed computing environments are well suited to meet the fast increasing computational demands. Task scheduling is very important for a heterogeneous distributed system to satisfy the large computational demands of applications. The performance of a scheduler in a heterogeneous distributed system normally has something to do with the dynamic task flow, that is, the scheduler always suffers from the heterogeneity of task sizes and the variety of task arrivals. From the long-term viewpoint it is necessary and possible to improve the performance of the scheduler serving the dynamic task flow. In this paper we propose a task scheduling method including a scheduling strategy which adapts to the dynamic task flow and a genetic algorithm which can achieve the short completion time of a batch of tasks. The strategy and the genetic algorithm work with each other to enhance the scheduler's efficiency and performance. We simulated a task flow with enough tasks, the scheduler with our strategy and algorithm, and the schedulers with other strategies and algorithms. We also simulated a complex scenario including the variant arrival rate of tasks and the heterogeneous computational nodes. The simulation results show that our scheduler achieves much better scheduling results than the others, in terms of the average waiting time, the average response time, and the finish time of all tasks.

Publication: IEICE TRANSACTIONS on Information Vol.E90-D No.4 pp.736-744

Publication Date: 2007/04/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e90-d.4.736

Type of Manuscript: PAPER

Category: Computer Systems

Cite this

Copy

Wei SUN, Yuanyuan ZHANG, Yasushi INOGUCHI, "Dynamic Task Flow Scheduling for Heterogeneous Distributed Computing: Algorithm and Strategy" in IEICE TRANSACTIONS on Information, vol. E90-D, no. 4, pp. 736-744, April 2007, doi: 10.1093/ietisy/e90-d.4.736.
Abstract: Heterogeneous distributed computing environments are well suited to meet the fast increasing computational demands. Task scheduling is very important for a heterogeneous distributed system to satisfy the large computational demands of applications. The performance of a scheduler in a heterogeneous distributed system normally has something to do with the dynamic task flow, that is, the scheduler always suffers from the heterogeneity of task sizes and the variety of task arrivals. From the long-term viewpoint it is necessary and possible to improve the performance of the scheduler serving the dynamic task flow. In this paper we propose a task scheduling method including a scheduling strategy which adapts to the dynamic task flow and a genetic algorithm which can achieve the short completion time of a batch of tasks. The strategy and the genetic algorithm work with each other to enhance the scheduler's efficiency and performance. We simulated a task flow with enough tasks, the scheduler with our strategy and algorithm, and the schedulers with other strategies and algorithms. We also simulated a complex scenario including the variant arrival rate of tasks and the heterogeneous computational nodes. The simulation results show that our scheduler achieves much better scheduling results than the others, in terms of the average waiting time, the average response time, and the finish time of all tasks.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.4.736/_p

Copy

@ARTICLE{e90-d_4_736,
author={Wei SUN, Yuanyuan ZHANG, Yasushi INOGUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Dynamic Task Flow Scheduling for Heterogeneous Distributed Computing: Algorithm and Strategy},
year={2007},
volume={E90-D},
number={4},
pages={736-744},
abstract={Heterogeneous distributed computing environments are well suited to meet the fast increasing computational demands. Task scheduling is very important for a heterogeneous distributed system to satisfy the large computational demands of applications. The performance of a scheduler in a heterogeneous distributed system normally has something to do with the dynamic task flow, that is, the scheduler always suffers from the heterogeneity of task sizes and the variety of task arrivals. From the long-term viewpoint it is necessary and possible to improve the performance of the scheduler serving the dynamic task flow. In this paper we propose a task scheduling method including a scheduling strategy which adapts to the dynamic task flow and a genetic algorithm which can achieve the short completion time of a batch of tasks. The strategy and the genetic algorithm work with each other to enhance the scheduler's efficiency and performance. We simulated a task flow with enough tasks, the scheduler with our strategy and algorithm, and the schedulers with other strategies and algorithms. We also simulated a complex scenario including the variant arrival rate of tasks and the heterogeneous computational nodes. The simulation results show that our scheduler achieves much better scheduling results than the others, in terms of the average waiting time, the average response time, and the finish time of all tasks.},
keywords={},
doi={10.1093/ietisy/e90-d.4.736},
ISSN={1745-1361},
month={April},}

Copy

TY - JOUR
TI - Dynamic Task Flow Scheduling for Heterogeneous Distributed Computing: Algorithm and Strategy
T2 - IEICE TRANSACTIONS on Information
SP - 736
EP - 744
AU - Wei SUN
AU - Yuanyuan ZHANG
AU - Yasushi INOGUCHI
PY - 2007
DO - 10.1093/ietisy/e90-d.4.736
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2007
AB - Heterogeneous distributed computing environments are well suited to meet the fast increasing computational demands. Task scheduling is very important for a heterogeneous distributed system to satisfy the large computational demands of applications. The performance of a scheduler in a heterogeneous distributed system normally has something to do with the dynamic task flow, that is, the scheduler always suffers from the heterogeneity of task sizes and the variety of task arrivals. From the long-term viewpoint it is necessary and possible to improve the performance of the scheduler serving the dynamic task flow. In this paper we propose a task scheduling method including a scheduling strategy which adapts to the dynamic task flow and a genetic algorithm which can achieve the short completion time of a batch of tasks. The strategy and the genetic algorithm work with each other to enhance the scheduler's efficiency and performance. We simulated a task flow with enough tasks, the scheduler with our strategy and algorithm, and the schedulers with other strategies and algorithms. We also simulated a complex scenario including the variant arrival rate of tasks and the heterogeneous computational nodes. The simulation results show that our scheduler achieves much better scheduling results than the others, in terms of the average waiting time, the average response time, and the finish time of all tasks.
ER -