关键词：
云计算
工作流调度
完工时间
执行成本
资源分配
摘要：
云计算作为一种基于互联网的计算服务模式,具有高度灵活性和可扩展性,云计算环境下的工作流调度是影响云服务质量的关键优化问题之一。伴随着大数据时代日益增长的计算需求,工作流的规模显著增加,结构也变得愈加复杂。在多元异构的海量计算资源环境下,如何高效解决云工作流调度问题,已成为云计算领域重要的研究课题。
针对云计算环境下的工作流调度问题,本文分别从云服务商、云用户以及联合角度出发,研究了三种不同场景的云工作流调度优化问题,包括完工期限约束下的工作流执行成本优化调度、成本预算约束下的工作流完工时间优化调度以及多目标优化调度问题,并针对性地提出了三类新的云工作流调度算法。本文研究内容主要包括以下三方面:
(1)针对完工期限约束下的工作流执行成本优化调度问题,本文提出了使用反馈机制的双向工作流调度算法(Bidirectional Workflow Scheduling with Feedback Mechanism,BFWS)。双向调度框架同时支持从正向和反向两个调度方向上选择计算任务,提高了任务处理的灵活性。在时间控制上,该框架设计了一种任务完成截止期限动态预测方法,该方法能够基于工作流拓扑信息以及现有调度信息,更准确地评估任务完成的截止期限。在资源选择上,该框架使用了一种新的成本感知资源选择算子,该算子能够精确且迅速地计算双向调度中不同计算资源处理给定任务所需的额外成本,指导算法选取合适的计算资源。除此之外,BFWS还引入了反馈控制机制,协同使用资源反馈和时间反馈两种反馈规则,使得BFWS能够在迭代过程中不断调整和改进其在时间和成本控制方面的决策。实验结果表明,BFWS在性能上显著优于同类型的代表性算法。
(2)针对成本预算约束下的工作流完工时间优化调度问题,本文设计了三种新的动态任务特征提取方法,并围绕任务特征的利用,提出了两类任务特征使用框架,分别聚焦于单一特征的独立使用和多重特征的联合利用。在单一特征的独立使用上,本文提出了一种新的工作流调度算法(Heterogeneous Earliest Finish Time Algorithm with Priority Adjusters and Critical Task Resource Optimizer,PACP-HEFT)。PACP-HEFT整合了两个任务优先级调节器和一个关键任务资源优化器。其中,优先级调节器能够随着调度解的变化动态地提取任务特征,灵活调整任务在资源分配中的优先级;关键任务资源优化器则基于任务的松弛时间特征进一步优化关键任务的资源分配,缩短整个工作流的完工时间。在多特征联合利用方面,本文提出了一种使用神经网络任务优先级决策器的云工作流调度算法(Workflow Scheduling Algorithm with Neural Priority Learning,LPWS)。LPWS 以多维任务特征作为决策器输入,利用人工神经网络整合多维特征并决策任务优先级值。此外,LPWS还引入了一种自适应优先级扰动策略。该策略能够依据历史搜索信息自适应地调整优先级扰动幅度,协助算法跳出局部最优。实验结果显示了 PACP-HEFT和LPWS在应对成本预算约束以及优化完工时间方面的优势。
(3)针对多目标云工作流调度优化问题,本文提出了一种基于两阶段分解的多目标工作流算法——MOD-HEFT(Multi-objective Decomposition-based Heterogeneous Earliest Finish Time Algorithm)。MOD-HEFT在第一阶段采用线性分解方法将多目标云工作流调度优化问题分解为若干个子问题,并在各子问题求解上整合了三种不同的调度器,三类调度器分别结合了不同调度场景的高效启发式策略,引导MOD-HEFT快速向帕累托前沿推进。在算法第二阶段,MOD-HEFT采用多轮次子区域分解的搜索方法,旨在发掘帕累托前沿上更多的非支配解。在搜索规划上,MOD-HEFT引入了自适应子区域分解策略,利用非支配解的整体分布信息,在目标空间不断整合计算资源,划分更低层次的子搜索区域。在搜索过程中,MOD-HEFF支持对多区域执行并行搜索,并在对每个子区域的内部搜索中,采用偏好帕累托选择方法筛选调度解,有效地扩充了帕累托非支配解集。实验表明MOD-HEFT在求解多目标云工作流调度优化问题上显著优于其他代表性算法。
欢迎来到三峡大学图书馆！
详细信息
