A multilevel algorithm for scalable independent task assignment

doi:10.1016/j.future.2025.108183

2025-10-08

H. Burhan Tabak

Cevdet Aykanat *

DOI：10.1016/j.future.2025.108183

原文链接

查看原文

摘要

En 中文

将大量独立任务分配给异构处理器是现代计算中的一个基本问题，其应用领域包括云服务、网页爬取和AI训练等。精确方法和数学启发式方法能提供高质量分配方案，但会产生超线性甚至指数级的运行时间成本，导致其在实际应用中不可行，尤其是在大规模问题实例中。相反，轻量级启发式方法虽然能高效扩展，但通常会产生质量较低的分配方案。为解决此问题，我们提出了首个针对独立任务分配问题的多级框架，该框架保持端到端的线性运行时间界限O(KN)，其中K×N表示预期计算时间矩阵的大小，K和N分别代表处理器和任务的数量。我们提出：(i)新型的高质量粗化指标，用于数值化定义任务特征和相似性；(ii)一种高效且有效的匹配算法，在整合这些指标的同时保持相对于输入规模的线性时间复杂度；(iii)一种初始解方案，利用互补启发式方法生成基解，并通过解粗化过程反向投影至不同层级；(iv)一种高效且有效的解粗化算法，通过不同精化算法迭代提升分配质量。涉及数亿级任务的广泛实验评估表明，我们的算法在质量上显著优于已知的高质量启发式方法，且运行速度更快，使其成为大规模问题实例的实用选择。

Keyword:

Parallel and distributed computing

Heterogeneous systems

Independent task assignment

Multilevel framework

Load balancing

Geographically distributed web crawling

Distributed and parallelized LLM training