алгоритмы графика на GPU
текущие потоки GPU так или иначе ограничены (предел памяти, предел структур данных, никакая рекурсия...).
Вы думаете, что было бы выполнимо реализовать проблему теории графов на GPU. например, покрытие вершины? доминирование над набором? независимый набор? макс. клика?....
также выполнимо иметь алгоритмы метода ветвей и границ на GPU? Рекурсивное отслеживание в обратном порядке?
2 ответа
Это косвенно связано с вашим вопросом, но я реализовал «рекурсивный» алгоритм поиска с возвратом для перечисления «самопроизвольных прогулок» на решетке (nb : стек был смоделирован в ядре CUDA, чтобы избежать накладных расходов на создание локальных переменных для целого набора вызовов функций). Это можно сделать эффективно, поэтому я уверен, что это можно адаптировать к теоретическому контексту графов. Вот ссылка на семинар по этой теме, где я дал общее обсуждение обратного отслеживания в парадигме SIMD (Single Instruction Multiple Data); это PDF-файл размером около 1 МБ http://bit.ly/9ForGS .
Я не утверждаю, что знаком с обширной литературой по алгоритмам теории графов на графических процессорах, но надеюсь, что изложенное выше мне немного поможет.
(@ TheMachineCharmer, спасибо за ссылки.)