多大规模的循环适合使用多线程并行化？

一、根据循环规模N判断并行收益的逻辑 #

这类计算逻辑简单的循环是否适合并行，核心判断标准是并行节省的计算时间是否大于并行引入的额外开销：

• 固定开销：OpenMP的fork-join模型会产生固定开销，包括线程创建/复用调度、循环任务拆分分配、同步等，这类开销通常在微秒级，和N的大小无关。
• 计算收益：串行执行总时间为 N * 单迭代执行时间t，并行理想计算时间为 (N * t) / 可用核心数P，节省的时间为 N*t*(1-1/P)。

你给出的c[i] = a[i] + b[i]属于极轻量的访存密集型迭代，单迭代执行时间仅几纳秒：

• N=400时，串行总执行时间不到1微秒，远低于并行的固定开销，因此看不到收益，甚至会比串行更慢
• N=1e7时，串行总执行时间达到几十毫秒，远高于并行固定开销，此时就能拿到接近线性的加速比

对于这类轻量循环，20核x86平台下可以参考经验阈值：N>1e5时开并行有明显收益，N<1e4时不建议开并行。

二、估算收益需要掌握的硬件&开销知识 #

要更精准的计算并行收益/损失，需要明确以下参数：

• 并行调度开销
  • OpenMP并行区的基础开销：首次创建线程池的开销通常在几到几十微秒，后续复用线程池的开销会降低到微秒级
  • 调度策略开销：默认static静态分块调度的任务分配开销极低，dynamic/guided动态调度的开销会高1~2个数量级
• 单迭代的执行特征
  • 迭代是计算密集还是访存密集：你给出的例子属于访存密集型，性能瓶颈最终会卡在缓存/内存带宽，无法随着核心数线性提升
  • 缓存命中情况：如果a、b、c数组总容量小于CPU的L2/L3缓存容量，单迭代执行时间会比走内存低1~2个数量级，对应的N阈值也会更小
• 硬件参数
  • CPU核心数、各级缓存的容量与带宽、整机内存带宽：比如20核CPU共享32MB L3缓存时，当数组总容量超过32MB后，并行加速比上限由内存带宽和单核心访存带宽的比值决定
  • 缓存一致性开销：如果循环存在相邻迭代写入同一块缓存行的伪共享问题，会额外增加几十纳秒到几百纳秒每迭代的开销，大幅降低并行收益

内容的提问来源于stack exchange，提问作者Bbllaaddee