6

約100万ポイントの大規模なデータセットで3つの整数（つまり[1 2 3]）を検索したいと思います。

私は現在MATLABのマップ（ハッシュマップ）を使用しており、各ポイントに対して次のことを行っています。

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

ただし、これにはかなりの時間がかかります-100万ポイント* 55 us=55秒。

これをCUDAを使用してGPUに移動したいのですが、これにアプローチする最善の方法がわかりません。

4つの配列を転送key1, key2, key3, resultしてからキーに対してバイナリ検索を実行することもできますが、これにはキーごとに20回の反復（2 ^ 20 = 1048576）が必要になります。次に、各スレッドからの同時メモリアクセスのために遅延も発生します。

CUDAでの並列（O（1）、理想的には）複数のキールックアップ用に最適化されたデータ構造はありますか？

Q：3つの整数の境界は何ですか？そして、どのようなデータが検索されますか？

整数キーは、現在0〜75,000の間である可能性がありますが、将来的にはさらに大きくなる可能性があります（200,000以上）。

この質問の目的のために、resultは0とデータセットのサイズの間の整数であると仮定することができます。

Q：3つの数値すべてを1つの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ビット数のスパース配列をサポートしていないようです。

これが他の誰かに役立つ場合に備えて、3つの<2^21符号なし整数から64ビットキーを作成する簡単な関数を作成しました。

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

Q：@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倍遅くなります。これを100万回実行するには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.

これは少し高速ですが、それでもマップを使用するよりも696倍遅くなります。

私はこれについてもう少し考えていて、単一のキールックアップからその場でデータの一部を再生成する速度をプロファイリングすることにしました-潜在的な問題を考えると、3キールックアップよりも速いかもしれませんこのアプローチで。

4

2 に答える 2

2

この質問は、四面体の面に関する以前の質問に関連していると思います。sparseその目的のために、ストレージとスパース行列-ベクトル乗算を試してみることをお勧めします。

size(spA)
ans =

 1244810     1244810

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

Elapsed time is 0.106581 seconds.

これは単なるタイミング分析です。あなたのケースでそれを実装する方法については、私の以前の回答を参照してください。CUDAに移動して複雑な作業を行う前に、より単純なオプションを確認してください。

于 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)

これは、M100万x 4であっても、非常に高速に評価されるはずです。

于 2012-10-17T20:47:49.797 に答える