异构计算平台上的任务调度算法研究

关键词：异构计算；任务调度；算法研究；性能优化

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2024）28-0059-03

0 引言

异构计算是指将不同类型、不同性能的计算资源（如CPU、GPU、FPGA等）整合到一个统一的计算平台中，通过协同工作来加速应用程序的执行[1]。这种计算模式能够充分利用各种计算资源的优势，提高计算效率和系统性能。然而，异构计算平台也带来了诸多挑战，其中之一就是任务调度问题。

任务调度是指在异构计算平台中将任务分配给合适的计算资源，并确定任务的执行顺序，以达到优化系统性能的目的。由于异构计算平台中计算资源的类型和性能差异较大，如何合理地进行任务调度成为一个具有挑战性的问题。

1 异构计算平台任务调度算法概述

任务调度算法是异构计算平台中的关键技术之一。根据调度策略的不同，可以将现有的任务调度算法分为静态调度算法和动态调度算法[2]。静态调度算法在编译时确定任务的执行顺序和计算资源的分配方案。这类算法的优点是实现简单、开销小，但缺点是灵活性差，无法适应运行时环境的变化。常见的静态调度算法有列表调度算法、聚类调度算法等。动态调度算法在运行时根据系统的实时状态进行任务调度。这类算法的优点是能够适应环境变化，实现动态负载均衡，但缺点是开销较大。常见的动态调度算法有基于任务复制的调度算法、基于任务迁移的调度算法等。

2 现有任务调度算法分析

列表调度算法：该算法通过构建一个任务列表，按照列表中的顺序依次将任务分配给计算资源。列表的构建通常基于任务的优先级或计算资源的利用率。列表调度算法实现简单，但无法充分利用异构计算平台的并行性。

聚类调度算法：该算法将任务按照相似性或关联性进行聚类，然后将每个聚类分配给合适的计算资源。聚类调度算法能够减少任务间的通信开销，但聚类的质量和计算资源的分配方案对系统性能影响较大。

基于任务复制的调度算法：该算法通过复制任务并在不同的计算资源上执行，以消除任务间的依赖关系，提高并行度。基于任务复制的调度算法能够显著减少任务的等待时间，但会增加系统的开销和复杂性。

基于任务迁移的调度算法：该算法根据系统的实时状态动态地将任务从一个计算资源迁移到另一个计算资源上执行。基于任务迁移的调度算法能够实现动态负载均衡，但需要解决任务迁移的开销和决策问题。

3 改进的任务调度算法策略

针对现有任务调度算法存在的问题，本文提出了一种改进的任务调度策略。该策略综合考虑任务的特性、计算资源的性能和系统的实时状态，采用动态与静态相结合的方式进行任务调度。该策略首先根据任务的特性和计算资源的性能进行静态分配，然后在运行时根据系统的实时状态进行动态调整。在静态分配阶段，采用基于任务聚类和资源匹配的方法来确定初始的任务分配方案；在动态调整阶段，根据任务的执行情况和系统的负载情况进行动态的任务迁移和复制。具体分为以下步骤：

3.1 静态分析与初始分配

采用了有向无环图（DAG） 对任务进行建模，节点表示任务，边表示任务间的依赖关系。同时，对计算资源进行抽象建模，包括资源类型、计算能力、可用性等属性。基于这些模型，使用聚类算法如K-means将任务聚类并初步分配给相应的计算资源。这一步骤考虑了任务间的通信开销和数据依赖，以优化任务的执行顺序。

3.2 动态调整与优化

设计了一个轻量级的监控机制，周期性地收集各计算资源的负载信息和任务执行状态。通过实时监控数据，实现了负载均衡，包括任务迁移和任务复制两种机制。任务迁移算法根据负载信息确定迁移的候选任务和目标资源，以减轻过载资源的负担。任务复制算法则识别关键路径上的任务，并根据资源可用性进行复制和并行执行，以减少总体执行时间。这些动态调整算法能够灵活地应对系统状态的变化，确保任务的高效执行。

明确需要监控的目标：在任务调度中，关注的关键指标包括计算资源的负载情况（如CPU使用率、内存占用率、磁盘I/O等）、网络状态（如带宽、延迟）、任务执行状态（如执行进度、等待时间）以及系统性能（如吞吐量、响应时间）等。这些指标能够反映系统的实时状态和任务调度的效果。

采用轻量级的数据采集方式：可以利用系统自带的监控工具或第三方性能监控库来定期收集数据[3]。此外，还可以采用事件驱动的方式，只在特定事件（如任务开始、任务结束、资源故障等）发生时进行数据采集，以进一步降低监控开销。

数据处理与分析：收集到的数据需要经过处理和分析才能提供有用的信息[4]。可以通过计算平均值、标准差等统计量来评估资源的负载情况和系统性能。同时，利用机器学习算法对历史数据进行分析，建立预测模型，以便预测未来一段时间内的系统状态和任务需求。

可视化展示与告警机制：为了方便管理人员直观地了解系统状态和任务调度情况，可以将监控数据以图表、仪表盘等形式进行可视化展示。同时，设置告警机制，当某些关键指标超过预设阈值时，及时发出告警信息，以便管理人员快速响应并采取相应措施[5]。

监控数据存储与查询：为了长期保存监控数据并支持后续的分析和查询操作，需要设计合理的数据存储结构。可以选择使用时间序列数据库来存储监控数据，以便高效地查询和分析时间序列数据。同时，建立索引和查询优化机制，提高数据查询的速度和准确性。

监控机制的可扩展性和灵活性：考虑到系统的不断发展和变化，监控机制需要具备一定的可扩展性和灵活性。可以采用插件化的设计思想，将不同的监控功能和数据采集方式以插件的形式实现，以便根据需要进行动态扩展和定制。

3.3 性能优化

利用机器学习技术对系统性能进行预测，并根据预测结果调整任务调度策略。同时，设计了启发式算法，根据实时性能数据动态调整任务的执行顺序和资源分配。这些性能优化机制能够最大化整体性能，提升任务调度的效果。

首先，收集大量历史任务执行数据，包括任务类型、资源需求、执行时间等关键信息。通过分析这些数据，识别影响任务性能的关键因素。随后，利用随机森林、神经网络等机器学习算法构建性能预测模型，该模型能根据任务特征预测执行时间和资源需求。通过不断训练和优化模型，提高预测准确性和稳定性。

启发式算法是一种基于经验的、能够快速找到问题近似最优解的算法。在任务调度中，设计了一种启发式算法，根据实时性能数据动态调整任务的执行顺序和资源分配。具体来说，该启发式算法会周期性地收集各计算资源的负载信息和任务执行状态。然后，它会根据任务的紧急程度、资源的需求情况和系统的整体负载情况，为每个任务计算一个优先级得分。该得分综合考虑了任务的等待时间、执行时间和资源利用率等因素。接下来，算法会根据任务的优先级得分，对任务队列进行排序，并优先调度得分较高的任务。同时，它还会根据资源的实时负载情况，动态分配和调整资源，以确保任务能够在最短的时间内完成。这种启发式算法能够快速做出决策，适应系统的动态变化。通过不断优化任务的执行顺序和资源分配，它能够在满足任务需求的前提下，最大化整体性能，提升任务调度的效果。

3.4 反馈与调整

在反馈与调整阶段，实现了一个性能反馈机制，收集并分析任务执行过程中的性能数据。根据性能反馈数据，动态调整任务调度策略的参数和规则，以适应系统的变化。这种反馈机制保证了策略的持续优化和适应性，为异构计算平台的应用和发展提供了有力支持。

数据收集模块：性能反馈机制首先通过数据收集模块来捕获任务执行的关键性能指标。这些数据包括但不限于任务执行时间、资源利用率（如CPU、内存、磁盘I/O等）、网络带宽和延迟、任务队列长度等。数据收集模块利用系统监控工具、性能计数器或自定义的监控脚本来实时获取这些数据，并将其记录在性能日志中。

数据处理与分析模块：收集到的性能数据随后被送入数据处理与分析模块。该模块负责数据的清洗、聚合和转换，以使其适用于后续的分析和决策。利用统计分析技术，可以计算出各项性能指标的平均值、标准差、最大值和最小值等，从而了解系统的整体性能水平和波动情况。此外，通过机器学习算法，还可以对历史数据进行趋势分析和预测，以便预测未来系统的性能需求。

决策与调整模块：基于数据处理与分析模块的输出结果，决策与调整模块负责制定任务调度策略的调整方案。它根据当前的性能指标和预测结果，评估当前任务调度策略的有效性，并确定是否需要调整。如果需要调整，该模块会计算新的参数和规则，如任务优先级、资源分配策略、任务队列管理策略等，并将其应用于任务调度器中。

应用与监控模块：一旦决策与调整模块制定了新的任务调度策略，应用与监控模块负责将其应用到系统中，并持续监控其效果。该模块会实时收集新的性能数据，并将其与之前的数据进行对比，以评估策略调整的效果。如果性能有所提升或保持稳定，说明调整有效；否则，可能需要重新调整或采用其他优化措施。

通过这样一个闭环的性能反馈机制，能够实现对任务调度策略的持续优化和适应。该机制能够及时发现系统的性能瓶颈和问题，并根据实时的性能数据做出相应调整，从而提高任务调度的效率和系统的整体性能。

4 实验与分析

4.1 实验设计

为了验证改进的任务调度策略的有效性，本文设计了一系列实验，并与现有算法进行了对比分析。实验结果表明，改进的任务调度策略在多个性能指标上均优于现有算法。

实验环境：构建了一个包含4种不同类型计算资源（CPU、GPU、FPGA、ASIC） 的异构计算平台，每种计算资源具有不同的计算能力和特性。

测试任务集：选择了10个具有不同计算复杂度和数据依赖关系的任务作为测试对象，这些任务涵盖了科学计算、数据处理和机器学习等应用领域。

对比算法：选择了列表调度算法（LS） 、聚类调度算法（CS） 和基于任务复制的调度算法（TDS） 作为对比算法。

4.2 实验指标

任务平均完成时间（Average Completion Time，ACT） ：所有任务从提交到完成的平均时间，单位为秒。

系统吞吐量（Throughput） ：单位时间内完成的任务数量，单位为任务/秒。

负载均衡度（Load Balancing Degree，LBD） ：通过计算各计算资源的利用率方差来衡量负载均衡效果，数值越小，表示负载均衡效果越好。

4.3 实验结果

表1展示了不同算法在任务平均完成时间、系统吞吐量和负载均衡度方面的实验结果。

从表1中可以看出，本文提出的改进任务调度策略在任务平均完成时间、系统吞吐量和负载均衡度方面均优于现有算法。

任务平均完成时间：改进策略的任务平均完成时间为75 秒，相较列表调度算法的120 秒，降低了37.5%。相较聚类调度算法的100秒和基于任务复制的调度算法的90秒，也分别降低了25%和16.7%。这表明改进策略能够更有效地利用异构计算平台的资源，减少任务的等待时间和执行时间。

系统吞吐量：改进策略的系统吞吐量为9任务/ 秒，相较列表调度算法的5任务/秒，提高了80%。相较聚类调度算法的6任务/秒和基于任务复制的调度算法的7任务/秒，也分别提高了50%和28.6%。这表明改进策略能够更高效地调度任务，提高系统的并行处理能力。

负载均衡度：改进策略的负载均衡度为0.10，相较列表调度算法的0.25、聚类调度算法的0.20和基于任务复制的调度算法的0.15，分别降低了60%、50% 和33.3%。这表明改进策略能够更好地平衡各计算资源的负载，避免资源过载或闲置的情况，提高整体资源利用率。

5 结论与展望

本文对异构计算平台上的任务调度算法进行了深入研究，分析了现有算法的优缺点，并提出了一种改进的任务调度策略。通过实验验证，该策略在降低任务完成时间、提高系统吞吐量等方面具备显著优势。未来，随着异构计算技术的不断发展和应用场景的不断扩展，任务调度算法将面临更多的挑战和机遇。未来的研究工作可以围绕以下几个方面展开：进一步优化任务调度策略以适应更复杂的应用场景；研究跨平台、跨架构的任务调度技术以实现更广泛的资源共享；探索基于机器学习和人工智能技术的任务调度方法以提高调度效率和准确性。