4. 负载均衡策略：静态与动态负载均衡
稀疏计算里有个让人头疼的问题——非零元素分布极不均匀。你想想看，一个矩阵里可能90%的非零值都挤在几行，剩下的行几乎全是零。这时候如果每个处理单元平均分配任务，那结果就是：有的PE忙到冒烟，有的PE闲得发慌。整体性能？直接被最慢的那个拖死。
我早年做过一个图像处理加速器，矩阵来自SIFT特征提取。非零分布那叫一个惨烈，前10%的行占了70%的权重。一开始没做负载均衡，加速比连理论值的1/3都不到。后来老老实实把调度策略重写了一遍，才把性能拉回来。嗯，这节课我们就聊聊怎么解决这个问题。
4.1 静态负载均衡：简单但看天吃饭
静态负载均衡，说白了就是在计算开始前就把任务分好。分完就不改了。它的优点是开销小、实现简单、没有运行时调度器。但缺点也很明显——它假设你知道非零元素的分布。
常见的静态策略有这么几种：
- 按行均分：每个PE分到相同数量的行。最简单，但碰上分布不均就完蛋。
- 按非零元素个数均分：先统计每行的非零数，然后尽量让每个PE分到的非零总数接近。比按行均分好一些，但依然无法应对计算量的动态变化。
- 按权重分块：给每行一个权重（比如非零数×计算复杂度），然后做背包问题式的划分。这个效果好一点，但预处理开销大。
静态均衡的核心矛盾：你必须在运行前就做出决策，而运行时的实际情况可能完全偏离你的预期。我建议只在非零分布相对稳定、或者硬件资源极度受限的场景下使用静态方案。
4.2 动态负载均衡：运行时见招拆招
动态负载均衡就不一样了。它允许在计算过程中重新分配任务。每个PE干完手里的活，就去任务池里领新的。这样就算某个PE分到了一块特别重的骨头，其他PE也能帮它分担。
动态策略的典型实现方式：
- 任务池（Task Pool）：把待处理的行或块放到一个共享队列里。PE空闲了就从中取任务。
- 工作窃取（Work Stealing）：每个PE有自己的本地队列。空闲的PE会从其他PE的队列尾部“偷”任务。这个在CPU多核上很常见，硬件实现起来稍微麻烦点。
- 基于硬件计数器的反馈调度：在PE上挂一个完成计数器，调度器根据计数器的值动态调整后续任务的分配权重。
我的经验：在硬件里实现任务池，最怕的就是队列访问冲突。我曾经用了一个多bank的FIFO结构，每个bank独立读写，配合一个简单的仲裁器，把冲突率降到了5%以下。如果你也在做类似设计，记得给任务池加上水位监测——满了就暂停分配，空了就提前预取。
4.3 针对非零分布不均的硬件调度算法
光有静态或动态的概念还不够。你得有具体的调度算法。下面这几个是我在实际项目中验证过的，分享给你。
4.3.1 基于行密度的自适应分块
核心思路：不按固定大小分块，而是根据每行的非零密度动态调整块的大小。密度高的行，块切小一点；密度低的行，块切大一点。这样每个块的计算量大致相当。
// 伪代码：自适应分块
int adaptive_chunk_size(int row_id, float density) {
if (density > 0.8) return 4; // 高密度，小块
else if (density > 0.4) return 8; // 中密度，中块
else return 16; // 低密度，大块
}这个算法我在一个稀疏矩阵乘法加速器上用过。配合一个简单的预处理器，在主机端把分块信息算好，写到片上的配置寄存器里。硬件调度器根据这些配置直接分发任务，几乎没有运行时开销。
4.3.2 两阶段调度：粗粒度分配 + 细粒度窃取
第一阶段：用静态方式把任务粗粒度地分配给每个PE（比如每个PE分8个块）。第二阶段：在PE内部，用工作窃取机制做细粒度的再平衡。
这样做的好处是：减少了全局任务池的访问频率（第一阶段已经分掉了大部分任务），同时保留了动态调整的能力（第二阶段处理尾部效应）。
| 阶段 | 粒度 | 调度方式 | 硬件开销 |
|---|---|---|---|
| 第一阶段 | 粗粒度（8~16行/块） | 静态预分配 | 低（配置寄存器） |
| 第二阶段 | 细粒度（1~4行/块） | 动态工作窃取 | 中（本地队列+窃取总线） |
注意：工作窃取在硬件里实现时，要小心死锁。我曾经遇到过两个PE同时互相偷任务，结果都卡在等待对方释放队列锁上。解决方案是给窃取操作加超时机制，超时了就放弃本次窃取，转而去全局任务池取任务。
4.3.3 基于历史统计的预测调度
这个思路稍微高级一点。它利用前几个时间窗口的计算数据，预测下一个窗口的负载分布。比如，如果某个PE在过去3个周期里都完成了超额的任务，调度器就给它多分配一些任务。
实现上需要一个滑动窗口统计器，记录每个PE的完成率。调度器根据完成率计算一个“信任因子”，然后按信任因子分配任务。
// 信任因子计算
float trust_factor[PE_NUM];
for (int i = 0; i < PE_NUM; i++) {
float avg_completion = window_sum[i] / WINDOW_SIZE;
trust_factor[i] = avg_completion / global_avg;
if (trust_factor[i] < 0.5) trust_factor[i] = 0.5; // 下限保护
}这个算法在非零分布有局部规律时效果特别好。比如在卷积神经网络里，不同层的稀疏模式往往有延续性，用历史预测就很准。
4.4 知识体系总览
下面这张图把本章的核心逻辑串起来了。你可以看到静态和动态两条路径，以及它们在不同场景下的适用性。
4.5 如何选择？我的建议
没有银弹。选哪种策略取决于你的具体场景。我列几个判断标准：
- 非零分布是否可预测？ 如果分布规律稳定（比如结构化稀疏），静态方案就够用。如果分布随机性大，必须上动态。
- 硬件资源是否紧张？ 动态方案需要额外的队列、仲裁器、统计逻辑。如果你的芯片面积和功耗预算很紧，优先考虑静态+简单动态的组合。
- 实时性要求高不高？ 动态调度有运行时开销。对于延迟敏感的场景（比如自动驾驶中的目标检测），我建议用两阶段调度，把大部分决策提前到预处理阶段完成。
一个小技巧：在芯片设计阶段，把调度器的参数（比如块大小、窃取阈值、窗口长度）做成可配置的。这样流片回来后，还能通过软件调整调度策略。我在三个项目里用了这个思路，每次都能在后期优化中再挤出10%~20%的性能提升。
好了，负载均衡这块就聊到这儿。记住一点：调度策略的好坏，最终要看最慢的那个PE。别让任何一个处理单元闲着，也别让任何一个处理单元累垮。这就是硬件调度员的艺术。