Как ускорить выполнение алгоритма распределенного графа? - PullRequest
Новая
       24

Как ускорить выполнение алгоритма распределенного графа?

3 голосов
/ 04 марта 2012

У меня проблема с графиком следующим образом, и мне нужно оптимизировать производительность по времени выполнения. Я ищу только технику программирования , а не алгоритмическую оптимизацию для повышения производительности. Проблема заключается в следующем: для заданного графа G (V, E) каждый узел u создает подмножество своих соседей N (u), называемое многосетевым ретранслятором (M_r (u)), таким образом, что каждый сосед в 2 скачка u является соседом по крайней мере, один узел в M_r (и). Конструкция M_r (u) в узле u выглядит следующим образом. 

construct_mr(u)
1) M_r(u) is initially empty.
1') The set of non-covered 2-hop of neighbors of u is the set of all 2-hop neighbors of u.  
// a covered 2-hop neighbor of u: is a 2-hop neighbor of u that is also a neighbor to at least one of the nodes of M_r(u). 
2) while (M _r(u) is not a multiset relay set) 
 2a) update the set of non-covered 2-hop neighbors of u. 
 2b) add to M_r(u) a neighbor v that cover the most non-covered 2-hop neighbors of u.

Теперь я сделал следующее: 

for each node u \in V: construct_mr(u).

Проблема в том, что она является сериализованной реализацией и имеет ужасное время выполнения, когда граф большой и плотный. Я ищу метод, который ускоряет выполнение такого алгоритма - предпочтительно с использованием Java или C ++. Я хоть и многопоточен, но должен ли я поиграть с планированием потоков, чтобы получить хорошую производительность? [Обратите внимание, что модели программирования с передачей сообщений не будут иметь никакого эффекта, так как мы не передаем никаких сообщений]

1 Ответ

1 голос
/ 04 марта 2012

Я сомневаюсь, что распределенная реализация поможет.

В основе проблемы лежит процесс обхода графа, в котором вы идентифицируете каждого из соседей по 2 скачкам. Для этого каждому экземпляру в распределенной версии алгоритма требуется копия графа:

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

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

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

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

Сказав это, я подозреваю, что настоящая причина медленных вычислений заключается в деталях алгоритма и в том, как вы реализовали структуры данных.

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

(Один из подходов, который работает, - это профилировать ваш код, определить места, в которых тратится большая часть времени, и ... после глубоких размышлений об этом ... переработать структуры кода / данных, чтобы улучшить его. Но есть здесь нет никакой магии. Просто тяжелая работа и размышления.)

...