GPU上高效的两两集合交集算法

Question

我有n个集合，它们是一个有限宇宙的子集。我想计算n×n矩阵，其中（I，J）条目包含集合I和集合J的交集的基数。 n的数量级为50000。

我的想法是将矩阵分成足够小的块，以便每个条目都有一个线程。每个线程应使用按位与运算符计算交集。

是否有更有效的方法来解决这个问题？

- Giovanni M.

---

集合的大小和宇宙的大小很可能非常相关；您应该发布您感兴趣的参数类型的示例。 - user1084944

据我所理解，(I,J)的基数应该与(J,I)相同，因此即使在您的朴素实现中，您只需要计算矩阵的约n*n/2个元素。 - Slizzered

@Hurkyl 宇宙的大小约为200000，集合的大小约为20000-30000。 - Giovanni M.

@Slizzered 是的，矩阵是对称的，我正在考虑使用这个映射方法将三角形矩阵映射到线性结构上并分块。 - Giovanni M.

Answer 1

一种不同的解决问题的方法是将“宇宙”分成每个小区域1024个元素，并仅计算该部分宇宙中交集的大小。

我不确定我是否描述得很好；基本上你正在计算。

A[i,j] = sum((k in v[i]) * (k in w[j]) for k in the_universe)

其中v和w是两个集合列表，k在S中如果为真则为1，否则为0。关键是要对索引进行排列，以使k在外部循环而不是内部循环中，尽管出于效率考虑，您必须一次处理许多连续的k，而不是一次一个。

也就是说，您将输出矩阵初始化为全零，并且对于每个1024个元素的宇宙块，您将计算交集的大小，并将结果累加到输出矩阵中。

我选择了1024，因为我想象你会有一个数据布局，在那里这可能是最小的大小，当从设备内存读取时，仍然可以获得完整的内存带宽，并且warp中的所有线程都可以一起工作。(如果您比我更了解，或者您不使用nVidia和您正在使用其他GPU，则应适当调整此参数)

现在，您的元素具有合理的大小，您现在可以使用传统的线性代数优化来计算此乘积。我可能会执行以下操作：

每个warp被分配了输出矩阵的大量行。它从第二个向量中读取相应的元素，然后迭代第一个向量，计算乘积。

你可以让所有的warp独立操作，但以下做法可能更好：

- 一个块中的所有warp一起工作，从第一个向量中加载一些元素 - 每个warp计算它可以交叉的部分，并将结果写入输出矩阵

你可以将加载的元素存储在共享内存中，但是将它们保存在寄存器中可能会得到更好的结果。每个warp只能计算它所持有的集合元素的交集，但在这样做之后，warp可以轮流持有哪些元素。

如果按照这些线路进行足够的优化，您可能会达到不再受限于内存的点，这意味着您可能不必采取最复杂的优化（例如，上面描述的共享内存方法可能已经足够）。

- user1084944

Answer 2

我假设您想按照您描述的方式计算：实际计算每对集合的交集，使用位集的按位与。通过正确的数学设置，您实际上正在计算两个向量的外积，因此我将从高性能线性代数的角度考虑。性能的关键将是减少内存流量，这意味着在可以时应将东西保存在寄存器中。最显着的因素是您的元素非常巨大; 一个单独的集合需要6250个32位字才能存储！例如，整个cuda计算能力为3.0的多处理器只能在寄存器中容纳10个集合。您可能想要做的是将每个元素分散到整个线程块中。使用896个线程和每个块7个寄存器，您可以存储200704个元素的一个集合。在cuda计算能力3.0下，每个块将有36个可用寄存器。最简单的实现方法是使每个块拥有输出矩阵的一行。它加载第二个向量的相应元素并将其存储在寄存器中，然后迭代第一个向量的所有元素，计算交集，计算并减少popcount，然后将结果存储在输出向量中。

这种优化应该能将内存读取总数减少2倍，因此有望将性能提高一倍。

更好的方法是让每个块同时拥有3-4行输出矩阵，并将第二个向量的相应3-4个元素加载到寄存器中。然后块遍历第一个寄存器的所有元素，并为其计算它可以处理的3-4个交集，将结果存储在输出矩阵中。

这种优化将额外地将内存流量降低3-4倍。

- user1084944

---

感谢您对这两个答案的回应，我会尽快实现您的建议并报告结果。 - Giovanni M.

@Giovanni：不用谢。思考这些问题很有趣！我希望它们真的能帮到你。 :) - user1084944

虽然也许我的两个（或三个？）回答可以结合成一个总体的想法，但我需要考虑一下。也许在未来几天内我会对我的阐述进行重大修订。 - user1084944

Answer 3

一种完全不同的方法是分别处理宇宙中的每个元素：对于宇宙中的每个元素，计算实际包含该元素的集合，然后（原子性地）增加输出矩阵的相应条目。

从渐近意义上讲，这应该比计算集合的交集更有效。不幸的是，这听起来很难高效实现。

---

一个改进的方法是一次处理四个宇宙元素。将所有集合分成16个桶，取决于该集合包含的这4个元素中的哪些。然后，对于每一个可能的16*16个桶对，您需要迭代从桶中获取的向量对，并（原子性地）适当地更新矩阵的相应条目。

这种方法可能比上述描述的版本更快，但实现起来仍可能很困难。

---

为了减少同步的难度，可以将所有输入集合划分为k组，每组包含n/k个集合。然后，第(i,j)个线程（或warp或block）仅更新输出矩阵相应块的值。保留html标签。

- user1084944