Scheduling of scientific workflow in non-dedicated heterogeneous multicluster platform
Scheduling of scientific workflow in non-dedicated heterogeneous multicluster platform
复制标题
非专用异构多集群平台科学工作流程调度
DOI：
10.1016/j.jss.2012.10.029
复制
发表时间：
2013-07
影响因子：
3.5
通讯作者：
Dong, Fang
中科院分区：
文献类型：
--
作者：
Zhang, Jinghui;Luo, Junzhou;Dong, Fang
许多科学工作流可以构造为并行任务图（PTG），即数据并行任务的图。将数据并行性添加到工作流为提高性能和可伸缩性提供了机会。工作流任务具有数据并行性和可塑性，集群不仅异构，而且非专用于工作流执行。因此，在多集群平台中调度这样的科学工作流成为一项具有挑战性的任务。为了解决这个问题，我们研究了科学工作流的调度在一个非专用的异构多集群平台，旨在最大限度地减少工作流执行的最大完工时间。本文提出了三种有效的工作流任务映射和资源分配调度算法，其中MHEFT-RSV和MHEFT-RSV-BD是启发式算法。一个精确的分支和切割调度算法的实现，它利用任务间的优先级和资源约束，从而加快获得一个可行的时间表，最小化最大完工时间的过程。详细的仿真实验表明，平均而言，精确的分支和切割算法获得较短的最大完工时间为中小规模的工作流，而MHEFT-RSV和MHEFT-RSV-BD实现更好的权衡之间的最大完工时间和计算时间为大型科学工作流。
Many scientific workflows can be structured as Parallel Task Graphs (PTGs), that is, graphs of data-parallel tasks. Adding data parallelism to a workflow provides opportunities for higher performance and scalability. Workflow tasks are data-parallel and moldable, and clusters are not only heterogeneous but also non-dedicated for workflow execution. Therefore, scheduling such scientific workflow in a multicluster platform becomes a challenging task. To address this problem, we study the scheduling of scientific workflow in a non-dedicated heterogeneous multicluster platform aimed at minimizing the makespan for workflow execution. In this paper, three scheduling algorithms for effective workflow task mapping and resource allocation are proposed, among them MHEFT-RSV and MHEFT-RSV-BD are heuristic algorithms. An exact branch-and-cut scheduling algorithm is implemented, which exploits the intertask precedence and resource constraints thereby accelerating the process of obtaining a feasible schedule with minimized makespan. Detailed simulation experiments show that on average the exact branch-and-cut algorithm obtains shorter makespan for small and medium size workflows, while MHEFT-RSV and MHEFT-RSV-BD achieves better tradeoff between makespan and computation time for large scientific workflows.
登录
查看更多内容
DOI：
10.1145/215399.215423
发表时间：
1995-07
期刊：
--
影响因子：
--
作者：
Soumen Chakrabarti;J. Demmel;K. Yelick
通讯作者：
Soumen Chakrabarti;J. Demmel;K. Yelick
影响因子：
0.7
作者：
Zhifeng Yu;Weisong Shi
通讯作者：
Zhifeng Yu;Weisong Shi
影响因子：
5.3
作者：
P. Dutot;Tchimou N'Takpé;F. Suter;H. Casanova
通讯作者：
P. Dutot;Tchimou N'Takpé;F. Suter;H. Casanova
DOI：
10.1142/s0129054102001308
发表时间：
2001-08
期刊：
Int. J. Found. Comput. Sci.
影响因子：
--
作者：
Renaud Lepère;D. Trystram;G. Woeginger
通讯作者：
Renaud Lepère;D. Trystram;G. Woeginger
影响因子：
1.7
作者：
Dash, S
通讯作者：
Dash, S