Title: Optimal Rate-Matrix Pruning For Large-Scale Heterogeneous Systems Show Chinese title

Title: 大规模异构系统的最优率矩阵剪枝

Abstract: We present an analysis of large-scale load balancing systems, where the processing time distribution of tasks depends on both the task and server types. Our study focuses on the asymptotic regime, where the number of servers and task types tend to infinity in proportion. In heterogeneous environments, commonly used load balancing policies such as Join Fastest Idle Queue and Join Fastest Shortest Queue exhibit poor performance and even shrink the stability region. Interestingly, prior to this work, finding a scalable policy with a provable performance guarantee in this setup remained an open question. To address this gap, we propose and analyze two asymptotically delay-optimal dynamic load balancing policies. The first policy efficiently reserves the processing capacity of each server for ``good" tasks and routes tasks using the vanilla Join Idle Queue policy. The second policy, called the speed-priority policy, significantly increases the likelihood of assigning tasks to the respective ``good" servers capable of processing them at high speeds. By leveraging a framework inspired by the graphon literature and employing the mean-field method and stochastic coupling arguments, we demonstrate that both policies achieve asymptotic zero queuing. Specifically, as the system scales, the probability of a typical task being assigned to an idle server approaches 1. Show Chinese abstract

Abstract: 我们分析了大规模负载均衡系统，其中任务的处理时间分布不仅依赖于任务类型还依赖于服务器类型。 我们的研究集中在渐近区域，即服务器数量和任务类型的数量以相同比例趋于无穷大时的极限情况。 在异构环境中，常用的负载均衡策略如Join Fastest Idle Queue和Join Fastest Shortest Queue表现不佳，甚至会缩小稳定性区域。 有趣的是，在本研究之前，如何在这个设置下找到一个具有可证明性能保证的可扩展策略一直是一个开放问题。 为了解决这一差距，我们提出了两种渐近延迟最优的动态负载均衡策略并进行了分析。 第一种策略有效地为“优质”任务保留每个服务器的处理能力，并使用朴素的Join Idle Queue策略路由任务。 第二种策略称为速度优先策略，显著提高了将任务分配给能够以高速度处理它们的相应“优质”服务器的可能性。 通过利用受图论启发的框架，采用平均场方法和随机耦合论证，我们证明这两种策略均实现了渐近零排队。 具体而言，随着系统的扩大，典型任务被分配到空闲服务器的概率趋近于1。