Nearest Neighbor in OpenCL

[djhoese]

I'd like to start this discussion because I might research this topic when I get bored. I am not an OpenCL or CUDA expert (or even novice) so I'm putting my findings here as I go.

• https://forums.khronos.org/showthread.php/7402-kd-tree-nearest-neighbour
  Summary: KDTree is not typically a great algorithm for GPUs, it is intentionally good for CPUs. At the end someone provides a link to their paper on a GPU-friendly KDTree algorithm.
• https://github.com/gieseke/bufferkdtree
  Python library with GPU OpenCL implementation with a mix of a KDTree and brute force algorithm.
• HALMD: http://halmd.org/
  C++ library advertised on Stackoverflow as "the fastest nearest neighbor algorithm on a GPU"
• https://stackoverflow.com/questions/5381397/openclnearest-neighbour-using-euclidean-distance
  Simple OpenCL code for a brute force "minimum distance between this point and all others"
• https://arxiv.org/abs/0804.1448
  Fast k Nearest Neighbor Search using GPU
• https://github.com/Jackie-Chou/pyopencl_knn
• https://github.com/yszheda/OpenCL-knn-1GPU
• https://github.com/chrischoy/knn_cuda
  Has a python wrapper and has lots of stars

[quasiben]

Hi @djhoese -- I came here via your recent thread on dask improvements for pyresample and started poking around. cuML has a GPU enabled KNeighborsClassifier . Happy to help run some experiments if you're still interested in this topic. Sadly, CUDA only

[djhoese]

That'd be great @quasiben! As an optional performance improvement, CUDA-only would still be fine. What would the code look like if we had dask arrays for X, Y, Z euclidean coordinates and a single 2D image array to be resampled? Are there optimizations available if we wanted to run the nearest neighbor again but with different image data (same coordinates)? Right now pyresample uses the pykdtree package. Also note that the X, Y, Z coordinates are converted from lon/lat arrays so if those could be given to the classifier directly that would save even more time.

[quasiben]

Looking deeper here I think cuML is lacking some functionality . While there are NearestNeighbor Classifiers, there is no KDTree implementation at the moment (though, there is an issue rapidsai/cuml#1690 ) . cuSpatial does had a quad-tree -- I'll ask around and see if there are any plans here. Apologies for the noise.

[djhoese]

No problem. Glad you could at least link to some other efforts in similar areas.

[grlee77]

Here is another CUDA kd-tree implementation I came across (BSD 3-clause license)
https://github.com/johnarobinson77/KdTreeGPU

[mraspaud]

Cupy seems to have a GPU-optimized kdtree docs.cupy.dev/en/latest/reference/generated/cupyx.scipy.spatial.KDTree.html
However at the time writing, this has not been released yet and would need manual building of cupy to try it out (which I don't have time for right now).