параллельное вычисление гамильтонова цикла в графе заданном генератором

Вычисления типа Master-Slave

Разработайте параллельный алгоритм Master-Slave технология, который использует технологии MPI и OpenMP. В начале расчета MPI созданы в общей сложности р процессах, где один из мастер-процесса контроля и другие процессы будут вычислительной раб. Мастера будут искаться пространстве состояний разделены между другими вычислительными процессами. Чтобы сделать это возможным, стандартный последовательный алгоритм начинает искать пространство состояний в ширину, и генерирует достаточно большой набор начальной конфигурации хранилища для вычислительных процессов раб. Создание начальной конфигурации используя ширину заканчивается, когда количество листов пространства состояний в первый раз более чем Zp , где р -число процессоров и Z> = 10 это предварительно постоянную (постоянная из экспериментально определить, в зависимости от типа работы - вам нужно для достижения оптимального детализации, раб вычислительных процессов работы достаточно долго, и число конфигураций достаточно большим, чем количество процессоров). Затем начинается начальной главной конфигурации готова распространять рабом вычислительных процессов. Мастер всегда выбирает одну конфигурацию из своей очереди и отправляет его на выбранный раб процесса.

Каждый ведомый всегда принято конфигурации хранятся в его локальной очереди, а затем генерирует достаточное количество конфигураций прохождения ширины, что вы сохранили в локальной очереди. Эти конфигурации будет иметь проблемы своего проходящего в глубину. Использование OpenMP будут обрабатываться параллельно несколько конфигураций, то есть каждый поток генерируется с использованием OpenMP обрабатываются последовательно глубина сканирования всегда одна конфигурация выбирается из очереди (количество потоков выбрать делится на 4, так как каждый узел имеет четыре вычислительных ядер). Раб никогда не вернулся в состояние выше их начальной конфигурации (то есть, первое дополнение к Master). Когда волокно проходит через присвоен государственный пространстве, определенном назначена начальная конфигурация имеет следующую свободную конфигурацию стека. Если подчиненный очереди больше нет свободных начальной конфигурации, сообщают, что мастер, он пошлет еще один свободный počátační конфигурации вашей очереди. Если мастер не имеет свободных конфигурация не сообщает об этом запрашивающей раб процесс посылает его локальное решение мастером, а затем останавливается. Если подчиненный решение с лучшей возможной цене, сообщите об этом хозяину, что использует связи, чтобы все операции с одним конце расчета. Они должны быть обработаны с ситуациями, когда решение одновременно обнаруживает несколько рабов (например, через параллельным сокращением).

Расчет Master-Slave используется в качестве библиотеки MPI для связи через распределенной памятью и OpenMP для обмена данными через общую память. При измерении применение план всегда один MPI процесс на "лезвие бритвы" (Blade объема STAR) и уровень OpenMP всегда создает несколько потоков в 4 (каждая бритва имеет 4 ядра процессора).



Роль HG: гамильтонова графа

Входные данные:

G (V, E) = не оценено простым неориентированый на регулярный граф на п вершинах и м краям, я = целое число, представляющее число узлов графа G , п> = 5 = целое число, представляющее порядок узел степень графа G , п> = к > = 3, я и то же время как нечетные


Рекомендации для G алгоритм генерации:

Использование генератора при графе графике " т-АД ".

Задача:

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

Выходной алгоритму:

Ответ ли заданный граф содержит гамильтонов путь. В случае положительного ответа на один такой список путей.

Последовательный алгоритм:

Последовательный алгоритм типа СО-DFS с глубиной состояние дерева ограничена н . Mezistav определяется список узлов, на построенной еще возможных маршрутов. Допустимая конечных состояниях всех перестановок N чисел, представляющих гамильтонов путь. Возврат осуществляется в государстве, где нет возможности продолжать строительство гамильтонов путь. Расчет заканчивается, когда первые находки гамильтонов путь и пройти или не все пространство государства.

Параллельный алгоритм:

Дизайн параллельного типа алгоритма ведущий-ведомый . Начальная конфигурация является начальным отрезком гамильтониана длины пути.

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

Первая строка содержит информацию о количестве узлов n в графе.

Остальные строки описывают матрицу смежности M [n, n], которая хранится в файле построчно. Ряд u показывает, с какими узлами соединен или не соединен узел u. Другими словами, узел u связаны c узлом v , если M [U, V] = 1 Если M [U, V] = 0, между узлами u и v нет связи. Не сложно заметить, что матрица M симметрична, то есть M [U, V] = M [V, U].
Например:

4
0110
1001
1000
0100
Этот файл описывает граф с 4 узлов, где грань между узлами 0 и 1, 0 и 2, 1 и 3

Генератор

Этот генератор (двоичный файл, скомпилированный для STAR = 64-разрядная SUSE Linux) генерирует случайные графы, которые являются k-регулярными (то есть, каждый узел имеет степень к) графов, где узлы имеют в уровени к степень, и графики c полностью случайными параметрами являются:

-t typ : тип генерируемого графа, где параметр типа может занимать от 3 ​​до следующие строковые значения:
REG : k-регулярный граф
AD : график со средней степенью к узла k
НАХ : случайный граф,

-t число: количество узлов
-k число : степень узлов,
-О файл : имя файла, где вы храните сгенерированный граф.

Пример:

generator -t AD -n 200 -k 13 -o test.txt

генерирует график на 200 узлов, где средняя степень узла 13, и сохранит эту таблицу в файл test.txt.

Графики этого генератора не обязательно должны быть непрерывными.