Influence of Inaccurate Performance Prediction on Task Scheduling in a Grid Environment

Yuanyuan ZHANG; Yasushi INOGUCHI

doi:10.1093/ietisy/e89-d.2.479

Influence of Inaccurate Performance Prediction on Task Scheduling in a Grid Environment

Yuanyuan ZHANG, Yasushi INOGUCHI

Full Text Views

0

Cite this

Summary :

Efficient task scheduling is critical for achieving high performance in grid computing systems. Existing task scheduling algorithms for grid environments usually assume that the performance prediction for both tasks and resources is perfectly accurate. In practice, however, it is very difficult to achieve such an accurate prediction in a heterogeneous and dynamic grid environment. Therefore, the performance of a task scheduling algorithm may be significantly influenced by prediction inaccuracy. In this paper, we study the influence of inaccurate predictions on task scheduling in the contexts of task selection and processor selection, which are two critical phases in task scheduling algorithms. We develop formulas for the misprediction degree, which is defined as the probability that the predicted values for the performances of tasks and processors reveal different orders from their real values. Based on these formulas, we also investigate the effect of several key parameters on the misprediction degree. Finally, we conduct extensive simulation for the sensitivities of some existing task scheduling algorithms to the prediction errors.

Publication: IEICE TRANSACTIONS on Information Vol.E89-D No.2 pp.479-486

Publication Date: 2006/02/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e89-d.2.479

Type of Manuscript: Special Section PAPER (Special Section on Parallel/Distributed Computing and Networking)

Category: Performance Evaluation

Cite this

Copy

Yuanyuan ZHANG, Yasushi INOGUCHI, "Influence of Inaccurate Performance Prediction on Task Scheduling in a Grid Environment" in IEICE TRANSACTIONS on Information, vol. E89-D, no. 2, pp. 479-486, February 2006, doi: 10.1093/ietisy/e89-d.2.479.
Abstract: Efficient task scheduling is critical for achieving high performance in grid computing systems. Existing task scheduling algorithms for grid environments usually assume that the performance prediction for both tasks and resources is perfectly accurate. In practice, however, it is very difficult to achieve such an accurate prediction in a heterogeneous and dynamic grid environment. Therefore, the performance of a task scheduling algorithm may be significantly influenced by prediction inaccuracy. In this paper, we study the influence of inaccurate predictions on task scheduling in the contexts of task selection and processor selection, which are two critical phases in task scheduling algorithms. We develop formulas for the misprediction degree, which is defined as the probability that the predicted values for the performances of tasks and processors reveal different orders from their real values. Based on these formulas, we also investigate the effect of several key parameters on the misprediction degree. Finally, we conduct extensive simulation for the sensitivities of some existing task scheduling algorithms to the prediction errors.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.2.479/_p

Copy

@ARTICLE{e89-d_2_479,
author={Yuanyuan ZHANG, Yasushi INOGUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Influence of Inaccurate Performance Prediction on Task Scheduling in a Grid Environment},
year={2006},
volume={E89-D},
number={2},
pages={479-486},
abstract={Efficient task scheduling is critical for achieving high performance in grid computing systems. Existing task scheduling algorithms for grid environments usually assume that the performance prediction for both tasks and resources is perfectly accurate. In practice, however, it is very difficult to achieve such an accurate prediction in a heterogeneous and dynamic grid environment. Therefore, the performance of a task scheduling algorithm may be significantly influenced by prediction inaccuracy. In this paper, we study the influence of inaccurate predictions on task scheduling in the contexts of task selection and processor selection, which are two critical phases in task scheduling algorithms. We develop formulas for the misprediction degree, which is defined as the probability that the predicted values for the performances of tasks and processors reveal different orders from their real values. Based on these formulas, we also investigate the effect of several key parameters on the misprediction degree. Finally, we conduct extensive simulation for the sensitivities of some existing task scheduling algorithms to the prediction errors.},
keywords={},
doi={10.1093/ietisy/e89-d.2.479},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - Influence of Inaccurate Performance Prediction on Task Scheduling in a Grid Environment
T2 - IEICE TRANSACTIONS on Information
SP - 479
EP - 486
AU - Yuanyuan ZHANG
AU - Yasushi INOGUCHI
PY - 2006
DO - 10.1093/ietisy/e89-d.2.479
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2006
AB - Efficient task scheduling is critical for achieving high performance in grid computing systems. Existing task scheduling algorithms for grid environments usually assume that the performance prediction for both tasks and resources is perfectly accurate. In practice, however, it is very difficult to achieve such an accurate prediction in a heterogeneous and dynamic grid environment. Therefore, the performance of a task scheduling algorithm may be significantly influenced by prediction inaccuracy. In this paper, we study the influence of inaccurate predictions on task scheduling in the contexts of task selection and processor selection, which are two critical phases in task scheduling algorithms. We develop formulas for the misprediction degree, which is defined as the probability that the predicted values for the performances of tasks and processors reveal different orders from their real values. Based on these formulas, we also investigate the effect of several key parameters on the misprediction degree. Finally, we conduct extensive simulation for the sensitivities of some existing task scheduling algorithms to the prediction errors.
ER -