алгоритмы графа на GPU

Question

Текущие потоки графического процессора как-то ограничены (ограничение памяти, ограничение структур данных, отсутствие рекурсии ...).

Как вы думаете, было бы возможно реализовать проблему теории графов на GPU. например, крышка верхушки? доминирующий набор? независимый набор? max clique? ....

Можно ли также использовать алгоритмы с ветвлением и границей на графических процессорах? Рекурсивный откат?

Answer 1

Вам будет интересно в

1. Exploring the Limits of GPUs With Parallel Graph Algorithms
   

2. Accelerating large graph algorithms on the GPU using CUDA.

Answer 2

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

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

(. @TheMachineCharmer, спасибо за ссылки)