Multi‐GPU algorithm for k‐nearest neighbor problem
Kimikazu Kato, Tikara Hosino · Concurrency and Computation Practice and Experience · 2011
SUMMARY The recommendation system is a mechanism which automatically recommends items that are likely to be of interest to the user. In the recommendation system, customers' preferences are encoded into vectors, and finding the nearest vectors to each vector is an essential part. This vector‐searching part of the problem is called a k‐nearest neighbor problem. We give an effective algorithm to solve this problem on multiple graphics processor units (GPUs). Our algorithm consists of two parts: the N‐body problem and the partial sort. For an algorithm of the N‐body problem, we applied the idea of a known algorithm, although another trick is needed to overcome the problem of small‐sized shared memory. For the partial sort, we give a novel GPU algorithm which is effective for small k. In our partial sort algorithm, a heap is accessed in parallel by threads with a low cost of synchronization. We show through an experiment that when the size of the problem is large, an implementation of the algorithm on two GPUs runs more than 330 times faster than a single core implementation on a latest CPU. Copyright © 2011 John Wiley & Sons, Ltd.