arrays - CUDA 减少了许多小的、大小不等的数组

Question

我想知道是否有人可以建议在 CUDA 中计算大量相对较小但不同大小的数组的均值/标准差的最佳方法？

SDK 中的并行缩减示例在一个非常大的数组上工作，看起来大小很方便地是每个 block 线程数的倍数，但我的情况非常不同:

从概念上讲，我有大量对象，每个对象包含两个组件，upper 和 lower，并且每个组件都有一个 x 和一个 y 坐标。即

upper.x, lower.x, upper.y, lower.y

每个数组的长度大约为 800，但它在对象之间(不在对象内)有所不同，例如

Object1.lower.x = 1.1, 2.2, 3.3
Object1.lower.y = 4.4, 5.5, 6.6
Object1.upper.x = 7.7, 8.8, 9.9
Object1.upper.y = 1.1, 2.2, 3.3

Object2.lower.x = 1.0,  2.0,  3.0,  4.0, 5.0 
Object2.lower.y = 6.0,  7.0,  8.0,  9.0, 10.0
Object2.upper.x = 11.0, 12.0, 13.0, 14.0, 15.0 
Object2.upper.y = 16.0, 17.0, 18.0, 19.0, 20.0

请注意以上只是我表示数组的方式，我的数据没有存储在 C 结构或类似的任何东西中:数据可以按我需要的任何方式组织。重点是，对于每个数组，均值、标准差和最终的直方图都需要计算，并且在一个特定对象内，数组之间的比率和差异需要计算。

我应该如何将这些数据发送到 GPU 设备并组织我的线程 block 层次结构？我的一个想法是对所有数组进行零填充，使它们的长度相同，并且有一组 block 在每个对象上工作，但如果该方法可以工作的话，它似乎存在各种问题。

提前致谢

Answer 1

如果我没理解错的话，您想将 Object1.lower.x 缩减为一个结果，将 Object1.lower.y 缩减为另一个结果，依此类推。对于任何给定的对象，有四个数组要减少，所有数组的长度都相等(对于对象)。

有很多可能的方法，一个影响因素是系统中的对象总数。我假设这个数字很大。

为了获得最佳性能，您需要最佳内存访问模式并避免分歧。由于全等数组的数量是四个，如果您采用每个线程执行一个数组的天真方法，如下所示，您不仅会遇到内存访问不佳的问题，而且 h/w 还需要检查每个迭代中的线程warp 需要执行循环 - 那些不需要的将被禁用，这可能是低效的(例如，特别是如果一个数组比其他数组长得多)。

for (int i = 0 ; i < myarraylength ; i++)
    sum += myarray[i];

相反，如果您让每个 warp 对一个数组求和，那么它不仅会更高效，而且您的内存访问模式也会更好，因为相邻的线程将读取相邻的元素 [1]。

for (int i = tidwithinwarp ; i < warparraylength ; i += warpsize)
{
    mysum += warparray[i];
}
mysum = warpreduce(mysum);

您还应该考虑数组的对齐方式，最好在 64 字节边界上对齐，但如果您正在开发 1.2 或更高的计算能力，那么这并不像在旧 GPU 上那么重要。

在此示例中，您将在每个 block 中启动四个 warp，即 128 个线程，以及与您拥有的对象一样多的 block 。

[1] 你确实说过你可以选择你喜欢的任何内存排列，通常交错数组很有用，这样数组 [0][0] 就在数组 [1][0] 旁边，因为这意味着相邻线程可以对相邻数组进行操作并获得合并访问。然而，由于数组的长度不是常数，这可能很复杂，需要填充较短的数组。