# Locality-Sensitive Hashing for Information Retrieval System on Multiple GPGPU Devices
## 2 Research Background and Related Works
### kNN Search Using Multiple GPGPUs  
Concerning research using multiple GPGPU devices for \(k\)NN search, in [16], [PERSON] proposed the use of multiple GPU devices for handling multiple \(k\)NN search queries simultaneously. Similarly to our study, the method in [16] sends queries to all GPU devices, where each GPU has its own heaps to store temporary ranked \(k\)NN candidates and the final \(k\)NN results are merged at the end. However, the workflows of the GPU devices in [16] are completely independent of each other; the merging process only takes place when all slaves are done with their searches.  
We recognize that this strategy may affect the performance of the whole search system; we called this strategy a \"Blind search\" in our research, which means that the GPU devices cannot see the current results of others. In [17], [PERSON] used multiple GPUs to process massive numbers of queries; however, the queries were divided into different GPUs, where each GPU device processed independently. Although there have been several studies using hashing on GPGPU for handing the \(k\)NN search problem [17], our study provides a new approach for the optimization of a parallel LSH algorithm using multiple GPGPUs.  
In our recommended system, a group of GPGPUs is responsible for parallel searching over all the incoming queries and a Master (CPU) is used to control the workflows of all slaves (i.e., GPGPUs). Computer clusters containing a great number of general-purpose GPUs (GPGPUs) have grown stronger by taking advantage of parallel computing using graphics processing units (GPUs) [18]. The typical locality-sensitive hashing algorithm makes use of different data types and plays different roles in the system. In addition, a raw data set is essential, but its access time is very limited. It is, thus, ideal to  
Figure 3: Demonstration of \(k\)NN Result Merger for three temporary sorted \(k\)NN results, where \(k=2\).  
store the data set in the GPGPU's global memory [7]. Furthermore, the memory space required for a family of hash functions is very small, yet its access number is very high due to the calculation of hash values for every query. For this purpose, we can take advantage of the GPGPU's constant memory, which is small but supports high-speed access.  
There exist several public Message Passing Interface (MPI) libraries for the C++ programming language that support use on parallel computers or supercomputers. The target of MPI is to transfer data among processes with high performance and scalability on various systems, as well as portability to different operating systems [19]. By using MPI, a program can be divided into multiple parallel processes; in our system, we use one Master process to control the workflows of the slave processes (GPGPUs). One computer node may have one or multiple GPGPU devices; we deliberately create MPI slave processes to match the number of GPGPU devices on that node. Then, we treat the slave processes fairly, regardless of which node they are in. Each slave process handles GPGPU tasks, such as loading the database, receiving queries, CPU-GPGPU communications, and broadcasting/receiving \(k\)NN results.