cuda - GPGPU:处理 'irregular' 转换的有效方法？

Question

在常规变换中，每个 GPU 线程都应具有相同的时间复杂度 O。例如:

for i=0 to 10: c[i] = a[i]*b[i]

在不规则变换上，它不是:

for i=0 to len(arr)
    for k=0 to random()%100
        arr[i] += 1

结果是一个类似于 [2,50,32,77,1,5,66, ...] 的数组，其中每个元素大致表示计算成本。

GPGPU 编程非常适合常规转换，例如“逐元素加法”、“矩阵乘法”、“卷积”...但是不规则变换呢？如何“很好”地分配 GPU 线程？如何设计一个“好的”内核？有通用的方法吗？

Answer 1

如果硬件既不是 Vega 也不是 Volta(每个项目都可以有几乎独立的命令执行)，那么最好的办法是将可疑的工作重新组合在一起。例如，Mandelbrot 图像生成器(每个项目的不同工作量)在 2D 平铺生成中可以更快，因为同一组中的所有项目可以或多或少地具有相同数量的相邻工作项目并且比一维(扫描线)更平衡一代(每组有更多不同的结果)。要么您应该根据上次迭代重新排序元素，要么使用空间分组。

在最坏的情况下，每个计算单元(每个计算单元有 8,64,128,192 个核心)的最大周期决定了最终的性能，随着计算单元的增加，性能会更快。但是所有其他工作项的工作仍将隐藏在这些最大周期之后，并且比 CPU 更高效。