📚 课程目录第4章负载均衡度量与评价指标

4. 负载均衡度量与评价指标

分块策略和调度算法是否有效，不能凭“看起来分得挺均匀”来判断，必须落到可计算的指标上。本节围绕五个核心度量展开：负载均衡因子、加速比、效率、任务完成时间方差和资源利用率，并说明它们在实际系统中如何采集原始数据、如何计算、如何解读。

五个指标的定义与计算口径

设系统有 P 个计算单元（进程、线程或节点），第 i 个单元实际承担的工作量为 w_i，其执行耗时为 t_i。各指标定义如下：

负载均衡因子：常用定义为 LBF = w̄ / w_max，其中 w̄ 为平均工作量，w_max 为最大单元工作量。取值在 (0, 1]，越接近 1 越均衡。也可用变异系数 CV = σ_w / w̄ 表达不均衡程度，越小越好。两者方向相反，报告中必须注明用的是哪一种。
加速比：S = T₁ / T_P，T₁ 为单单元串行执行时间，T_P 为 P 个单元并行执行时间。它衡量并行带来的实际收益，受 Amdahl 定律约束。
效率：E = S / P = T₁ / (P · T_P)，表示每个计算单元的平均有效利用率，理想值为 1。
任务完成时间方差：σ_t² = (1/P) Σ (t_i − t̄)²，反映各单元结束时刻的离散程度。方差大意味着存在明显“拖尾”单元，是负载不均的直接证据。
资源利用率：U = (Σ t_i) / (P · T_P)，即所有单元忙碌时间之和占“单元数 × 总墙钟时间”的比例，与效率数值接近但口径不同：效率以串行时间为基准，利用率以实际墙钟时间为基准，能反映空转与等待。

注意参照约定：T_P 一律指从并行任务启动到最后一个单元结束的墙钟时间（makespan），而非各单元耗时之和。所有指标必须基于同一批运行数据计算，否则不可比。

指标之间的关系与解读

这五个指标并非彼此独立。加速比和效率回答“并行值不值”，均衡因子和方差回答“分得匀不匀”，资源利用率回答“机器闲没闲”。一个常见误区是只看加速比：当问题规模随 P 同步增大时，加速比可能很好看，但效率却在下降，说明单单元的有效产出在摊薄。反之，若方差很小而效率仍低，问题往往不在分块，而在通信开销、同步等待或串行段占比过高。

下图给出从原始采集数据到五项指标的计算链路，以及各指标指向的诊断方向：

在实际系统中采集与计算

采集的关键是“每单元一条记录”。以 Python 多进程处理一个数组求和为例，可在每个工作进程内用 time.perf_counter() 记录起止时刻，并把处理元素数一并回传主进程：

import time, statistics

def worker(chunk_id, data):
    t0 = time.perf_counter()
    s = sum(data)                      # 实际计算
    t1 = time.perf_counter()
    return {"id": chunk_id, "n": len(data), "t": t1 - t0}

# 主进程汇总（示例数据）
records = [{"id":0,"n":25000,"t":0.82},{"id":1,"n":25000,"t":0.85},
           {"id":2,"n":25000,"t":1.31},{"id":3,"n":25000,"t":0.79}]
P = len(records)
w = [r["n"] for r in records]; t = [r["t"] for r in records]
T_P = max(t)                            # 简化：以最长单元耗时近似墙钟
T_1 = 3.62                              # 同规模单进程基线（示例）
lbf = (sum(w)/P) / max(w)
S   = T_1 / T_P
E   = S / P
var = statistics.pvariance(t)
U   = sum(t) / (P * T_P)
print(f"LBF={lbf:.3f} S={S:.2f} E={E:.2f} σ²={var:.4f} U={U:.3f}")

按上述示例数据计算：LBF = 25000/25000 = 1.000（工作量完全均分），但 T_P = 1.31，S ≈ 2.76，E ≈ 0.69，σ² ≈ 0.043，U ≈ 0.72。这组结果揭示了一个典型现象：按元素数均分并不等于按耗时均分。单元 2 处理同样多的元素却慢了约 60%，可能是数据局部性差、缓存未命中或所在核被其他进程抢占。此时均衡因子“看起来完美”，方差和利用率却暴露了真实问题——这正是必须多指标联合判读的原因。

采集时务必区分“单元自身耗时”和“墙钟时间”。若各单元启动时刻不同（如任务队列逐个派发），max(t_end) − min(t_start) 会包含派发延迟，此时应额外记录派发时刻，或改用各单元耗时的最大值作为 T_P 的近似，并在报告中注明口径。

采集实施的几个要点

基线要同规模：T₁ 必须用与并行运行相同的问题规模和相同实现（去掉并行部分）测得，否则加速比失真。
多次运行取中位数：单次测量受调度抖动影响大，建议重复 5～10 次，用中位数计算指标，同时记录最大值以观察最坏情况。
记录分块元数据：除耗时外，保存每块的数据范围、元素数、是否命中缓存等，便于把方差归因到具体分块。
区分计算与等待：在单元内分别累计计算时间和阻塞等待时间，二者之和与墙钟的差额即为调度或 I/O 开销，是解释利用率不足的直接依据。
固定环境变量：CPU 频率策略、绑核方式、后台负载都会影响结果，对比实验时应保持一致并记录。

把上述指标做成一张运行记录表，每次调参后填写一行，就能直观看出分块粒度或调度策略变化对五项指标的影响。例如把块大小从 25000 减到 8000 后，若 LBF 略降而 σ² 明显下降、U 上升，说明细粒度动态分配确实缓解了拖尾，代价是少量调度开销——这种“指标间的取舍”正是负载均衡调优的常态，也是评价体系真正的价值所在。