【优化调度】基于遗传算法GA异构分布式计算系统上实时并行工作流的能量最小化调度附Matlab代码

✅作者简介：热爱科研的Matlab仿真开发者，擅长毕业设计辅导、数学建模、数据处理、程序设计科研仿真。

🍎完整代码获取 定制创新 论文复现点击：Matlab科研工作室

👇 关注我领取海量matlab电子书和数学建模资料

🍊个人信条：做科研，博学之、审问之、慎思之、明辨之、笃行之，是为：博学慎思，明辨笃行。

🔥 内容介绍

当今大规模并行工作流常于异构分布式计算平台上处理。从经济角度看，计算资源提供商需在提供高服务质量的同时将成本降至最低。能耗在计算系统总成本中占比巨大，且及时性与可靠性是两项重要的服务指标。本文研究在响应时间与可靠性约束下，对并行工作流进行调度以最小化系统能耗的问题。首先将此问题数学建模为非线性混合整数规划问题，鉴于其直接求解难度大，故提出若干高效启发式解决方案。具体而言，先开发一种在满足可靠性要求的同时最小化调度长度的算法，在此基础上，利用动态电压频率缩放（DVFS）技术提出处理器合并算法与松弛时间回收算法以降低能耗。处理器合并算法尝试关闭部分能源利用效率低的处理器，从而实现能耗最小化。DVFS 技术应用于处理器和任务层面以降低处理器频率进而减少能耗。在两个实际工作流及大量合成并行工作流上的实验结果证明了这些算法的有效性。

一、引言

随着信息技术的飞速发展，大规模并行工作流在科学研究、商业应用等诸多领域得到广泛应用。异构分布式计算平台因其强大的计算能力和灵活性，成为处理这些工作流的常用选择。然而，在追求高性能计算的同时，能耗问题日益凸显。计算资源提供商不仅要确保服务的及时性和可靠性，还要考虑成本效益，而能耗是成本的重要组成部分。因此，研究如何在异构分布式计算系统上对实时并行工作流进行能量最小化调度具有重要的现实意义。

二、问题建模

三、启发式算法设计

（一）满足可靠性要求的调度长度最小化算法

1. 任务优先级计算：根据任务在 DAG 中的位置和依赖关系，计算每个任务的优先级。例如，离工作流结束节点越近且依赖任务越少的任务优先级越高。

2. 处理器选择策略：对于每个任务，按照处理器的计算能力从高到低的顺序进行尝试分配，选择能最早完成该任务且满足可靠性要求的处理器。在计算完成时间时，考虑任务之间的依赖关系和处理器上已分配任务的执行情况。

（二）处理器合并算法

1. 能耗效率评估：计算每个处理器在当前任务分配情况下的能耗效率，能耗效率定义为单位能耗所完成的计算量。

2. 处理器关闭决策：从能耗效率低的处理器开始，尝试关闭该处理器，并将其分配的任务重新分配到其他处理器上。重新分配任务时，遵循满足可靠性要求的调度长度最小化算法的分配策略。若重新分配后仍能满足响应时间和可靠性约束，则关闭该处理器，以减少系统能耗。

（三）基于 DVFS 技术的松弛时间回收算法

1. 松弛时间计算：在满足响应时间约束的前提下，计算每个任务的松弛时间。松弛时间是指任务可以延迟开始而不影响整个工作流截止时间的时间量。

2. 频率调整策略：对于每个任务，根据其松弛时间和处理器的频率 - 能耗关系，利用 DVFS 技术降低处理器频率。具体来说，在处理器层面，若多个任务共享一个处理器，根据这些任务的总松弛时间调整处理器频率；在任务层面，对于单个任务，根据其自身松弛时间调整处理器频率。通过降低频率来减少能耗，同时确保任务仍能在截止时间内完成。

四、基于遗传算法（GA）的实现

⛳️ 运行结果

📣 部分代码

function succArray = pickUpSuccFuc(matrixF,i)​vector = matrixF(i,:);succArray = [];for go = 1:size(vector, 2)if vector(go) > 0succArray = [succArray, go];endend

🔗 参考文献

[1] Hu B , Cao Z , Zhou M .Energy-Minimized Scheduling of Real-Time Parallel Workflows on Heterogeneous Distributed Computing Systems[J].IEEE Transactions on Services Computing, 2021, PP(99):1-1.DOI:10.1109/TSC.2021.3054754.

🍅更多免费数学建模和仿真教程关注领取