Hybrid Scheduling Strategy for Multiple DAGs Workflow in Heterogeneous System
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [46]
  • |
  • Related [20]
  • |
  • Cited by [2]
  • | |
  • Comments
    Abstract:

    Recent research in multiple DAG workflows in heterogeneous systems have been making progress andhave solved some problems, but fail to classify the multiple DAGs, according to the demand of the performanceasked by the varied DAG workflow and also fail to address the scheduling multiple DAGs workflow with multiplepriorities submitted at different times. To solve these problems, the paper presents a new model of multiple DAGsmanagement system for multiple DAGs workflow with multiple priorities and an adjustment method to the previousFairness algorithm to solve the fairness issue in scheduling multiple DAGs with the same priorities submitted atdifferent times. In addition, the study also proposes an implementation method of the Backfill algorithm formultiple DAGs with different priorities to improve utilization rate of resource, and then, based on the new modeland the two methods, propose a hybrid strategy for scheduling multiple DAGs with multiple priorities submitted atdifferent times. These experimental results show that it is possible to meet different requirements of DAGssubmitted at different times and to improve utilization rate of a resource. In addition, the results about schedulingtwo-DAGs show a significant “Trail Ending” principle, which is valuable for academic study and application.

    Reference
    [1] Yuan YC, Li XP, Wang Q, Wang KJ. Time optimization heuristics for scheduling budget-constrained grid workflows. Journal of
    Computer Research and Development, 2009,46(2):194 201 (in Chinese with English abstract). http://crad.ict.ac.cn:81/CRAD/
    ePublish/Search/Search.asp
    [2] Topcuoglu H, Hariri S, Wu MY. Performance-Effective and low-complexity task scheduling for heterogeneous computing. IEEE
    Trans. on Parallel and Distributed Systems, 2002,13(3):260 274. [doi: 10.1109/71.993206]
    [3] Tao Y, Gerasoulis A. DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. on Parallel and
    Distributed Systems, 1994,5(9):951 967. [doi: 10.1109/71.308533]
    [4] Kwok Y-K, Ahmad I. On multiprocessor task scheduling using efficient state space search approaches. Journal of Parallel and
    Distributed Computing, 2005,65(12):1515 1532. [doi: 10.1016/j.jpdc.2005.05.028]
    [5] Kwok Y-K, Ahmad I, Jun G. FAST: A low-complexity algorithm for efficient echeduling of DAGs on parallel processors. In: Proc.
    of the ’96 Int’l Parallel Processing. Piscataway: IEEE, 1996. 150 157. [doi: 10.1109/ICPP.1996.537394]
    [6] Yuan D, Yang Y, Liu X, Chen J. A data placement strategy in scientific cloud workflows. Future Generation Computer Systems,
    2010,26(8):1200 1214. [doi: 10.1016/j.future.2010.02.004]
    [7] Byun E, Choi S, Baik M, Gil J, Park C, Hwang C. MJSA: Markov job scheduler based on availability in desktop grid computing
    environment. Future Generation Computer Systems, 2007,23(4):616 622. [doi: 10.1016/j.future.2006.09.004]
    [8] Tian GZ, Yu J, He JS. Towards critical region reliability support for grid workflows. Journal of Parallel and Distributed Computing,
    2009,69(12):989 995. [doi: 10.1016/j.jpdc.2009.04.010]
    [9] Zhao HN, Sakellariou R. Scheduling multiple DAGs onto heterogeneous systems. In: Proc. of the 2006 20th Int’l Parallel and
    Distributed Processing Symp. (IPDPS 2006). Piscataway: IEEE, 2006. 14. [doi: 10.1109/IPDPS.2006.1639387]
    [10] Kertész A, Sipos G, Kacsuk P. Brokering multi-grid workflows in the P-GRADE portal. In: Proc. of the Parallel Processing
    (Euro-Par 2006), Vol.4375. Berlin: Springer-Verlag, 2007. 138 149. [doi: 10.1007/978-3-540-72337-0_14]
    [11] H nig U, Schiffmann W. A meta-algorithm for scheduling multiple DAGs in homogeneous system environments. In: Proc. of the
    2006 18th Int’l Parallel and Distributed Computing and Systems. Piscataway: IEEE, 2006. 147 152.
    [12] Bennett JCR, Zhang H. WF
    2
    Q: Worst-Case fair weighted fair queueing. In: Proc. of the 15th Annual Joint Conf. of the IEEE
    Computer Societies (INFOCOM’96), Networking the Next Generation. Piscataway: IEEE, 1996. 120 128. [doi: 10.1109/INFCOM.
    1996.497885]
    [13] Yu ZF, Shi WS. A planner-guided scheduling strategy for multiple workflow applications. In: Proc. of the Int’l Parallel Processing-
    Workshops (ICPPW 2008). Piscataway: IEEE, 2008. 1 8. [doi: 10.1109/ICPP-W.2008.10]
    [14] Fahringer T, Prodan R. ASKALON: A grid application development and computing environment. In: Proc. of the 6th IEEE/ACM
    Int;l Workshop on Grid Computing. Piscataway: IEEE, 2005. 122 131. [doi: 10.1109/GRID.2005.1542733]
    [15] Dagman. Condor 7.4.2 released, 2010. http://www.cs.wisc.edu/condor/dagman/[16] Yu J, Buyya R. Budget constrained scheduling of workflow applications on utility grids using genetic algorithms. In: Proc. of the
    Workshop on Workflows in Support of Large-Scale Science (WORKS 2006). Piscataway: IEEE, 2006. 1 10. [doi: 10.1109/
    WORKS.2006.5282330]
    [17] Buyya R, Abramson D, Venugopa S. The grid economy. Proc. of the IEEE, 2005,93(3):698 714. [doi: 10.1109/JPROC.2004.
    842784]
    [18] Stuer G, Vanmechelena K, Broeckhovea J. A commodity market algorithm for pricing substitutable grid resources. Future
    Generation Computer Systems, 2007,23(5):688 701. [doi: 10.1016/j.future.2006.11.004]
    [19] Buyya R, Yeo CS, Venugopal S, Broberg J, Brandic I. Cloud computing and emerging IT platforms: Vision, hype, and reality for
    delivering computing as the 5th utility. Future Generation Computer Systems, 2009,25(6):599 616. [doi: 10.1016/j.future.2008.
    12.001]
    [20] Stavrinides GL, Karatza HD. Scheduling multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing
    imprecise computations. Journal of Systems and Software, 2010,83(6):1004 1014. [doi: 10.1016/j.jss.2009.12.025]
    [21] Kwok Y-K, Dynamic AI. Critical-Path scheduling: An effective technique for allocating task graphs to multiprocessors. IEEE
    Trans. on Parallel and Distributed Systems, 1996,7(5):506 521. [doi: 10.1109/71.503776]
    Comments
    Comments
    分享到微博
    Submit
Get Citation

田国忠,肖创柏,徐竹胜,肖霞.异构分布式环境下多DAG工作流的混合调度策略.软件学报,2012,23(10):2720-2734

Copy
Share
Article Metrics
  • Abstract:4145
  • PDF: 6847
  • HTML: 0
  • Cited by: 0
History
  • Received:April 04,2011
  • Revised:February 15,2012
  • Online: September 30,2012
You are the first2049976Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063