ece408

ECE408 MPs 详细讲解
MP2 - 矩阵乘法 (Matrix Multiplication)

做什么: 最基础的 GPU 并行计算 - 矩阵乘法 C = A × B

原理:

• 每个 GPU 线程计算输出矩阵 C 的一个元素
• 线程 (i,j) 计算 C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + ...
• 朴素算法，没有优化

为什么重要: GPU 编程入门，学习如何启动 kernel、分配内存、数据传输

MP3 - 分块矩阵乘法 (Tiled Matrix Multiplication)

做什么: 优化版的矩阵乘法，使用 shared memory 加速

原理:

• 把大矩阵分成小块（tile），每块 16×16
• 利用 shared memory（片上高速缓存）减少全局内存访问
• 每个 block 的线程协作加载数据到 shared memory
• 速度比 MP2 快很多倍

关键技术:

• Shared Memory: GPU 的高速缓存，比全局内存快 100 倍
• Tiling: 分块计算，提高数据重用率

为什么重要: 学习 GPU 内存层次结构和优化技术

MP4 - 3D 卷积 (3D Convolution)

做什么: 对 3D 数据（如视频、医学影像）进行卷积操作

原理:

• 输入是 3D 数组（z×y×x），卷积核是 3×3×3
• 每个输出点是周围 27 个点的加权和
• 使用 constant memory 存储卷积核（只读，快速）
• 使用 shared memory tiling 减少重复加载

应用场景:

• 视频处理（时间维度 + 空间维度）
• 医学影像分析（CT、MRI 扫描）
• 3D 物体识别

关键技术:

• Constant Memory: 存储只读数据，所有线程共享
• Halo 区域: 边界扩展，处理卷积边界

MP5 - 列表归约 (List Reduction)

做什么: 计算数组所有元素的和（或其他归约操作）

原理:

• 输入：[1, 2, 3, 4, 5, 6, 7, 8]
• 输出：36（所有元素的和）
• 使用树形归约算法，每轮减少一半元素
• 第一轮：[1+2, 3+4, 5+6, 7+8] = [3, 7, 11, 15]
• 第二轮：[3+7, 11+15] = [10, 26]
• 第三轮：[10+26] = [36]

关键技术:

• Work-efficient: 避免线程空闲，提高效率
• Shared Memory: 块内归约使用 shared memory
• 两阶段: GPU 归约到块级别，CPU 完成最终归约

应用场景: 求和、求最大值、求平均值等

MP6 - 并行扫描 (Parallel Scan / Prefix Sum)

做什么: 计算前缀和（累加和）

原理:

• 输入：[1, 2, 3, 4, 5]
• 输出：[1, 3, 6, 10, 15]（每个位置是前面所有元素的和）
• 使用 work-efficient scan 算法
• 分为上扫（up-sweep）和下扫（down-sweep）两个阶段

应用场景:

• 数据压缩
• 并行排序
• 图像处理
• 任何需要"累积"的操作

关键技术:

• 三个 Kernel:
  a. 块内 scan
  b. 块和 scan
  c. 添加块和到每个块
• 处理任意长度数组

MP7 - 直方图均衡化 (Histogram Equalization)

做什么: 图像增强技术，改善图像对比度

原理:

1. RGB → 灰度: 彩色图像转灰度图
   - Gray = 0.21R + 0.71G + 0.07*B
2. 计算直方图: 统计每个灰度值出现的次数
   - histogram[0-255] = 每个灰度值的像素数量
3. 计算 CDF: 累积分布函数（使用 scan）
   - CDF[i] = histogram[0] + ... + histogram[i]
4. 均衡化: 重新映射灰度值
   - new_value = (CDF[old_value] / total_pixels) * 255

效果: 让暗的图像变亮，提高对比度

应用场景:

• 医学影像增强
• 夜间照片处理
• 卫星图像处理

关键技术:

• Atomic Operations: 多线程安全地更新直方图
• Scan: 计算累积分布函数

MP8 - 稀疏矩阵向量乘法 (Sparse Matrix-Vector Multiplication, SpMV)

做什么: 计算稀疏矩阵与向量的乘法 y = A × x

什么是稀疏矩阵:

• 大部分元素是 0 的矩阵
• 例如：社交网络（大部分人不认识）、网页链接（大部分网页不互联）

为什么需要特殊处理:

• 普通矩阵：1000×1000 = 100万个元素
• 稀疏矩阵：只存储非零元素，节省内存

JDS 格式 (Jagged Diagonal Storage):

• 按行的非零元素数量排序
• 把非零元素按列存储
• 优化内存访问模式，提高 GPU 效率

应用场景:

• 科学计算（有限元分析）
• 图算法（PageRank）
• 机器学习（推荐系统）

关键技术:

• CSR → JDS 转换: 从常见格式转换到 GPU 友好格式
• 合并内存访问: 相邻线程访问相邻内存

学习路径

1. MP2: 基础 - 学会写 GPU 程序
2. MP3: 优化 - 学会用 shared memory
3. MP4: 进阶 - 学会用 constant memory 和 3D 数据
4. MP5: 归约 - 学会树形算法
5. MP6: 扫描 - 学会前缀和算法
6. MP7: 应用 - 综合运用多种技术
7. MP8: 实战 - 处理真实世界的稀疏数据

核心概念

GPU 内存层次（从快到慢）:

8. 寄存器 (Registers): 最快，每个线程私有
9. Shared Memory: 很快，block 内共享
10. Constant Memory: 快，只读，所有线程共享
11. 全局内存 (Global Memory): 慢，但容量大

优化原则:

• 尽量用 shared memory 减少全局内存访问
• 合并内存访问（相邻线程访问相邻内存）
• 避免线程分支（if-else）
• 最大化并行度