6

我想在大约一百万点的大型数据集中查找 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 我们 = 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）慢 1632 倍！运行一百万次需要 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 键查找更快用这种方法。

4

2 回答 2

2

I'm guessing this question is related to your previous question about tetrahedron faces. I still suggest you should try the sparse storage and sparse matrix-vector multiplication for that purpose:

size(spA)
ans =

 1244810     1244810

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

Elapsed time is 0.106581 seconds.

This is just timing analysis, see my previous answer about how to implement it in your case. Before you move to CUDA and do complicated stuff, check out simpler options.

于 2012-10-15T08:28:40.467 回答
0

鉴于这个问题已经受到关注，感觉这个答案太简单了，但你为什么不这样做：

M=[1:6; 2:7; 3:8; 4:9]'; %Some matrix that contains key 1 2 3, corresponding value is 4
idx=M(:,1)==1&M(:,2)==2&M(:,3)==3;
M(idx,4)

这应该很快评估，即使M是 100 万 x 4。

于 2012-10-17T20:47:49.797 回答