整数负载下基于改进方法的负载均衡

《Array》：Load balancing for integer loads using a modified approach

　　

负载均衡在提升分布式系统性能方面起着关键作用，其中不均匀的任务分布常导致资源利用率低下和系统吞吐量下降。现有负载均衡方法要么依赖非最优流构造，要么需要在网络中大量通信。研究人员提出了一种改进的负载均衡算法，该算法完全在整数运算中生成平衡流，同时降低重分配过程的通信代价（即流的 l2-范数）。该方法使用确定性的广度优先搜索（Breadth-First Search，BFS）过程构造生成树结构，并以策略性顺序分配负载，从而产生稀疏流向量，其 l2-范数相较现有方法显著降低。在基准图（包括 Petersen 图、环图 C6 和超立方体 Q3）上的实验评估表明，该方法在通信效率和平衡质量上具有竞争力。所提方法为分布式与并行计算环境中的整数负载均衡提供了一种实用且可扩展的解决方案。

研究背景方面，分布式系统中负载均衡旨在将工作负载合理分配至各处理器，避免部分节点空闲而其余节点过载。当负载为不可分的整数单位（如任务调度、包路由）时，直接平均分配往往不可行：平均值可能非整数、负载只能沿图边移动、且重分配通信量取决于所用边集合。现有方法存在三类不足：基于图谱的早期算法（Cvetkovi? 等）仅在积分图（integral graph）上保证整数流，Stevanovi? 的 Algorithm 2 虽对任意弱连通有向图可整数执行，但其平衡流的 l₂-范数（通信流量平方和的度量）偏大；另一类云/边缘启发式算法则面向 makespan、时延等平台指标，不直接优化重分配通信代价。因此研究人员开展本研究，目标是确定性地构造整数平衡流并使 l₂-范数尽可能低。

主要关键技术方法上，研究人员首先以固定根节点 v_n 对弱连通有向图的无向底层图做确定性 BFS（同层按最小顶点标号破平局），得到唯一 BFS 生成树 T；据此构造 m×(n?1) 整数矩阵 C，其第 i 列对应从根到顶点 i 的路径在各项边上的前向(+1)/反向(?1)/不在路径(0)指示。随后提出两阶段算法：Algorithm 1（Parameter Computing Algorithm）从 C 导出生成树 G′ 并计算各顶点距根距离表 D_L、按距离增序的顶点索引表 I_L、根邻表 N_L 及树中度表 Deg_L；Algorithm 2 利用这些参数按策略顺序将整数负载指派到节点，再算平衡流 f=C·(wˉ?w)_?，满足 Nf=wˉ?w。样本仅为 Petersen 图、C₆、Q₃ 等基准图，无生物样本队列。

研究结果部分，按原文小节叙述如下。1. Introduction 节指出整数负载均衡在任务调度与 NoC（Network-on-Chip）路由器队列等场景必不可少，并明确定义弱连通有向图 G=(V,E)、顶点–边关联矩阵 N、负载向量 w∈Zⁿ、平均负载 wˉ 及平衡流 f∈Z^E 使 Nf=wˉ?w，最小化 ‖f‖₂。1.1 Notations 节固化上述记号。1.2 Deterministic construction of matrix C 节给出 BFS 树构造 C 的具体规则，证明固定根与破平局规则使 C 唯一确定，从而全算法确定性可复现。2. Algorithm proposed by Dragan Stevanovi? 节复述 Stevanovi? 的 Algorithm 2：由积分图特征向量流矩阵 F 与 B_? 推得 C=F·B_?^?1 且 N_?C=I，故 f=C·(wˉ?w)_? 为整数流；但在 Petersen 图上其 ‖f_A‖₂=41.95，远大于 Hu 等的 28，说明 Steiner 式 C 并非 l₂ 最优。3. The proposed algorithms for load balancing 节给出研究人员的新两算法，核心在于借 BFS 树参数控制负载指派顺序，使最终 f 的 l₂-范数低于 Stevanovi? Algorithm 2；文中宣称该流对任意弱连通有向图均整数可行且通信代价更低，并在 Petersen、C₆、Q₃ 上验证效率与平衡质量具竞争性。

讨论与结论部分，研究人员强调所提方法属图论线工作但区别于随机扩散或谱方法：它不要求积分图、不调用特征向量、不在迭代平均化，而是单次遍历 BFS 树以确定性产出整数流，把通信代价（l₂-范数）作为直接优化目标。结论为：该改进算法在保持整数算术与广泛拓扑适应性的同时，较 Stevanovi? Algorithm 2 获得了更低的平衡流 l₂-范数，适用于 MapReduce 机架内数据块调度与 NoC 相邻路由器队列重分配等离散不可分负载场景，为分布式并行系统提供了通信高效、可扩展的整数负载均衡方案。论文发表于《Array》。