并行算法

并行算法 (Parallel Algorithm)

并行算法是指在多个处理单元上同时执行的计算方法，通过将问题分解为可并发处理的子任务，利用并行计算（Parallel Computing）架构来加速求解过程。与传统的串行算法不同，并行算法的核心挑战不仅在于计算的正确性，还在于如何有效地管理处理器之间的通信、同步与负载均衡，以最大化计算资源的利用率。

并行计算模型

PRAM模型 (Parallel Random Access Machine)

PRAM模型是并行算法理论分析的经典抽象模型。它假设有 $p$ 个处理器共享一个全局存储器，每个处理器在单位时间内可执行一次操作并访问一次共享内存，所有处理器同步执行指令。PRAM模型忽略了通信延迟和存储器层次结构，虽然理想化，但为算法的渐近分析提供了统一框架。

根据并发访问内存的冲突处理策略，PRAM可分为三种子模型：

1. EREW (Exclusive Read Exclusive Write)：同一时刻最多一个处理器可读/写同一内存单元。这是最严格也最贴近实际硬件的模型。
2. CREW (Concurrent Read Exclusive Write)：允许多个处理器同时读取同一内存单元，但写操作必须互斥。该模型在广播数据时具有天然优势。
3. CRCW (Concurrent Read Concurrent Write)：允许多个处理器同时读/写同一内存单元。写冲突的解决策略有 Common（所有写入值必须相同）、Arbitrary（任选其一写入）、Priority（按优先级写入）等。

实际并行模型

PRAM的简化假设与实际硬件差距较大。更贴近现实的模型包括：

• BSP模型 (Bulk Synchronous Parallel)：将计算组织为一系列超步（Superstep），每个超步内处理器独立计算，之后通过全局同步进行通信。该模型显式地考虑了通信成本。
• LogP模型：用四个参数——延迟（Latency）、开销（Overhead）、通信间隔（Gap）和处理器数（Processors）——刻画分布式存储器并行系统的性能特征。
• MapReduce与并行计算中的BSP变体：如Google的MapReduce、Apache Spark等现代大数据并行框架，其底层也暗含了BSP或类BSP模型的思想。

并行算法的性能度量

加速比与效率

设 $T(n)$ 为串行算法在问题规模 $n$ 下的运行时间，$T_p(n)$ 为使用 $p$ 个处理器时并行算法的运行时间：

• 加速比 (Speedup)：$S_p = \dfrac{T(n)}{T_p(n)}$。理想加速比为 $p$（线性加速比），但受限于数据依赖和通信开销，实际加速比往往低于 $p$。
• 效率 (Efficiency)：$E_p = \dfrac{S_p}{p} = \dfrac{T(n)}{p \cdot T_p(n)}$，反映处理器资源的平均利用率。
• 成本 (Cost)：$C_p = p \cdot T_p(n)$。若 $C_p = O(T(n))$，则称算法为成本最优（Cost-optimal）。

Amdahl定律与Gustafson定律

Amdahl定律揭示了固定问题规模下并行加速的上限。设问题中可并行部分的比例为 $f$（$0 \le f \le 1$），则 $p$ 个处理器的最大加速比为：

当 $p \to \infty$ 时，$S_p \le \frac{1}{1-f}$。这意味着即使拥有无限多的处理器，加速比也受限于串行部分的瓶颈。若 $5\%$ 的代码不可并行（$f=0.95$），则最大加速比仅为 $20$。

Gustafson定律则从另一个视角出发：当问题规模可随处理器数扩展时，设串行执行时间为 $\alpha + (1-\alpha)p$（$\alpha$ 为串行比例），则缩放加速比为：

该定律更为乐观——随着问题规模扩大，可并行的工作量增加，加速比可接近线性增长。

并行算法设计范式

分治策略 (Divide-and-Conquer)

分治策略天然适用于并行化：将问题递归分解为若干独立子问题，各子问题并行求解后合并结果。典型的例子包括并行归并排序（Parallel Merge Sort）和并行快速排序。关键在于分解与合并阶段本身也可并行化。

数据划分 (Data Partitioning)

将数据按块（Block）、循环（Cyclic）或块-循环（Block-Cyclic）的方式分配给各处理器。块划分有利于缓存局部性，循环划分则有利于负载均衡。数据划分广泛用于矩阵运算——如并行矩阵乘法中 $C = A \times B$ 可按行、列或子矩阵块分配给不同处理器。

流水线并行 (Pipeline Parallelism)

将计算过程划分为若干阶段，各阶段由不同处理器负责，数据流经各阶段形成流水线。适合可表示为有向无环图（DAG）的计算任务，常见于信号处理和深度学习推理中。

工作池模式 (Work Pool / Master-Worker)

维护一个共享的任务池，Master节点分发任务，Worker节点领取并执行。该模式具有良好的动态负载均衡能力，适合任务大小不一的场景，但Master节点可能成为通信瓶颈。

典型并行算法

\paragraph{并行前缀和 (Parallel Prefix Sum / Scan)}：给定数组 $a_1, a_2, \ldots, a_n$，计算所有前缀和 $s_k = \sum_{i=1}^{k} a_i$。该问题表面上具有强顺序依赖，但可通过上扫（Up-Sweep）和下扫（Down-Sweep）两阶段在 $O(\log n)$ 时间内完成，是构建众多并行算法的基本原语。

\paragraph{并行排序}：除并行归并排序和并行快速排序外，双调排序（Bitonic Sort）和奇偶交换排序（Odd-Even Sort）专为并行硬件设计。双调排序的比较模式固定，适合在GPU等SIMD架构上高效实现。

\paragraph{并行矩阵乘法}：经典的Cannon算法和DNS（Dekel-Nassimi-Sahni）算法将两个 $n \times n$ 矩阵的乘法从 $O(n^3)$ 降低到并行时间 $O(\log n)$（使用 $O(n^3)$ 个处理器）。实际中更常用的是分块矩阵乘法（Tiled Matrix Multiplication），以利用多级缓存层次结构。

\paragraph{并行图算法}：包括并行广度优先搜索（BFS）、并行最短路径算法（如 $\Delta$-stepping）和并行连通分量算法。图算法的并行化极具挑战性，因为图的不规则结构导致负载均衡困难，且内存访问模式不可预测。

同步与通信

并行算法不可避免地涉及处理器间的协同：

• 屏障同步 (Barrier Synchronization)：所有处理器必须到达同一点后才能继续。常用于超步之间的全局同步。
• 互斥与锁 (Mutual Exclusion / Lock)：保护共享资源的原子访问，防止竞态条件（Race Condition）。锁的粒度过粗会串行化并行执行，过细则增加锁管理开销。
• 无锁数据结构 (Lock-Free Data Structures)：利用原子操作（如CAS, Compare-And-Swap）实现并发数据结构，避免锁带来的性能瓶颈和死锁风险。
• 消息传递 (Message Passing)：在分布式存储器系统中，处理器通过发送和接收消息进行通信。MPI（Message Passing Interface）是实现此模式的主流标准。

并行算法的正确性与确定性

并行算法的正确性不仅要求最终结果正确，还须避免死锁（Deadlock）、活锁（Livelock）和数据竞争（Data Race）。非确定性并行算法即使对相同输入也可能产生不同输出（如使用随机化调度），这对调试和可重现性提出了更高要求。确定性并行（Deterministic Parallelism）是近年来研究的热点方向，旨在保证并行执行的确定性语义。

并行算法的设计与分析融合了算法理论、计算机体系结构和分布式系统的知识，是高性能计算、大数据处理和人工智能训练的基础支撑技术。