文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > A heuristic task scheduling algorithm for grid computing
侵权投诉

A heuristic task scheduling algorithm for grid computing

A heuristic task scheduling algorithm for grid computing

A General Self-adaptive Task Scheduling System for

Non-dedicated Heterogeneous Computing

Ming Wu, Xian-He Sun Department of Computer Science Illinois Institute of Technology Chicago, Illinois 60616, USA {wuming, sun}@iit.edu

Abstract

The efforts to construct a national scale grid computing environment has brought unprecedented computing capacity. Exploiting this complex infrastructure requires efficient middleware to support the execution of a distributed application, composed of a set of subtasks, for best performance. This presents the challenge how to schedule these subtasks in shared heterogeneous systems. Current work has several limitations. Most scheduling systems are based on determined estimation of task completion time. Current application-level scheduling algorithms are too closely coupled with application internal structures. The application performance may suffer when some resources represent abnormal usage pattern during applications execution. To address these issues, we develop a prototype of Grid Harvest Service (GHS) to provide dynamic and self-adaptive task scheduling. Experimental results show GHS outperforms current systems in scheduling large applications in a non-dedicated heterogeneous environment.

1. Introduction

In order to provide high performance computation power to serve the increasing need of large applications, people strive to improve the single machine's capacity or construct a distributed system composed of a scalable set of machines. Compared to the former, in which improvement is mainly up to hardware technology development, the construction of a distributed system for resource collaboration is more complex. Some of well-known existing or ongoing distributed systems composed of heterogeneous resources are Condor [1], NetSolve [2], Nimrod [3], Globus and the Grid computation environment [4]. While these systems, especially the Grid, bring unprecedented computing power for users, how to deliver this great computing power is still an elusive problem. One of the major puzzles is how to schedule

applications in these systems. In general, scheduling applications in a distributed system is a NP-hard problem. Many heuristic scheduling algorithms and systems are proposed to address this issue. However, most of scheduling algorithms so far proposed are for dedicated systems. By dedicated, we refer resources in the system serve the application in a dedicated fashion. This is against the situation that most of current distributed systems are resource-sharing environments [5].

Good schedules in a shared environment involve the integration of application specific information and system specific information. We study a performance-prediction based task scheduling system, which provides task allocation and scheduling based on application-level and system-level performance prediction. The effects of system specific information, such as utilization, job service rate and job arrival rate, and application-specific information, such as workload, divisibility, parallel processing, on the application performance have been identified. Our preliminary results demonstrate the effectiveness of our scheduling mechanism for long-term applications. Our earlier work [6] focuses on the task scheduling for parallel processing which assumes that the total workload of a parallel application could be arbitrarily partitioned. In this study, we extend our scheduling policy for a class of widely used Grid applications, the parameter-sweep applications. It is composed of a set of independent and indivisible tasks [7].

A key question is that how to maintain the parallel application performance when some of resources assigned for subtasks represent abnormal status from their historical information. A successful scheduling depends on the accuracy of system status prediction, which is deducted from the resource historical information. The application performance suffers under the situation of resource abnormality and there is a fair chance that a resource may show different usage pattern from its history in a large distributed system. To provide a robust task scheduler to work in this dynamic situation, we introduce a self-adaptive task scheduling algorithm, which monitors the long-running application progress and detects possible

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email