HPC 并行算法设计模式

1. 主从模式 (Master-Worker)

主从模式是最直观的并行范式：一个 Master 负责任务分发与结果归并，多个 Worker 执行实际计算。该模式适合任务独立、粒度过细的场景，如蒙特卡洛模拟、参数扫描。

// 伪代码：MPI 主从模式
if (rank == MASTER) {
    for (int i = 0; i < N; i++) {
        int worker = receive_request_from_any();
        send_task(i, worker);
    }
    // 发送终止信号
    for (int w = 1; w < num_procs; w++)
        send_terminate(w);
} else {
    while (true) {
        send_request(MASTER);
        task = receive_task(MASTER);
        if (task == TERMINATE) break;
        result = compute(task);
        send_result(result, MASTER);
    }
}

复杂度分析：设总任务数 $N$，Worker 数 $P$，单次通信开销 $c$，单任务计算 $t$。理想加速比 $S = \frac{N \cdot t}{\frac{N \cdot t}{P} + P \cdot c}$。当 $N \gg P$ 且 $t \gg c$ 时，效率趋近 1。

2. 分治并行 (Divide and Conquer)

将原问题递归拆分为规模更小的子问题，子问题并行求解后合并结果。经典实例为并行快速排序、FFT、Karatsuba 乘法。

parallel_quicksort(A, lo, hi):
    if (hi - lo < CUTOFF) {
        sequential_sort(A, lo, hi);
        return;
    }
    pivot = partition(A, lo, hi);
    // 递归子问题并行执行
    spawn parallel_quicksort(A, lo, pivot);
    spawn parallel_quicksort(A, pivot + 1, hi);
    sync;  // 等待两个子任务完成

复杂度：并行快速排序在 CRCW PRAM 模型下深度为 $O(\log^2 n)$，工作量 $O(n \log n)$。

3. 流水线并行 (Pipeline Parallelism)

将计算划分为有序的多个阶段 (Stage)，数据像流水线一样依次流经各阶段，相邻阶段可 overlap 执行。适用于流式处理、图像滤波链、指令流水线抽象。

Input  → [Stage 1: 读取&解码] → [Stage 2: 滤波处理] → [Stage 3: 编码输出] → Done
         Thread A                Thread B              Thread C

假设每个 Stage 的处理时间分别为 $T_1, T_2, T_3$，则吞吐率由瓶颈阶段决定：$\text{Throughput} = \frac{1}{\max(T_1, T_2, T_3)}$。

4. SPMD (Single Program Multiple Data)

SPMD 是 HPC 的核心编程模型。所有进程执行同一份程序，但依据自身 rank 操作不同数据分区。MPI 程序几乎全部是 SPMD。

// 二维网格 Jacobi 迭代的 SPMD 实现
int i_start = rank * (N / num_procs);
int i_end   = (rank + 1) * (N / num_procs);

for (int iter = 0; iter < MAX_ITER; iter++) {
    // 计算内部点
    for (int i = i_start; i < i_end; i++)
        for (int j = 1; j < N - 1; j++)
            U_new[i][j] = 0.25 * (U[i-1][j] + U[i+1][j] + U[i][j-1] + U[i][j+1]);

    // 交换 halo 边界
    if (rank > 0)          MPI_Sendrecv(..., rank - 1, ...);
    if (rank < num_procs-1) MPI_Sendrecv(..., rank + 1, ...);
    swap(&U, &U_new);
}

关键要点：避免跨进程的全局同步；将全局通信转化为成对邻居通信，可显著降低延迟。

5. 数据并行 (Data Parallelism)

数据并行指对大规模数据集施加相同的操作，常见于 GPU 编程 (CUDA/OpenCL) 和 SIMD 指令集。特点是单指令流多数据流 (SIMD)。

// CUDA 向量加法 —— 数据并行示例
__global__ void vec_add(float *C, const float *A, const float *B, int n) {
    int idx = blockIdx.x * blockDim.x + threadIdx.x;
    if (idx < n)
        C[idx] = A[idx] + B[idx];
}

// 启动: <<< (n+255)/256, 256 >>>

性能考量：

• 全局内存合并访问 (Coalesced Access) 可将带宽提升 10 倍以上。
• 共享内存用于线程块内数据复用，减少 global memory 流量。
• 线程束分支发散 (Warp Divergence) 会串行化执行路径。

6. 任务窃取 (Work Stealing)

任务窃取用于动态负载均衡。每个 Worker 维护双端队列 (deque)，本地任务执行完毕时，从其它 Worker 队列尾部 “窃取” 任务，降低全局同步开销。

// Cilk / OpenMP task 的任务窃取语义
void execute(node *n) {
    if (n == NULL) return;
    if (is_leaf(n)) {
        process(n);
        return;
    }
    // 生成两个子任务，调度器自动处理任务窃取
    #pragma omp task
    execute(n->left);
    #pragma omp task
    execute(n->right);
    #pragma omp taskwait
}

理论保证：在 $P$ 个处理器的独占调度下，期望执行时间 $T_P \leq T_1/P + O(T_\infty)$，其中 $T_1$ 为串行工作量，$T_\infty$ 为关键路径长度。

7. 并行前缀和 (Parallel Scan / Prefix Sum)

前缀和是构建并行算法的基础原语，用于负载均衡、稀疏矩阵压缩、直方图计算等。

Blelloch Scan（Work-Efficient）：

1. Up-sweep（Reduction）：构建二叉树，计算各子树和。
2. Down-sweep：自顶向下传播前缀值。

// CUDA 并行前缀和（简化版）
__global__ void scan(float *out, const float *in, int n) {
    __shared__ float temp[2 * SECTION_SIZE];
    int tid = threadIdx.x;
    int offset = 1;

    // 加载数据到共享内存
    temp[2*tid]   = in[2*tid];
    temp[2*tid+1] = in[2*tid+1];

    // Up-sweep
    for (int d = n >> 1; d > 0; d >>= 1) {
        __syncthreads();
        if (tid < d) {
            int ai = offset * (2 * tid + 1) - 1;
            int bi = offset * (2 * tid + 2) - 1;
            temp[bi] += temp[ai];
        }
        offset *= 2;
    }

    // Down-sweep...
    if (tid == 0) temp[n - 1] = 0;
    // ... 反向传播省略

    out[2*tid]   = temp[2*tid];
    out[2*tid+1] = temp[2*tid+1];
}

复杂度：工作量 $O(n)$，深度 $O(\log n)$。相比串行 $O(n)$ 扫描，PRAM 效率为 $O(1/\log n)$，但在 $P = O(n/\log n)$ 时可达到线性加速。

8. 并行排序

样本排序 (Sample Sort) 在分布式内存环境下表现优异：

1. 每个进程本地排序并均匀采样 splitter；
2. Allgather 采样后全局确定 $P-1$ 个分界点；
3. 各进程按分界点交换数据（Alltoallv）；
4. 本地最终排序。

P0 [局部排序+采样] --splitters--> P1 P2 P3
P1 [局部排序+采样] --splitters--> P0 P2 P3
P2 [局部排序+采样] --splitters--> P0 P1 P3
P3 [局部排序+采样] --splitters--> P0 P1 P2
         ↓ 全局投票确定 splitter
      Alltoallv 数据交换
         ↓
   各进程本地 merge_sort

Bitonic Sort 适合 $n = O(P)$ 的小规模数据在超立方体拓扑上排序，其比较交换模式天然适配 Butterfly 网络，深度为 $O(\log^2 n)$。

选择并行排序算法时，需综合数据分布、内存拓扑、通信延迟和带宽进行权衡。对于不规则数据，样本排序结合任务窃取可显著改善负载均衡。