I have n集合，有限宇宙的子集。我想计算n*n矩阵，其中(I, J)条目包含集合交集的基数I并设置J. n的顺序是50000.
我的想法是将矩阵分割成足够小的块，以便每个条目都有一个线程。每个线程都应该使用以下方法计算交集bitwise and.
有没有更有效的方法来解决这个问题？
我假设您想要按照您所描述的方式计算它：实际上使用位集的按位和来计算每对集合的交集。
通过正确的数学设置，您实际上是在计算两个向量的外积，因此我会从高性能线性代数的角度进行思考。
性能的关键是减少内存流量，这意味着尽可能将数据保存在寄存器中。最重要的因素是你的元素很大；存储一组数据需要 6250 个 32 位字！例如，整个 cuda 计算能力 3.0 的多处理器只能在寄存器中保存区区 10 个集合。
您可能想要做的是将每个元素分布在整个线程块中。一个块中有 896 个线程，每个块有 7 个寄存器，您可以存储一组 200704 个元素。借助 cuda 计算功能 3.0，每个块将有 36 个可用寄存器。
最简单的实现是让每个块拥有输出矩阵的一行。它加载第二个向量的相应元素并将其存储在寄存器中，然后迭代第一个向量的所有元素，计算交集，计算并减少 popcount，然后将结果存储在输出向量中。
此优化应将内存读取总数减少 2 倍，因此可能使性能提高一倍。
更好的办法是让每个块同时拥有 3-4 行输出矩阵，并将第二个向量的相应 3-4 个元素加载到寄存器中。然后，该块迭代第一个寄存器的所有元素，并为每个元素计算 3-4 个交集，并将结果存储在输出矩阵中。
此优化将内存流量减少了 3-4 倍。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
