Team from Purdue University wins Best Paper at the International Conference on Supercomputing
A team from Purdue University was awarded Best Paper at the International Conference on Supercomputing. Durga Mandarapu, a PhD student, was first author on the paper “Arkade: k-Nearest Neighbor Search with Non-Euclidean Distances using GPU Ray Tracing,” which talks about improving a specific type of search algorithm called k-Nearest Neighbor (kNN) for finding the closest points in a dataset.
kNN is like finding the closest friends to your house on a map. To make this search quick, special data structures based on trees are usually used. However, these trees are tricky to use with GPUs, which are powerful accelerators that accelerate graphics and machine learning tasks, but typically cannot accelerate tree-based computations. However, newer Nvidia GPUs have special hardware parts called ray-tracing cores that can speed up tree operations found in certain graphics algorithms. Researchers have invented algorithms to use these cores to speed up distance measurements in non-graphics algorithms like kNN.
The problem is that these ray-tracing cores can only handle one type of distance measurement, called Euclidean distance, which is a straight-line measurement like using a ruler. To fix this, the researchers came up with two new methods, Arkade Filter-Refine and Arkade Monotone Transformation. These methods allow for the use of other types of distance measurements by converting them into a form that the ray-tracing cores can handle.
“Tree traversals are ubiquitous in computer science applications, making their efficient acceleration essential on modern hardware, like GPUs,” says Durga. “Arkade winning the best paper award shows just how much the community values the advancements in GPU acceleration of tree traversals. This achievement inspires me to investigate a wider array of applications that can leverage various GPU architectures for enhanced performance.”
With these new methods, the kNN searches become much faster, up to 200 times faster in some cases, compared to prior state of the art, opening up a broader class of applications to these new ray-tracing cores.
In addition to Mandarapu, other authors on the paper include ECE PhD student Vani Nagarajan, ECE postdoctoral researcher Artem Pelenitsyn, and Milind Kulkarni, Michael and Katherine Birck Head and Professor of Electrical and Computer Engineering.