CUDA使用coalesced_threads配合labeled_partition减少原子操作提升并行效率

1. cg::coalesced_threads() —— “当前活跃的线程组”

含义

• 在 GPU 上，线程是以 “线程束（Warp）”（通常 32 个线程）为单位执行的。
• 但有时候由于 if/else 分支或 while 循环，部分线程可能不活跃（比如某些线程提前退出）。
• cg::coalesced_threads() 返回当前所有还在运行的线程（即"合并的线程组"）。

类比

• 假设你是一个班级（Warp）的班长，原本有 32 个同学。
• 但今天有 5 个同学请假了，只有 27 人上课。
• cg::coalesced_threads() 就是 今天实际来上课的 27 个同学。

典型用途

• 减少原子操作：让活跃的线程协作，减少 atomicAdd 调用次数。
• 动态线程协作：处理不规则数据时（如某些线程提前结束）。

示例

auto active_threads = cg::coalesced_threads(); // 获取当前活跃的线程
if (active_threads.thread_rank() == 0) {
    // 只有第一个活跃线程执行（比如做一次原子操作）
    atomicAdd(&counter, active_threads.size());
}

2. cg::labeled_partition(warp, leafptr) —— “按标签分组”

含义

• 它的作用是把一个线程组（如 Warp）按某个标签（leafptr）分成多个小组。
• 相同标签的线程会被分到同一组，并选一个代表（thread_rank() == 0）来执行操作。

类比

• 假设班级（Warp）有 32 个同学，每个人手里拿着一张卡片（leafptr，代表叶节点地址）。
• 老师让 拿相同卡片的同学组成小组（比如 3 个人拿"A"，5 个人拿"B"……）。
• 每个小组选一个组长（thread_rank() == 0）代表全组做任务。

典型用途

• 八叉树/哈希表：让访问同一内存地址的线程合并操作。
• 减少原子竞争：同一分组的线程只需 1 次原子操作，而不是每人 1 次。

示例

auto warp = cg::tiled_partition<32>(cg::this_thread_block()); // 获取当前 Warp
auto group = cg::labeled_partition(warp, leafptr); // 按叶节点地址分组

if (group.thread_rank() == 0) {
    // 每组选一个代表，执行原子操作
    atomicAdd(&leaf->counter, group.size());
}

3. 它们如何一起优化点云计数？

在之前的代码中：

1. cg::coalesced_threads() 先找出当前活跃的线程（避免无效线程）。
2. cg::labeled_partition(warp, leafptr) 再按 leafptr（叶节点地址）分组：
   • 访问 同一叶节点 的线程归为一组。
   • 每组只做 1 次原子操作（而不是每个线程 1 次），极大减少竞争。

4. 通俗总结

核心思想：让 访问同一数据的线程协作，减少原子操作竞争，提升 GPU 并行效率！

5. 适用场景

• 八叉树/KD 树（点云管理）
• 哈希表（减少原子冲突）
• 稀疏矩阵计算（合并相同位置的操作）

举个例子，给出一个八叉树，和一组点云，现在要遍历每一个点，找出点对应的叶子节点，并给叶子节点的点数+1，
如果每一个点对应一个线程，每个线程都执行原子操作，可能出现冲突，不如统计下当前Warp中活跃线程数，
按照叶子节点的地址来进行分类计数，一个Warp组仅执行一次原子操作。
如果有 8 个线程访问同一个叶节点，只需 1 次 atomicAdd +8，而不是 8 次 atomicAdd +1。

uint64_t leafptr = uint64_t(leaf);
auto warp = cg::coalesced_threads(); // 获取当前 活跃的线程束（Warp）（32 个线程）。
auto group = cg::labeled_partition(warp, leafptr); // 根据 leafptr（叶节点地址）将线程分组，同一叶节点的线程归为一组。

uint32_t old = 0;
// 每组（同一叶节点）选一个 代表线程（Leader） 执行原子操作。
if(group.thread_rank() == 0){
	// 使用 atomicAdd 原子操作来更新叶节点的点数。
	// group.num_threads() 是该组内的线程数（即该叶节点本次新增的点数）。
	old = atomicAdd(&leaf->counter, group.num_threads());

	// MAX_POINTS_PER_NODE的默认值为50k
	// 如果原来叶子节点的数目不超过MAX_POINTS_PER_NODE，且增加了新的点之后超过了MAX_POINTS_PER_NODE
	// 则该节点需要分裂，将其放入溢出节点数组中，且溢出节点数量+1
	if(old <= MAX_POINTS_PER_NODE)
	if(old + group.num_threads() > MAX_POINTS_PER_NODE)
	{
		// needs splitting
		uint32_t spillIndex = atomicAdd(numSpillingNodes, 1);
		spillingNodes[spillIndex] = leaf;
	}
}