CUDA中的3个整数键查找

Question

我想在大约一百万点的大数据集中查找3个整数(即[1 2 3]).

我目前正在使用MATLAB的Map(hashmap),对于每个点我都在做以下事情:

key = sprintf('%d ', [1 2 3]);       % 23 us
% key = '1 2 3 '
result = lookup_map( key );          % 32 us

这是非常耗时的 - 100万分*55 us = 55秒.

我想用CUDA将它移到GPU上,但我不确定接近它的最佳方法.

我可以传输四个数组 - key1, key2, key3, result然后在键上执行二进制搜索,但每个键需要20次迭代(2 ^ 20 = 1048576).然后由于每个线程的并发内存访问,我也会有延迟.

是否存在针对CUDA中的并行(O(1),理想情况下)多键查找优化的数据结构？

---

问:三个整数的界限是什么？查找了哪些数据？

当前整数键可以在0到约75,000之间,但将来可能更大(200,000+).

出于这个问题的目的,我们可以假设它result是一个介于0和数据集大小之间的整数.

---

问:为什么不将所有三个数字打包成一个64位数字(每个数字21位给出的范围为0-2,097,152).并使用它来索引到稀疏数组？

>> A = uint64(ones(10));
>> sparse_A = sparse(A)
??? Undefined function or method 'sparse' for input arguments of type 'uint64'.

>> A = int64(ones(10));
>> sparse_A = sparse(A)
??? Undefined function or method 'sparse' for input arguments of type 'int64'.

我的matlab似乎不支持64位数字的稀疏数组.

如果这有助于其他任何人,我写了一个快速函数来从三个<2 ^ 21个无符号整数创建一个64位密钥:

function [key] = to_key(face)
    key = uint64(bitsll(face(1), 42) + bitsll(face(2), 21) + rand(face(3),1));
end

---

问:来自@Dennis - 为什么不使用逻辑索引？

我们来试试吧!

% Generate a million random integers between 0 and 1000
>> M = int32(floor(rand(10000000,4)*1000));
% Find a point to look for
>> search =  M(500000,1:3)             
search =
         850         910         581  
>> tic; idx = M(:,1)==search(1) & M(:,2)==search(2)&M(:,3)==search(3); toc;
Elapsed time is 0.089801 seconds.
>> M(idx,:)
ans =
         850         910         581         726

不幸的是,这需要89801us,比我现有的解决方案(55us)慢1632x!运行这一百万次需要2.5小时!

我们可以M在每次搜索后尝试过滤:

>> tic; idx1=M(:,1)==search(1); N=M(idx1,:); idx2=N(:,2)==search(2); N2=N(idx2,:); idx3 = N2(:,3)==search(3); toc;
Elapsed time is 0.038272 seconds.

这速度要快一些,但仍然比使用Map慢696倍.

---

我一直在考虑这个问题,并且我决定通过单个键查找来分析重新生成一些数据的速度 - 考虑到潜在的问题,它可能比3键查找更快用这种方法.

Answer 1

我猜这个问题与您之前有关四面体面的问题有关。我仍然建议您应该sparse为此目的尝试存储和稀疏矩阵向量乘法：

size(spA)
ans =

 1244810     1244810

tic;
vv = spA*v;
idx = find(vv);
toc;

Elapsed time is 0.106581 seconds.

这只是时序分析，请参阅我之前关于如何在您的案例中实现它的答案。在转向 CUDA 并执行复杂操作之前，请先查看更简单的选项。