一种用于可扩展独立任务分配的多层算法

《Future Generation Computer Systems》：A Multilevel Algorithm for Scalable Independent Task Assignment

提出一种基于多级框架的独立任务分配算法，通过分层聚类和优化策略有效平衡负载，在保持线性时间复杂度O(KN)的同时显著提升解的质量，适用于大规模异构计算场景。实验表明该方法在网页爬取、大语言模型训练和稀疏矩阵运算等典型场景中均优于现有启发式算法，负载均衡质量提高20%-60%，且计算效率提升1-2个数量级。

　　在现代计算系统中，任务分配问题一直是一个核心挑战，特别是在并行和分布式系统中，如何高效地将独立任务分配给非同构处理器，以最小化任务完成时间（即周转时间或makespan）是一个关键目标。这一问题通常被称为“独立任务分配问题”，在文献中已经被广泛研究。然而，由于该问题具有NP完全性，因此，对于大规模问题实例，传统的精确算法无法在合理的时间内得到最优解。因此，研究者们提出了多种启发式算法，以在计算效率和任务分配质量之间取得平衡。本文提出了一种新的多级任务分配方法，该方法结合了线性时间复杂度和高任务分配质量，适用于各种任务负载分布情况，包括高度偏斜和非偏斜数据集。

传统的启发式方法如MinMin、MaxMin、RC、Suff和GA在不同的任务分配场景中表现各异。MinMin+和MaxMin+作为这些方法的改进版本，虽然在某些情况下表现良好，但它们的二次时间复杂度限制了其在大规模问题中的可扩展性。而Suff+在处理偏斜数据时效果更好，但同样面临计算效率的挑战。因此，为了克服这些局限，本文引入了多级框架，该框架基于图形和超图划分中的多级方法，将任务分配问题划分为三个阶段：粗化（coarsening）、初始分配（initial solution）和细化（uncoarsening）。这种方法允许在不同层次上进行任务匹配和分配优化，同时保持整体的线性时间复杂度。

在粗化阶段，任务被按照相似性进行聚类。本文提出了两个新的聚类指标：差异性指标（dissimilarity metric）和偏好比（favor ratio）。差异性指标用于衡量两个任务在被匹配后的执行时间差异，而偏好比则用于进一步区分任务之间的相似性。这些指标的引入使得任务匹配过程更加高效，同时保证了分配质量。此外，为了进一步提高匹配效率，本文还采用了一种对偏好比进行对数映射的策略，将任务特征值映射到一个更小的区间，从而实现快速匹配，同时不会显著降低分配质量。

在初始分配阶段，本文采用两种互补的启发式方法：MinMin+和MaxMin+，分别用于处理非偏斜和偏斜数据集。通过这两种方法，可以在粗化后的任务集合上生成初始分配方案。随后，这些初始方案通过多级细化过程进行优化。在细化阶段，本文采用了两种优化策略：移动细化（move refinement）和交换细化（swap refinement）。移动细化适用于更细粒度的分配层次，而交换细化则用于更粗粒度的层次。这两种细化方法在时间复杂度和分配质量之间进行了权衡，确保了整体算法的效率和性能。

为了评估所提出方法的性能，本文在多个实际应用场景中进行了实验。这些场景包括地理分布式的网络爬虫任务（GDWC）、分布式和并行化的大型语言模型（LLM）训练任务以及稀疏矩阵向量乘法（SpMV）任务。实验结果表明，所提出的多级任务分配方法在所有测试实例中都表现出了优越的负载平衡性能。对于大规模任务集，所提出方法不仅能够提供高质量的分配方案，还显著优于现有方法，同时保持了线性时间复杂度。例如，在处理大规模任务集时，该方法在大多数情况下都能提供最佳或接近最佳的分配方案，而其他方法如MinMin+和MaxMin+在某些情况下无法在规定时间内完成计算。

此外，本文还通过实验验证了所提出方法在不同任务负载分布情况下的鲁棒性。对于偏斜数据集，该方法能够有效减少makespan，而对于非偏斜数据集，其分配质量也得到了保证。实验结果进一步表明，该方法在计算效率和分配质量之间取得了良好的平衡，特别是在处理大规模任务集时，其运行时间显著优于其他高质量启发式方法，例如MinMin+、MaxMin+和Suff+。

综上所述，本文提出的多级任务分配方法不仅在理论上有创新，而且在实际应用中也展现出了显著的优势。该方法通过多级划分策略，实现了高效的任务匹配和分配优化，适用于各种类型的任务负载分布。同时，其线性时间复杂度使得该方法在处理大规模问题实例时具有更好的可扩展性。实验结果表明，该方法在多个实际应用场景中都能提供高质量的分配方案，同时保持了较高的计算效率。因此，本文所提出的多级任务分配方法为独立任务分配问题提供了一种新的、有效的解决方案，具有广泛的应用前景。