Параллельный поиск в глубину в Erlang медленнее, чем его последовательный аналог

Question

Я пытаюсь реализовать модифицированный алгоритм параллельного поиска в глубину в Erlang (назовем его * dfs_mod *).

Все, что я хочу получить, это все «тупиковые пути», которые в основном являются путями, которые возвращаются, когда * dfs_mod * посещает вершину без соседей или вершину с соседями, которые уже были посещены. Я сохраняю каждый путь в ets_table1, если моя пользовательская функция fun1(Path) возвращает true, и в ets_table2, если fun1(Path) возвращает false (мне нужно отфильтровать получившиеся «тупиковые» пути с помощью некоторого пользовательского фильтра) .

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

Идея параллельной реализации проста:

• посетите Vertex с [Vertex|Other_vertices] = Unvisited_neighbours,
• добавить это Vertex к текущему пути;
• отправить {self(), wait} процессу 'сборщика';
• запустить * dfs_mod * для Unvisited_neighbours текущего Vertex в новом процессе ;
• продолжить выполнение * dfs_mod * с остальными предоставленными вершинами (Other_vertices);
• если вершин больше нет для посещения - отправьте {self(), done} процессу сбора и завершите работу;

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

Сразу после запуска первого процесса * dfs_mod * я начинаю собирать все сообщения {Pid, wait} и {Pid, done} (сообщение wait заставляет сборщик ожидать всех сообщений done). Через N миллисекунд после ожидания функция коллектора возвращает ok.

---

По какой-то причине эта параллельная реализация выполняется от 8 до 160 секунд, а последовательная версия - всего 4 секунды (тестирование проводилось на полностью подключенном орграфе с 5 вершинами на машине с процессором Intel i5).

Вот мои мысли о такой плохой производительности:

• Я передаю орграф Graph каждому новому процессу, который запускает * dfs_mod *. Может быть, выполнение digraph:out_neighbours(Graph) против одного орграфа из многих процессов вызывает эту медлительность?
• Я накапливаю текущий путь в списке и передаю его каждому новому порожденному процессу * dfs_mod *, может, проблема в пропуске такого количества списков?
• Я использую таблицу ETS для сохранения пути каждый раз, когда посещаю новую вершину и добавляю ее в путь. Свойства ETS ([bag, public,{write_concurrency, true}), но, возможно, я что-то не так делаю?
• каждый раз, когда я посещаю новую вершину и добавляю ее в путь, я проверяю путь с помощью пользовательской функции fun1() (она в основном проверяет, есть ли у пути вершины, обозначенные буквой "n", встречающиеся перед вершинами с "m" и возвращает true/false в зависимости от результата). Может быть, это fun1() замедляет ход событий?
• Я пытался запустить * dfs_mod * без сбора сообщений done и wait, но htop довольно долго показывает активность Erlang после того, как * dfs_mod * возвращает ok в оболочке, поэтому Я не думаю, что активная передача сообщений замедляет работу.

---

Как я могу заставить мой параллельный dfs_mod работать быстрее, чем его последовательный аналог?

Редактировать : когда я запускаю параллель * dfs_mod *, pman вообще не показывает никаких процессов, хотя htop показывает, что все 4 потока ЦП заняты.

Answer 1

Нет быстрого способа узнать без кода, но вот краткий список причин, по которым это может не сработать:

• Возможно, вы путаете параллелизм и параллелизм.Модель Эрланга не разделяется и нацелена в первую очередь на параллелизм (независимый запуск отдельных блоков кода).Параллелизм - это всего лишь оптимизация (запуск некоторых блоков кода одновременно).Обычно параллелизм принимает форму на более высоком уровне, скажем, вы хотите запустить свою функцию сортировки на 50 различных структурах - тогда вы решаете запустить 50 функций последовательной сортировки.

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

• Затраты на копирование данных, переключение контекста и все такое значительно уменьшают выгоды, которые вы получаете в плане параллелизма.Это первое особенно верно для больших наборов данных, которые вы разбиваете на поднаборы данных, а затем соединяете обратно в большой.Последнее особенно верно для высокопоследовательного кода, как видно из тестов кольца процесса.

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

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