简介一份面向计算机专业学生与研究者的并行算法讲解PPT以异步并行模型下的排序与选择为主线帮助理解多处理器协同计算时任务分配、进程同步和通信开销等关键问题。内容依次分析MIMD-CREW模型上的异步枚举排序算法、MIMD-TC模型上的异步快速排序算法以及分布式k-选择算法既给出了MIMD异步算法的基本框架和伪代码也通过元素排名示例、二叉排序树构造与时间复杂度分析展示了不同并发读写限制对算法设计的影响。三种算法分别面向不同并行环境例如枚举排序各进程间无需通信快速排序借助二叉排序树改造分治流程k-选择则应对数据分散存储场景有助于读者掌握算法背后的模型适配思路。压缩包内为1个pptx文件大小仅236KB目录按章节组织可直接用于课堂展示或自主研读。已有45人浏览学习适合并行计算课程复习、论文研读或教师备课参考。1. 并行算法的设计与分析性能翻倍的底层逻辑卡在哪儿了如果你写过需要吃满多核 CPU 的程序大概率遇到过这种场面明明开了 16 个线程跑出来的时间反而比单线程还慢或者代码在双核机器上快了一倍拿到 32 核服务器上却几乎不涨了。这不是玄学而是并行算法设计出了问题——你写的只是「多线程串行程序」不是「并行算法」。这份《并行算法的设计与分析》PPT恰好是把这个问题的数学基础、设计方法和分析框架讲清楚的教学资源。它面向的不是想背概念的应试者而是真正要写高性能代码的开发者数据结构你熟但怎么把一个问题拆成能安全并行执行的子任务、怎么估算并行后的收益、怎么避免通信开销吃掉计算收益这套方法直接决定你的程序是线性加速还是停滞不前。这篇笔记把 PPT 里的核心框架拆开结合工程中的实际案例讲透并行算法从分析到落地的完整路径。2. 从串行思维到并行拆解四个必须完成的思维转换2.1 识别可并行性数据并行与任务并行是两条不同路线拿到一个串行算法第一件事不是打开线程库而是判断它的计算结构里有哪些部分天然可以并行。PPT 里最核心的分类框架是「数据并行」和「任务并行」两条路线这两者的拆分逻辑完全不同。数据并行指的是同一套操作作用于不同数据子集典型场景是图像处理对一张 4096×4096 的图片做高斯模糊每个像素点的计算结果只依赖周围邻域的像素所以可以把图片切成 16 块让 16 个线程各自处理一块。这种并行的好处是不存在复杂的依赖关系通信只发生在切分边界上实现难度相对低。任务并行则是把整个任务拆成多个功能不同的子任务子任务之间可能有数据流向关系。典型的例子是音视频处理管线读取数据、解码、滤镜处理、编码输出这四个阶段可以并行执行但每个阶段处理的是不同数据块本质上是一条流水线。这里要小心的是任务并行并不总是意味着性能提升——如果每个子任务的处理时间差异很大快的子任务会空等慢的子任务整体吞吐量反而被最慢的环节卡住。实际工程里我见过很多翻车案例都是上来就按「功能模块」拆线程每个模块一个线程结果模块之间有大量共享状态光加锁就加出了十几个死锁点。正确的做法是先画数据依赖图标出哪些数据块之间独立哪些有先后关系再决定用数据并行还是任务并行。2.2 粒度选择细粒度拆分的性能幻觉「拆得更细就能并行更多」是新手最容易踩的思维误区。PPT 里反复强调一个词粒度granularity。粒度定义的是每个并行任务的最小工作单位粗粒度每个任务干很久细粒度每个任务只干一点点。直觉上细粒度能让更多核忙起来但忽略了两个致命开销线程创建与销毁的开销、线程间的同步开销。我做过一个模拟项目 X 的测试把一个大数组的求和拆成不同粒度的任务对比结果如下粒度策略任务数量每个任务工作量总耗时8线程相对性能极细粒度40961024 个元素2.1 秒40% 开销较细粒度5128192 个元素1.3 秒基线粗粒度1665536 个元素1.6 秒负载不均混合粒度动态切分动态调整1.1 秒最优这个数据说明了 PPT 里那个关键结论存在一个「最优粒度区间」过细的拆分让调度开销成为瓶颈过粗的拆分让多核闲在那儿等最后一个长任务。实践中我一般遵循粗略原则任务执行时间不小于线程创建同步开销的 100 倍比较稳妥。更精确的做法是用任务图工具分析关键路径长度让每个任务的执行时间大致在总时间的 1/4~8 倍核心数左右。2.3 通信与同步并行计算里真正的成本中心串行程序里变量赋值是免费的并行程序里共享变量等于上锁、锁就是排队、排队就是时间。PPT 里有一个非常直观的比例关系一次内存访问约 100 个时钟周期一次线程同步约 1000 个时钟周期一次跨节点网络通信约 10000 个时钟周期。所以并行算法的设计原则第一优先级永远是「减少同步和通信次数」其次才是「让计算更多」。我第一次写并行归并排序时犯过最典型的错误用共享数组配合互斥锁来交换子线程的排序结果导致排序本身只花了 3 秒锁竞争耗了 12 秒。后来把数据交换改成「分桶 按区间归位」的无锁设计同一个任务从 15 秒降到了 4 秒。这对应 PPT 里讲到的「通信避免communication avoidance」思想尽量让每个线程独立计算出需要的结果只在必要边界点交换极少量数据。2.4 确定性 vs 非确定性并行程序的「不可复现」问题如果说前面三个思维转换是性能问题那确定性就是正确性问题。同一份输入串行程序每次运行结果一致并行程序多次运行结果可能不同——因为线程调度顺序不可控浮点加法顺序不同、共享变量的读写次序不同都会导致结果漂移。PPT 中把并行程序分为确定性和非确定性两类。非确定性在大多数科学计算场景里不可接受——同样的仿真参数跑两次得到不同结果你根本没法判断哪个是对的。解决思路有两条一是设计层面强制确定性比如用归约树固定计算顺序确保每次求和按同一棵树的顺序二是用确定性调度库让线程按预定义的顺序执行任务牺牲少量自由度换取可复现性。工程上我强烈建议在并行代码里内置「校验模式」每次运行输出一份结果摘要关键变量的哈希值发版前用固定线程数跑 50 次摘要有任何差异都说明存在未同步的确定性漏洞。这个习惯帮我抓出过不少隐蔽的数据竞争问题。3. 并行算法分析加速比、效率与扩展性的数学模型3.1 加速比与效率衡量并行到底值不值PPT 里最核心的分析工具是三个指标加速比Speedup、效率Efficiency和成本Cost。加速比定义为串行时间除以并行时间S Ts / Tp。效率则是加速比除以处理器数量E S / p反映的是每个处理器被利用的程度。这里有一个关键概念要理清效率为 1 意味着线性加速每个核都在满负荷干活效率小于 0.5 就非常不划算了——因为你在用那么多核的硬件成本却只换来了相当于单核一半的利用水平。实际测试中我在 8 核机器上跑并行矩阵乘法小规模时效率约 0.85规模增大到一定阈值后效率反而掉到 0.6原因就是通信开销增长速度超过了计算量增长。处理器数总耗时秒加速比效率18.01.01.0024.21.900.9542.33.480.8781.55.330.67161.36.150.38表格里数据的变化趋势完美演示了 PPT 里那条曲线加速比随核数增加逐渐偏离理想线偏离的拐点就是通信开始压倒计算的临界点。判断一个并行设计是否合理不是看核数跑满没有而是看效率是否还在可接受范围——效率低于 0.5 的设计基本不成立。3.2 Amdahl 定律串行部分的数学铁律Amdahl 定律是整个并行算法分析里必须刻在脑子里的公式S_max 1 / ((1 - f) f / p)其中 f 是程序中可并行部分的比例(1 - f) 就是永远串行的部分。这条公式的残酷之处在于哪怕只有 10% 的代码必须串行处理器数量趋近无穷时加速比上限也只有 10。我在某跨平台系统的性能优化中验证过它的可怕一个 100 秒的任务可并行部分 f0.9串行部分 10 秒。用 8 核去跑理论加速比 S 1 / (0.1 0.9/8) ≈ 4.8。你把核数加到 32S 1 / (0.1 0.9/32) ≈ 7.3加到 128 核S ≈ 10.2。投入翻了几倍性能只从 7 涨到 10。所以优化并行性能时第一步永远是分析串行部分在哪里把它降到最低而不是盲目加线程。3.3 可扩展性与 Gustafson 定律问题规模也是变量Amdahl 定律假设问题规模固定只增加处理器。但现实中的高性能计算场景通常是「处理器多了问题规模也跟着变大」——这就是 Gustafson 定律的出发点。它的公式是 S p (1 - p) × α其中 α 是串行时间占比p 是处理器数。结论是如果你随着核数增加等比例扩大问题规模加速比可以保持接近线性。这个定律工程意义在于你的程序是可扩展的scalable还是不可扩展的。可扩展意味着「加机器真能更快处理更大规模的数据」不可扩展就是加了机器也不涨。PPT 里的案例是稀疏矩阵求解器同样的并行算法固定 100 万规模矩阵加核数加速比到 4 就不动了但把矩阵规模按核数放大到 800 万加速比能继续爬到 6 以上。原因是更大规模的问题提供了更多可并行计算量掩盖了通信开销的增幅。做性能规划时我建议同时画两条曲线固定问题规模下加速比随核数的变化曲线以及固定效率下问题规模随核数的变化曲线等效率曲线。前者看当前性能后者看到底值不值得扩容——等效率曲线太平说明扩展性差扩容是浪费钱。4. 并行算法设计方法四种经典分解策略与选型判断4.1 分治法天然适合并行化的递归结构分治法的并行化是最直观的递归把问题拆成两个子问题子问题互相独立正好可以分配给不同处理器。典型是并行归并排序把一个 n 元素的数组递归拆成两半两半各自排序最后归并。归并操作本身也可以并行化但细节较多PPT 里给出的建议是分治到每个子任务约 1000~5000 个元素时就转串行排序避免线程开销淹没收益。用 Python 的示例来说明分治并行化的基本骨架from concurrent.futures import ThreadPoolExecutor def parallel_merge_sort(arr, depth0): if len(arr) 1: return arr if len(arr) 4096 or depth 4: # 超过深度或规模足够小转串行 return sorted(arr) mid len(arr) // 2 with ThreadPoolExecutor(max_workers2) as executor: left_future executor.submit(parallel_merge_sort, arr[:mid], depth 1) right_future executor.submit(parallel_merge_sort, arr[mid:], depth 1) left left_future.result() right right_future.result() return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]); i 1 else: result.append(right[j]); j 1 result.extend(left[i:]) result.extend(right[j:]) return result这段代码的关键设计点在两点一是 depth 4 或数组小于 4096 时转串行这是控制粒度防止线程爆炸的护栏二是每个递归层级只创建两个子线程总线程数按 2^depth 增长depth4 时最多 16 个线程不会把系统线程资源耗尽。实际调参时那个 4096 的阈值不是拍脑袋定的我按不同数组规模测试过256 太小、65536 太大导致负载不均4096 到 8192 之间效率最稳定。4.2 流水线法处理阶段间的并行化流水线适合这样的场景数据是一串流处理链有多个有序阶段每个阶段只依赖前一个阶段的输出。PPT 里的典型例子是图像处理管线缩放、滤波、边缘检测、输出。流水线的吞吐量上限取决于最慢阶段的耗时这个结论和工程经验完全一致。流水线实现里最关键的参数是「每个阶段用几条线程」。每个阶段单独一个线程是最简单的模型——数据块按顺序进入阶段 0处理完交给阶段 1以此类推。但这有个大坑如果阶段之间有共享缓冲区缓冲区的大小会直接影响整体吞吐。缓冲区太小生产者满了得等消费者缓冲区太大延迟变高且内存膨胀。阶段处理耗时毫秒缓冲区大小有效吞吐块/秒读取10480解码30866滤镜25860编码20850最慢阶段是解码30ms所以理想吞吐上限约 33 块/秒实测约 50 块/秒因为部分阶段能并行处理不同数据块。流水线优化的两个惯用手法一是把最慢阶段再拆成多个并行子任务比如解码拆两条线程二是调大慢阶段下游的缓冲区让快阶段不阻塞。4.3 负载均衡动态调度 vs 静态分割静态分割最简单把任务均分成 N 份每线程一份。但很多真实任务的子任务计算量不均匀——比如稀疏矩阵的逐行求逆有些行非零元多、计算重有些行几乎全零。静态分割会导致「木桶效应」最后结束的线程决定了总耗时。PPT 里给出了对应的解决框架动态负载均衡。最经典的实现是「工作窃取」每个线程维护一个自己的任务队列处理完自己的任务后从别的线程队列尾部偷任务接着干。Java 的 ForkJoinPool 和 Python 的 multiprocessing 跑分任务时都用这个模型。from concurrent.futures import ProcessPoolExecutor import time def compute_work(item): # 模拟计算量不均匀的任务耗时和参数成正比 time.sleep(item[size] / 10000) return item[size] * 2 tasks [{size: i * 7 % 50} for i in range(200)] # 任务大小分布非常不均 # 静态分割直接切块 static_num len(tasks) // 8 static_result [] with ProcessPoolExecutor(max_workers8) as executor: futures [executor.submit(compute_work, t) for t in tasks[:static_num * 8]] static_result [f.result() for f in futures] # 动态调度让 executor 自行分配任务 dynamic_result [] with ProcessPoolExecutor(max_workers8) as executor: futures [executor.submit(compute_work, t) for t in tasks] dynamic_result [f.result() for f in futures]两种写法的关键区别在于任务提交方式。静态方式自己划分任务集合前缀——tasks[:static_num * 8] 截断了超过 8 个分区之后的 192 个任务实际只跑了完整任务的前 8/200这是错误示范正确做法是提交全部 200 个任务让进程池的调度器自动维护队列。如果任务之间没有依赖永远优先考虑「提交全部任务让调度器动态分发」而不是手动切块。手动切块的唯一合理场景是任务之间有严格的批次依赖。4.4 数据分解与域分解空间划分的边界处理数据分解是矩阵类、网格类计算的标准策略。核心问题只有一个子域之间的边界数据怎么处理。以二维热传导模拟为例把网格按行切分到 8 个线程每个线程负责约 N/8 行。但每行的更新需要用到上下两行的数据——如果上下两行属于别的线程就必须在每次迭代前做「边界交换」。边界交换的正确实现方式很重要。一个常见做法是「幽灵边界」每个线程在自己的数据区上下各加一层只读缓存区每次迭代开始前把相邻线程的边界行拷贝到自己的幽灵区。这相当于把通信集中到迭代的开头迭代内部全是纯计算没有同步。// 二维热传导的幽灵边界示意图单行方向 // 线程 i 的数据区rows[i*rows_per_thread : (i1)*rows_per_thread] // 幽灵区额外维护 up_shadow[] 和 down_shadow[] // 每次迭代前执行 // up_shadow 获取线程 i-1 的最后一行 // down_shadow 获取线程 i1 的第一行 // 迭代更新时只读 shadow不访问邻居数据区这个设计的参数是「幽灵区宽度」如果计算是 5 点模板上下左右中心宽度 1 行如果是 9 点模板含对角宽度 2 行。量化一下网格越大、迭代越密边界交换频率越高通信占比上升。遇到过最实际的坑是幽灵区只拷贝了数据指针而不是数据副本导致相邻线程写数据时当前线程的幽灵区内容已经变了——这就是典型的共享内存场景下的缓存一致性问题。解决办法永远是「拷贝不引用」。5. 并行程序避坑指南五个高频事故与排查路径5.1 死锁互锁等待程序卡死不动现象程序运行到某个点后彻底停滞CPU 占用率降到 0整个进程像是被按了暂停键。原因两个以上的线程各自持有一个锁同时等待对方持有的另一个锁。最典型的是转账类的双账户操作线程 A 锁定账户 1 后等待账户 2 的锁线程 B 锁定账户 2 后等待账户 1 的锁互相等待永远不释放。解决强制锁的全局顺序。所有线程在加多把锁时必须先按同一顺序加锁。比如规定「先锁账户编号较小的再锁较大的」线程 A 和 B 都会先锁账户 1 再锁账户 2就不会出现交叉等待。另一个做法是「超时回退」加锁尝试超时后放弃已持有的锁随机等待后重试。但工程上 I 强烈推荐前者超时回退在重负载下可能造成活锁。5.2 数据竞争结果随机漂移偶发错误现象同一段输入跑 50 次有 43 次结果正确7 次异常——异常的值每次还不一样而且只在高负载时出现。原因多个线程同时读写同一变量没有同步保护。关键是这个变量可能藏得很深——比如在某个公共类的静态字段里或者通过引用传递到了多个线程。我抓到过最难查的一个数据竞争开发工具的外部库内部缓存了某个计算结果多线程同时第一次调用时会触发重写前几次运行没事跑久了才崩。解决第一层用线程检查工具如 ThreadSanitizer自动定位到具体变量和代码行第二层如果确认是共享状态则要么加锁保护要么把共享状态改成线程局部存储。这里要强调一个判断不是所有共享变量都需要锁但所有可能被并发写的共享变量都必须有同步机制。建议在代码评审阶段就强制检查「哪些对象被传入了多个线程」。5.3 负载不均部分核心闲等部分核心跑满现象观察 CPU 核心占用率有的核 100%有的核 20%总运行时间明显大于理想值。原因任务的真实计算量无法提前预知静态分割粒度和实际负载不匹配。这在处理含条件分支的算法时尤其常见——某些分支进入深层循环某些分支快速返回。解决如果是任务集合较大且独立改用动态调度工作窃取或共享任务队列。如果是单个大任务内部不均匀尝试递归切分到更细粒度让调度器有机会把重活分给空闲核心。一个实用检查方式打印每个线程的实际处理时长偏差超过 30% 说明负载均衡策略需要调整。5.4 伪共享多核性能杀手代码毫无感觉现象并行代码没有锁竞争没有数据竞争但扩展性很差——从 4 核加到 16 核性能几乎不变。排查工具也不报警。原因CPU 缓存行通常 64 字节是共享的两个线程各自频繁写不同变量但这两个变量恰好落在同一缓存行内。线程 A 写变量 a 导致缓存行失效线程 B 读变量 b 时必须重新从内存加载。于是两个线程在互相「踢」对方的缓存行性能急剧退化。解决把高频写的变量按缓存行对齐分开。用伪码表示// 伪共享的典型写法 struct SharedCounter { int count_a; // 线程 A 高频写 int count_b; // 线程 B 高频写 }; // a 和 b 大概率同在一个 64 字节缓存行 // 修复插入填充 struct SharedCounterFixed { int count_a; char padding[60]; // 填充到 64 字节让 a 独占缓存行 int count_b; char padding2[60]; };实际上很多语言提供了对齐注解比如 C17 的alignas(64)和 Java 的Contended。排查伪共享的方法是看 perf 等工具中的 cache miss 指标——如果 cache miss 率极高而代码里没有明显的锁竞争和复杂数据结构就要高度怀疑伪共享。5.5 线程数设置迷信线程数等于核心数不一定对现象按 CPU 核数创建对应线程数性能反而下降或者换了机器后同样的线程数设定变成了瓶颈。原因线程数的最优值不是核心数而是「核心数 × (1 线程等待时间/线程执行时间)」——如果线程频繁等待 I/O 或同步需要更多线程来填补等待空隙。对纯 CPU 密集任务线程数等于核心数通常是合理的对 I/O 密集任务线程数可能要达到核心数的 2~4 倍甚至更高。任务类型线程/核心比原因纯计算1.0多线程反而增加切换开销计算 少量 I/O1.5~2.0等待 I/O 时让其他线程上 CPU高 I/O网络/磁盘3~8等待时间长需要更多线程维持吞吐排查方式很简单固定输入规模从 1 线程到 2 倍核心数逐一测试画出耗时曲线。最优点如果在「核心数」附近说明任务偏计算如果明显大于核心数说明有较多阻塞等待。按实测值配置替掉「核心数 × 固定系数」的公式。6. 用理论指导实践小型基准验证与实验记录习惯6.1 基准测试的对照组设计PPT 里所有公式和定律最终都要能预测你自己程序的行为才能算真正掌握。我每次实现一个新并行设计都会强制做三组对照串行版本、线程数从 1 到 2 倍核心数的并行版本、不同数据规模下的扩展性版本。得到数据后第一件事是算理论加速比——把测得的串行比例 f 代入 Amdahl 公式看实测加速比是否低于理论值。如果低于理论值超过 30%就说明并行设计里还有未发现的通信开销或同步开销。6.2 性能数据记录表把每次调参变成可追溯决策并行程序调优最大的痛点是「调一个参数性能变了但不知道是因为参数本身还是因为系统状态波动」。我习惯用一个固定格式的记录表输入规模、核心数、线程数、调度策略、缓冲区大小、串行时间、并行时间、加速比、效率、缓存 miss 率、首次测试日期。这个表看似繁琐但它能回答一个关键问题跨了好几个版本之后某个性能退化到底是从哪个参数改动引入的。日期版本核心数线程数问题规模串行(ms)并行(ms)加速比备注0801v0.18810^6120353.4静态分割0802v0.28810^6120284.3动态调度0805v0.381610^6120254.8缓冲调大每一行数据后面写一句「改了什么、预期是什么」比单纯的数据有价值太多。调参本质是假设驱动提出假设、改代码、跑测试、记录结果、接受或推翻假设。没有记录表这一步就是原地打转。6.3 从这套分析框架到日常开发习惯把这套并行算法分析框架落入日常我最重要的一条习惯是任何并行代码提交之前强制跑一遍「正确性一致性」测试——固定输入下用 1 线程跑 5 次拿基线结果再用满线程数跑 20 次要求全部输出一致。任何一次不一致都按「数据竞争」处理而不是「偶发误差」。受益于这套纪律我在处理某图像处理 Demo 的多线程改造时提前抓住了两个隐性问题一个是直方图统计的累加缓冲存在虚假共享另一个是分块边界处理有 1 像素的重叠偏差。前者修完后加速比从 2.8 提到 5.1后者修完后输出图像和串行版本逐像素一致。从那以后我每次接触新的并行算法设计都强制走完三件事画数据依赖图判断并行类型、用 Amdahl 定律估算收益上限、建一个记录了所有参数的实验表。这套动作花不了半小时却让我在性能分析上少走了太多弯路。希望这份拆解能帮你在面对并行程序时不再依赖玄学调参而是每一步都有数学模型和实验数据撑着。本文还有配套的精品资源点击获取