期刊
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
卷 69, 期 3, 页码 307-314出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jpdc.2008.11.003
关键词
Distributed scheduling; Grid computing; Successful schedulable ratio; Peer to peer scheduler; Priority; Deadline; Shuffling
资金
- NSF [0408136, 0411540]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [0411540] Funding Source: National Science Foundation
- Direct For Computer & Info Scie & Enginr
- Office of Advanced Cyberinfrastructure (OAC) [0408136] Funding Source: National Science Foundation
We consider non-preemptively scheduling a bag of independent mixed tasks (hard, firm and soft) in computational grids. Based upon task type, we construct a novel generalized distributed scheduler (GDS) for scheduling tasks with different priorities and deadlines. GDS is scalable and does not require knowledge of the global state of the system. It is composed of several phases: a multiple attribute ranking phase, a shuffling phase, and a task-resource matched peer to peer dispatching phase. Results of exhaustive simulation demonstrate that with respect to the number of high-priority tasks meeting deadlines, GDS outperforms existing approaches by 10%-25% without degrading schedulability of other tasks. Indeed, with respect to the total number of schedulable tasks meeting deadlines, GDS is slightly better. Thus, GDS not only maximizes the number of mission-critical tasks meeting deadlines, but it does so without degrading the overall performance. The results have been further confirmed by examining each component phase of GDS. Given that fully known global information is time intensive to obtain, the performance of GDS is significant. GDS is highly scalable both in terms of processors and number of tasks-indeed it provides superior performance over existing algorithms as the number of tasks increase. Also, GDS incorporates a shuffle phase that moves hard tasks ahead improving their temporal fault tolerance. Furthermore, since GDS can handle mixed task types, it paves the way to open the grid to make it amenable for commercialization. The complexity of GDS is O(n(2)m) where n is the number of tasks and m the number of machines. (C) 2008 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据