专题：LeetGPU - 从零手写 CUDA 算子

在这个 AI 爆发的时代，GPU 编程已经成为高性能计算和深度学习系统的基石。然而，许多开发者对 CUDA 的理解仅停留在调用 PyTorch 或 Triton 的层面。

本专题 (LeetGPU) 旨在通过一系列由浅入深的编程挑战，带你亲手实现从基础向量加法到 GPT-2 Transformer Block 的核心算子。每一个挑战都不仅是代码实现，更是对并行计算思维、内存层次结构和硬件特性的深度探索。

特别值得强调的是，从 CPU 到 GPU 的编程思维转变，核心在于从“以指令为中心”转向“以数据为中心”，以及在具体算子实现中灵活运用“以输入为中心（Input-centric / Scatter）”与“以输出为中心（Output-centric / Gather）”的计算模式。理解这些模式的适用场景（如写冲突处理、访存合并等），是写出高性能 Kernel 的关键。

目录

1. GPU 编程基础 (Hello World)

这一阶段主要熟悉 CUDA 编程模型、线程层次结构（Grid/Block/Thread）以及基本的全局内存访问模式。

本阶段所有挑战均属于以输出为中心（Output-centric / Gather）的模式。这是 GPU 编程中最直观的范式：每个线程负责计算结果数组中的一个元素，从输入数组的对应位置（或多个位置）读取数据。

• Vector Addition Easy
• Matrix Addition Easy
• Matrix Copy Easy
• Color Inversion Easy
• RGB to Grayscale Easy
• Reverse Array Easy
• Interleave Arrays Easy
• Value Clipping Easy
• Simple Inference Easy

2. 核心数学运算与内存优化 (Math Kernel)

深入理解共享内存（Shared Memory）、访存合并（Coalescing）以及矩阵分块（Tiling）技术。

矩阵乘法（GEMM） 是以输出为中心的极致体现：每个输出元素 C[i][j] 收集（Gather）了 A 的行和 B 的列的所有数据。而稀疏矩阵运算（SpMV/SpMM）则需要根据存储格式（CSR vs CSC）在 Gather 和 Scatter 模式之间权衡，以应对不规则的内存访问。

• Matrix Multiplication Easy
• Matrix Transpose Easy
• Dot Product Medium
• Matrix Power Medium
• General Matrix Multiplication (GEMM) Medium
• Batched Matrix Multiplication Medium
• Sparse Matrix-Vector Multiplication Medium
• Sparse Matrix-Dense Matrix Multiplication Medium

3. 并行算法模式 (Parallel Patterns)

掌握并行计算中的经典模式，这是构建复杂算子的积木。本章节涵盖了Map（映射）、Reduce（规约）、Scan（扫描/前缀和）、Stencil（模版）、Scatter/Gather（散布/聚集）、Sort（排序）以及 Filter/Compact（过滤/压缩）等核心模式。

本章正式引入模式对比：Scan 和 Stencil 是典型的以输出为中心（Gather）模式；而 Histogramming（直方图） 则是经典的以输入为中心（Input-centric / Scatter）模式（每个线程处理一个输入数据，竞争写入输出 Bin，需使用 Atomic 操作解决冲突）。Sort（排序） 和 Reduce（规约） 则往往需要在多个阶段中交替使用这两种思维。

• Reduction Medium
• Prefix Sum Medium
• Histogramming Medium
• Stream Compaction Medium
• Merge Sorted Arrays Medium
• Parallel Merge Medium
• Sorting Hard
• Radix Sort Hard
• Top K Selection Medium
• Count Array Element Medium
• Count 2D Array Element Medium
• Count 3D Array Element Medium
• Subarray Sum Medium
• 2D Subarray Sum Medium
• 3D Subarray Sum Medium
• Max Subarray Sum Medium

4. 神经网络基础组件 (NN Primitives)

实现深度学习中常用的激活函数、归一化层和损失函数。

卷积（Convolution）和池化（Pooling）本质上是Stencil（模版）模式的变体，属于以输出为中心。

• 激活函数
  • ReLU Easy
  • Leaky ReLU Easy
  • Sigmoid Activation Easy
  • Sigmoid Linear Unit (SiLU) Easy
  • Swish-Gated Linear Unit Easy
  • Gaussian Error Gated Linear Unit Easy
• 卷积与池化
  • 1D Convolution Easy
  • 2D Convolution Medium
  • 3D Convolution Medium
  • Gaussian Blur Medium
  • 2D Max Pooling Medium
• 归一化与损失
  • Batch Normalization Medium
  • RMS Normalization Medium
  • Categorical Cross Entropy Loss Medium
  • Mean Squared Error Medium
  • Ordinary Least Squares Medium
  • Logistic Regression Medium

5. Transformer 与大模型核心 (LLM Core)

深入 Transformer 架构的核心组件，包括各种 Attention 变体和推理优化技术。

Attention 机制的核心 Softmax(Q @ K.T) @ V 主要是矩阵乘法的变体，依然是以输出为中心。但在 MoE（混合专家模型） 的 Gating 和 Routing 环节，会将 Token 分发到不同的专家，这涉及到了Scatter（输入中心）的操作。

• Attention 机制
  • Softmax Medium
  • Softmax Attention Medium
  • Multi-Head Attention Hard
  • Causal Self-Attention Hard
  • Linear Self-Attention Hard
  • Sliding Window Self-Attention Hard
  • Attention with Linear Biases (ALiBi) Medium
  • Rotary Positional Embedding (RoPE) Medium
• 推理优化与量化
  • Top-p Sampling (Nucleus) Medium
  • Weight Dequantization Medium
  • MoE Top-K Gating Medium
  • INT8 Quantized MatMul Medium
  • FP16 Batched Matrix Multiplication Medium
  • FP16 Dot Product Medium
• 综合挑战
  • GPT-2 Transformer Block Hard

6. 科学计算与其它 (Scientific & Misc)

探索 GPU 在科学计算、图算法和其它领域的应用。

• Fast Fourier Transform (FFT) Hard
• K-Means Clustering Hard
• BFS Shortest Path Hard
• All-Pairs Shortest Paths Hard
• Multi-Agent Simulation (Boids) Hard
• Monte Carlo Integration Medium
• 2D Jacobi Stencil Medium
• Rainbow Table Easy
• Nearest Neighbor Medium

---

"Talk is cheap. Show me the code (kernel)."

希望通过这些挑战，你能真正掌握 GPU 编程的精髓，从单纯的 API 调用者成长为能够手写高性能算子的专家。