Решение задачи изоморфизма подграфов на многопроцессорных системах

В данной работе рассматривается решение задачи поиска изоморфного подграфа в графе для многопроцессорных систем. На базе алгоритма Ульмана было разработано и описано два варианта решения задачи на языке Erlang. Представлены результаты эксперимента, проведенного для оценки производительности описанных решений, и дно объяснение полученных результатов.

Цель проекта – разработка решения задачи изоморфизма подграфов для многопроцессорных систем
Задачи:
• рассмотреть последовательные решения поставленной задачи, определить, возможно ли на базе данных решений разработать решение для многопроцессорных систем;
• рассмотреть структуры данных и операции, необходимые для решения задачи;
• разработать распределенное решение;
• провести оценку производительности разработанного решения

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

Данная задача имеет следующие вариации:

• поиск подграфа в графе;
• поиск самого часто встречающегося подграфа;
• подсчет подграфов в графе;
• вычисление функции распределения количества графлетов в графе.

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

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

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

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

На основе решений было разработано две параллельные версии алгоритма Ульмана и были выдвинуты две гипотезы относительно эффективности данных алгоритмов:

1. асинхронный вызов рекурсии мало эффективен на больших данных;
2. пул потоков предоставляет более эффективное решение на данных любого объема.

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

Были выдвинуты две гипотезы относительно эффективности разработанных алгоритмов:

1. алгоритм, реализованный с помощью асинхронного вызова рекурсий мало эффективен на больших данных. Это связано с тем, что такой подход подразумевает, что в ходе решение динамически создается и завершает работу большое количество акторов, что влечет за собой большие накладные расходы на управление акторами;
2. алгоритм, реализованный на основе пула акторов эффективен на данных любого объема, так как при инициализации решения задачи сразу создается необходимое количество акторов, следовательно, уменьшаются расходы на управление акторами.

Для подтверждения гипотез было проведено два эксперимента. В ходе экспериментов производился поиск в графах, состоящих из 10, 50, 100, 150 и 200 вершин, изоморфного подграфа из 4 вершин.

Первый проводился на на персональном компьютере со следующими характеристиками:

• процессор Intel® Core™ i7-3770K CPU @ 2.20 GHz, имеющий 4 физических ядра (8 логических ядер);
• оперативная память DDR3 (4 гб);
• 64-разрядная ОС Windows 10;
• виртуальная машина BEAM
• язык программирования Erlang 18

Эксперимент показал, что оба алгоритма имеют примерно одинаковые ускорения и эффективность: ускорение 3,38 эффективность 0,84 для асинхронного вызова рекурсии на графе из 200 вершин; ускорение 3,6, эффективность 0,9 для пула из 5 потоков на графе из 200 вершин.

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

• персональный компьютер из первого эксперимента;
• персональный компьютер с характеристиками:
  • процессор Intel® Core™ i7-3770K CPU @ 3.50 GHz, имеющий 4 физических ядра (8 логических ядер);
  • оперативная память DDR3 (8 гб);
  • 64-разрядная ОС Windows 10;
  • виртуальная машина BEAM
  • язык программирования Erlang 18

Эксперимент также показал, что оба алгоритма имеют примерно одинаковые ускорения и эффективность: ускорение 6,34 эффективность 0,79 для асинхронного вызова рекурсии на графе из 200 вершин; ускорение 6,49, эффективность 0,72 для пула из 9 потоков на графе из 200 вершин.

В результате первая гипотеза была опровергнута: асинхронный вызов поток примерно одинаковое с пулом потоком ускорение. Это было связано с тем, что BEAM (виртуальная машина Erlang) осуществляет эффективное управление акторами и распределение нагрузки между вычислительными узлами с помощью редукций.

Вторая гипотеза была подтверждена.

Судоплатов, С. В. Дискретная математика [Текст]/С. В. Судоплатов, Е. В. Овчинникова. – Изд-во НГТУ: Новосибирск, 2012. – 280 с.

Ullmann J. R. An Algorithm for Subgraph Isomorphism Problem [текст]/J. R. Ulmann. – Journal of the Association for Computing Machinery, VoI 23, No 1, 1976. – 31-42 p.

Erlang/OTP 18 [электронный ресурс] – электрон. текст. дан. – режим доступа: http://erlang.org/doc/ (дата обращения 21.06.2016)

Solving the subgraph isomorphism problem for multiprocessor systems is considered in this project. Two solutions are designed and described for Erlang based on the Ullmann algorithm. The results of the performance evaluation experiments and interpretation of this results are presented.