algorithm - GPU 上的高效全对集交集

Question

我有 n 集合，是有限宇宙的子集。我想计算 n*n 矩阵，其中 (I, J) 条目包含集合 I 和集合的交集的基数J。 n 的顺序是 50000。

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

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

Answer 1

我假设您想按照您描述的那样计算它:实际计算每对集合的交集，使用位集和位集。

通过正确的数学设置，您实际上是在计算两个向量的外积，所以我会考虑高性能线性代数。

性能的关键在于减少内存流量，这意味着尽可能将内容保存在寄存器中。压倒性的最重要因素是您的元素很大；存储一个集合需要6250个32位字!例如，整个 cuda 计算能力 3.0 的多处理器只能容纳 10 组寄存器。

您可能想要做的是将每个元素分散到整个线程 block 中。一个 block 中有 896 个线程，每个 block 有 7 个寄存器，您可以存储一组 200704 个元素。使用 cuda 计算能力 3.0，每个 block 将有 36 个寄存器可用。

最简单的实现是让每个 block 拥有输出矩阵的一行。它加载第二个向量的相应元素并将其存储在寄存器中，然后迭代第一个向量的所有元素，计算交集，计算和减少 popcount，然后将结果存储在输出向量中。

此优化应将内存读取总数减少 2 倍，因此可能会使性能翻倍。

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

此优化将内存流量减少了 3-4 倍。