3 Ricerca chiavi intera in CUDA

Question

Vorrei cercare 3 numeri interi (ad esempio [1 2 3]) in un grande set di dati di circa un milione di punti.

Attualmente sto usando Map MATLAB (HashMap), e per ogni punto che sto facendo quanto segue:

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

Questa è notevole dispendio di tempo anche se - 1 milione di punti * 55 US = 55 secondi.

Mi piacerebbe spostare questo nella GPU usando CUDA, ma non sono sicuro del modo migliore di avvicinarsi a questo.

È possibile trasferire quattro array - key1, key2, key3, result e quindi eseguire la ricerca binaria sui tasti, ma ciò richiederebbe 20 iterazioni (2^20 = 1048576) per chiave. Quindi avrei anche dei ritardi dovuti all'accesso alla memoria concorrente da ogni thread.

Esiste una struttura dati ottimizzata per ricerche di chiavi multiple parallele (O (1), idealmente) in CUDA?

---

D: Quali sono i confini dei tre numeri interi? E quali dati vengono consultati?

I tasti interi possono essere compresi tra 0 e ~ 75.000 al momento, ma potrebbero essere più grandi (200.000+) in futuro.

Ai fini di questa domanda, possiamo supporre che lo result sia un numero intero compreso tra 0 e la dimensione del set di dati.

---

D: Perché non imballare tutti e tre i numeri in un numero a 64 bit (21 bit per il numero ti dà una serie di 0-2,097,152). E lo usi per indicizzare in una matrice sparsa?

>> 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'. 

Sembra che il mio MATLAB non supporta array sparsi di numeri a 64 bit.

Nel caso in cui questo aiuta chiunque altro, ho scritto una funzione veloce per creare una chiave a 64 bit da tre < 2^21 numeri interi senza segno:

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

---

D: Da @Dennis - perché non usare l'indicizzazione logica?

Proviamoci!

% 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 

Sfortunatamente questo richiede 89801us, che è 1632x più lento della mia soluzione esistente (55us)! Ci vorrebbero 2,5 ore per eseguire questo milione di volte!

abbiamo potuto provare il filtraggio M dopo ogni ricerca:

>> 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. 

Questo è un po 'più veloce, ma ancora più lento di 696x utilizzando Map.

---

Ho riflettuto su questo un po 'di più, e ho deciso di profilo della velocità di ri-generare alcuni dei dati al volo da una singola ricerca della chiave - potrebbe essere più veloce di un 3 ricerca chiave, dati i potenziali problemi con questo approccio.

Answer 1

Sto supponendo che questa domanda sia relativa al tuo previous question sui volti del tetraedro. Ho ancora suggerisco di provare il sparse stoccaggio e sparse matrice-vettore moltiplicazione a tal fine:

size(spA) 
ans = 

1244810  1244810 

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

Elapsed time is 0.106581 seconds. 

Questo è solo tempi di analisi, vedere la mia risposta precedente su come implementarlo nel tuo caso. Prima di passare a CUDA e fare cose complicate, controlla le opzioni più semplici.

Answer 2

Data l'attenzione a questa domanda ha già ricevuto ci si sente come questa risposta è troppo semplice, ma perché non basta fare in questo modo:

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) 

Questo dovrebbe valutare abbastanza veloce, anche se è M 1 milione x 4.