Task ranking and allocation in list-based workflow scheduling on parallel computing platform

详细信息    查看全文

• 作者：Kuo -Chan Huang (1)
  Ying -Lin Tsai (1)
  Hsiao -Ching Liu (1)
  
• 关键词：Workflow ; List ; based scheduling ; Task ranking ; Task allocation
• 刊名：The Journal of Supercomputing
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：71
• 期：1
• 页码：217-240
• 全文大小：1,987 KB
• 参考文献：1. Bittencourt LF, Sakellariou R, Madeira ERM (2010) DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. In: Proceedings of the 18th euromicro conference on parallel, distributed and network-based processing. pp 27鈥?4
  2. Gary MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-Completeness. W.H. Freeman and Co., San Francisco
  3. Bittencourt LF, Madeira ERM (2008) A performance-oriented adaptive scheduler for dependent tasks on grids. J Concurr Comput Pract Exp 20(9):1029鈥?049 CrossRef
  4. ASKALON (2013) http://www.dps.uibk.ac.at/projects/teuta/. Accessed 20 oct 2013
  5. DAGman (2013) http://research.cs.wisc.edu/htcondor/dagman/dagman.html. Accessed 20 oct 2013
  6. Cloudbus (2013) http://www.cloudbus.org/workflow/. Accessed 20 oct 2013
  7. Pegasus (2013) http://pegasus.isi.edu/. Accessed 20 oct 2013
  8. Wieczorek M, Prodan R, Fahringer T (2005) Scheduling of scientific workflows in the askalon grid environment. ACM SIGMOD Record 34(3):56鈥?2 CrossRef
  9. Topcuoglu H, Hariri S, Wu MY (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 2(13):247鈥?60
  10. Wieczorek M, Prodan R, Hoheisel A, Wieczorek M, Prodan R, Hoheisel A (2008) Taxonomies of the multi-criteria grid workflow scheduling problem. In: Grid middleware and services. pp 237鈥?64
  11. Mandal A, Kennedy K, Koelbel C, Marin G, Mellor-Crummey J, Liu B, Johnsson L (2005) Scheduling strategies for mapping application workflows onto the grid. In: Proceedings of the 14th IEEE symposium on high performance distributed computing. pp 125鈥?34
  12. Wu Z, Liu X, Ni Z, Yuan D, Yang Y (2013) A market-oriented hierarchical scheduling strategy in cloud workflow systems. J Supercomput 63(1):256鈥?93 CrossRef
  13. Javadi B, Thulasiraman P, Buyya R (2012) Enhancing genetic algorithms for dependent job scheduling in grid computing environments. J Supercomput 62(1):290鈥?14 CrossRef
  14. Deelman E, Singh G, Kesselman C (2005) Optimizing grid-based workflow execution. J Grid Comput 3(3):201鈥?19
  15. Falzon G, Li M (2012) Enhancing list scheduling heuristics for dependent job scheduling in grid computing environments. J Supercomput 59(1):104鈥?30 CrossRef
  16. Sih GC, Lee EA (1993) A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans Parallel Distrib Syst 4(2):175鈥?86 CrossRef
  17. EI-Rewini H, Lewis TG (1990) Scheduling parallel program tasks onto arbitrary target machines. J Parallel Distrib Comput 9(2):138鈥?53 CrossRef
  18. Kwok Y, Ahmad I (1996) Dynamic critical-path scheduling: an effective technique for allocating task graphs to multi-processors. IEEE Trans Parallel Distrib Syst 7(5):506鈥?21 CrossRef
  19. Hsu CH, Hsieh CW, Yang CT (2007) A generalized critical task anticipation technique for DAG scheduling. In: Proceedings of ICA3PP 2007. pp 493鈥?05
  20. Sinnen O (2007) Task Scheduling for Parallel Systems. John Wiley, New York
  21. Kim SJ, Browne JC (1988) A general approach to mapping of parallel computation upon multiprocessor architectures. In: Proceedings of international conference on parallel processing. pp 1鈥?
  22. Yang T, Gerasoulis A (1994) DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Trans Parallel Distrib Syst 5(9):951鈥?67 CrossRef
  23. Liou J, Palis MA (1996) An efficient clustering heuristic for scheduling DAGs on multiprocessors. In: Proceedings of the 8th symposium on parallel and distributed processing
  24. Bittencourt LF, Madeira ERM (2009) Towards the scheduling of multiple workflows on computational grids. J Grid Comput 1(8):419鈥?41
  25. Park G, Shirazi B, Marquis J (1997) DFRN: a new approach for duplication based scheduling for distributed memory multi-processor systems. In: Proceedings of international conference on parallel processing. pp 157鈥?66
  26. Zhao H, Sakellarious R (2006) Scheduling multiple DAGs onto heterogeneous systems. In: Proceedings of the 20th international conference on parallel and distributed processing
  27. Yu Z, Shi W (2008) A planner-guided scheduling strategy for multiple workflow applications. In: Proceedings of the 37th international conference on parallel processing. pp 8鈥?2
  28. N鈥檛akp茅 T, Suter F (2007) A comparison of scheduling approaches for mixed-parallel applications on heterogeneous platforms. In: Proceedings of the 6th international symposium on parallel and distributed computing
  29. Business Process Execution Language (BPEL) (2013) http://en.wikipedia.org/wiki/Business_Process_Execution_Language. Accessed 20 oct 2013
  30. Cicerre FRL, Madeira ERM, Buzato LE (2006) A hierarchical process execution support for grid computing. J Concurr Comput Pract Exp 18(6):581鈥?94 CrossRef
  31. Ramakrishnan A, Singh G, Zhao H, Deelman E, Sakellariou R, Vahi K, Blackburn K, Meyers D, Samidi M (2007) Scheduling data-intensive workflows onto storage-constrained distributed resources. In: Proceedings of the seventh IEEE international symposium on cluster computing and the grid. pp 401鈥?09
  
• 作者单位：Kuo -Chan Huang (1)
  Ying -Lin Tsai (1)
  Hsiao -Ching Liu (1)
  
  1. Department of Computer Science, National Taichung University of Education, Taichung, Taiwan
  
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers and Interpreters
  Processor Architectures
  Computer Science, general
  
• 出版者：Springer Netherlands
• ISSN：1573-0484

文摘

List-based workflow scheduling has received much research attention and been implemented in many existing workflow computing systems as more and more scientific and engineering applications need to exploit task parallelism for performance improvement. In this paper, we propose two task-ranking mechanisms and one task allocation method for the two major steps in list-based workflow scheduling. The proposed task-ranking approaches are based on innovative ideas of remaining workload and hybrid ranking, in contrast to the single path-oriented concept widely used in existing methods. The investigation of task allocation points out an important aspect, amount of available resources, which was not considered seriously in previous research. The proposed approaches were evaluated extensively with a series of simulation experiments and compared to existing widely used task-ranking and allocation methods. The experimental results show that our approaches has potential to outperform existing methods significantly in many cases, but no one single method can always achieve the best performance, which indicates a promising direction for future research work.