实时人工智能驱动的监控技术，用于多节点异构系统中的高效能源调度

《Future Generation Computer Systems》：Real-Time AI-Powered Monitoring for Energy-Efficient Scheduling in Multi-Node Heterogeneous Systems

　　塔哈·阿卜杜勒阿齐兹·拉赫马尼（Taha Abdelazziz Rahmani）| 加莱姆·贝拉莱姆（Ghalem Belalem）| 西迪·艾哈迈德·马哈茂迪（Sidi Ahmed Mahmoudi）| 拉菲克·奥马尔·梅拉德·布迪亚（Rafik Omar Merad Boudia）
罗马智慧大学（University of Roma Sapienza）计算机科学系，意大利罗马维阿莱·雷吉娜·埃莱娜（Viale Regina Elena）295号，邮编00161

**摘要**
负载均衡对于维持计算系统的稳定性和实现最佳性能至关重要。其重要性在各个计算领域得到了广泛认可，尤其是在异构系统的背景下。这些系统由具有不同计算能力和架构的计算设备组成，每种设备都针对特定的工作负载进行了优化。这种异构性引入了动态资源限制、架构不匹配以及不可预测的任务-设备亲和性，从而加剧了负载均衡的挑战。本文提出了一种基于人工智能的负载均衡解决方案，用于实时分布式异构系统。我们的方法持续监控系统状态，捕捉影响性能的关键因素，如任务和设备特性。利用基于人工智能的模型，根据收集的数据为每个设备计算出一个动态负载指数。通过这种负载估计，该方法通过一种新颖的不平衡度量标准预测潜在的不平衡，并主动将传入的应用程序调度到最合适的设备上，以确保系统范围内的平衡。为了验证我们的方法，我们首先通过比较多种机器学习算法和特定于设备的深度学习模型来评估预测模型，后者取得了更高的准确性。然后，我们将我们的方法与多种工作负载下广泛使用的调度技术进行了对比。结果表明，我们的方法实现了更平衡的工作负载分布、更快的执行速度、更高的吞吐量、更好的资源利用率以及更低的能耗，展示了其在动态条件下的适应性和在现实世界环境中的适用性。

**1. 引言**
数据密集型应用（如人工智能（AI）和物联网（IoT）的快速发展产生了前所未有的数据量，使得传统的仅依赖CPU的系统不堪重负。为了满足这些需求，现代计算平台集成了更强大的加速器，尤其是图形处理单元（GPUs）。这种集成将原本同构的基于CPU的架构转变为异构系统，在这些系统中，CPU和GPU在多个节点上协同工作。在这些CPU-GPU异构系统中，GPU作为CPU的协处理器，利用它们的互补优势：GPU擅长数据并行、计算密集型任务，而CPU则高效处理顺序性和对延迟敏感的操作。

虽然异构计算通过高效执行多样化的工作负载增强了灵活性，但由于架构差异和不可预测的任务-设备亲和性，它也引入了重大挑战。仅仅依赖应用程序与设备的适应性往往会导致强大设备过载，而其他设备则利用率不足。为了说明这个问题，图1概念性地展示了在一个异构集群中执行CPU适用和GPU适用的应用程序时的两种工作负载分布情况。在第一种情况下，仅考虑设备适应性的调度器倾向于将大多数计算密集型任务分配给GPU，如图所示。结果，GPU的队列因需要大量计算时间的任务而过载，而CPU则因较早完成较轻的工作负载而处于空闲状态。这种不平衡是由于忽略了当前的负载状况和工作负载特性造成的，导致执行时间延长、吞吐量降低和能耗增加。相比之下，图2展示了在分配任务时同时考虑设备适应性和当前负载所实现的平衡状态。通过将GPU的部分工作负载卸载到空闲的CPU上，调度器实现了更高的设备利用率、更低的响应时间和更高的吞吐量以及更好的能源效率。

**2. 背景**
GPU在各种计算系统中的日益广泛应用，引发了人们对CPU-GPU异构系统研究的兴趣。这一转变归因于GPU的可访问性和简化编程性，当GPU与CPU同时使用时，它们为通用计算提供了显著的优势。

**2.1. 编程异构系统**
在异构系统中，应用程序通常遵循主机-内核模型（host-kernel model）进行开发[11]。在这种模型中，代表应用程序并行组件的内核在包括CPU和GPU在内的各种设备上执行计算操作。另一方面，主机管理应用程序的顺序方面，协调内核在设备间的执行，并且仅在CPU上运行。OpenCL[12]是一个广泛采用的异构系统编程框架。在OpenCL范式中，内核代码通过启动多个线程（称为工作项，work-items）来执行，每个工作项代表内核的一个实例。这些工作项被分组到工作组中，每个工作组在单个计算单元上执行。OpenCL允许单个内核的工作组独立运行，不同的工作组可以在不同的设备上执行。

在异构系统中调度应用程序可以通过两种方法实现：数据并行（data-parallel）和任务并行（task-parallel）[13]。数据并行方法允许单个应用程序的内核在多个设备上同时执行，而任务并行方法将每个内核分配给单个设备。选择合适的调度方法至关重要，这取决于应用程序的计算需求和系统内设备的性能[5]。在单个设备上执行大量数据的应用程序可能会导致性能瓶颈，因为内存和处理能力有限。在这种情况下，采用数据并行方法至关重要，因为它可以在多个设备之间分配工作负载，从而减少任何单个设备的计算负担。然而，数据并行方法实现起来更为复杂，因为它们需要额外的机制来根据每个设备的性能进行最优的数据划分。此外，整体加速效果必须能够抵消数据划分和设备间传输所带来的开销[2]。

相比之下，任务并行方法实现起来更简单，传输开销最小，因为数据仅在应用程序执行的开始和结束时传输。然而，这些方法适用于数据量较小的应用程序[2]。

**2.2. 负载均衡**
负载均衡确保工作负载在计算资源之间均匀分布，从而优化系统性能。实时实现这种负载均衡特别具有挑战性，因为它需要处理工作负载的动态特性以及硬件组件的多样化能力。现有编程框架中缺乏内置的调度机制，进一步复杂化了这一过程，迫使开发人员在低级别手动管理同步。因此，最初为同构系统设计的传统策略变得不足够，突显了需要能够适应动态和复杂执行条件的上下文感知调度器的需求。

持续监控设备负载对于异构系统中的有效负载均衡至关重要。它允许调度器在任务分配时主动防止过载，从而消除了应用程序迁移的需要。相比之下，反应式策略（如工作窃取调度器[1]）依赖于将任务从过载设备迁移到负载不足的设备，这会在执行时间和带宽消耗方面引入大量开销[2]。然而，准确的监控需要一个精确的、上下文感知的设备负载定义，该定义能够捕捉设备能力和应用程序需求之间的相互作用。架构特性（如内存层次结构）决定了设备的计算能力，而应用程序特性（如算术强度）定义了工作负载需求。这些因素的任何变化都必须动态地反映在负载测量中；否则，调度器可能会做出不准确的评估，导致工作负载分配不高效和性能不佳。

以往的研究通常使用总处理数据字节数[3]或CPU/内存利用率[4]等指标来定义设备负载。然而，这些指标仅关注当前正在执行的应用程序，而忽略了排队中的工作负载。待处理的应用程序仍然占据执行管道中的位置，一旦启动就会消耗处理资源，从而延迟后续任务。忽略排队中的工作负载会导致对设备利用率的评估不完整，可能会使调度器使已经负担过重的设备过载。因此，尽管这些指标对性能评估有用，但它们不适合异构系统中的实时调度[5]。

为了解决这个问题，我们将负载定义为在给定设备上执行所有当前待处理应用程序所需的总时间。这种定义提供了精确的负载度量，因为执行时间反映了设备和应用程序的特性。然而，这种方法需要预先知道执行时间，而这在提交时是不可用的[6]。为了克服这一限制，我们预测应用程序的执行时间来计算设备负载。执行时间预测可以使用两种方法：传统方法和人工智能方法。传统方法依赖于手动计算，往往产生不太准确和可靠的结果[7]。相比之下，人工智能预测器即使在高度动态的工作负载和更大规模的应用场景（如云数据中心的工作负载预测[8]、[9]）中也表现出强大的有效性。人工智能方法能够捕捉应用程序和设备特性之间的复杂关联，从而实现更高的预测准确性。

然而，仅监控单个设备负载只能提供局部状态信息，而无法捕捉系统范围内的负载分布。评估整个负载分布需要一个指标，该指标能够量化所有可用设备之间的负载差异，代表整个系统的不平衡。以往的研究主要将不平衡定义为性能评估指标，而不是监控工具。例如，[10]中提出的不平衡度（DI）衡量了负载最重和最轻的设备与平均值之间的偏差，重点关注最坏情况，以防止极端过载或负载不足。在这项工作中，我们将不平衡定义为所有设备与平均负载的累积偏差。这种定义使调度器能够在分配新任务时捕捉完整的工作负载分布，并积极减少系统不平衡。与仅关注极端情况的DI不同，我们的指标能够惩罚系统中分布的小负载差异，允许更细粒度的优化。当最大和最小负载接近时，DI可能会忽略这些不平衡，而许多设备仍然适度偏离平均值。

本文介绍了Smart-Balance，这是一种新颖的基于人工智能的调度框架，可以实时主动缓解多节点CPU-GPU异构系统中的负载不平衡。Smart-Balance利用人工智能模型预测负载、计算系统不平衡，并将每个应用程序分配到能够最小化该指标的设备上，确保系统内的工作负载均衡。

**3. 方法论**
在本研究中，我们的主要贡献包括：
- 对多种机器学习（ML）模型与特定于设备的深度学习（DL）模型进行比较评估，以预测应用程序的执行时间。
- 将人工智能技术集成到实时异构系统中，解决应用程序调度和负载监控中的挑战。
- 识别并实证验证影响异构系统负载均衡的关键因素。
- 引入一种新的不平衡度量标准用于负载监控。
- 适应来自不同领域的现有负载均衡技术来验证我们的方法。

**4. 实验与结果**
本文的后续部分结构如下：第2节提供了关于异构系统、负载均衡和相关研究的背景信息。第3节介绍了我们提出的负载均衡调度器。第4节讨论了设备数据集的构建和执行时间预测模型的训练。第5节详细介绍了实验结果。最后，第6节总结了我们的工作，并讨论了未来研究的潜在改进方向。

**5. 结论**
GPU在各种计算系统中的日益广泛应用，引发了人们对CPU-GPU异构系统研究的兴趣。这一转变归因于GPU的可访问性和简化编程性，当GPU与CPU同时使用时，它们为通用计算提供了显著的优势。任务被分配给预计完成速度最快的处理单元。负载均衡：[17]文献的作者探讨了异构系统中数据并行应用的不同负载均衡技术，包括静态、动态和H引导的方法。静态负载均衡算法将整个工作负载划分为与系统中设备数量相匹配的包。每个设备接收到的包量与其在给定时间单位内可以执行的工作量成正比。相反，动态算法将总工作负载分割成更多数量相等的小包。最初，每个设备执行一个包。完成指定包的执行后，设备继续按顺序执行后续包。如果某个设备处于空闲状态且队列中没有更多包可用，它会从负载过重的设备那里“抢夺”包。另一方面，H引导的负载均衡方法使用与动态方法相同的算法来分配包，但采用不同的方法来确定包的大小。与动态方法不同，H引导算法会不断减小包的大小。[18]文献的作者提出了一种用于优化单节点异构计算系统的调度方法。他们结合了AI规划启发式方法和机器学习来确定接近最优的系统配置，包括CPU线程数、GPU线程数以及CPU和GPU之间的工作负载分配。AI规划启发式方法引导搜索过程，以找到在高性能和低能耗之间提供最佳平衡的配置，从而显著减少需要评估的配置数量。PDAWL（基于轮廓的AI辅助动态调度）[19]是一种针对单节点异构系统的混合调度方法。该方法整合了多个组件来优化工作负载分配，结合了在线调度、应用程序分析、数学建模和离线机器学习预测。PDAWL调度器根据分析的应用程序执行数据和历史性能记录动态调整工作负载。它使用数学模型根据这些历史记录预测各种工作负载的执行时间，从而实现计算资源的粗粒度选择。同时，用历史性能数据训练的机器学习模型可以更准确地预测性能与能耗之间的关系。2.3.2. 任务并行方法性能优化KubeSCRTP [20]是一个基于机器学习的Kubernetes框架调度器，用于最小化应用程序的执行时间。它使用预训练的ML模型将应用程序动态分类为两类：快速执行和慢速执行。快速执行的应用程序被分配给CPU，而慢速执行的应用程序则被卸载到GPU。[21]文献提出了一种针对异构系统中OpenCL程序的调度策略。该策略通过考虑应用程序的属性（如指令计数）和硬件的配置来预测每个应用程序最适合的设备。随后，调度器将每个应用程序分配到预测的设备上。[11]文献的作者介绍了一种优化CPU/GPU异构系统中应用程序执行的调度器。该调度器根据在GPU上运行应用程序相比CPU时的加速比动态分配应用程序。利用机器学习预测加速比，如果预测的加速比超过“1”，则将应用程序分配给GPU；否则，应用程序被分配给CPU。[22]是一个针对异构HPC集群的AI驱动、节能型调度框架。它使用关键作业指标（例如提交时间和请求的核心数）和节点特性（例如功耗、可用性和时钟频率）作为深度神经网络的输入特征，以过滤掉不可行的作业-节点配对（例如，当作业超出节点容量时）。随后，InEPS方法应用深度强化学习来选择最佳调度配置，以最小化作业的能耗。[23]是一个针对异构系统中不规则工作负载的动态调度框架。它使用多个机器学习模型来预测内核执行时间、通信成本和能耗。然后，该方法评估所有调度配置并选择最佳平衡性能和能耗的配置。负载均衡“Troodon”[24]调度器使用机器学习分类器将应用程序分为适合CPU和适合GPU的池。然后根据回归机器学习模型预测的加速比对每个池中的应用程序进行排序。适合CPU的池按加速比升序排序，适合GPU的池按降序排序。两个池合并后，适合CPU的池位于顶部。池顶部的应用程序被分配给CPU，底部的应用程序被分配给GPU。“Troodon”将应用程序分配给设备，直到满足每个设备的预计负载。如果设备无法达到其预计负载，它会将不合适的应用程序分配给该设备。[25]文献的作者为具有多个CPU和GPU的单节点异构系统引入了一种设备适用性分类器。该分类器使用机器学习模型预测运行每个OpenCL应用程序最快的设备。随后，调度器在预测的更快设备上执行每个应用程序。[1]文献提出了一种针对单节点异构CPU-GPU系统的任务窃取调度器。调度器使用基于机器学习的预测器来估计应用程序在CPU和GPU上的执行时间，并将任务分配给最适合的设备。系统在运行时动态重新分配任务，从负载过重的设备的队列中窃取任务，并将其分配给空闲的设备。[26]文献的作者介绍了“RTLB_Sched”，这是一种针对实时CPU-GPU异构系统的机器学习驱动的负载均衡器。“RTLB_Sched”通过使用ML模型动态估计设备负载并分配应用程序来优化资源分配，防止工作负载不平衡，确保系统平衡和高效。[27]文献的作者研究了高效负载均衡对系统性能的影响。他们引入了“HBalancer”，这是一种机器学习驱动的调度器，通过选择最佳调度配置来预测和缓解负载不平衡。通过实现更好的负载分配，“HBalancer”减少了应用程序的响应时间。[28]文献对集群式Web服务器领域常见的负载均衡策略进行了比较分析。这些策略包括轮询、加权轮询和最少连接。这项研究的主要目的是评估这些方法在不同服务器节点之间分配用户请求的效率。[28]文献提出了一种称为优先级加权轮询（PWRR）的新调度技术，用于医疗监控系统。PWRR为数据分配优先级，以确保关键信息首先传输。它使用加权轮询（WRR）调度在不同设备之间公平分配可用带宽。在WRR中，每个设备被分配一定的时间来传输数据。权重较高的设备获得更多带宽。如果设备在分配的时间内无法传输所有数据，剩余数据会被排队并在下一轮传输。[29]文献对云Web服务的加权轮询负载均衡方法进行了全面评估。他们根据服务器的规格（如CPU速度和内存）为其分配不同的权重。研究表明正确的权重分配对整体系统性能有影响。[30]论文在虚拟云环境中为流行的负载均衡算法（如轮询和最短作业优先）提供了实验设置。这项研究的主要目的是在模拟云环境中比较这些算法的性能。[31]文献在Web集群系统中实现了加权最少连接（WLC）调度算法。所提出的算法为连接较少的服务器分配更高的权重，从而通过确保连接较少的服务器更有可能被选为新请求来改善负载均衡。它还解决了传统最少连接算法导致服务器过载的问题，通过暂时将其从调度列表中排除。[2.3.3. 讨论]本节介绍的研究调查了异构系统中不同的任务调度方法。数据并行调度策略将应用程序的工作组分布在多个设备上。与设备之间划分内核和传输数据相关开销可能很大。因此，数据并行方法的可行性取决于应用程序具有足够高的计算需求以抵消这些开销。相比之下，任务并行方法特别适合计算强度较低的应用程序。这些方法允许系统容纳更多的用户应用程序，因为每个设备可以分配不同的内核，而不是限制整个系统一次只执行一个内核。这种方法也适用于数据依赖性不规则的应用程序，因为设备可以独立处理自己的数据。[11]、[20]、[21]和[25]的工作主要集中在最小化应用程序的执行时间上。另一方面，[22]和[23]的工作将任务分配给能够最小化能耗的设备，以牺牲性能来换取能源效率。然而，这些方法通常优先考虑单个任务的优化，而忽视了当前的工作负载分布。结果，某些被优先分配任务的设备可能会过载，导致排队时间延长、响应时间增加和整体能耗增加。[24]中介绍的调度器将所有应用程序分组到一个作业池中，不考虑它们的提交时间和顺序。这种方法假设每个应用程序的处理需求是已知的，并将它们分类为适合CPU或适合GPU。然而，这种分类仅依赖于计算能力（以FLOPS衡量），忽略了制造商特定的特性。实时系统必须应对动态和不可预测的提交。由于应用程序到达的时间不规律，提前预测所有任务的计算需求是不可行的。因此，在这些环境中依赖预计算工作负载数据的解决方案是不切实际的。[6]、[28]、[29]和[31]的研究调查了各种负载均衡策略。其中，[28]、[29]和[30]采用了静态方法（如轮询和加权轮询）来分配应用程序。虽然简单，但这些静态方法缺乏对变化工作负载的适应性。[6]和[31]使用动态方法（包括最少连接和加权最少连接）来更公平地分配请求。然而，这些方法往往忽略了单个请求的独特特性。[26]、[27]和[1]中提出的负载均衡方法通过考虑所有关键特征来解决许多这些问题，以实现异构系统中设备之间的公平负载分配。尽管如此，这些方法是为单节点CPU-GPU系统设计的，不能直接应用于更复杂的配置。总之，所讨论方法的局限性包括：-代码分割：实现困难且引入额外的时间开销。-忽略负载均衡。-缺乏系统状态监控。-应用程序顺序提交到作业池中。-需要先验知识。-过度简化了异构性，忽略了设备能力和应用程序需求的差异。在下一节中，我们将讨论我们的解决方案，该解决方案解决了这些局限性，并利用异构系统的优势来提高系统性能。3. Smart-Balance在本节中，我们介绍了我们提出的调度器Smart-Balance。我们提供了系统架构、数学模型和调度算法的详细信息。3.1. 系统架构在实时异构系统中，应用程序不断提交以供执行。调度器必须迅速将它们分配给计算设备以最小化开销。每个提交的应用程序都有与可用设备数量相等的调度选项。对于每个选项，调度器在实际分配之前预测可能产生的系统不平衡（见第3.2节）。然后，应用程序被分配给能够最小化不平衡的设备。图2显示了Smart-Balance的架构工作流程，它分为两个阶段：1. 预测阶段：调度器通过以下步骤估计将应用程序分配给每个设备可能产生的不平衡：-用户使用提供的脚本编译他们的应用程序，该脚本在编译过程中提取关键的应用程序特征。为了保护隐私，用户提交的是编译后的代码以及提取的特征，而不是源代码。-调度器使用预训练的深度学习模型Execution Time Predictor，根据提取的特征来估计应用程序在所有可用设备上的执行时间。-利用预测的执行时间和设备负载，调度器计算每个设备的潜在不平衡，并选择不平衡值最低的选项。

2. 调度阶段：
- 应用程序被分配到选定的设备上执行，并更新该设备的负载。

下载：下载高分辨率图片（286KB）
下载：下载全尺寸图片
图2. 智能平衡

3.2. 数学模型
表1提供了用于描述解决方案数学模型的符号。

表1. 符号
描述
ASubmitted 提交的OpenCL应用程序
F提交应用程序的代码特征
n系统设备的数量
nbr提交的应用程序总数
totalTime执行所有提交应用程序所需的总时间
sched调度器的队列
Time应用程序在所有系统设备上的预测执行时间列表
Timeij应用程序i在设备j上的预测执行时间
Fi应用程序‘i’的OpenCL内核代码特征列表
Loadj节点‘j’的负载
Qj节点‘j’队列中的应用程序数量
Balance系统的平均负载
Imbalance系统的不平衡
Timeactivej设备‘j’的活跃时间
Timeidlej设备‘j’的空闲时间
Eactivej节点‘j’在执行任务时每秒消耗的能量
Eidlej节点‘j’在空闲时每秒消耗的能量

为了计算设备‘j’的负载，我们汇总了当前在该设备上排队等待执行的所有应用程序的预测执行时间。这包括所有尚未完成的任务。正式定义如下：
(1) Loadj=∑i=0Qj?1Timeij

为了量化工作负载分配的不平衡，我们提出了一个不平衡指标，定义如下：
在一个平衡的系统中，所有设备的负载是相等的：
(2) Load1=Load2=...=Loadn
通过汇总所有设备的负载，我们得到：
(3) ∑j=1nLoadj=n×Loadi,?i∈[1,n]

因此，为了使系统平衡，每个设备的负载必须等于平均值Balance：
(4) Balance=1n∑j=1nLoadj

我们将“不平衡”指标定义为每个设备负载与“平衡”值的累积绝对偏差：
(5) Imbalance=∑j=1n∣Loadj?Balance∣

在计算出所有潜在调度选项的不平衡并选择不平衡最小的设备后，所选设备的负载更新如下：
(6) LoadminImabal=LoadminImabal+TimeminImabal

3.2.1. 优化不平衡
计算每个候选设备的不平衡需要遍历所有设备，在每次假设分配后重新计算偏差。这导致每个设备的时间复杂度为O(n)，因此每个应用程序的时间复杂度为O(n2)，在大规模系统中计算成本较高。

为了降低这种成本，我们利用了这样一个事实：在将应用程序分配给设备k之后，只有该设备的负载和系统平衡会发生变化。这使我们能够重用预先计算出的总和，而无需重新计算不平衡。

在每次调度决策开始时，我们首先计算当前的平衡（公式4），以及每个设备与平衡的偏差：
(7) Devj=Loadj?Balance

然后我们根据符号对这些偏差进行分组，并计算它们的总和和计数：
偏差总和：
(8) sumPos=∑Dj>0Dj
sumNeg=∑Dj<0Dj
正偏差、负偏差和零偏差的计数：
(9) cp=|Dj>0|, cn=|Dj<0|, cz=|Dj=0|

所有五个值都在同一个循环中计算，成本为O(n)。

当假设将具有预测执行时间Timei,k的应用程序分配给设备k时，新的负载变为：
(10) Loadk′=Loadk+Timei,k

这会使平衡变为：
(11) Balance′=Balance+Timei,k

设备k和j ≠ k的偏差更新为：
(12) Devk′=Devk+Timei,k?shift
Devj′=Devj?shift

分配后的候选k的不平衡变为：
(13) Imbalance′=∣Devk′∣+∑j≠k∣Devj?shift∣

假设在减去shift后，j ≠ k的设备偏差不会变为负值：
每个零Devj偏差变为shift
每个正Devj偏差变为Devj?shift
每个负Devj偏差变为?Devj+shift

(14) Imbalance(1)′=∣Devk+Timei,k?shift∣+shift·cz(?k)+(sumPos(?k)?shift·cp(?k))+(?sumNeg(?k)+shift·cn(?k))

其中上标(?k)表示从相应的总和和计数中移除了设备k。

然而，某些设备的Devj < shift将从正偏差变为非正偏差。对于每个这样的设备，偏差项被错误地计算为Devj?shift，而不是正确的值shift?Devj。每个交叉设备的结果误差为：
(15) ?(Devj?shift)+(shift?Devj)=2·(shift?Devj)

对所有交叉设备求和，其中ccross表示它们的计数，sumCross表示它们的偏差总和，得到修正值：
(16) 2·(ccross·shift?sumCross)

因此，确切的不平衡变为：
(17) Imbalance′=Imbalance(1)′+2·(ccross·shift?sumCross)

天真地计算ccross和sumCross需要遍历每个候选设备的所有正偏差，这会重新引入原来的O(n2)复杂度。为了避免这种情况，我们维护了一个平衡搜索树，其中包含所有正偏差Devj > 0以及每个节点的子树计数和总和。构建树需要O(n · logn)，因为插入每个设备并更新相应的子树统计信息需要O(logn)。

一旦树构建完成，可以通过从根到叶子的遍历来在O(logn)时间内查询偏差小于或等于给定shift的设备数量和总和。这种优化在常见情况下将不平衡评估的时间复杂度降低到O(n)，在最坏情况下降低到O(n · logn)。

为了进一步优化算法，我们利用了这样一个事实：在每次调度步骤中，只有所选设备的偏差会发生变化。这种更新可以在O(logn)时间内应用到树上。所有其他设备的偏差都会统一地移动相同的偏移量?shift。因此，我们不需要单独更新每个值，而是维护一个全局偏移量变量，在每次调度决策时递增它，然后设备的偏差由Devj?globalShift给出。

3.2.2. 性能指标
为了评估系统的性能，我们考虑了几个关键指标：
1. 总不平衡：该指标计算了整个实验过程中的累积不平衡，作为系统全局负载平衡的指标。
(18) totalImbalance=∫t0tnimbalance

2. 吞吐量：该指标量化了单位时间内执行的应用程序数量[24]。它直接反映了系统的生产力：更高的吞吐量表示在同一时间框架内完成了更多的工作负载，意味着服务了更多的用户。
(19) throughput=nbrApptotalTime

3. 总资源利用率：该指标表示所有设备的平均利用率[32]。
(20) Utilization=1n∑i=1nTimeactiveitotalTime

4. 设备的能耗是使用其活跃和空闲能耗计算的，以瓦特为单位。
设备‘j’的活跃能量是设备在执行计算任务时消耗的总能量：
(21) Energyactivej=Timeactivej×Eactivej
设备‘j’的空闲能量是设备在空闲状态时消耗的总能量：
(22) Energyidlej=Timeidlej×Eidlej
设备的总能耗是：
(23) Energyj=Energyactivej+Energyidlej

因此，所有系统设备的总能耗是：
(24) Energy=∑j=1nEnergyj

3.3. 调度算法
Smart-Balance调度器（算法1）将应用程序分配到设备上，以最小化系统不平衡。调度过程首先将应用程序及其相关特征插入队列，并根据提交时间对它们进行排序（第1-2行）。对于从队列中检索的每个应用程序，使用为此目的设计的预训练深度学习模型ExecutionTimePredictor来预测其在所有设备上的执行时间（第5行）。

下载：下载高分辨率图片（128KB）
下载：下载全尺寸图片
算法1. 智能平衡

对于每个调度决策，调度器首先预计算当前系统状态，包括平衡、每个设备与这个平衡的偏差，以及正偏差、负偏差和零偏差的聚合总和（(7), (8), (9)）。这些值为高效的不平衡评估奠定了基础（第7行）。然后调度器将正偏差集合存储在一个平衡搜索树中（第9行）。

对于每个候选设备，调度器使用预计算的总和来估计如果将应用程序分配给该设备将导致的不平衡（见第3.2节）。具体来说，调度器查询树Cross以确定应用偏移后交叉的偏差数量和总和（第14行）。如果没有交叉发生（第15-16行），则直接使用公式14计算不平衡。否则，根据公式17应用修正（第19行）。

最后，选择预测不平衡最小的设备（第21-24行），将应用程序分配给它（第27行），并相应地更新系统状态（第28行）。如第3.2节中的数学模型所详述，可以通过使用全局偏移量进一步优化此更新（第29行）。这个过程重复进行，直到调度队列中的所有应用程序都被调度完毕。

4. 执行时间预测
构建执行时间预测模型涉及四个关键阶段：数据集准备、模型训练和模型测试。数据集准备阶段包括创建数据集，然后对其进行预处理，以确保它适合训练模型。集群中的每个计算设备都有针对其硬件特性定制的预测模型，这些模型是在不同的数据集上训练的。

4.1. 数据集创建
本研究中使用的数据集是使用PolyBench基准套件[33]构建的，该套件包含多个计算领域的OpenCL并行应用程序，包括线性代数、线性代数求解器、数据挖掘和模板计算。这些应用程序表现出不同的计算和内存访问模式，导致在不同配置下设备的适用性不同。

为了确保数据集内的多样性，我们在一系列输入数据大小上执行了每个应用程序，并记录了其相应的执行时间。这产生了一个数据集，其中包含应用程序的代码特征及其测量的执行时间，作为训练的目标变量。

4.1.1. 特征提取
为了表示每个应用程序，我们提取了一组18个OpenCL内核代码特征，这些特征捕获了影响应用程序在设备上执行时间的各种特性。这些特征列在表2中。

表2. OpenCL的代码特征
特征提取
提取方法
输入数据大小
RegExp减法
LLVM返回
LLVM函数调用
LLVM控制
LLVM函数
LLVM内存加载
LLVM指令块
LLVM内存存储
LLVM整数操作
RegExp乘法
LLVM浮点操作
RegExp除法
LLVM总指令数
LLVM条件
LLVM循环操作
LLVM加法
LLVM循环
LLVM

这个过程是使用我们开发的特征提取脚本执行的，该脚本结合了低级虚拟机（LLVM）传递[34]和正则表达式。LLVM提供了程序的可理解中间表示（IR），我们使用自定义的LLVM传递从中提取了15个特征。其余3个特征是通过直接从内核源代码解析正则表达式提取的。整个特征提取工作流程如图3所示。

下载：下载高分辨率图片（165KB）
下载：下载全尺寸图片
图3. 代码特征提取器

4.1.2. OpenCL应用程序执行
每个OpenCL应用程序在每个设备上执行了2000次，输入数据大小各不相同。总共为每个设备生成了40,000个样本，形成了训练执行时间预测模型的基础。

4.2. 数据集预处理
数据预处理将原始数据转换为适合机器学习的格式。这包括数据清洗、格式化和特征选择。在我们的研究中，我们使用PyCaret[35]库来预处理数据集并构建ML预测模型。

4.2.1. 特征选择
特征选择是从数据集中识别和提取最相关特征的过程，这些特征显著影响模型的预测性能。这个过程通过排除冗余和不太相关的特征来减少数据集的维度[36]，从而带来几个优势，例如更快的训练时间、更好的可解释性和更高的预测准确性。此外，它通过减少模型对噪声和不相关数据模式的暴露来降低过拟合的风险。

总之，特征选择可以提高预测准确性和模型鲁棒性。在我们的研究中，我们采用了三种互补的技术来进行特征选择，以确保提取最相关的特征：
- 通过基于它们对模型性能影响的决策树分析对特征进行排名。
- 递归特征选择，以确定实现模型最高性能的最佳特征数量。
- 相关性分析，以验证前几阶段中选择的特征。这确保所选特征不是冗余的。

决策树特征重要性排名
基于决策树的特征重要性排名量化了每个特征对模型预测能力的贡献。根据重要性分数为特征分配排名，最重要的特征具有最高的排名[36]。结果特征排名如图4所示。

下载：下载高分辨率图片（165KB）
下载：下载全尺寸图片
图4. 特征排名

递归特征选择
递归特征选择（RFS）是一个迭代训练过程，每次迭代从数据集中移除一个特征。在每次迭代中，使用剩余的特征重新训练模型，并使用决定系数（R2）评估其性能。这个过程持续进行，直到没有特征剩余[37]，从而识别出对模型性能影响最大的最重要特征。这个过程的结果如图5所示。

下载：下载高分辨率图片（94KB）
下载：下载全尺寸图片
图5. 递归特征选择

相关性分析
相关性分析是一种统计方法，用于量化数据集内特征之间的关系。它用于通过识别表现出强相关性的特征来检查这些特征之间的依赖性[24]。高度相关的特征提供相似的信息，导致冗余，从而降低准确性、增加训练时间和过拟合。过拟合发生在模型仅针对训练数据进行了调整，而无法泛化到新数据时。消除相关特征可以防止模型学习训练数据的特定模式，从而创建出更准确且更具泛化能力的模型。图6展示了表2中列出的特征之间的相关矩阵。值得注意的是，它识别出了一些相关性值超过0.9的特征对，这些特征包括：-(“Control”，“Blocks”)-(“Load”，“Total instructions”)-(“Store”，“Blocks”)-(“Total instructions”，“Integer operations”)-(“Loop instructions”，“Loops”)。下载：下载高分辨率图片（484KB）下载：下载全尺寸图片。图6. 相关矩阵。

4.2.2. 选定的特征
递归特征选择过程的结果表明，排名前10的特征能够产生最高的模型准确率。这些特征根据其重要性得分被选中，代表了最佳预测子集。表3列出了通过决策树分析最初排名的前10个特征。重要的是，相关性分析确认这些特征之间没有高度相关性，从而验证了它们的选择，并确保了数据集内的冗余最小化。表3. 选定的OpenCL特征。

4.3. 模型训练
在本节中，我们使用机器学习（ML）和深度学习（DL）技术开发了回归模型来预测应用程序的执行时间。回归是一种用于预测连续值的基本AI方法，用于构建这些模型。这些模型可以在任何外部机器上进行训练，之后可以与调度器一起部署在系统中。随后，我们评估并比较这些模型的性能。

4.3.1. 机器学习预测模型
每个数据集被分为三个不同的子集：训练集占数据集的80%，验证集占10%，测试集占剩余的10%。
机器学习模型是使用PyCaret库开发的。PyCaret自动训练多种回归算法，并使用交叉验证来比较它们的性能。在此阶段确定的性能最好的三个模型使用组合的训练和验证集进行了重新训练。最佳模型在测试集上的最终结果如表4所示。该表报告了测试集的均方误差（MSE）和决定系数（R2）值。

表4. ML时间预测模型的测试结果。
| 设备 | MSE | R2 |
|--------------|-----------|-----------|
| CPU1 | 1.512e-3 | 0.9498 |
| GPU1 | 2.916e-3 | 0.9529 |
| CPU2 | 7.744e-3 | 0.9612 |
| GPU2 | 4.489e-3 | 0.9427 |
| CPU3 | 2.560e-3 | 0.9339 |
| GPU3 | 5.320e-3 | 0.9273 |

MSE指标通过计算预测值与实际值之间的平方差的平均值来评估预测准确性。另一方面，R2指标表示模型表示数据的有效性。较高的R2值表示更好的拟合度，而较小的MSE值表示更高的准确性[38]。因此，对于每种设备来说，最佳预测模型具有最高的R2值和最低的MSE值。

4.3.2. 深度学习预测模型
为了实现神经网络预测模型，我们使用了Keras库[39]。Keras提供了一个高级接口，用于构建和训练深度学习（DL）模型。它是基于TensorFlow[40]构建的，TensorFlow是一个广泛使用的框架，提供了构建和训练DL模型的强大工具。
在我们的实验中，我们为每个深度学习模型配置了以下训练参数：500个周期、Adam优化器、学习率为0.001以及批量大小为64。
深度多层感知器（DMLP）模型的架构如表5所示。每个模型在其隐藏层中使用修正线性单元（ReLU）函数作为激活函数。这些模型的超参数经过手动微调以达到最佳性能。

表5. DL模型架构。
| 层次 | CPU1 | GPU1 | CPU2 | GPU2 | GPU3 |
|--------------|-----------|-----------|-----------|-----------|
| 1 | 10 | 10 | 10 | 10 |
| 2 | 8 | 6 | 8 | 6 |
| 3 | 7 | 5 | 5 | 7 |
| 4 | 5 | 4 | 4 | 5 |
| 5 | 1 | 1 | 1 | 1 |

为了评估深度学习模型在训练期间的性能，我们使用了均方误差（MSE）作为损失函数。图7、8、9、10、11和12展示了深度学习预测模型的训练和验证损失曲线。训练集（蓝色）和验证集（橙色）的损失曲线随时间逐渐减少并趋于零，表明模型有效地从训练数据中学习到了知识。两条曲线之间的紧密对齐表明模型能够很好地泛化到未见数据，没有过拟合或欠拟合的迹象。

下载：下载高分辨率图片（65KB）下载：下载全尺寸图片。图7. CPU1损失曲线。
下载：下载高分辨率图片（68KB）下载：下载全尺寸图片。图8. GPU1损失曲线。
下载：下载高分辨率图片（61KB）下载：下载全尺寸图片。图9. CPU2损失曲线。
下载：下载高分辨率图片（65KB）下载：下载全尺寸图片。图10. GPU2损失曲线。
下载：下载高分辨率图片（56KB）下载：下载全尺寸图片。图11. CPU3损失曲线。
下载：下载高分辨率图片（62KB）下载：下载全尺寸图片。图12. GPU3损失曲线。

为了评估DL模型的最终性能，我们在代表新数据和未见数据的测试集上对它们进行了评估。评估结果如表6所示。

表6. DL时间预测模型的测试结果。
| 设备 | MSE | R2 |
|--------------|-----------|-----------|
| CPU1 | 1.3456e-3 | 0.9633 |
| GPU1 | 2.500e-3 | 0.9684 |
| CPU2 | 2.916e-3 | 0.9787 |
| GPU2 | 3.844e-3 | 0.9523 |
| GPU3 | 2.528e-3 | 0.9497 |

总之，深度学习（DL）预测模型的表现优于传统的机器学习（ML）模型，实现了更低的均方误差（MSE）和更高的R2值。这些结果表明，DL模型提供了更准确的数据表示，并比ML模型提供了更精确的预测。

5. 性能评估
我们将调度器部署在一个由多个CPU和GPU组成的异构集群上。我们进行了一系列实验，使用不同的工作负载分布来评估调度器的性能及其在现实世界场景中的适应性和高效运行能力。

5.1. 实验设置
5.1.1. 系统
系统由一个主节点和三个工作节点组成，每个节点都配备了一个CPU和一个GPU。主节点负责在各个工作节点之间调度任务。集群的详细规格如表7所示。

表7. 异构集群。
| 节点 | 操作系统 | 内存 | CPU | GPU |
|--------------|------------|------------|------------|------------|
| Master | Ubuntu Desktop 22.04.1 LTS | 8 GB | Intel? Core? i5-6300 | Intel HD Graphics 520 |
| Worker 1 | Ubuntu Server 18.04.1 LTS | 8 GB | Intel? Xeon? E3-1225 v6 | NVIDIA GM107GL Quadro P620 |
| Worker 2 | Ubuntu Server 18.04.1 LTS | 8 GB | Intel? Xeon? E3-1225 v6 | NVIDIA GM107GL Quadro P400 |
| Worker 3 | Ubuntu Server 18.04.1 LTS | 8 GB | Intel? Core? i7-6700 | NVIDIA GM107GL Quadro K400 |

5.1.3. 工作负载
我们评估了20个具有五种输入大小的OpenCL应用程序，共生成了100个不同的作业。报告的结果是基于51次独立运行得出的平均值，以确保可靠性和平均稳定性。

5.1.4. 场景
为了模拟真实的计算场景，我们根据应用程序的计算需求设计了三种工作负载类型：
- 中等工作负载：输入规模相对较小的应用程序（1,000,000 – 10,000,000个浮点元素），通常更适合CPU。
- 重工作负载：输入规模较大的应用程序（10,000,000 – 100,000,000个浮点元素），通常更适合GPU。
- 混合工作负载：中等和重工作负载的应用程序的组合。

5.1.5. 基线
为了评估我们提出的调度技术的性能，我们将其与其他领域的几种基线调度策略进行了比较，包括一些改编自其他领域的策略：
1. 轮询（RR）：按轮询顺序将应用程序分配给设备。它在[6],[28],[30]中实现。
2. 加权轮询（WRR）：根据设备的处理能力为设备分配权重。权重较高的设备执行更多任务。WRR在[6],[28],[29]中实现。
- 计算设备权重：每个计算设备的权重与其计算能力成比例。所有设备的权重之和等于一[28]。在我们的系统中，我们根据每个设备的核心数量和频率来计算其权重。设备的权重按照公式(25)计算：
Weight = (Number of Cores / Total Number of Cores) * (Total Frequency / 2)
表8展示了系统设备的权重计算结果。数值四舍五入到小数点后两位。

表8. 权重计算。
| 设备 | 核心数量 | 频率 | 权重 |
|--------------|------------|------------|------------|
| CPU1 | 4 | 3.7 | 0.13 |
| GPU1 | 4 | 2.5 | 0.18 |
| CPU2 | 4 | 3.7 | 0.18 |
| GPU2 | 8 | 4 | 1.12 |
| GPU3 | 8 | 4 | 1.24 |

根据权重分配，在WRR中：
- CPU1、CPU2、CPU3每轮各接收一个应用程序。
- GPU3每轮接收两个应用程序。
- CPU1和GPU2每两轮交替接收一个和两个应用程序。

5.1.6. 设备适用性（DS）
我们使用DL模型预测每个任务在所有可用设备上的执行时间，然后将其分配给最快的设备。这种方法在[20],[21],[22],[23],[25],[45]中采用。

5.1.7. 最少连接数（LC）
在我们的LC版本中，它将任务分配给队列中应用程序数量最少的设备，而不是分配给连接最少的服务器。这种方法在[6]和[30]中提出。

5.1.8. 加权最少连接数（WLC）
该策略同时考虑了设备队列中的应用程序数量和其权重。应用程序被分配给连接数与权重比率最小的设备。这种方法在[31]中实现。

5.1.9. 指标
我们使用以下指标比较了我们提出的方法与基线方法的性能：
1. “不平衡”：该指标表示实验过程中特定时间的系统不平衡情况。
2. “总不平衡”：表示整个实验期间的累积负载不平衡。较低的总不平衡值表示整个实验期间的负载平衡更有效。
3. “完成时间”：表示在系统中执行整个工作负载所需的总时间。它表明系统处理分配给它的所有任务的快慢。
4. “设备活跃时间”：指每个设备完成分配给它的所有应用程序所需的时间。该指标有助于评估工作负载在设备之间的分布情况。
5. “设备空闲时间”：指每个设备在没有执行任何计算任务时的时间。该指标表明资源利用率不足和潜在的能量浪费。
6. “能耗”：该指标测量实验期间所有设备消耗的总能量。
7. “吞吐量”：该指标表示每秒执行的应用程序数量。更高的吞吐量表示系统更高效。
8. “系统利用率”：表示所有设备积极执行计算的时间百分比，提供了系统效率的总体衡量。

5.2. 实验结果
在报告Smart-Balance（S-Balance）、最少连接数（LC）、加权最少连接数（WLC）、设备适用性（DS）、轮询（RR）和加权轮询（WRR）方法的结果时，考虑了与执行时间预测相关的开销。

5.2.1. 不平衡
图13、14和15展示了不同工作负载场景下系统的负载不平衡曲线。时间已标准化，以便在五种调度器之间进行清晰比较。

下载：下载高分辨率图片（158KB）下载：下载全尺寸图片。图13. 中等工作负载的不平衡曲线。
下载：下载高分辨率图片（160KB）下载：下载全尺寸图片。图14. 重工作负载的不平衡曲线。
下载：下载高分辨率图片（144KB）下载：下载全尺寸图片。图15. 混合工作负载的不平衡曲线。
Smart-Balance方法随着应用程序数量的增加，负载不平衡始终趋于零。相比之下，其他方法显示出负载不平衡逐渐增加的趋势。这些结果突显了Smart-Balance在保持负载平衡方面的有效性。

5.2.2. 总不平衡
图16、17和18展示了整个实验期间累积的总负载不平衡情况。Smart-Balance方法在所有场景中的总不平衡程度最低。
- 对于中等工作负载，Smart-Balance分别比最少连接数、加权最少连接数、设备适用性、轮询和加权轮询减少了79%、81%、86%、78%、82%的总不平衡。
- 对于重工作负载，Smart-Balance分别比最少连接数、加权最少连接数、设备适用性、轮询和加权轮询减少了76%、72%、86%、78%、70%的总不平衡。
- 对于混合工作负载，Smart-Balance分别比最少连接数、加权最少连接数、设备适用性、轮询和加权轮询减少了76%、71%、86%、78%、70%的总不平衡。

下载：下载高分辨率图片（71KB）下载：下载全尺寸图片。图16. 中等工作负载的总不平衡。
下载：下载高分辨率图片（82KB）下载：下载全尺寸图片。图17. 重工作负载的总不平衡。
下载：下载高分辨率图片（72KB）下载：下载全尺寸图片。图18. 混合工作负载的总不平衡。

5.2.3. 完成时间
图19、20和21展示了完成提交的工作负载所需的总执行时间。在所有三种场景中，Smart-Balance方法都实现了最短的执行时间。
- 对于中等工作负载，Smart-Balance分别比最少连接数、加权最少连接数、设备适用性、轮询和加权轮询快2.1、2.5、2.25、2.2、2.47倍。
- 对于重工作负载，Smart-Balance分别比最少连接数、加权最少连接数、设备适用性、轮询和加权轮询快2.6、2.5、2.5、2.1倍。
- 对于混合工作负载，Smart-Balance分别比最少连接数、加权最少连接数、设备适用性、轮询和加权轮询快1.6、1.6、2.4、1.6、1.9倍。

下载：下载高分辨率图片（74KB）下载：下载全尺寸图片。图19.完成时间（中等工作负载）：
下载：下载高分辨率图片（68KB）
下载：下载全尺寸图片

图20. 完成时间（重工作负载）：
下载：下载高分辨率图片（58KB）
下载：下载全尺寸图片

图21. 完成时间（混合工作负载）：

5.2.4. 设备活跃时间
图22、23和24展示了每个计算设备的活跃时间。Smart-Balance方法实现了负载在设备间的公平分配，因为各设备的活跃时间接近相等。相比之下，其他方法在所有三种情况下都出现了负载过载的情况。
下载：下载高分辨率图片（144KB）
下载：下载全尺寸图片

图22. 中等工作负载下的设备活跃时间
下载：下载高分辨率图片（121KB）
下载：下载全尺寸图片

图23. 重工作负载下的设备活跃时间
下载：下载高分辨率图片（111KB）
下载：下载全尺寸图片

图24. 混合工作负载下的设备活跃时间

5.2.5. 设备空闲时间
图25、26和27显示了实验过程中设备的空闲时间。较长的空闲时间表明能源被浪费且负载分配不平衡。
下载：下载高分辨率图片（119KB）
下载：下载全尺寸图片

图25. 中等工作负载下的设备空闲时间
下载：下载高分辨率图片（100KB）
下载：下载全尺寸图片

图26. 重工作负载下的设备空闲时间
下载：下载高分辨率图片（112KB）
下载：下载全尺寸图片

图27. 混合工作负载下的设备空闲时间

Smart-Balance方法在所有设备上始终实现了最小的空闲时间，证明了其能够充分利用可用的计算资源。相反，其他方法显示出显著的空闲时间，表明资源利用效率低下。

5.2.6. 能源消耗
能源消耗是通过“perf”[46]（针对Intel设备）和“nvidia-smi”[47]（针对NVIDIA设备）来测量的。由于影响能耗的动态因素（如连接的外设、后台进程和操作系统配置），所报告的值是在相同条件下进行多次测量后的平均值。
图28、29和30展示了能源消耗情况：
- 对于中等工作负载，Smart-Balance方法比“最少连接数”、“加权最少连接数”、“设备适用性”、“轮询”和“加权轮询”方法分别减少了38%、45%、44%、47%的能源消耗。
- 对于重工作负载，Smart-Balance方法分别减少了56%、42%、63%、56%、42%的能源消耗。
- 对于混合工作负载，Smart-Balance方法分别减少了42%、33%、53%、46%、32%的能源消耗。

下载：下载高分辨率图片（115KB）
下载：下载全尺寸图片

图28. 中等工作负载下的能源消耗
下载：下载高分辨率图片（97KB）
下载：下载全尺寸图片

图29. 重工作负载下的能源消耗
下载：下载高分辨率图片（112KB）
下载：下载全尺寸图片

图30. 混合工作负载下的能源消耗

5.2.7. 吞吐量
图31、32和33展示了系统的吞吐量。在所有场景中，Smart-Balance方法始终实现了最高的吞吐量，使系统能够同时高效地处理更多应用程序。
下载：下载高分辨率图片（75KB）
下载：下载全尺寸图片

图31. 中等工作负载下的系统吞吐量
下载：下载高分辨率图片（81KB）
下载：下载全尺寸图片

图32. 重工作负载下的系统吞吐量
下载：下载高分辨率图片（76KB）
下载：下载全尺寸图片

图33. 混合工作负载下的系统吞吐量

5.2.8. 系统利用率
图34、35和36展示了资源利用率。Smart-Balance方法在每种场景下都实现了最高的整体系统利用率，表明其能够有效利用计算资源并减少空闲时间。

5.3. 结果讨论
根据图13-36中报告的实验结果，Smart-Balance方法在负载平衡、执行时间、吞吐量、资源利用率和能源效率方面始终优于其他调度方案。这些结果证明了其在异构系统中对动态工作负载的鲁棒性和适应性，突显了其在实际应用中的潜力。
在本节中，我们分析了每种调度方法在三种工作负载场景下的行为和性能。

5.3.1. 最少连接数（Least Connections）
LC算法将每个应用程序分配给待处理任务最少的设备，优先考虑完成任务速度更快的设备。然而，该算法仅根据排队应用程序的数量来定义设备的负载，而没有考虑任务或设备的特定特性。它假设所有任务都是相同的，并且所有设备的处理速度相同。这种假设在异构环境中存在显著限制。
对于中等工作负载，应用程序通常在CPU上运行得更快，主要是因为数据传输的成本高于GPU加速带来的速度提升。因此，由于LC算法没有考虑应用程序与设备的匹配性，GPU会因不合适的应用程序而过载（见图22）。
相比之下，在重工作负载下，GPU的性能显著优于CPU。尽管如此，LC算法仍会继续将过多任务分配给CPU，导致CPU过载，而GPU则未被充分利用（见图23）。
对于具有不同计算需求的应用程序，LC方法倾向于使CPU过载，因为重任务经常被分配给CPU，从而导致CPU利用率升高（见图24）。
LC方法在所有三种场景中都导致了负载不平衡，主要是因为不合适的设备被过度使用。这突显了LC方法的一个根本局限性，即它没有区分应用程序的特性及其与计算设备的兼容性。

在异构系统中，设备的计算能力各不相同。因此，即使设备适合处理大量应用程序，也可能因应用程序不匹配而未被充分利用。相反，如果应用程序与设备不兼容，设备也可能过载。
因此，LC调度方法更适用于具有相同计算设备的同构系统，这些系统执行相似的应用程序，而不是在动态的异构环境中。

5.3.2. 加权最少连接数（Weighted Least Connections）
加权最少连接数算法通过根据设备的计算能力为其分配权重来扩展最少连接数方法。然后，应用程序被分配给连接权重比最低的设备，优先考虑计算能力更强的设备（如GPU）。然而，WLC算法继承了LC方法的局限性，因为它仍然采用简单的负载定义。它假设权重较高的设备总是优于其他设备，而不考虑它们与应用程序的匹配性。
在第一种情况下，由于GPU的权重较高且不适合中等强度的应用程序，GPU会因不合适的应用程序而过载（见图22）。
在第二种情况下，WLC算法通过将较重的应用程序分配给更适合这些任务的GPU来略微减少不平衡。然而，GPU仍然因接收过多任务而过载（见图23）。
同样，对于混合工作负载，WLC方法也会导致GPU过载，因为GPU的较高权重增加了它们接收更多不合适和重任务的可能性（见图24）。
因此，WLC调度方法在设备类型相同但计算能力不同的同构系统中更为有效，尤其是在处理计算强度高的应用程序时。

5.3.3. 设备适用性（Device Suitability）
设备适用性调度器选择执行应用程序最快的设备，忽略实时队列长度。这种方法虽然减少了单个应用程序的执行时间，但会导致较快的设备过载。
在中等工作负载场景下，CPU通常比GPU执行应用程序更快。因此，设备适用性调度器倾向于将更多应用程序分配给CPU，导致CPU过载（见图22）。而在重工作负载场景下，设备适用性调度器会导致GPU严重过载，而CPU则被忽视（见图23）。对于同时包含重任务和中等任务的工作负载，设备适用性调度器会将重任务分配给GPU，而中等任务则在CPU上执行（见图24）。因此，设备适用性调度器在针对设备优势进行负载平衡时更为有效。

5.3.4. 轮询（Round Robin）
轮询调度器以循环方式将应用程序分配给下一个可用设备，不考虑任何因素。在这种方法中，系统中的所有设备处理相同数量的应用程序。
在第一种场景（见图22）中，轮询调度器倾向于使GPU过载，因为CPU更适合中等强度的应用程序，并能更快完成分配的任务。当工作负载包含高强度应用程序时，这种负载分配不平衡更加明显。CPU由于不适合处理高强度任务，经常被分配这类任务，导致其在大多数情况下过载（见图23和图24）。总之，轮询调度方法适用于具有相同计算设备的同构系统。

5.3.5. 加权轮询（Weighted Round Robin）
加权轮询算法根据设备的计算能力为其分配应用程序。每轮会将更多应用程序分配给权重较高的设备。
当工作负载强度中等时，加权轮询方法会导致GPU因分配了大量不合适的应用程序而过载（见图22）。然而，在包含高强度应用程序的第二和第三种场景中，加权轮询调度器通过优先将这类应用程序分配给GPU来减少负载不平衡（见图23和图24）。尽管如此，系统内的GPU仍然过载。
加权轮询调度方法更适合由计算能力不同的相似设备组成的同构系统，尤其是在处理计算强度一致的应用程序时。

5.3.6. Smart-Balance
实验结果强调了这些调度方法在动态和异构系统中的局限性。这些局限性源于对设备负载的简化定义，忽略了影响应用程序性能的关键因素，如计算强度、并行性、设备能力和实时系统状态。因此，调度器无法适应变化的工作负载并做出最优调度决策。
由于调度不当（见图22、图23和图24），导致执行时间延长。过载设备完成额外任务所需时间更长（见图19、图20和图21），从而使负载不足的设备空闲时间增加（见图25、图26和图27）。结果，系统吞吐量和资源利用率降低（见图31、图32和图33），能源消耗也增加（见图28、图29和图30）。
在这项工作中，我们通过平衡系统内的负载分配来克服这些方法的局限性。我们引入了一个全面的负载定义，准确量化了每个设备的负载，并引入了一个反映系统负载分配状态的指标。我们的调度器实时监控系统状态并动态更新设备负载。收到新应用程序时，调度器评估所有调度场景下的负载分配，并将应用程序分配给能最小化系统不平衡的设备。
优先选择不平衡较小的设备可以实现更公平的负载分配（见图16、图17和图18）。这种选择策略体现在不平衡曲线趋近于零，表明随着更多应用程序的分配，系统不平衡逐渐减少（见图13、图14和图15）。
实现负载平衡显著提高了性能，包括减少执行时间（见图19、图20和图21）和空闲时间（见图25、图26和图27），因为设备能够同步完成任务。优化的设备利用率和减少的过载提高了吞吐量，使系统能够支持更多用户应用程序。这些综合效果共同减少了能源浪费，从而降低了能源消耗（见图28、图29和图30）。特别是在工作负载计算强度增加时，不正确的调度会加剧不平衡，导致能源消耗显著增加。
在我们的研究中，我们利用了异构系统的固有特性来优化性能。通过识别影响应用程序执行的关键因素，我们能够持续监控系统设备并策略性地将应用程序分配给保持负载平衡的设备。值得注意的是，我们的方法能够适应动态工作负载和异构设备，在所有场景中始终提供高性能。

5.3.7. 开销
特征提取和执行时间预测所产生的开销很小，对系统性能的影响可以忽略不计。这归功于特征提取与应用程序编译过程的无缝集成。此外，执行时间预测模型只需训练一次，可以在使用期间直接应用，无需重新训练，从而确保系统运行的高效性。结论
负载均衡计算工作负载对于计算系统的稳定性和性能至关重要，尤其是在实时异构系统中，这些系统中的应用程序对时间非常敏感，并且事先无法获得工作负载信息。本研究介绍了一种名为Smart-Balance的实时调度方法，用于异构集群。该方法利用基于人工智能的预测技术来监控系统负载，并将应用程序分配到最优设备上。这种能力得益于我们提出的新型不平衡度量指标，该指标能够量化设备负载之间的差异。在与主流调度器进行对比测试时，我们的方法实现了更低的负载不平衡度、更短的执行时间、更高的能源效率以及更优的整体吞吐量。

尽管Smart-Balance表现出色，但它也存在一些局限性：该方法依赖于特定平台，需要针对不同的硬件配置重新训练预测模型；其性能还受到预测准确性的影响；此外，将该方法扩展到非常大的集群仍然是一个挑战，因为现有的框架（如CUDA、OpenCL）缺乏对全局调度的内置支持。

为了解决Smart-Balance方法的局限性，我们提出了以下未来研究方向：
- **泛化预测模型**：开发适用于多种设备的预测模型，使Smart-Balance能够直接应用于不同的硬件配置中。
- **提高预测准确性**：使用更广泛的应用程序范围训练模型，以确保能够更精确地处理各种计算工作负载。
- **提升可扩展性**：探索适用于大规模异构系统的高级抽象层或中间件支持。

**CRediT作者贡献声明**
Taha Abdelazziz Rahmani：撰写——原始草案、软件设计、方法论。
Ghalem Belalem：撰写——审阅与编辑、指导。
Sidi Ahmed Mahmoudi：撰写——审阅与编辑、指导。
Rafik Omar Merad Boudia：撰写——审阅与编辑。