《基于串归约的网格工作流费用优化方法》由会员分享，可在线阅读，更多相关《基于串归约的网格工作流费用优化方法（8页珍藏版）》请在金锄头文库上搜索。
1、计算机研究与发展ISSN 1000 ?1239?CN 11 ?1777?TP Journal of Computer Research and Development45( 2) : 246 253, 2008? 收稿日期: 2007-04-14; 修回日期: 2007-10-29? 基金项目: 国家自然科学基金项目( 60672092, 60504029)基于串归约的网格工作流费用优化方法苑迎春1, 3? 李小平1, 2? 王 ? 茜1,21(东南大学计算机科学与工程学院? 南京? 210096)2(东南大学计算机网络和信息集成教育部重点实验室? 南京? 210096)3(河北农业大学信息科
2、学与技术学院? 保定? 071001)(nd?hd?yyc 163?com)Cost Optimization Heuristics for Grid Workflows Scheduling Based on Serial ReductionYuan Yingchun1,3, Li Xiaoping1,2, and Wang Qian1,21( School of Computer Science and Engineering, Southeast University , Nanjing 210096)2( Ministry of Education Key Laboratory of
3、Computer Network and Information Integration, Southeast University, Nanjing210096)3( Faculty of Information Science and Technology , Agriculture University of Hebei, Baoding 071001)Abstract? Workflow scheduling which guarantees the anticipated QoS ( quality of service) is a fundamental and complexit
4、y problem in computational grids? In this paper, the scheduling of workflows represented bydirected acyclic graph ( DAG) with the objective of cost minimization is considered? In general, the opti? mization problem is NP?hard? Two new heuristics, FSRD ( forward serial reduction with deadline) and BS
5、RD ( backward serial reduction with deadline) are proposed? According to the property of serial activi?ties, a new concept called series reduction ( SR) is defined? The time window for each serial reduction group is recalculated based on leveling algorithms? A dynamic programming method is presented
6、 for implementing the cost minimization of each serial reduction group? By integrating the local optimization strategy with two leveling algorithms ( DBL and DTL) , BSRD and FSRD are investigated? The two heuristics take into ac?count comprehensive serial and parallel properties of DAG, and improve
7、the cost optimization strategies adopted by leveling algorithms? Experimental results show that BSRD and FSRD can considerably improve the average performance of corresponding leveling heuristics? For pipeline workflows, BSRD ( FSRD) can achieve the optimal solutions but require a little more comput
8、ational time? For hybrid workflows, BSRDcan save 8?77% average cost of DBL and FSRD can save 6?00% average cost of DTL? Moreover, BSRD outperforms FSRD? As well, the impact of serial reduction ratio on two heuristics is analyzed?Key words? service grid; directed acyclic graph; workflow; heuristics;
9、serial reduction摘? 要?针对截止期限约束下有向无环图DAG( directed acyclic graph) 表示的工作流费用优化问题, 提出 两个新的费用优化算法: 时间约束的前向串归约算法 FSRD( forward serial reduction within deadline) 和时间约束的后向串归约算法 BSRD( backward serial reduction within deadline)? 算法利用 DAG 图中串行 活动特征给出串归约概念; 基于分层算法对串归约组的时间窗口重定义, 并提出动态规划的求解策略实 现组内费用的最优化? 两种归约算法综合考
10、虑 DAG 图中活动的串并特征, 改变分层算法中仅对单一活动的费用优化策略, 实现了串归约组的时间收集和最优利用? 模拟实验结果表明: BSRD 和 FSRD 能够 显著改进相应分层算法的平均性能, 且 BSRD优于 FSRD?关键词?服务网格; 有向无环图; 工作流; 启发式算法; 串归约中图法分类号? TP393? ? 开放网格服务架构 OGSA( open grid service ar?chitecture) 1和 Web 服务资源框架WSRF( Web ser?vice resource framework) 2将网格技术和 Web 服务技术相融合, 以服务为基本构成元素的服务网格成
11、为网格架构的主流方向之一? 多个服务相互协作( 即服务组合) 共同完成一个复杂任务成为服务网格下构建应用的一种重要方式, 这种应用可看做是一些工作流实例3? 有向无环图 DAG( directed acyclicgraph) 是工作流应用的一种常用描述方式, 广泛存在于 e?science 和 e?business 领域 ? 另一方面, Web 服务的发展使得网格中存在着大量功能相同、 服务质量QoS( quality of service, 如执行时间、 费用、 可靠性等) 4等非功能特性各异的服务? 用户期望工作流执行能够满足预期的服务质量需求( 如完工时间或总成本)? 因此, 工作流调度
12、是从众多候选服务中为各活动结点选择最适服务, 以满足用户特定需求?基于 QoS 的服务选择实质是一个 NP?hard 问题5? 不同约束条件、 QoS 参数构成不同优化问题?考虑时间、 费用、 可用性、 可靠性等多 QoS 的服务选择问题, Zeng 等人4利用线性规划原理求解服务选择的 QoS 全局优化问题; 文献 5?6 针对不同 QoS优化模型分别提出遗传算法的求解策略; 金海等人7给出高性价比的 QoS 优化模型, 用模拟退火算法求解 DAG 图表示的组合服务优化问题; 张伟哲等人 8提出多目标演化算法求解多 QoS 约束的网格独立作业调度问题? 线性规划和智能算法虽能获得较好性能,
13、但当问题规模较大时, 算法需要较大时间开销 ?构造式启发算法由于能在一个合理的运行时间内获得可接受解而被广泛采用? 考虑时间、 成本两个质量参数, Buyya 等人 9基于不同 deadline? budget约束提出解决独立任务调度的 3 种启发式算法; 陈宏伟等人 10考虑 DAG 应用调度, 提出有效路径分组法, 在时间允许下, 基于优先级策略把有效路径上的任务映射到价格便宜的资源上运行, 最小化费用?上述算法将网格看做是计算力资源的共享环境? 对服务网格下时间费用优化问题, Lin 等人11提出在特定条件满足下, DAG 应用的时间-费用优化问题可抽象为 Discrete time?c
14、ost tradeoff 问题? 文献 12对截止期( deadline) 约束的工作流( DAG 描述) 费用优化问题, 提出截止期分解思想? 利用正向分层 TL( top level) 将截止期分解为活动的时间区间, 但文中并未给出具体分解过程? 我们在前期工作中实现了正向分层算法 DTL( deadline top level) , 并提出逆向分层的截止期分解策略 DBL( deadline bottom level)? 结果表明 DBL 能显著提高 DTL 的平均性能? 尽管分层算法是一种简单、 有效的方法, 但由于活动被限制在独立的时间区间局部优化费用, 使活动在服务选择时会产生许多
15、离散? 时间碎片 ( 所选服务的执行时间小于活动的时间区间) 不能利用, 分层算法的性能受到影响?本文针对分层算法不足, 提出两种新的基于串归约的时间-费用优化算法: 时间约束的前向串归约算法 FSRD( forward series reduction with deadline) 和时间约束的后向串归约算法 BSRD( backward seriesreduction with deadline) ? 两种归约算法综合考虑DAG 图中活动的串并特征, 在分层算法基础上, 对串行活动提出动态规划方法最优化费用, 改变分层算法仅对单一活动的局部优化策略, 降低? 时间碎片 产生, 提高分层算法
16、性能?1? 问题描述服务网格下的计算、 通信、 存储、 仪器、 软件等所有资源都以服务形式存在, 用户有一致的资源使用模式 ? DAG 表示的工作流是网格环境下的一种重要应用形式 ? 令DAG 图记做 G= V , E, 其中结点集V = 1, 2, !, n表示所有活动(任务); 活动 1 和 n是添加的虚活动, 分别表示惟一入口和出口活动(虚活动是执行时间和成本都为 0 的任务); E 是有向边集合, 表示活动的偏序约束, 即对 ( i, j ) E,i 执行完j 才能执行( i, j 是活动编号且拓扑有序,即 i j )?网格中功能相同、 服务质量各异的服务可用执行时间、 费用、 可靠性等 QoS 参数标识, 这些 QoS 参数可注册到网格信息服务器中? 通过网格信息服务查询接口能获得服务的所有 QoS 信息? 因此, 对 G中任一活动i , 通过查询接口能搜索到完成该活动247苑迎春等: 基于串归约的网格工作流费用优化方法的所有候选服务集合 SP ( i) ( 称之为服务池, 虚活动的服务池为空), 服
