CS267 · 第 10 课

数据并行算法

数据并行是并行计算中最基础也最强大的范式——通过统一操作作用于大量数据，我们可以设计出 span 极低、可高效映射到 GPU、SIMD、SMP 等硬件的算法。

---

什么是数据并行？

数据并行（data parallelism）是指对一组数据元素执行相同的操作。它是并行计算中最自然的并行来源，因为数据元素之间通常相互独立。

归约（Reduce）与扫描（Scan）

数据并行中最核心的两个全局操作是归约和扫描：

• 归约（Reduce）：将数组 [x0, x1, ..., xn-1] 用二元算子 ⊕ 合并为单个值：x0 ⊕ x1 ⊕ ... ⊕ xn-1。
• 扫描（Scan / Prefix）：产生所有前缀的数组。包含（inclusive）扫描：out[i] = x0 ⊕ x1 ⊕ ... ⊕ xi；排他（exclusive）扫描：out[i] = x0 ⊕ ... ⊕ x(i-1)。

理想化代价模型：Span 与 Depth

为了分析并行算法的效率，我们使用两个关键度量：

• Work (W)：总操作数，对应串行时间。
• Span (S) / Depth：关键路径长度，即无限多处理器时的最短执行时间。

在 P 个处理器上的执行时间满足：

T(P) ≥ max(W/P, S)

并行度（parallelism）定义为 W / S。算法能达到的最大加速比受限于并行度。

Blelloch 并行前缀算法

Blelloch（1990）提出的并行 prefix 算法是一个经典的 work-efficient 并行算法：

• 上扫（reduce / up-sweep）：构建一棵二叉树，计算每个子树的局部和。
• 下扫（down-sweep）：利用树的信息，把部分和分发到每个位置，得到所有前缀。

// Blelloch parallel prefix (exclusive scan)
// Phase 1: up-sweep (reduce)
for d = 0 to log(n)-1:
  parallel for k = 0 to n-1 by 2^(d+1):
    a[k + 2^(d+1) - 1] += a[k + 2^d - 1]

// Phase 2: down-sweep
a[n-1] = 0  // exclusive scan: set identity
for d = log(n)-1 down to 0:
  parallel for k = 0 to n-1 by 2^(d+1):
    t = a[k + 2^d - 1]
    a[k + 2^d - 1] = a[k + 2^(d+1) - 1]
    a[k + 2^(d+1) - 1] += t

归约的下界证明

对基于二元算子 ⊕ 的归约，我们证明其 span 的下界为 Ω(log n)。

扫描的应用

扫描看似简单，却能解决大量问题。以下是一些典型应用：

1. 流压缩（Stream Compression）

给定数组 A 和布尔掩码 M，保留 M[i]==true 的元素并紧凑排列。

// 对掩码做 exclusive scan，得到输出下标
scan(M, out_idx)  // out_idx[i] = 前面 true 的个数
parallel for i:
  if M[i]: B[out_idx[i]] = A[i]

2. 基数排序（Radix Sort）

基数排序的每一轮都可以用 scan 实现：统计每个桶的元素个数，用 scan 确定每个桶的起始偏移，再用 scatter 把元素放到正确位置。

// 对 k 位 key 的数组做 radix sort（1 位为例）
// 1. 分离 0-bit 和 1-bit 的 mask
mask0 = (key & 1) == 0
// 2. 对 mask0 做 exclusive scan，得到 0 桶的输出位置
scan(mask0, pos0)
// 3. 1 桶的起始位置 = 总 0 个数
total0 = reduce(mask0)
// 4. 1 桶的输出位置
pos1 = (key & 1) * (total0 + pos1_raw) + ...
// 5. scatter 到输出数组

3. 链表排名（List Ranking / Pointer Doubling）

给定一个链表，计算每个节点到尾部的距离。串行是 O(n)，并行用 pointer doubling 可达 O(log n)。

// Pointer doubling for list ranking
// next[i] = 下一个节点的下标，-1 表示尾
// dist[i] = 到 next[i] 的距离（初始为 1，尾节点为 0）
while any next[i] != -1:
  parallel for i:
    if next[i] != -1:
      dist[i] += dist[next[i]]
      next[i] = next[next[next[i]]]
      next[i] = next[next[i]]

4. 斐波那契数列（Fibonacci via Matrix Prefix）

斐波那契递推可以写成矩阵乘法：

[F(n+1)]   [1 1]^n   [F(1)]
[ F(n) ] = [1 0]   × [F(0)]

因此 F(n) 就是矩阵 [[1,1],[1,0]] 的 n 次幂。多个 n 对应的值可以通过矩阵乘法并行前缀一次性算出。

5. n 位整数加法（Parallel Prefix Addition）

超大规模整数加法可以通过并行前缀进位（carry-lookahead）实现 O(log n) span。核心思想：

• 对每一位计算 generate（g = a & b）和 propagate（p = a ⊕ b）。
• 进位 c[i] 满足：c[i+1] = g[i] OR (p[i] AND c[i])。
• 这定义了一个"前缀"关系，可以用并行前缀求解。

// Parallel prefix addition ( Brent-Kung / Sklansky style )
for i in 0..n-1:
  g[i] = a[i] & b[i]
  p[i] = a[i] ^ b[i]
// (g, p) 定义一个二元算子:
// (g2,p2) ∘ (g1,p1) = (g2 | (p2 & g1), p2 & p1)
scan on (g, p) with operator ∘ → carry[i]
sum[i] = p[i] ^ carry[i]

6. 词法分析（Lexical Analysis）

在编译器中，需要判断每个字符是否是 token 的起始位置。这可以通过 scan 实现：

// is_start[i] = 1 当且仅当 A[i] 是 token 的第一个字符
// 规则：A[i] 与 A[i-1] 属于不同字符类
is_start[0] = 1
parallel for i = 1..n-1:
  is_start[i] = (class(A[i]) != class(A[i-1]))
// 如果需要给每个 token 编号，对 is_start 做 exclusive scan

7. 矩阵求逆（Triangular / Dense Matrix Inversion）

三角矩阵的求逆可以通过分块 + 并行前缀实现。对于稠密矩阵，LU 分解中的多个步骤都可以识别出 scan 模式。

8. 分段扫描（Segmented Scan）

给定一个数组和一组分段标志，在每个分段内独立做 scan。例如：

A     = [1, 2, 3 | 4, 5 | 6, 7, 8]
flag  = [1, 0, 0 | 1, 0 | 1, 0, 0]
result= [1, 3, 6 | 4, 9 | 6, 13, 21]

分段 scan 可以通过扩展扫描算子（在分段边界处重置）来实现。

映射到硬件

数据并行算法需要在具体硬件上执行。主要目标平台：

硬件	并行模型	适合的数据并行模式
SIMD / 向量机	同一指令作用于多个数据元素	规则的一元/二元操作、连续访存
GPU	SIMT，大量线程，内存层次丰富	大规模规则 stencil、reduce、scan
SMP / MPP	多核共享内存或分布式内存	分块数据并行，MPI + OpenMP 混合

SIMD 映射

SIMD（Single Instruction, Multiple Data）是最直接的数据并行硬件。一条向量指令同时对 V 个元素执行相同操作。SIMD 要求数据对齐且连续，不支持不规则的 scatter/gather（或效率很低）。

GPU 映射

GPU 通过 SIMT 实现数据并行：

• 规则操作（一元/二元）直接映射为 kernel，每个线程处理一个或多个元素。
• Reduce 用树形规约（如 warp shuffle + shared memory）。
• Scan 用 Blelloch 或 Hillis-Steele 算法，配合 shared memory 实现 block 内高效扫描。
• 不规则模式（scatter/gather、pointer doubling）需要小心处理访存冲突与负载均衡。

SMP / MPP 映射

在共享内存多处理器（SMP）和大规模并行处理器（MPP）上：

• 数据按块划分到不同节点/核心。
• 全局 reduce 需要跨节点通信（tree reduction、recursive halving）。
• 全局 scan 需要节点间通信，通常采用"局部 scan → 收集尾部 → 广播修正 → 合并"的策略。

---

本课要点

---

知识检查

---