循环优化¶

串行 vs 并行循环优化

1. 通用循环变换（兼顾串行与并行）

循环展开（Loop Unrolling）：重复循环体以减少循环判断与增量变量开销，同时为并行执行提供更大的指令调度空间（如 4 级展开后，可一次性处理 4 个数据元素）；
循环剥离（Loop Peeling）：将循环的前几次或后几次迭代单独展开（如处理非 2 的幂次的剩余数据），避免主循环中的条件判断，提升并行效率；
循环合并/扁平化（Loop Coalescing/Collapsing）：将嵌套循环（如二维数组遍历）扁平化为单循环，简化数据访问模式，适配 GPU 等并行硬件的内存访问要求；
循环交换（Loop Interchange）：交换嵌套循环的内外层顺序，将数据访问更密集的循环置于内层，提升缓存命中率与并行化潜力（如矩阵乘法中，将列优先访问改为行优先）。
循环旋转（Loop Rotate）：将循环从 for 形式转换为 do-while 形式，并在前面增加一个条件判断。该变换主要为其他循环变换做准备，比如插入一个 loop guard 之后，再进行循环不变量外提。

2. 串行专属优化（不直接支持并行）

循环融合（Loop Fusion）：将两个独立循环合并为一个，减少循环判断开销，但复杂的循环体难以被编译器向量化（如 GPU 更适合简单独立的循环体）；
循环代码外提（Loop Code Motion）：将循环不变计算（如数组长度、常量系数）移到循环外，减少重复计算，但不改变循环的并行性；
循环强度降低（Loop Strength Reduction）：将乘法等强运算替换为加法（如 a[i] = 10*i 改为 x += 10），但会引入迭代间的数据依赖，无法并行执行。

3. 并行专属优化（向量化核心技术）

循环分裂（Loop Fission）：将一个复杂循环拆分为多个简单循环（如将“减均值+乘方差”拆分为两个独立循环），每个循环体仅含单一操作，便于硬件并行执行，同时提高缓存引用局部性；
循环分块（Loop Tiling/Blocking）：将大规模数据（如 512x512 矩阵）划分为小块（如 16x16 瓷砖），确保块内数据可驻留于缓存，减少内存访问延迟，同时适配 GPU 线程块的并行处理；
循环分布（Loop Distribution）：将循环内的条件分支（如 if(do_add) add else subtract）拆分为两个独立循环，避免分支预测失败，同时使每个循环可独立向量化。

核心循环变换技术

1. 循环展开（Loop Unrolling）：减少开销，适配并行

循环展开是最基础的向量化准备技术，通过重复循环体减少“循环判断（i < n）”与“增量（i++）”的开销，同时为 SIMD 指令提供“批量数据处理”的机会。

（1）完全展开（已知循环次数）

// 基础版本：循环计算 5 元素向量点积（串行）
float aussie_vecdot_basic(float v1[], float v2[]) {
  float sum = 0.0f;
  for (int i = 0; i < 5; i++) {
    sum += v1[i] * v2[i];
  }
  return sum;
}

// 完全展开版本：无循环开销，可直接向量化
float aussie_vecdot_unroll_full(float v1[], float v2[]) {
  return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2] + v1[3] * v2[3] +
         v1[4] * v2[4];
}

（2）部分展开（未知循环次数）

// 4 级部分展开：主循环处理 4 的倍数数据，剩余数据单独处理
float aussie_vecdot_unroll4(float v1[], float v2[], int n) {
  float sum = 0.0f;
  int i = 0;
  // 主循环：4 级展开，每次处理 4 个元素
  for (; i < n - 3; i += 4) {
    sum += v1[i] * v2[i];
    sum += v1[i + 1] * v2[i + 1];
    sum += v1[i + 2] * v2[i + 2];
    sum += v1[i + 3] * v2[i + 3];
  }
  // 处理剩余元素（0~3 个）
  for (; i < n; i++) {
    sum += v1[i] * v2[i];
  }
  return sum;
}

部分展开的关键是“展开因子与硬件 SIMD 宽度匹配”（如 CPU AVX-2 支持 8 个 32 位浮点数并行，展开因子设为 8），避免硬件资源浪费。

2. 循环分块（Loop Tiling/Blocking）：提升缓存效率，适配 GPU

循环分块是矩阵/张量运算向量化的核心技术，通过将大规模数据划分为“缓存友好”的小块，减少内存访问延迟，同时适配 GPU 线程块的并行处理模式。

对于 2D 矩阵，直接嵌套循环遍历会频繁引发缓存失效，分块后可确保块内数据驻留于 L1/L2 缓存：

// 定义矩阵类型（ROWS x COLUMNS）
typedef float Matrix[ROWS][COLUMNS];
const int TILE_SIZE = 16;  // 分块大小（16x16，适配 64 字节缓存行）

// 基础版本：无分块，缓存失效频繁
void clear_matrix_basic(Matrix m) {
  for (int i = 0; i < ROWS; i++) {
    for (int j = 0; j < COLUMNS; j++) {
      m[i][j] = 0.0f;
    }
  }
}

// 分块版本：按 16x16 块处理，提升缓存命中率
void clear_matrix_tiled(Matrix m) {
  // 外层循环：按块遍历行和列
  for (int i = 0; i < ROWS; i += TILE_SIZE) {
    for (int j = 0; j < COLUMNS; j += TILE_SIZE) {
      // 内层循环：处理单个块（16x16）
      for (int ti = i; ti < i + TILE_SIZE; ti++) {
        for (int tj = j; tj < j + TILE_SIZE; tj++) {
          m[ti][tj] = 0.0f;
        }
      }
    }
  }
}

向量化适配：分块后的内层循环（处理 16x16 块）可直接调用 GPU 核函数或 CPU SIMD 指令（如 AVX-512），一次性处理块内多个元素，吞吐量提升显著。

3. 循环分裂（Loop Fission）：拆分复杂循环，支持并行

循环分裂是将一个含多操作的循环拆分为多个单操作循环，消除数据依赖与分支，使每个循环可独立向量化，尤其适合 GPU 等并行硬件。

BatchNorm 中的“减均值+乘方差”操作含两个独立计算，直接在一个循环中执行难以向量化，分裂后可并行处理：

// 基础版本：单循环含多操作，难以向量化
void batchnorm_slow(float v[], int n, float mean, float var, float eps) {
  float denom = sqrtf(var + eps);
  for (int i = 0; i < n; i++) {
    v[i] = (v[i] - mean) / denom;  // 减均值 + 除方差，单循环多操作
  }
}

// 分裂版本：两个独立循环，可分别向量化
void batchnorm_fast(float v[], int n, float mean, float var, float eps) {
  float neg_mean = -mean;
  float inv_denom = 1.0f / sqrtf(var + eps);

  // 循环1：减均值（仅加法，可向量化）
  for (int i = 0; i < n; i++) {
    v[i] += neg_mean;
  }

  // 循环2：乘方差倒数（仅乘法，可向量化）
  for (int i = 0; i < n; i++) {
    v[i] *= inv_denom;
  }
}

优势分析：分裂后的两个循环均为“单操作+连续数据访问”，GPU 可通过 warp 线程并行处理，吞吐量比单循环提升 2~4 倍。

循环向量化的注意事项与进阶优化

1. 规避数据依赖：并行化的前提

向量化的核心前提是“循环迭代间无数据依赖”，若存在依赖（如 a[i] = a[i-1] + 1），并行执行会导致结果错误。列举常见依赖类型及规避方案：

写后读依赖（RAW）：如 a[i] = b[i]; b[i] = c[i]，需确保读写操作无重叠；
读后写依赖（WAR）：如 b[i] = c[i]; a[i] = b[i-1]，需调整循环顺序或拆分循环；
写后写依赖（WAW）：如 a[i] = 1; a[i] = 2，需合并重复写操作。

2. 适配硬件 SIMD 宽度：最大化并行效率

不同硬件的 SIMD 宽度不同（如 CPU AVX-2 为 256 位、AVX-512 为 512 位，GPU warp 为 32 位），需调整循环展开因子与分块大小适配：

CPU 示例：AVX-512 支持 16 个 32 位浮点数并行，循环展开因子设为 16；
GPU 示例：NVIDIA GPU warp 支持 32 线程并行，分块大小设为 32 的倍数。

3. 进阶优化：循环剥离与哨兵技术

循环剥离（Loop Peeling）：处理非 SIMD 宽度倍数的剩余数据，避免主循环中的条件判断：

// 剥离前：主循环含条件判断（i % 4 != 0）
for (int i = 0; i < n; i++) {
  if (i % 4 == 0) { /* 特殊处理 */
  } else {          /* 普通处理 */
  }
}

// 剥离后：剩余数据单独处理，主循环无判断
int i = 0;
// 处理前 0~3 个剩余数据
for (; i < n % 4; i++) { /* 特殊处理 */
}
// 主循环：4 的倍数数据，无判断
for (; i < n; i += 4) { /* 普通处理 */
}

循环哨兵（Loop Sentinel）：在数组末尾添加“哨兵元素”，消除循环中的边界判断（如查找负数时，在数组末尾添加一个负数，避免 i < n 的判断），但需确保数组可写且无越界风险。

总体流程

循环向量化需遵循“先准备、再变换、后适配”的优先级，确保并行效率最大化：

基础准备：通过循环展开、代码外提减少串行开销，同时消除循环内的数据依赖，为并行化扫清障碍；
核心变换：对嵌套循环执行交换/合并，对复杂循环执行分裂，对大规模数据执行分块，构建适配并行硬件的循环结构；
硬件适配：根据 CPU/GPU 的 SIMD 宽度调整展开因子与分块大小，确保硬件资源充分利用；
边缘处理：用循环剥离处理剩余数据，用哨兵技术消除边界判断，避免并行效率被边缘逻辑拖累。