Сортировка наименьших K элементов вектора для реализации алгоритма прямого перебора K-ближайшего соседа на GPU

Я реализовал ближайшего соседа K на графическом процессоре, используя как чистые вызовы функций CUDA, так и библиотечные функции Thrust.

Евклидовы расстояния вычисляются с помощью чистого ядра CUDA. Затем используются средства сортировки Thrust (сортировка по основанию) для сортировки расстояний в порядке возрастания. Наконец, первые K элементов (т. Е. K ближайших соседей) извлекаются из отсортированных векторов.

Моя реализация работает хорошо. Однако сортировка всей матрицы евклидовых расстояний (наборы могут содержать более 250000 образцов поездов) только для получения K -nn кажется неоптимальной.

Поэтому я ищу реализацию алгоритма графического процессора, которая позволяет останавливать вычисления сортировки, как только будут найдены K наименьших элементов, или которая выполняет эффективную K из N сортировка. Это действительно будет быстрее для небольшого K, чем сортировка всей матрицы.

Если такая реализация недоступна, меня также будут интересовать советы по ее эффективной реализации на чистом CUDA или Thrust. Я думал использовать несколько потоков на тестовые образцы для поиска ближайшего K, причем каждый поток проходит на часть евклидовых расстояний. Я бы сохранил буфер размером K в общей памяти. Я пробегал через расстояния и вставлял Knn в вектор разделяемой памяти. Однако это потребует некоторой синхронизации уровня деформации и расхождения потоков.

Спасибо за помощь.


gpu sorting cuda knn thrust
person user3806305    schedule 04.07.2014    source источник
comment
Вопросы о рекомендации или поиске библиотеки не относятся к теме StackOverflow. Однако мне кажется, что вам лучше нужен подход, а не библиотека. Вы можете изменить формулировку своего вопроса соответствующим образом. Насколько мне известно, K-ближайшие соседи эффективно решаются подходами KD-деревьев, см., Например, Проектировать 12 ближайших соседей графического процессора с использованием минимального kd-дерева.   -  person Vitality    schedule 05.07.2014
comment
@JackOLantern спасибо за ответ. Однако моя цель - реализовать алгоритм KNN грубой силы на GPU, а не версию kd-tree. Вы правы, вопрос с рекомендацией библиотеки не по теме, поэтому я изменил свой вопрос. Надеюсь, теперь все в порядке.   -  person user3806305    schedule 05.07.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вы ищете подход к решению проблемы ближайшего соседа K, состоящий из двух шагов:

  1. Нахождение евклидовых расстояний между элементами;
  2. Нахождение первых K элементов, обеспечивающих K наименьшие расстояния.

Похоже, что такой подход уже существует и реализован в

К.Като и Т. Хосино, "Решение k -задачи ближайшего соседа для нескольких графических объектов Процессоры "

и представлен на конференции GTC 2009 как

К.Като и Т. Хосино " Вам также может понравиться: Система рекомендаций для нескольких графических процессоров ".

Подход решает два вышеупомянутых шага с помощью

  1. с использованием классического подхода N-body, разработанного L.Nyland, M.Harris, J.Prins, "Fast N -body Simulation with CUDA", In: GPU Gems III . NVIDIA (2007) 677–695 для вычисления евклидовых расстояний;
  2. с использованием метода частичной сортировки, основанного на идее параллельной heapsort .

Опять же, как упоминалось в моем комментарии выше, лучший подход, избегающий вашего «грубого перебора», - это использовать KD-деревья.

person Vitality    schedule 05.07.2014
comment
Спасибо @JackOLantern, это именно то, что я искал. Эти научные статьи полезны. Я полагался только на academypublisher.com/proc/iscsct09/papers/iscsct09p151.pdf, но похоже, что у вас есть более умные идеи. - person user3806305; 06.07.2014