第11章：Parallel STL

从“可拆分、可独立、可合并”开始

parallel algorithm只有在work能拆成足够大的independent chunks、每个chunk执行不互相冲突、partial results能低成本合并时才可能加速。并行化同时引入task creation、scheduling、synchronization、cache coherence和load imbalance；小输入或cheap operation常被这些fixed overhead吞没。

先预测serial fraction、per-element cost、memory bandwidth和output coordination，再测threads scaling。不要只比较单线程与“最大线程数”；应画1、2、4...workers曲线，并记录CPU time、wall time、bandwidth与task count。plateau可能来自grain太小、bandwidth饱和或共享write contention。

parallel transform与grain size

parallel transform可把input range切成chunks，每个task在相同offset的output区间写独占元素，因此通常无需per-element lock。正确性要求input/output overlap符合algorithm contract，callable能并发调用且不修改共享state。若transform抛异常，runtime如何传播/终止也由具体parallel framework或execution-policy规则决定。

template <class Input, class Output, class Function>
void parallel_transform(Input first, Input last, Output output,
                        Function function, Executor& executor) {
    const auto count = std::distance(first, last);
    const auto grain = choose_grain(count, executor.worker_count());
 
    executor.for_chunks(count, grain, [&](auto begin, auto end) {
        for (auto index = begin; index != end; ++index) {
            output[index] = function(first[index]);
        }
    });
}

这个骨架隐含random access iterators；generic implementation需按category处理。grain size过小产生大量tasks与queue contention，过大则parallelism不足、tail chunk拖慢completion。dynamic work stealing改善不均匀任务，static partition在均匀contiguous data上更低overhead且locality更稳定。

memory-bound transform很快饱和DRAM bandwidth，多core不再线性加速。若function只是一次简单加法，SIMD可能比threads更重要；若每元素进行昂贵独立计算，task overhead更容易摊薄。parallel与vectorization是不同axes，par_unseq才允许两者组合但约束更强。

parallel count_if是reduction

count_if没有独立output positions，只需每个chunk计算local count，最后reduce partial counts。让所有threads每匹配一次就increment同一atomic会产生contention；local accumulator避免hot cache line，合并只与chunk数相关。

std::vector<std::size_t> partial(chunk_count);
 
parallel_for_chunks(input, [&](std::size_t chunk, auto first, auto last) {
    partial[chunk] = static_cast<std::size_t>(
        std::count_if(first, last, predicate));
});
 
const auto count =
    std::accumulate(partial.begin(), partial.end(), std::size_t{0});

partial counters本身若紧邻并被不同threads同时写，仍可能false sharing；可让每个task返回value给executor，或对per-worker slots做适当layout。predicate必须线程安全，且count type要容纳range size。

parallel copy_if的写位置难题

copy_if的每个input是否产生output取决于predicate，事先不知道目标offset。最直接方案用atomic fetch_add取得synchronized write position：每个matched item得到唯一slot，但所有matches竞争同一atomic，output order由runtime interleaving决定，通常不稳定。

稳定parallel copy_if可使用三阶段：第一遍并行计算match flag与per-chunk count；对counts做prefix sum得到每chunk exclusive output base；第二遍并行scatter，各chunk按input order写自己的exclusive output interval。它多一次pass和flags/count storage，却消除per-item global atomic并保留order。

// phase 1: local selection
parallel_for_chunks(input, [&](auto chunk) {
    for (auto index : chunk.indices()) flags[index] = predicate(input[index]);
    counts[chunk.id()] = count_flags(flags, chunk);
});
 
// phase 2: exclusive prefix sum of chunk counts
std::exclusive_scan(counts.begin(), counts.end(), offsets.begin(), 0uz);
 
// phase 3: stable scatter into disjoint output intervals
parallel_for_chunks(input, [&](auto chunk) {
    auto write = offsets[chunk.id()];
    for (auto index : chunk.indices())
        if (flags[index]) output[write++] = input[index];
});

0uz是较新标准的size_t literal，为了第一版C++17代码应改用std::size_t{0}；这里刻意暴露版本差异，项目代码不能直接复制而不检查language mode。完整实现还需分配恰当output size、处理move/copy exceptions和non-default-constructible value。

execution policies表达允许的执行方式

C++17 execution policies包括sequenced std::execution::seq、parallel par与parallel unsequenced par_unseq。seq在calling thread按顺序执行；par允许多个threads并行；par_unseq还允许同一thread内unsequenced/vectorized execution，因此callable不能使用vectorization-unsafe synchronization或依赖调用顺序。

std::transform(std::execution::par,
               input.begin(), input.end(), output.begin(), expensive_pure_fn);
 
const auto sum = std::transform_reduce(
    std::execution::par,
    input.begin(), input.end(), 0.0,
    std::plus<>{}, [](double x) { return x * x; });

implementation可以选择不创建threads，policy是permission而非performance guarantee。标准execution-policy overload对user function异常有特殊规则，常见标准policy下未捕获异常会导致std::terminate，不能假定像普通algorithm一样传播；应核对所用standard/library版本。

par_unseq callable不能拿普通mutex、allocate via unsafe paths或使用依赖forward progress的blocking primitive；vector lane阻塞可能deadlock。shared counters、logging和random engine都需重新审计。pure transform最适合，带side effects的for_each风险最高。

accumulate、reduce与transform_reduce

std::accumulate按iterator顺序把accumulator与每个element组合，适合order-sensitive fold。std::reduce允许重排与分组以支持parallel reduction，所以operation需满足足够的associativity/commutativity与type closure。floating-point addition不严格associative，并行结果可能与serial bit pattern不同。

transform_reduce把map与reduce融合，避免显式intermediate container，也可表达dot product。binary/unary operations必须能接受标准允许的argument combinations；不能只让T op T偶然工作。数值稳定性可通过wider accumulator、pairwise/Kahan-like策略或允许误差contract处理，但要测parallelism与accuracy取舍。

for_each没有返回reduction结果，parallel side effects只能写disjoint elements或使用明确同步。若真正意图是sum/count/collect，应选reduce或两阶段algorithm，不在for_each里锁住一个global accumulator。

GPU algorithms与数据移动

GPU拥有大量throughput-oriented execution lanes，适合规则、data-parallel、arithmetic-intensive work。host到device transfer、kernel launch、device allocation和result copy是fixed overhead；数据已驻留device且pipeline连续执行多个kernels时更容易获益，小range单次offload常得不偿失。

Boost Compute提供类似STL的GPU algorithms，并通过OpenCL管理context、queue、device buffers和kernels。API形似transform不代表host iterator可直接零成本使用；数据位置和queue synchronization决定实际路径。OpenCL kernel还需考虑work-group、coalesced access、branch divergence与device capability。

CPU parallel STL与GPU algorithms的比较应包括end-to-end transfer，而不只kernel time。若input由GPU前一步产生、output被GPU下一步消费，可把整个pipeline留在device；若每次从CPU复制少量数据再取回，CPU SIMD/threads往往更合理。数值结果还可能因device math、reduction order和precision不同，需定义tolerance。

第11章实验协议

1. 对parallel transform改变n、function cost与grain，绘制threads/scaling和bandwidth。
2. 比较global atomic count与per-chunk count+reduce，采集retries/cache traffic。
3. 对copy_if比较atomic write index与flag/count/prefix/scatter，验证stable order。
4. 用serial result作oracle，检查seq/par/par_unseq的side effects与异常路径。
5. 比较accumulate与reduce在integer/floating-point上的结果、速度和误差。
6. 用transform_reduce替代transform+temporary+reduce，记录allocation和passes。
7. 比较CPU serial、CPU parallel、GPU kernel-only与GPU end-to-end transfer。
8. 保持数据驻留GPU执行多stage pipeline，再与每stage往返host对比。

小结

• parallel algorithms需要可拆分work、独立chunks和低成本merge，grain决定overhead与balance
• parallel count_if应使用local counts后reduce，避免每match争用global atomic
• stable parallel copy_if可用flags、counts、prefix sum和disjoint scatter
• seq、par、par_unseq允许不同程度重排/并行/vectorization，不保证一定使用threads或更快
• accumulate保持顺序，reduce允许重组；floating-point结果可能改变
• transform_reduce融合映射与归约，for_each不适合隐藏global reduction
• GPU/Boost Compute/OpenCL收益取决于data residence、transfer、launch与kernel规则性
• 并行性能必须报告correctness、scaling、CPU/GPU资源、bandwidth和end-to-end时间