Есть ли эффективный способ отобразить граф на блоки в программировании CUDA?

Question

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

Для задач с обычной структурой данных это очень просто и эффективно, например, умножение матриц, БПФ и т. Д.

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

Мне интересно, существуют ли эффективные решения для такого типа разделов?

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

Answer 1

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

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

Answer 2

Вы можете использовать MapGraph, который использует метод GAS для всех упомянутых вами вещей .... у них также есть некоторые примеры, реализованные для того же самого, и библиотека, включенная для Gather, Apply и Scatter в cuda для реализации только на GPU и только для процессоров.

Вы можете найти последнюю версию здесь: http://sourceforge.net/projects/mpgraph/files/0.3.3/