Подходит ли CUDA от nVidia для выполнения поиска пути?

13

Я хочу знать, стоило ли бы выполнять поиск пути на GPU (используя nVidia CUDA или его эквивалент) в определенных ситуациях, или это было бы напрасным усилием. Ситуация, которую я представляю, будет безголовым многопользовательским сервером, отвечающим за поиск путей для ботов.

Я особенно интересуюсь поиском пути A * с использованием навигационных сеток, но если есть другой алгоритм поиска пути, который выиграл бы больше от выполнения графического процессора, я бы хотел услышать его.

Keeblebrox
источник

Ответы:

8

Поиск пути - это, по сути, проблема графа, в которой происходит много параллелизма. Есть много статей о том, как реализовать и оптимизировать алгоритмы на основе графов для CUDA.

Я нашел несколько работ, которые могут вас заинтересовать (хотя они довольно академичны):
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://ppl.stanford.edu/papers/ppopp070a-hong.pdf

Итак, короткий ответ: да :).

Однако я не знаю, может ли это стоить того, чтобы написать реализацию A * CUDA вместе с накладными расходами на вызовы на безголовый сервер. Обязательно сначала сделайте небольшой прототип! (Также это могло бы сделать интересную запись в блоге, поэтому обязательно напишите, что вы делаете;)).

Рой Т.
источник
Это фантастические ссылки, спасибо! Я могу обращаться с некоторой академической информацией время от времени. Я не имею в виду игру для использования этого еще, но мне нравится идея прототипирования этого. Я обязательно документирую свой прогресс.
Keeblebrox
Круто, мне очень интересно, как это будет работать.
Рой Т.