GPU计算/着色器分支优化模式名称及相关技术咨询

这种模式同样适用于图形着色器与GPGPU代码，我主要关注GPGPU，所以示例是类计算风格的。由于SIMD处理器的固有局限，GPU没法高效执行分支代码。我之前多次用一种模式：把单个核拆成多个核，第一个核负责判断每个工作项属于哪个分支，剩下的核只针对特定分支执行无分支代码。过去我是在设备外做分区，这次示例里在分支判定核内用原子递增索引完成分区，我叫它"n+1核模式"，但估计它有正式名称。

// n+1 kernels pattern

// 未使用n+1核模式的设备代码（通用GPGPU语言）：

kernel void oneKernel(const int[] intArray, const float[] floatArray, float[] out) {
    int globalId = getId();
    int thisInt = intArray[globalId];
    float thisFloat = floatArray[globalId];
    
    if (someCondition(thisInt, thisFloat)) {
        if (someOtherCondition(thisInt)) {
            out[globalId] = expensiveCalc0(thisInt, thisFloat);
        } else {
            out[globalId] = expensiveCalc1(thisInt, thisFloat);
        }
    } else {
        out[globalId] += expensiveCalc2(thisInt, thisFloat);
    }
}

// 使用n+1核模式的设备代码：先调用createBranchMappings()

kernel void createBranchMappings(const int[] intArray, const float[] floatArray, int[][] globalIdsByBranch, volatile int[] nextIndexByBranch) {
    int globalId = getId();
    int thisInt = intArray[globalId];
    float thisFloat = floatArray[globalId];
    int branchId;
    
    // someCondition由所有线程同步执行...
    if (someCondition(thisInt, thisFloat)) {
        // ...但someOtherCondition不是。要避免这里失去同步需要更多核，逻辑会非常绕，
        // 除非someOtherCondition本身开销极大，否则得不偿失。另外后面的原子操作本来也会打破完全同步
        if (someOtherCondition(thisInt)) {
            branchId = 0;
        } else {
            branchId = 1;
        }
    } else {
        branchId = 2;
    }
    globalIdsByBranch[branchId][atomic_add(&nextIndexByBranch[branchId], 1)] = globalId;
}

// 接着调用branch0()
// getId()的范围是0到分支ID为0的元素数量（调用createBranchMappings后可从nextIndexByBranch获取）
// 这个核完全没有分支，线程保持同步执行

kernel void branch0(const int[] intArray, const float[] floatArray, const int[][] globalIdsByBranch, float[] out) {
    int indexInThisBranch = getId();
    int globalIndex = globalIdsByBranch[0][indexInThisBranch];
    int thisInt = intArray[globalIndex];
    float thisFloat = floatArray[globalIndex];
    out[globalIndex] = expensiveCalc0(thisInt, thisFloat); 
}

// 之后调用branch1()、branch2()即可完成计算。branch1()和branch2()的结构和branch0()一致，
// 只是分别调用expensiveCalc1和expensiveCalc2代替expensiveCalc0。

问题与解答 #

1. 假设该方法并非首创，它是否有正式名称？ #

这个模式的正式名称是分支拆分（Branch Splitting），也常被称为核内分支分离（Kernel Branch Separation），部分资料里也叫它数据流分区（Dataflow Partitioning）。本质是把控制依赖转化为数据依赖，通过提前分区让同分支的工作项归为一组，避免SIMD warp内的分支发散。

2. 有无比本文所示更优的工作项分区方法用于分支核？能否避免原子操作的开销？ #

确实有更高效的分区方式，能大幅降低原子操作的开销，核心思路是先在工作组内做本地计数，再用全局原子操作汇总：

• 第一步：每个工作组内，线程先统计各分支的本地数量，用共享内存记录每个线程的分支ID，再通过前缀和计算出每个分支在工作组内的偏移量。
• 第二步：用一次全局原子操作获取当前分支的全局起始索引，再把工作组内的分支数据拷贝到全局数组对应位置。
  这种方式把全局原子操作的次数从每个线程一次降到每个工作组一次，开销会小很多，尤其当工作组规模较大时效果明显。

3. 经验表明该方法能提升执行效率，但是否存在该方法并非始终有效的情况？ #

是的，以下场景下这个模式反而会降低性能：

• 分支计算开销极低：如果分支里的计算逻辑很简单，拆分核带来的额外内存拷贝、核启动开销会远大于分支发散的损失。
• 分支分布极度不均衡：比如某个分支占了99%的工作项，剩下的分支只有极少数，拆分后额外核的启动和数据处理开销会得不偿失。
• 数据局部性被破坏：拆分后工作项的全局索引被打乱，原有的连续内存访问变成随机访问，缓存命中率暴跌，反而拖慢整体性能。

4. 我认为GPGPU编译器可自动透明地对所有分支核进行此类代码转换，但为何实际并未这么做？ #

编译器很难自动完成这种优化，核心原因有几个：

• 运行时分支不可预测：编译阶段没法知道分支条件的运行时分布，比如someCondition的满足比例、分支内计算的开销，没法判断拆分是否划算。
• 内存依赖复杂：拆分核需要额外全局内存存储分支映射，编译器要自动分配内存、处理数据同步，还要保证原代码的内存语义不变，逻辑复杂度极高。
• 核启动开销的不确定性：不同GPU的核启动延迟差异大，编译器没法预估拆分后多核启动的额外开销是否能抵消分支发散的损失。
• 用户语义的模糊性：有些分支里可能有隐式同步或副作用，编译器没法保证拆分后行为和原代码完全一致，容易引入bug。

内容的提问来源于stack exchange，提问作者barneypitt