CHAPTER 31 / 架构、性能与并行

并行分解、分块与负载均衡

十个元素分给三个线程，怎样证明没有漏算、重算和越界？

阅读与推演约 60 分钟练习时间另计

这一章要弄清楚

建立半开区间的分块不变量
区分静态分配与动态调度
用串行参考验证并行结果

先备知识：线程、互斥锁与死锁 / CPU cache、缓存一致性与 SIMD / 可信测量、原始样本与性能模型

C++20 / macOS 与 Linux；本章的硬件模型只推演逻辑，不代表设备性能。

先找独立工作，再找线程数

并行化不是在已有循环外面随手创建几个线程。先定义每个输入元素对应什么工作、需要读哪些数据、会写到哪里。若每个线程写不同输出位置，并且输入只读，数据并行通常容易建立。若多个线程同时更新一个总和，就需要局部结果再合并，或其他正确同步；性能上的选择应在正确性之后讨论。

本章先处理均匀数组分块。把长度 n 分给 p 个工作者，令 q=n/p、r=n%p，前 r 个工作者各拿 q+1 个，其余拿 q 个。第 t 个区间起点可写为 t*q + min(t,r)，终点是起点加自己的长度。半开区间 [begin,end) 让长度等于 end-begin，相邻边界自然衔接，空区间也无需特殊表示。

三条证明比几个样例更强

覆盖性要求第一个 begin=0、最后一个 end=n；连续性要求前一区间 end 等于下一区间 begin；互斥性要求每个区间只包含自己的下标。再检查 begin 不大于 end，便能说明没有空洞和重叠。p 大于 n 时，有些线程分到空区间，这是合法状态；p=0 没有数学意义，接口应该拒绝。

常见公式 begin=n*t/p 也能均匀切分，但 n*t 可能在除法之前溢出。商余数写法能避免这种不必要的大乘积。它仍需要类型与输入范围检查：线程数来自用户输入时不能无限创建线程，真实实现通常使用线程池并限制资源。第一个例子穷举许多小规模与线程数组合，验证区间合同，而不是只检查十除以三这一种整齐案例。

局部归约让共享变少

第二例把每个区间累加到该线程专属的槽位，主线程 join 后再合并。工作线程不修改同一总和，因此不需要在每个元素处加锁。结果槽位预先分配，线程运行时不改变 vector 大小，也不产生会使引用失效的扩容。示例使用整数并限制数据范围，结果能精确比较；浮点版本下一章会解释为什么合并顺序会改变舍入。

相邻局部槽位可能落在同一缓存行，有伪共享风险。先把局部和留在工作线程的局部变量，结束时只写槽位一次，通常比循环中反复更新共享槽位更合理。不要过早为每个槽位添加巨大 padding；先评估写入频率与实际测量。

均匀元素不一定是均匀工作

如果每个元素耗时相近，静态连续分块简单、调度开销低、局部性好。如果元素代表大小不同的图节点或不同复杂度的请求，同样的元素数并不保证负载均衡。可以把任务拆成更小块，通过原子任务索引或工作队列动态领取；代价是调度开销、局部性下降与结果顺序管理。工作窃取适合某些递归任务，但不是所有 workload 的默认最优解。

性能上，线程创建和最终合并也要计入端到端时间。很短的数组串行可能更快，更多线程会竞争内存带宽。面试时先展示覆盖证明、读写所有权和串行参考，再讨论粒度、调度和上限。这样即使目标换成 GPU block 或多设备分区，基础推理仍能复用。

观察 · 推演

10 个元素分给 3 个工作者

计算大小

10/3 得到商 3、余数 1。

1 / 3

阅读完整推演文字

计算大小
n：10；p：3；q / r：3 / 1
10/3 得到商 3、余数 1。
确定区间
T0：[0,4)；T1：[4,7)；T2：[7,10)
前一个区间多拿一项，其余各三项。
局部结果
T0：10；T1：18；T2：27；合并：55
输入 1..10，局部和 10、18、27 合并成55。

跟着例子，走完一遍

例题 01C++20 · 本机可运行

商余数分块与边界穷举

n=10、p=3，随后遍历 n=0..257、p=1..16 检查区间。

q=3、r=1，首块多拿一个元素。
起点是 t*q+min(t,r)。
检查首尾、连续性和长度差至多一。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <utility>
std::pair<std::size_t,std::size_t> range(std::size_t n,std::size_t p,std::size_t t) {
    if(p==0 || t>=p) throw std::invalid_argument("partition");
    const auto q=n/p,r=n%p,begin=t*q+std::min(t,r);
    return {begin,begin+q+(t<r?1:0)};
}
int main() {
    for(std::size_t n=0;n<=257;++n) for(std::size_t p=1;p<=16;++p) {
        std::size_t previous=0;
        for(std::size_t t=0;t<p;++t) {
            const auto [begin,end]=range(n,p,t);
            if(begin!=previous || end<begin || end>n) throw std::runtime_error("coverage");
            previous=end;
        }
        if(previous!=n) throw std::runtime_error("last");
    }
    bool rejected=false;
    try {
        const auto [begin,end]=range(1,0,0);
        std::cout<<"unexpected zero-worker range=["<<begin<<','<<end<<")\n";
        return 1;
    } catch(const std::invalid_argument&){rejected=true;}
    if(!rejected) throw std::runtime_error("zero workers");
    std::cout<<"ranges=";
    for(std::size_t t=0;t<3;++t){auto [b,e]=range(10,3,t);std::cout<<(t?" ":"")<<'['<<b<<','<<e<<')';}
    std::cout<<'\n';
}

如何编译和运行下载的 .cpp 文件 →

结果与解释

ranges=[0,4) [4,7) [7,10)

半开区间连续覆盖原数组；空输入和比元素更多的分块同样成立。

在本机运行这个例子

下载后，在文件所在目录执行。需要支持 C++20 的编译器；POSIX 示例还需要章节说明中的系统条件。

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 27-a.cpp -o example && ./example

预期标准输出：

ranges=[0,4) [4,7) [7,10)

例题 02C++20 · 本机可运行

局部累加再合并

对 1..10 用 3 个工作者求和，再用多种规模与线程数比较串行参考。

提前分配 partial 槽位和线程容器。
每个线程局部累加，只在结束写一次自己的槽。
join 后合并，与 accumulate 比较。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <thread>
#include <vector>
long long parallel_sum(const std::vector<int>& values,std::size_t p) {
    if(p==0 || p>64) throw std::invalid_argument("workers");
    const auto n=values.size(),q=n/p,r=n%p;
    std::vector<long long> partial(p,0);std::vector<std::thread> workers;workers.reserve(p);
    struct JoinAll {
        std::vector<std::thread>& threads;
        ~JoinAll() {for(auto& t:threads) if(t.joinable()) t.join();}
    } join_all{workers};
    for(std::size_t t=0;t<p;++t) {
        const auto begin=t*q+std::min(t,r),end=begin+q+(t<r?1:0);
        workers.emplace_back([&,t,begin,end]{
            long long local=0;for(auto i=begin;i<end;++i) local+=values[i];partial[t]=local;
        });
    }
    for(auto& worker:workers) worker.join();
    return std::accumulate(partial.begin(),partial.end(),0LL);
}
int main() {
    int cases=0;
    for(std::size_t n: {0U,1U,2U,3U,7U,31U,1000U}) for(std::size_t p=1;p<=6;++p) {
        std::vector<int> v(n);for(std::size_t i=0;i<n;++i) v[i]=static_cast<int>(i%17)-8;
        if(parallel_sum(v,p)!=std::accumulate(v.begin(),v.end(),0LL)) throw std::runtime_error("oracle");
        ++cases;
    }
    const auto result=parallel_sum({1,2,3,4,5,6,7,8,9,10},3);
    if(result!=55) throw std::runtime_error("example");
    std::cout<<"sum="<<result<<" cases="<<cases<<'\n';
}

结果与解释

sum=55 cases=42

线程间没有共享累加写入；主线程在 join 后读取结果。

在本机运行这个例子

下载后，在文件所在目录执行。需要支持 C++20 的编译器；POSIX 示例还需要章节说明中的系统条件。

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 27-b.cpp -o example && ./example

预期标准输出：

sum=55 cases=42

常见错误

分块后剩余元素无人处理

每个线程只处理 n/p 个元素；n=10、p=3 时最后一个元素被遗漏。

修正思路：通过商余数分配或正确尾部区间覆盖全部 n；用覆盖、相邻边界和串行参考双重验证。

轮到你动手

先写预测或代码，再按需打开提示。完整答案用于对照自己的推理。

练习 1

把 n=3 分给 p=5，按本章公式列出区间并解释空块。

给我一点提示

q=0、r=3。
后两个块长度为零。

查看答案与推理

区间是[0,1)、[1,2)、[2,3)、[3,3)、[3,3)。所有三个元素恰好一次覆盖；空块合法，但实际线程池可能避免为其启动任务。

练习 2

若第一个元素处理100毫秒，其余九个各1毫秒，静态三个连续块会怎样？提出替代方案。

给我一点提示

元素数均衡不代表耗时均衡。
比较大任务是否可进一步拆分。

查看答案与推理

第一块约103毫秒，其余各3毫秒，整体受第一块限制。动态小块领取可分散其余工作，却无法消除不可拆的100毫秒任务；若业务允许，应继续拆该大任务，否则承认关键路径上限。

把理解说出来

先用中文讲清因果，再用英文回答。问题依据技能主题编写，并非公司内部题库。

解释

为什么用半开区间？

参考回答 / English answer

长度是end-begin，空区间自然表达，相邻区间共享边界却不共享元素。

Half-open ranges make lengths and empty ranges simple. Adjacent ranges meet without overlapping elements.

找错

n/p 固定分块遗漏什么？

参考回答 / English answer

当有余数时尾部没有分配；必须把余数分散或让最后一块延伸到n。

Integer division leaves a remainder. The partition must explicitly assign those remaining elements.

预测

p 大于 n 是否必然错误？

参考回答 / English answer

不是，允许空任务即可正确覆盖；资源上可能不值得启动那么多线程。

Empty partitions can be correct. They may still be wasteful if each creates a real thread.

追问

局部结果为什么要提前分配？

参考回答 / English answer

线程运行时扩容会移动存储并使引用失效；固定槽位让各线程写入所有权清晰。

Preallocation keeps result storage stable. Each worker can then own a distinct slot without concurrent structural changes.

解释

动态调度什么时候有用？

参考回答 / English answer

任务成本不均时减少尾部空闲；需支付领取、同步与局部性代价。

Dynamic scheduling helps when task costs vary. It trades scheduling overhead and locality for better balance.

找错

更多线程为何可能更慢？

参考回答 / English answer

线程创建、调度、共享带宽、缓存争用和合并开销都可能增加；小任务尤其明显。

More threads add overhead and can saturate shared resources. The useful thread count depends on the workload and memory system.

继续查证

CS149：Parallel Computing ↗
parallel decomposition、work distribution、scheduling 讲次
C++ draft：Thread completion ↗
join 的同步关系与线程完成