先记住一句话
先找成熟 primitive/library，再写 kernel；CUB/Thrust/cuFFT/cuSPARSE 已处理许多 architecture、dtype、edge case 和 autotuning。
1. Map
每个 output 独立：y[i]=f(x[i])。parallelism 最大，通常 memory-bound。多个 maps 应 fusion，避免每步读写 HBM；复杂 f 要看 special-function throughput 与 branch divergence。
2. Reduction
sum/max/min 等 associative operation 用树形合并，把 span 降到 O(log N)：thread local → warp reduce → block reduce → grid/final reduce。浮点加法不严格 associative，parallel order 会带来数值差异。
3. Prefix scan
输出 y[i]=x[0]⊕...⊕x[i]，用于 compaction、radix sort、CSR offsets。既有 up-sweep/down-sweep，也有 warp/block hierarchical scan。它有跨元素 dependency，但仍可通过 tree decomposition 并行。
4. Sort、select 与 histogram
radix sort 适合整数/bitwise keys；comparison sort 更通用。histogram/TopK 常受 atomics 和 skew 支配，可 privatize per warp/block bins 再 merge。K、key range 与 distribution 决定实现。
5. Gather、scatter 与 atomics
gather 的 reads irregular，scatter 还可能 write collision。index sorting/reordering 可改善 locality，但 preprocessing 有成本；重复 indices 的 gradient/update 需要 atomic 或先 segment reduce。确定性与速度常冲突。
6. Stencil
PDE、image convolution、finite difference 每点读邻域。tile + halo 放 shared memory，复用相邻数据；边界条件、time tiling 和 domain decomposition 决定效果。算术少时通常 bandwidth-bound。
7. FFT
FFT 把 O(N²) DFT 降到 O(N log N)，但 stages 含全局 data reordering/butterflies。cuFFT plan 创建、workspace、batch、size factorization 和 layout 对性能很重要；不要把 plan/setup 算进 steady-state kernel time却不说明。
8. Sparse kernels
SpMV/SpMM work 取决于 nonzeros，CSR row length 不均会 load imbalance；index bytes、random access 让 arithmetic intensity 低。结构化 sparsity可用专门 Tensor Core path，非结构稀疏只有足够 sparsity 且格式/shape 合适才可能胜 dense。
9. Domain decomposition
多 GPU stencil/PDE 把 domain 分块，每卡计算 interior 并交换 halo。通信可与 interior compute overlap；surface/volume ratio 决定 strong scaling，block 越小边界占比越大。
10. Library map
| 需求 | 优先工具 |
|---|---|
| BLAS/GEMM | cuBLAS/cuBLASLt |
| Conv/deep learning | cuDNN |
| FFT | cuFFT |
| Sparse linear algebra | cuSPARSE |
| Reduce/scan/sort | CUB / Thrust |
| Solver | cuSOLVER |
11. 四个 parallel primitive 手算
例 1：tree reduction depth
1024 values 求和，sequential 需 1023 adds、span 1023；balanced tree work 仍 1023，但 depth=log₂1024=10 stages（同步/通信另算）。
例 2：exclusive scan
Input [3,1,4,2] 的 exclusive prefix sums 为 [0,3,4,8]；inclusive 为 [3,4,8,10]。Compaction 常用 scan 把 0/1 flags 变成输出 indices。
例 3：histogram contention
1M samples、256 bins，均匀时每 bin 平均 3906 updates；若 90% 都落 bin 0，该地址约 900k atomics。Privatized block histograms 再 reduce 可大幅减 global contention。
例 4：2D stencil halo
16×16 output tile、radius=1，需要加载 18×18=324 inputs，产生 256 outputs；overhead=324/256=1.266，约 26.6%。Tile 越大 halo 比例越低，但 shared memory 越多。
稀疏意味着少做 FLOPs，但不自动更快。index、irregular memory、低 reuse 与 load imbalance 可能让 sparse kernel 比高度优化的 dense Tensor Core kernel 更慢。
自测
1. reduction 为什么常分 warp/block/grid 多级？
线程只能在有限 scope 高效同步；先局部合并可减少全局 traffic/atomics。
2. parallel sum 为什么与 CPU 结果末位不同？
浮点加法不满足严格结合律，不同 reduction tree 改变舍入顺序。
3. stencil 的 halo 是什么？
一个 tile/domain 为计算边界点必须额外读取的邻域数据，多 GPU 时需从相邻 rank 交换。
官方资料
NVIDIA CUDA Libraries汇总 cuBLAS、cuFFT、cuSPARSE、cuSOLVER、CUB 与 Thrust；先用库的 correctness/performance baseline 再决定 custom kernel。