3. 任务分块基础方法

在科学计算中，一个任务往往由大量可并行的计算单元组成，例如矩阵分块乘法中的子块、粒子模拟中的粒子集合、参数扫描中的独立参数点。把这些计算单元划分给多个进程或线程的过程就是任务分块。分块方式不仅决定每个进程承担多少工作，还直接决定进程之间需要交换多少数据、每个进程访问内存时能否命中缓存。本节围绕四种基础分块方法展开，并分析它们对通信开销与缓存局部性的影响。

均匀分块：连续切分，简单但易失衡

均匀分块（Block Partitioning）把总任务量 N 按进程数 P 切成 P 段连续区间，每个进程获得约 N/P 个连续单元。若 N=1000、P=4，则进程 0 获得 [0,250)，进程 1 获得 [250,500)，依此类推。实现上只需计算起止下标：

int block_size = (N + P - 1) / P;          // 向上取整
int start = rank * block_size;
int end   = min(N, start + block_size);

均匀分块的最大优点是数据连续：每个进程访问的是一段连续内存，空间局部性极好，适合按行遍历的数组计算。同时，进程间边界清晰，若相邻块需要交换边界数据（如模板计算中的晕圈），通信只发生在相邻进程之间，通信模式规整。其缺点是负载容易失衡：当各计算单元耗时不同（如稀疏矩阵非零元分布不均、粒子密度不均）时，连续切分可能让某个进程承担远多于平均的工作量。此外，当 N 不能被 P 整除时，末尾进程块偏小，需要额外处理。

循环分块：轮转分配，均衡但局部性差

循环分块（Cyclic Partitioning）采用轮转方式分配：进程 i 获得下标 i, i+P, i+2P, … 的任务单元。若 N=1000、P=4，进程 0 获得 0,4,8,…，进程 1 获得 1,5,9,…。这种分配在任务单元耗时相近且数量远大于进程数时，负载非常均衡，因为每个进程拿到的单元数几乎相同，且任意连续区间的任务都被均匀摊到所有进程。

但循环分块的代价是访存不连续：进程每次只取一个单元，步长为 P，缓存行中大部分数据被其他进程使用，导致缓存利用率低。若每个单元需要与邻居交换数据，则一个进程的邻居分散在多个进程中，通信对象增多、消息数量上升。因此循环分块更适合任务单元独立、无邻接通信、且单元数量巨大的场景，例如独立的参数扫描或蒙特卡洛采样。

块循环分块：折中方案

块循环分块（Block-Cyclic Partitioning）把上述两者结合：先将任务按固定块大小 B 切成若干块，再以轮转方式把块分配给进程。进程 i 获得第 i、i+P、i+2P… 个块，每块含 B 个连续单元。当 B=1 时退化为循环分块；当 B≥N/P 时接近均匀分块。调节 B 即可在负载均衡与数据连续性之间取舍。

块循环分块是高性能线性代数库（如 ScaLAPACK）中二维矩阵分布的标准做法。以 4×4 进程网格分布 1000×1000 矩阵、块大小 B=64 为例，每个进程持有若干 64×64 的子块，既保证了子块内部访存连续、便于分块矩阵乘法复用缓存，又通过轮转使各进程负载接近均衡。其代价是实现较复杂，需要维护块索引到全局下标的映射，且通信伙伴数量介于均匀分块与循环分块之间。

动态分块：面向不规则负载的调度

当任务单元耗时差异大且无法预先估计时，静态分块难以保证均衡。动态分块把任务放入共享队列，进程完成当前任务后主动领取下一个（或下一批）任务。常见实现是主从模式或原子计数器：

// 原子计数器实现动态领取，chunk 为每次领取的任务数
int next = atomicAdd(&counter, chunk);
while (next < N) {
    for (int i = next; i < min(next + chunk, N); ++i)
        compute(i);
    next = atomicAdd(&counter, chunk);
}

动态分块能自动适应负载波动，适合粒子模拟、不规则网格遍历、分支代价差异大的搜索等场景。代价是每次领取都有同步开销，chunk 过小会导致原子操作和队列争用成为瓶颈，chunk 过大又削弱均衡效果，通常取几十到几百个单元作为经验起点，并结合实测调整。此外，动态分配使任务与进程的对应关系不确定，若任务间存在邻接通信，通信伙伴会动态变化，实现难度显著上升。

分块方式对通信开销与缓存局部性的影响

从通信角度看，均匀分块的通信拓扑最规整：在模板计算或区域分解中，只有相邻块需要交换晕圈数据，消息数量约为进程数的常数倍。循环分块把相邻单元分散到不同进程，若存在邻域依赖，每个进程需与多个甚至全部进程通信，消息数量上升且模式不规则。块循环分块通过块大小 B 控制通信伙伴数量，B 越大越接近均匀分块。动态分块的通信取决于任务依赖结构，通常需要额外的数据定位或重分布机制。

从缓存局部性看，均匀分块和块循环分块（B 足够大时）让进程访问连续内存段，缓存行被充分利用，预取器也能有效工作。循环分块步长为 P 的访问模式使每次取用的数据分散在不同缓存行，缓存命中率下降，在带宽受限的计算中可能成为主要瓶颈。因此，选择分块方法时应先判断任务是否存在邻接通信与规则访存需求：若存在，优先均匀分块或块循环分块；若任务完全独立且数量巨大，循环分块或动态分块更利于均衡。实际工程中常以块循环分块为默认起点，通过调整块大小 B 在负载均衡、通信量和缓存效率之间取得平衡，再用性能剖析工具观察通信时间占比与缓存未命中率，据此微调分块参数。