https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html
在本文中，重点强调了使扫描“高效工作”。换句话说，GPU算法执行的加法运算应不超过CPU算法O（n）。作者提出了两种算法，一种是“天真的”算法，可以进行O（nlogn）加法运算，另一种是他们认为“工作效率高”。但是，高效的算法执行的循环迭代次数是原来的两倍。在“高效工作”算法中执行两倍的循环似乎意味着从长远来看许多线程将处于空闲状态并降低性能。我想念什么？
#1 楼
首先，请再说一遍：“ GPU只是巨型SIMD处理器，应该按步操作”，这要复杂得多。整个GPU不能同步运行。着色器线程被分为32组，称为“扭曲”（在NVIDIA上；在AMD上，它们是64组，称为“波前”，但概念相同）。在一次扭曲中，所有线程都以SIMD数组的形式同步运行。但是，不同的经纱彼此之间并不协调。此外，某些扭曲可能正在主动运行，而其他扭曲可能会被挂起，就像CPU线程一样。可以暂停扭曲，因为它们正在等待某些东西（例如内存事务返回或清除障碍），或者因为没有可用的插槽（因为GPU只能在以下位置主动运行一定数量的扭曲）时间）。现在，回到您的问题。我可以看到该论文中的“高效工作”算法看起来比“朴素”算法更有效的两种方式。
高效工作版本需要一半的效率。很多线程开始。在朴素的算法中，每个数组元素只有一个线程。但是在高效的版本中，每个线程都在数组的两个相邻元素上运行，因此它们只需要数组元素一半的线程。更少的线程意味着更少的经线，因此大部分经线可以有效运行。
尽管高效的版本需要更多的步骤，但以下事实可以弥补这一点：活动线程的数量减少得更快，并且所有迭代中活动线程的总数要小得多。如果一个warp在迭代过程中没有活动线程，则该warp只会跳到下一个障碍并被挂起，从而允许其他warp运行。因此，较少的活动扭曲通常可以在执行时间上获得回报。 （这隐含的是，需要以这样的方式设计GPU代码：将活动线程打包到尽可能少的线程束中-您不希望它们分散分布，因为即使一个活动线程也会强制整个线程束保持活动状态。）
请考虑朴素算法中活动线程的数量。查看文章中的图2，您可以看到除了第k次迭代的前2k之外，所有线程都处于活动状态。因此，对于N个线程，活动线程的数量大约为N − 2k。例如，在N = 1024的情况下，每次迭代的活动线程数为：向上），我得到：
1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512
总和为289。另一方面，高效算法从一半的线程开始，然后将一半每次迭代中的活动数减少到1，然后开始加倍，直到再次返回到数组大小的一半：
32, 32, 32, 32, 32, 31, 30, 28, 24, 16
将其转换为活动数经线：
512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
总和为71，仅为总数的四分之一。因此，您可以看到，在整个操作过程中，使用高效工作算法的活动经纱数量要少得多。 （实际上，对于中间的长时间运行，只有很少的活动扭曲，这意味着大部分芯片都没有被占用。如果还有其他计算任务在运行，例如来自其他CUDA流，它们可以扩展以填充话虽如此，但不幸的是，GPU Gems文章并未明确解释其中的任何内容，而是专注于big-O“加法数量”分析，虽然并非完全无关紧要，但是却遗漏了有关此算法为何更快的许多细节。