1. 课程导入与问题定义

在单机单核时代，科学计算程序的性能瓶颈往往集中在算法复杂度上；而到了多核、众核与集群时代，真正的瓶颈常常变成“任务如何切分、如何分配到各个计算单元、如何让它们几乎同时结束”。这就是本课程要解决的核心问题：任务分块（Task Partitioning）与负载均衡（Load Balancing）。前者决定“把一个大计算拆成哪些可并行的子任务”，后者决定“这些子任务如何映射到进程、线程或节点上，使整体完成时间最短”。

可以用一个直观的量化目标来定义问题。设总计算量为 W，可用计算单元数为 P，第 i 个单元实际承担的工作量为 w_i，则并行执行时间近似由最慢的单元决定：T_parallel ≈ max(w_i) / s（s 为单元处理速率）。理想均衡时 w_i = W / P，加速比上限为 P；而一旦某个单元承担了 2W/P 的工作量，加速比立刻被压到 P/2 以下。这说明：分块决定并行度的上限，均衡决定这个上限能被兑现多少。再叠加通信开销、内存带宽争用与同步等待，实际性能还会进一步下降，因此分块与均衡必须与通信、存储访问模式一起设计。

三类典型场景，分块方式完全不同

大规模数值模拟（如有限差分、有限元、格子玻尔兹曼）通常以空间网格为对象。分块的基本单位是网格子区域，块与块之间存在边界数据交换。此时块不能切得太小：块越小，边界面积与体积之比越大，通信占比越高。一个常用的经验判断是“计算/通信比”，例如三维区域分解中，若每块每方向有 n 个网格点，则计算量约正比于 n³，而边界通信量约正比于 n²，因此增大块尺寸能显著改善比值，但块数减少又会限制并行度——这正是分块需要权衡的地方。

参数扫描（如批量求解不同雷诺数、不同材料参数、不同初始条件）是典型的“易并行”任务：每个参数组合相互独立，没有运行期通信。此时分块的核心不是空间切分，而是任务粒度与调度策略。若各参数点的计算耗时差异很大（例如某些参数导致迭代不收敛、耗时陡增），静态平均分配就会失衡，需要采用动态任务队列：把参数点放入共享队列，空闲进程主动领取下一个任务，从而用“谁空谁取”的方式自然均衡。

数据并行处理（如大规模数组运算、批量文件解析、机器学习中的样本批处理）关注的是数据划分与访存局部性。分块时要尽量让每个单元处理连续内存段，避免跨块随机访问；同时要考虑分块大小与缓存行、页大小的匹配。例如按行分块处理一个 10000 × 10000 的矩阵时，按行连续切分通常优于按列切分，因为后者会破坏行优先存储下的空间局部性。

本课程的学习路径

课程整体按“先建立判断力，再掌握方法，最后落到工程实现”的顺序展开。前期会讲清楚分块粒度、通信开销、负载度量与加速比之间的关系，建立可量化的分析框架；中期进入具体方法：静态分块（均匀切分、加权切分、区域分解）、动态调度（任务队列、工作窃取、主从模式）、以及面向不规则计算的自适应重划分；后期结合实战项目，把方法落到可运行的程序上。实战项目概览如下（示例设定，用于说明任务形态，非实测结果）：

• 项目一：二维热传导模拟的区域分解。将 512 × 512 网格按块划分到 4 个进程，观察块尺寸变化对边界通信量与总时间的影响，并用计时对比不同分块方案。
• 项目二：参数扫描的动态调度。构造 200 个参数点、单点耗时在 0.1～2 秒之间波动的任务集，分别用静态均分与动态队列调度，统计各进程工作量与总完成时间。
• 项目三：不规则任务的自适应均衡。模拟粒子分布不均的场景，先按空间均分，再根据运行期统计进行重划分，比较重划分前后的最大负载偏差。

需要强调的是，分块与负载均衡不是一次性的设计动作，而是贯穿程序生命周期的持续判断：问题规模变了、硬件拓扑变了、输入数据分布变了，原先合理的分块可能立刻失效。因此本课程更看重“如何度量、如何判断、如何调整”的能力，而不是记住某一种固定切法。接下来各节将围绕这些判断逐层展开。