We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 21 Issue 4
July  2006
Turn off MathJax
Article Contents
Abstract
References
Li-Na Ni, Jin-Quan Zhang, Chun-Gang Yan, Chang-Jun Jiang. A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid[J]. Journal of Computer Science and Technology, 2006, 21(4): 559-564.
Citation: Li-Na Ni, Jin-Quan Zhang, Chun-Gang Yan, Chang-Jun Jiang. A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid[J]. Journal of Computer Science and Technology, 2006, 21(4): 559-564.
shu

A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid

  • 1Department of Computer Science, Tongji University, Shanghai 200092, P.R. China2College of Information Science \& Engineering, Shandong University of Science \& Technology, Qingdao 266510, P.R. China

More Information
  • Revised Date: May 14, 2006
  • Published Date: July 14, 2006
    Abstract
  • Efficient task scheduling is critical to achieving highperformance on grid computing environment. The task scheduling on gridis studied as optimization problem in this paper. A heuristic taskscheduling algorithm satisfying resources load balancing on gridenvironment is presented. The algorithm schedules tasks by employingmean load based on task predictive execution time as heuristicinformation to obtain an initial scheduling strategy. Then an optimalscheduling strategy is achieved by selecting two machines satisfyingcondition to change their loads via reassigning their tasks under theheuristic of their mean load. Methods of selecting machines and tasksare given in this paper to increase the throughput of the system andreduce the total waiting time. The efficiency of the algorithm isanalyzed and the performance of the proposed algorithm is evaluated viaextensive simulation experiments. Experimental results show that theheuristic algorithm performs significantly to ensure high loadbalancing and achieve an optimal scheduling strategy almost all thetime. Furthermore, results show that our algorithm is high efficient interms of time complexity.
    • FullText(HTML)
    • References (19)
  • [1]
    Kwok Y, Ahmad I. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors. -\it IEEE Trans. Parallel and Distributed Systems}, 1996, 7(5): 506--521.
    [2]
    Hou E S H, Ansari N, Ren H. A genetic algorithm for multiprocessor scheduling. -\it IEEE Trans. Parallel and Distributed Systems}, 1994, 5(2): 113--120.
    [3]
    Sih G C, Lee E A. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. -\it IEEE Trans. Parallel and Distributed Systems}, 1993, 4(2): 175--186.
    [4]
    Singh H, Youssef A. Mapping and scheduling heterogeneous task graphs using genetic algorithms. In -\it Proc. 5th IEEE Int. Heterogeneous Computing Workshop}, Honolulu, Hawaiian Islands, April 15-16, 1996, pp.86--97.
    [5]
    Ahmad I, Kwok Y. A new approach to scheduling parallel programs using task duplication. In -\it Proc. 4th Int. Parallel Processing}, Chapel Hills, North Carolina, August 15-19, 1994, pp.47--51.
    [6]
    Palis M A, Liou J, Wei D S L. Task clustering and scheduling for distributed memory parallel architectures. -\it IEEE Trans. Parallel and Distributed Systems}, 1996, 7(1): 46--55.
    [7]
    Zhuge H. Semantic grid: Scientific issues, infrastructure, and methodology. -\it Communications of the ACM}, 2005, 48(4): 117--119.
    [8]
    Zhuge H, Sun X, Liu J \it et al. \rm A scalable P2P platform for the knowledge grid. -\it IEEE Trans. Knowledge and Data Engineering}, 2005, 17(12): 1721--1736.
    [9]
    Cannataro M, Talia D. Semantics and knowledge grids: Buil\-ding the next-generation grid. -\it IEEE Trans. Intelligent Systems,} 2004, 19(1): 56--63.
    [10]
    Thain D, Tannenbaum T, Livny M. Condor and the Grid. Grid Computing: Making The Global Infrastructure a Reality, Hey A J G, Berman F, Fox G C (eds.), Wiley, West Sussex, England, 2003, pp.299--335.
    [11]
    Krauter K, Buyya R, Maheswaran M. A taxonomy and survey of grid resource management systems for distributed compu\-ting. -\it Software Practice and Experience}, 2002, 32(1): 135--164.
    [12]
    Ibarra O H, Kim C E. Heuristic algorithms for scheduling independent tasks on non-identical processors. -\it Journal of the Association for Computing Machinery}, 1997, 24(2): 280--289.
    [13]
    Taura K, Chien A. A heuristic algorithm for mapping communicating tasks on heterogeneous resources. In -\it Proc. 9th Int. Heterogeneous Computing Workshop}, Cancun, Mexico, May 1--5, 2000, pp.102--115.
    [14]
    Sun X H, Wu M. Grid harvest service: A system for long-term, application-level task scheduling. In -\it Proc. 17th IEEE Int. Parallel and Distributed Processing Symp}., Nice, France, April 22--26, 2003, pp.363--370.
    [15]
    Allen D. Predicting queue times on space-sharing pa\-rallel computers. In -\it Proc. 11th Int. Parallel Processing Symp}., Geneva, Switzerland, April 1--5, 1997, pp.209--218.
    [16]
    Richard G. A historical application profiler for use by pa\-rallel schedulers. -\it Lecture Notes on Computer Science}, 1997, 1291: 58--77.
    [17]
    Smith W, Ian F, Valerie T. Predicting application run times using historical information. -\it Lecture Notes in Computer Science}, 1998, 1459: 122--142.
    [18]
    Miller B P, Tamches A. Fine-grained dynamic instrumentation of commodity operating system kernels. In -\it Proc. 3rd Int. Operating Systems Design and Implementation Symp}., New Orleans, LA, February 22--25, 1999, pp.117--130.
    [19]
    Dinda P, O'Hallaron D. An Extensible Toolkit for Resource Prediction in Distributed Systems. Technical Report CMU-CS-99-138, School of Computer Science, Carnegie Mellon University, July, 1999.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (24) PDF downloads (1304) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return