3 CUDA中的整數鍵查找

Question

我想在大約100萬個點的大型數據集中查找3個整數（即[1 2 3]）。

我目前使用MATLAB的地圖（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. 

這是一個快一點，但仍比696x使用地圖慢。

---

我一直在思考這個多一些，我已經決定輪廓曲線的速度，重新生成一些從一個鍵查找運行中的數據 - 這可能是比3快關鍵查找，鑑於這種方法的潛在問題。

Answer 1

我猜這個問題是關於你的previous question關於四面體的面孔。我還是建議你應該嘗試sparse存儲以及稀疏矩陣向量乘爲此目的：

size(spA) 
ans = 

1244810  1244810 

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

Elapsed time is 0.106581 seconds. 

這只是時序分析，看看我以前有關如何實現它在你的情況的答案。在轉移到CUDA並執行復雜的任務之前，請查看更簡單的選項。

Answer 2

鑑於這個問題已經收到感覺這個答案太簡單了，但你爲什麼不只是做了這樣的注意：

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.