An Online Scheduling Algorithm for Assigning Jobs in the Computational Grid

Chuliang WENG; Minglu LI; Xinda LU

doi:10.1093/ietisy/e89-d.2.597

An Online Scheduling Algorithm for Assigning Jobs in the Computational Grid

Chuliang WENG, Minglu LI, Xinda LU

Full Text Views

0

Share
Cite this

Summary :

The computational grid provides a promising platform for the deployment of various high-performance computing applications. Problem in implementing computational grid environments is how to effectively use various resources in the system, such as CPU cycle, memory, communication network, and data storage. There are many effective heuristic algorithms for scheduling in the computational grid, however most scheduling strategies have no theoretical guarantee at all. In this paper, a cost-based online scheduling algorithm is presented for job assignment in the grid environment with theoretical guarantee. Firstly, a scheduling framework is described, where the grid environment is characterized, and the online job model is defined. Secondly, the cost-based online scheduling algorithm is presented where costs of resources are exponential functions of their loads, and the performance of this algorithm is theoretically analyzed against the performance of the optimal offline algorithm. Finally, we implement the algorithm in the grid simulation environment, and compare the performance of the presented algorithm with the other three algorithms, and experimental results indicate that the cost-based online scheduling algorithm can outperform the other three online algorithms.

Publication: IEICE TRANSACTIONS on Information Vol.E89-D No.2 pp.597-604

Publication Date: 2006/02/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e89-d.2.597

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

Category: Grid Computing

Cite this

Copy

Chuliang WENG, Minglu LI, Xinda LU, "An Online Scheduling Algorithm for Assigning Jobs in the Computational Grid" in IEICE TRANSACTIONS on Information, vol. E89-D, no. 2, pp. 597-604, February 2006, doi: 10.1093/ietisy/e89-d.2.597.
Abstract: The computational grid provides a promising platform for the deployment of various high-performance computing applications. Problem in implementing computational grid environments is how to effectively use various resources in the system, such as CPU cycle, memory, communication network, and data storage. There are many effective heuristic algorithms for scheduling in the computational grid, however most scheduling strategies have no theoretical guarantee at all. In this paper, a cost-based online scheduling algorithm is presented for job assignment in the grid environment with theoretical guarantee. Firstly, a scheduling framework is described, where the grid environment is characterized, and the online job model is defined. Secondly, the cost-based online scheduling algorithm is presented where costs of resources are exponential functions of their loads, and the performance of this algorithm is theoretically analyzed against the performance of the optimal offline algorithm. Finally, we implement the algorithm in the grid simulation environment, and compare the performance of the presented algorithm with the other three algorithms, and experimental results indicate that the cost-based online scheduling algorithm can outperform the other three online algorithms.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.2.597/_p

Copy

@ARTICLE{e89-d_2_597,
author={Chuliang WENG, Minglu LI, Xinda LU, },
journal={IEICE TRANSACTIONS on Information},
title={An Online Scheduling Algorithm for Assigning Jobs in the Computational Grid},
year={2006},
volume={E89-D},
number={2},
pages={597-604},
abstract={The computational grid provides a promising platform for the deployment of various high-performance computing applications. Problem in implementing computational grid environments is how to effectively use various resources in the system, such as CPU cycle, memory, communication network, and data storage. There are many effective heuristic algorithms for scheduling in the computational grid, however most scheduling strategies have no theoretical guarantee at all. In this paper, a cost-based online scheduling algorithm is presented for job assignment in the grid environment with theoretical guarantee. Firstly, a scheduling framework is described, where the grid environment is characterized, and the online job model is defined. Secondly, the cost-based online scheduling algorithm is presented where costs of resources are exponential functions of their loads, and the performance of this algorithm is theoretically analyzed against the performance of the optimal offline algorithm. Finally, we implement the algorithm in the grid simulation environment, and compare the performance of the presented algorithm with the other three algorithms, and experimental results indicate that the cost-based online scheduling algorithm can outperform the other three online algorithms.},
keywords={},
doi={10.1093/ietisy/e89-d.2.597},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - An Online Scheduling Algorithm for Assigning Jobs in the Computational Grid
T2 - IEICE TRANSACTIONS on Information
SP - 597
EP - 604
AU - Chuliang WENG
AU - Minglu LI
AU - Xinda LU
PY - 2006
DO - 10.1093/ietisy/e89-d.2.597
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2006
AB - The computational grid provides a promising platform for the deployment of various high-performance computing applications. Problem in implementing computational grid environments is how to effectively use various resources in the system, such as CPU cycle, memory, communication network, and data storage. There are many effective heuristic algorithms for scheduling in the computational grid, however most scheduling strategies have no theoretical guarantee at all. In this paper, a cost-based online scheduling algorithm is presented for job assignment in the grid environment with theoretical guarantee. Firstly, a scheduling framework is described, where the grid environment is characterized, and the online job model is defined. Secondly, the cost-based online scheduling algorithm is presented where costs of resources are exponential functions of their loads, and the performance of this algorithm is theoretically analyzed against the performance of the optimal offline algorithm. Finally, we implement the algorithm in the grid simulation environment, and compare the performance of the presented algorithm with the other three algorithms, and experimental results indicate that the cost-based online scheduling algorithm can outperform the other three online algorithms.
ER -