深入篇第1节：并行扫描（ScanPrefix Sum）——从串行到并行的经典演化

张开发
• 2026/4/8 22:24:48 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

深入篇第1节：并行扫描（ScanPrefix Sum）——从串行到并行的经典演化
引言前缀和是并行算法中的“Hello World”，但想写好它，你需要吃透共享内存、warp shuffle和归约树在进阶篇中，我们学习了归约——将一组数据合并为一个值。今天，我们将探讨一个更强大的并行原语：扫描（Scan），又称前缀和（Prefix Sum）。扫描是许多并行算法的基础：排序、基数排序、流压缩、稀疏矩阵运算等。它的目标很简单：给定输入数组[a0, a1, ..., an-1]，计算输出数组[a0, a0+a1, a0+a1+a2, ..., a0+...+an-1]。但简单背后藏着复杂的并行化挑战。串行扫描是线性的，但并行扫描需要大量通信和同步。今天，我们将从朴素实现出发，逐步构建一个高效的并行扫描算法，并学习如何利用共享内存和warp shuffle优化。一、问题定义1.1 扫描的两种变体包含扫描（Inclusive Scan）：输出第i个元素包含第i个输入out[i] = sum_{j=0}^{i} in[j]排除扫描（Exclusive Scan）：输出第i个元素不包含第i个输入（通常将out[0]设为0）out[i] = sum_{j=0}^{

更多文章