Adaptive dual-criteria task group allocation for clustering-based multi-workflow scheduling on parallel computing platform

详细信息    查看全文

• 作者：Ying-Lin Tsai ; Hsiao-Ching Liu ; Kuo-Chan Huang
• 关键词：Task allocation ; Workflow scheduling ; Parallel computing ; Clustering ; based scheduling
• 刊名：The Journal of Supercomputing
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：71
• 期：10
• 页码：3811-3831
• 全文大小：2,461 KB
• 参考文献：1.Pinedo ML (2008) Scheduling: theory, algorithms, and systems. Springer, New York
  2.Bittencourt LF, Madeira ERM (2008) A performance-oriented adaptive scheduler for dependent tasks on grids. Concurr Comput Pract Exp 20(9):1029-049CrossRef
  3.ASKALON (2015) http://?www.?dps.?uibk.?ac.?at/?projects/?teuta/-/span>
  4.DAGman (2015) http://?www.?cs.?wisc.?edu/?condor/?manual/-/span>
  5.Gridbus (2015) http://?www.?cloudbus.?org/?workflow/-/span>
  6.Pegasus (2015) http://?pegasus.?isi.?edu/-/span>
  7.Wieczorek M, Prodan R, Hoheisel A (2008) Taxonomies of the multi-criteria grid workflow scheduling problem. In: Grid Middleware and Services, pp 237-64
  8.Business Process Execution Language (BPEL) (2015) http://?en.?wikipedia.?org/?wiki/?Business_?Process_?Execution_?Language
  9.Cicerre FRL, Madeira ERM, Buzato LE (2006) A hierarchical process execution support for grid computing. Concurr Comput Pract Exp 18(6):581-94CrossRef
  10.Topcuoglu H, Hariri S, Wu MY (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 2(13):260-47CrossRef
  11.Huang KC, Tsai YL, Liu HC (2015) Task ranking and allocation in list-based workflow scheduling on parallel computing platform. J Supercomput 71(1):217-40CrossRef
  12.Zhao H, Sakellarious R (2006) Scheduling multiple DAGs onto heterogeneous systems. In: Proceedings of the 20th international conference on parallel and distributed processing
  13.Hsu CC, Huang KC, Wang FJ (2011) Online scheduling of workflow applications in grid environments. Future Gen Comput Syst 27(6):860-70CrossRef
  14.Hirales-Carbajal A, Tchernykh A, Yahyapour R, González-García JL, R?blitz T, Ramírez-Alcaraz JM (2012) Multiple workflow scheduling strategies with user run time estimates on a grid. J Grid Comput 10(2):325-46CrossRef
  15.Mu PC, Nezan JF, Raulet M (2011) A list scheduling heuristic with new node priorities and critical child technique for task scheduling with communication contention. In: Algorithm-Architecture Matching for Signal and Image Processing. Lecture Notes in Electrical Engineering, vol 73, pp 217-36
  16.Garg R, Singh AK (2014) Multi-objective workflow grid scheduling using \(\varepsilon \) -fuzzy dominance sort based discrete particle swarm optimization. J Supercomput 68(2):709-32CrossRef
  17.Deelman E, Singh G, Kesselman C (2005) Optimizing grid-based workflow execution. J Grid Comput 3(3):201-19
  18.Adabi S, Movaghar A, Rahmani AM (2014) Bi-level fuzzy based advanced reservation of Cloud workflow applications on distributed grid resources. J Supercomput 67(1):175-18CrossRef
  19.Bittencourt LF, Madeira ERM (2007) Fulfilling task dependence gaps for workflow scheduling on grids. In: Proceedings of the 3rd IEEE International Conference on Signal-Image Technology and Internet Based Systems (SITIS), pp 468-75
  20.Yang T, Gerasoulis A (1994) DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Trans Parallel Distrib Syst 5(9):951-67CrossRef
  21.Bittencourt LF, Madeira ERM (2010) Towards the scheduling of multiple workflows on computational grids. J Grid Comput 8(3):419-41CrossRef
  22.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
  23.Jiang HJ, Huang KC, Chang HY, Gu DS, Shih PJ (2011) Scheduling concurrent workflows in HPC cloud through exploiting schedule gaps. In: Proceedings of the 11th International Conference on Algorithms and Architectures for Parallel Processing, pp 282-93
  24.Stavrinides GL, Karatza HD (2011) Scheduling multiple task graphs in heterogeneous distributed real-time systems by exploiting schedule holes with bin packing techniques. Simul Model Pract Theory 19(1):540-52CrossRef
  25.Tsai YL, Huang KC, Chang HY, Ko J, Wang ET, Hsu CH (2012) Scheduling multiple scientific and engineering workflows through task clustering and best-fit allocation. In: Proceedings of 2012 IEEE Eighth World Congress on Services, pp 1-
  26.Sinnen O (2007) Task scheduling for parallel systems. Wiley, New YorkCrossRef
  27.Bharathi S, Chervenak A, Deelman E, Mehta G, Su MH, Vahi K (2008) Characterization of scientific workflows. In: Proceedings of 3rd workshop on workflows in support of large-scale science (WORKS08)
  
• 作者单位：Ying-Lin Tsai (1)
  Hsiao-Ching Liu (1)
  Kuo-Chan Huang (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

文摘

Workflow scheduling has long been an important research topic in the field of parallel computing. Clustering-based methods are one of the major types of workflow scheduling approaches which have been shown superior to other kinds of methods in many cases due to their advantage of minimizing inter-task communication costs. Most previous research dealt with single workflow scheduling and focused on how to cluster the tasks within a workflow into a set of task groups. Recent research showed that utilizing idle time gaps between scheduled tasks is a promising direction for efficient multiple workflow scheduling. Since executing multiple workflows simultaneously is an inevitable need in modern shared parallel computing platforms, efficient task group allocation becomes a critical issue. In this paper, we studied such issue and proposed an innovative dual-criteria task group allocation method which considers both task group’s finish time and potential resource utilization to effectively improve overall multi-workflow execution performance. In addition, an adaptive task group rearrangement mechanism was adopted to further improve performance. The proposed method has been evaluated with a series of simulation experiments and compared to previous approaches. The experimental results show that our method outperforms previous approaches across different workload conditions and workflow properties in terms of average makespan. The performance improvement ranges from 5 to 29 % for different conditions, achieving the largest performance improvement for workflows of smaller CCR. Keywords Task allocation Workflow scheduling Parallel computing Clustering-based scheduling