# Locality-Sensitive Hashing for Information Retrieval System on Multiple GPGPU Devices
## 3 Our Previous Work: Muti-Thread Implementation of StagedLSH on Single GPGPU (CUSTagedLSH)  
In the first version of DLSH, presented in [6], the DLSH algorithm mainly aims to handle a real, dynamic data set and acquire high-performance parallel processing. This section will discuss the model design, the principles, and multiple-thread optimization of DLSH with a GPGPU.  
The traditional search algorithm of StagedLSH uses continuous probes to search multiple buckets with multiple corresponding hash values. For the ANN search problem, StagedLSH can stop in the very first probe when an acceptable item is found. However, StagedLSH has 126 probes for the search process of a query. With the CUSTagedLSH search algorithm on a GPGPU, we parallelize the probe processes of the queries in order to increase occupancy.  
StagedLSH needs the Merger process to merge the new \(k\)NN results after every probe, which involves the duplication of comparisons of the same \(k\)NN results after each probe. To avoid this problem, we use multiple CUDA threads to process the StagedLSH probes. As shown in Figure 4, the temporary \(k\)NN results are stored in CUDA shared memory and the Merger process can be carried out only one time, after all probes are finished. Using this approach, CUSTagedLSH can take advantage of both local memory and shared memory. Thus, CUSTagedLSH can handle more \(k\)NN results than the original StagedLSH method.  
Although the original StagedLSH approach uses 126 probes for each query, we deliberately created 128 threads to handle the tasks of 126 probes (where two threads are idle). By allocating 128 (\(2^{7}\)) threads, we can optimize the utilization of CUDA's warp, which has 32 threads in each warp. The shared memory of each block is limited, so we use one block for the process of searching with respect to one query. This helps us to increase the rank size for the candidates of each thread. With 3584 CUDA cores, the P100 device can process 114,688 threads at once. With this number of parallel threads, the P100 GPGPU device is able to process 114,688 probes (i.e., \(\sim\)900 queries) in the StagedLSH algorithm in parallel. We realized that a StagedLSH probe is an ideal process for a thread in GPGPU. However, in practical cases, some queries may stop before others, creating an empty slot for the un-processed queries on the same CUDA grid.  
A comparison of CUSTagedLSH versus other variants of LSH on GPGPU is given in Figure 5. On CPU, CUSTagedLSH had a higher search speed than StagedLSH, in cases where these methods had the same recall [6]. However, CUSTagedLSH is optimized for processing on GPGPU by parallelizing query probes and using shared memory. This meant that CUSTagedLSH could process faster than StagedLSH when using GPGPU. StagedLSH and CUSTagedLSH required less hash tables, which meant that StagedLSH and CUSTagedLSH could process each probe faster. Entropy-Based LSH [20] has better accuracy when using a selective family of hash functions, but requires a longer amount of time due to the requirements of dynamic hash function allocation. The Basic LSH method was too simple for processing with multiple probes and, so, the recall of Basic LSH was not high, with a single probe for each query.  
Figure 4: CUStagedLSH: Hardware-oriented optimization of StagedLSH with multiple threads (1 CUDA block) to handle probes related to a query.  
Figure 5: Search time for 10K queries on 1 million audio fingerprints for the approximate \(k\)NN search problem using a single GPGPU and the same number of probes.