Содержание

Введение. 3

1. Параллельные алгоритмы на графах. 4

2. Фрактальные и предфрактальные графы.. 5

3. Параллельный алгоритм поиска ОДМВ. 9

4. Параллельный алгоритм поиска совершенного паросочетания. 12

5. Параллельный алгоритм поиска эйлеровой цепи. 14

6. Параллельный алгоритм поиска гамильтонова цикла. 17

Заключение. 19

Литература. 19

Введение

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

Обычно выделяют два вида параллелизма: крупноблочный [1] и мелкозернистый [2, 3]. Основное различие между этими двумя видами параллелизма заключается в отношении числа последовательно выполняемых команд к числу межпроцессорных обменов. Алгоритмы, основанные на крупноблочном параллелизме, выполняют (параллельно) небольшое число сложных последовательных вычислений с редкими обменами промежуточными результатами. Мелкозернистый параллелизм подразумевает большое количество параллельно выполняемых простых, часто одинаковых, вычислений, обмен результатами при этом происходит на каждом шаге [3]. Достоинства и недостатки есть у обоих видов параллелизма, подтверждают это и работы [3,4]. Параллельные вычислительные системы принято называть многопроцессорными или суперЭВМ [4].

В [4] предложена классификация наиболее распространенных многопроцессорных систем:

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

─      Массивно-параллельные компьютеры с распределенной памятью, представляют собой соединение микропроцессоров с помощью сетевого оборудования.

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

─      Кластерные компьютеры. Это класс, представляющий собой комбинацию предыдущих трех.

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

Наиболее распространенным методом распараллеливания алгоритмов является метод, описанный в книге [5]. Широко используется этот метод и в распараллеливании алгоритмов решения теоретико-графовыех задач. О некоторых их них рассказано в следующем параграфе.

В настоящей работе проведено исследование, посвященное распараллеливанию алгоритмов на предфрактальных графах [6]. Предфрактальные графы – класс графов, обладающий рядом отличительных топологических и метрических свойств, с использованием которых и проводится распараллеливание алгоритмов.

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

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

1. Параллельные алгоритмы на графах

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

Большинство известных параллельных графовых алгоритмов построено для PRAM (Parallel Random Access Machine) – модели параллельной вычислительной системы. В представленной раннее классификации, PRAM относится к компьютерам с общей памятью. Во избежание конфликтных ситуаций при одновременном обращении нескольких процессоров к общей памяти в PRAM заданы следующие правила:

─      конкурентное чтение / конкурентная запись (CRCW);

─      конкурентное чтение / исключительная запись (CREW);

─      исключительное чтение / конкурентная запись (ERCW);

─      исключительное чтение / исключительная запись (EREW).

 С более подробным описанием PRAM модели можно ознакомиться, например, в [8] или [9].

Простейшие параллельные алгоритмы для графа  с  вершинами и  ребрами можно найти в переводном учебнике [10].

В [11] предлагается эффективный алгоритм нахождения связных компонент неориентированного графа . В этом алгоритме используется  процессоров CREW PRAM, а сам алгоритм исполняется за время . В -[12] разработан параллельный алгоритм поиска всех пар кратчайших путей, где на модели CRCW PRAM достигается временная сложность , используя при этом  процессоров. Для проверки того является ли данное остовное дерево минимальным, разработан параллельный алгоритм [13] на EREW PRAM модели. Алгоритм исполняется за время  и использует  процессоров. Для графа, степень каждой вершины которого , существует алгоритм [14] вершинной раскраски в  цветов на EREW PRAM (допуская при этом, что граф не содержит -клик). Время выполнения алгоритма на  процессорах равно . Для обновления остовного дерева минимального веса, при одновременном добавлении к исходному графу  новых вершин, используется алгоритм [15], время выполнения которого . Алгоритм реализуется на EREW PRAM с  процессорами. В [16] описан параллельный алгоритм поиска максимальных ациклических множеств. Алгоритм исполняется за  время на  процессорах EREW PRAM. В работе [17] предлагается эффективное выполнение алгоритма Эдмондса для нахождения оптимального ветвления графа на STAR машине. Время исполнения алгоритма – , а число используемых процессоров – . STAR машина основана на модели параллельной машины типа SIMD с вертикальной обработкой информации [5].

2. Фрактальные и предфрактальные графы

Термином затравка условимся называть какой-либо связный граф . Для определения фрактального (предфрактального) графа [18] нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем. В данном графе  у намеченной для замещения вершины  выделяется множество , , смежных ей вершин. Далее из графа  удаляется вершина  и все инцидентные ей ребра. Затем каждая вершина , , соединяется ребром с одной из вершин затравки . Вершины соединяются произвольно (случайным образом) или по определенному правилу, при необходимости.

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

Использование операции ЗВЗ в процессе порождения предфрактального графа , для элементов , , его траектории позволяет ввести отображение  или , а в общем виде

, .                                                                 (1)

В выражении (1) множество  - образ множества , а множество  - прообраз множества .

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

Если из предфрактального графа , порожденного -вершинной затравкой , последовательно удалить все старые ребра (ребра ранга , ), то исходный граф распадется на множество связных компонент , каждая из которых изоморфна [19] затравке . Множество компонент  будем называть блоками первого ранга. Аналогично, при удалении из предфрактального графа  всех старых ребер рангов , получим множество блоков  второго ранга. Обобщая, скажем, что при удалении из предфрактального графа  всех ребер рангов , получим множество , , блоком -го ранга, где  -порядковый номер блока. Блоки  первого ранга также будем называть подграф-затравками  предфрактального графа .Очевидно, что всякий блок , , является предфрактальным графом , порожденным затравкой .

Уточним для отображения  в формуле (1) ряд подробностей. Для любой вершины , , предфрактального графа , , из траектории графа , справедливо

,                                                                                      (2)

, где , .

Аналогично,

,                                                                                   (3)

, , .

Два блока предфрактального графа назовем смежными, если существует ребро, вершины которого принадлежат различным блокам. Не требует доказательства тот факт, что блоки предфрактального графа смежны тогда и только тогда, когда смежны их прообразы из (2).

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

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

На рис. 1 изображена траектория предфрактального графа , порожденного затравкой  - полным 4-вершинным графом (см. рис. 1 А). Самыми “жирными” линиями нарисованы ребра подграф-затравки .

Линиями средней “жирности” нарисованы ребра подграф-затравок , ,  и . И наконец, тонкими линиями (см. рис. 1 В) нарисованы новые ребра предфрактального графа , которые образуют подграф-затравки , .

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

3. Параллельный алгоритм поиска ОДМВ

Параллельный алгоритм  осуществляет поиск остовного дерева минимального веса (ОДМВ) [19]  на взвешенном предфрактальном графе . Алгоритм использует k процессоров . Назначим каждый процессор одной из подграф-затравок , , , предфрактального графа , тогда число используемых процессоров равно .

Суть работы алгоритма заключается в следующем. Каждая подграф-затравка  рассматривается как отдельно взятый граф. При этом каждый из  процессоров параллельно независимо друг от друга находит ОДМВ на своей подграф-затравке . Поиск ОДМВ отдельно взятой подграф-затравки осуществляется алгоритмом Прима [20]. Алгоритм Прима используется в алгоритме  в виде процедуры, по мере необходимости. Нахождения ОДМВ всех подграф-затравок , позволяет построить ОДМВ предфрактального графа .

Каждое ребро предфрактального графа имеет свой “уникальный” номер, однозначно определяющий ребро во всей траектории. Таким образом, выделение ОДМВ на подграф-затравке  будет соответствует выделению множества ребер на предфрактальном графе .

Использование  процессоров, равное числу подграф-затравок позволяет достичь, как это будет показано далее, максимальной эффективности алгоритма .

Для обоснования алгоритма  будем использовать

Утверждение 1. Всякий предфрактальный граф  можно представить в виде множества подграф-затравок , соединенных старыми ребрами разных рангов. А именно, старые ребра -го ранга объединяют множество подграф-затравок в множество блоков  второго ранга, их в свою очередь, старые ребра -го ранга объединяют в множество блоков  третьего ранга и т.д. Окончательно, старые ребра первого ранга объединяют множество  блоков -го ранга в связный предфрактальный граф .

Теорема 1. Для предфрактального графа  всякий его связный остовный подграф  удовлетворяет двум условиям:

1. В множество ребер  входит хотя бы одно ребро каждого ранга.

2. Старые ребра  ранга , , имеющие общую вершину-прообраз, на графе  из траектории, образуют связный подграф.

Доказательство. Первая часть теоремы целиком вытекает из утверждения 1. Действительно, если на подграфе  будут отсутствовать все ребра какого-либо ранга, то он не будет связным. Вторую часть теоремы докажем от противного. Предположим, что некоторое множество ребер , имеющих общую вершину-прообраз не образует на предфрактальном графе , , связный подграф. Это значит, что среди образов концов ребер  на графе  найдутся такие, что ни одна из цепей их соединяющих не войдет в остовый подграф , что противоречит условию связности этого подграфа. ◄[1]

Теорема 2. Параллельный алгоритм  строит на предфрактальном графе  ОДМВ .

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

Далее ОДМВ  выделенные на подграф-затравках , в соответствии с утверждением 1, образуют  связных компонент. Каждая компонента будет представлять собой ОДМВ блоков . Продолжая данную линию рассуждений получим, что ОДМВ выделенные на подграф-затравках  в совокупности с раннее найденными ОДМВ образуют  связных компонент. Каждая компонента будет представлять ОДМВ блока . И, наконец, ОДМВ подграф-затравки  связывает  компонент в одну связную компоненту. Полученный связный остовный подграф, в силу добавления деревьев минимального веса, будет представлять ОДМВ предфрактального графа . ◄

Теорема 3. Время исполнения алгоритма  на предфрактальном графе ,  при использовании  процессоров, равно .

Доказательство. Основой алгоритма является шаг 2, с ним и связано затрата времени на исполнение. Остальные шаги производят простые операции и инициализацию переменных. Алгоритм  выполняет шаг 2 параллельно, каждым из  процессоров. Для выполнения шага 2 потребуется  времени (столько времени [20] требует процедура Prim для обработки подграф-затравки). Так как это верхняя оценка в наихудшем случае, тогда будем считать что все  процессоров закончат свою работу – выполнение шага 2 – одновременно, за время . Тогда алгоритм   исполняется за время . ◄

Отметим, что  определяет размерность задачи поиска ОДМВ на подграф-затравке, в то время как размерность задачи поиска ОДМВ на предфрактальном графе  равна , . Таким образом время исполнения алгоритма  равно времени затрачиваемому на поиск ОДМВ на подграф-затравке.

Время исполнения последовательного алгоритма Прима на предфрактальном графе ,  равно . Сравнив последовательный алгоритм Прима с параллельным алгоритмом , получаем что время исполнения алгоритма  меньше на порядок: .

Следствие 3.1. Ускорение параллельного алгоритма  на предфрактальном графе ,  при использовании  процессоров, , от последовательного алгоритма Прима равно .

Теорема 4. Вычислительная сложность алгоритма  на предфрактальном графе ,  равна .

Доказательство. Алгоритм  представляет собой, по существу многократное выполнение шага 2. Шаг 2 потребует выполнения  операций на каждой подграф-затравке (столько операций требует процедура Прима). В сумме будет выполнено  операций, . ◄

Тогда, . Отсюда вычислительная сложность алгоритма  равна .

Вычислительная сложность алгоритма Прима равна . Сравнив ее с вычислительной сложностью алгоритма , получаем: .

Следствие 4.1. Вычислительная сложность алгоритма  меньше вычислительной сложности алгоритма Прима в  раз.

4. Параллельный алгоритм поиска совершенного паросочетания

Алгоритм  производит поиск совершенного паросочетания [19] на заданном предфрактальном графе. Рассмотрим взвешенный предфрактальный граф  и траекторию , . Алгоритм использует k процессоров . Где  может варьировать в промежутке от одного до . Назначим каждый процессор одной из подграф-затравок , .

Теорема 5. Предфрактальный граф , порожденный затравкой , имеет совершенное паросочетание, если затравка  имеет совершенное паросочетание.

Основная идея алгоритма заключается в том, что каждая подграф-затравка рассматривается как отдельно взятый граф. При этом каждый из  процессоров параллельно независимо друг от друга находит совершенные паросочетания на своей подграф-затравке . Поиск совершенного паросочетания подграф-затравки осуществляется с помощью алгоритма Эдмондса [19]. Алгоритм Эдмондса оформлен в виде процедуры и используется по мере необходимости. В результате нахождения совершенных паросочетаний всех подграф-затравок , получаем совершенное паросочетание предфрактального графа . ◄

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

Теорема 6. Параллельный алгоритм  строит на предфрактальном графе  совершенное паросочетание .

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

Теорема 7. Время исполнения алгоритма  на предфрактальном графе ,  при использовании  процессоров, равно .

Доказательство. Основой алгоритма является шаг 2, с ним и связано затрата времени на исполнение. Остальные шаги производят простые операции и инициализацию переменных. Алгоритм  выполняет шаг 2 параллельно, каждым из  процессоров. Для выполнения шага 2 потребуется  времени (столько времени [20] требует процедура Edmonds для обработки подграф-затравки). Так как это верхняя оценка в наихудшем случае, тогда будем считать что все  процессоров закончат свою работу – выполнение шага 2 – одновременно, за время . Тогда алгоритм   исполняется за время . ◄

Время исполнения последовательного алгоритма Эдмондса на предфрактальном графе ,  равно . Сравнив последовательный алгоритм Эдмондса с параллельным алгоритмом , получаем что время исполнения алгоритма  меньше на два порядка: .

Следствие 7.1. Ускорение параллельного алгоритма  на предфрактальном графе ,  при использовании  процессоров, , от последовательного алгоритма Эдмондса равно .

Теорема 8. Вычислительная сложность алгоритма  на предфрактальном графе ,  равна .

Доказательство. Алгоритм  представляет собой, по существу многократное выполнение шага 2. Шаг 2 потребует выполнения  операций на каждой подграф-затравке (столько операций требует процедура Edmonds). В сумме будет выполнено  операций, . ◄

Тогда, . Отсюда, вычислительная сложность алгоритма  равна .

Вычислительная сложность алгоритма Эдмондса равна . Сравнив ее с вычислительной сложностью алгоритма , получаем: .

Следствие 8.1. Вычислительная сложность алгоритма  меньше вычислительной сложности алгоритма Эдмондса в  раз.

5. Параллельный алгоритм поиска эйлеровой цепи

Для поиска эйлеровой цепи [19] предфрактального графа предложим алгоритм . Рассмотрим предфрактальный граф  и его траекторию , . Алгоритм использует k процессоров .  Число процессоров не обязано соответствовать количеству входных записей, а может варьировать в промежутке от одного до . Назначим каждый процессор одной из подграф-затравок , , .

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

1. Смежность старых ребер предфрактального графа  сохраняется.

2. На затравке  существует эйлерова цепь.

Таким образом, будем предполагать, что алгоритм требует выполнения условий утверждения 2.

Основная идея алгоритма заключается в следующем. Каждая подграф-затравка  рассматривается как отдельно взятый граф. При этом каждый из  процессоров параллельно независимо друг от друга находит эйлерову цепь на своей подграф-затравке . Поиск эйлеровой цепи отдельно взятой подграф-затравки осуществляется алгоритмом Эйлера [20]. Алгоритм Эйлера используется в алгоритме  в виде процедуры по мере необходимости. В результате нахождения эйлеровых цепей всех подграф-затравок , получаем эйлерову цепь предфрактального графа .

Использование  процессоров, равное числу подграф-затравок позволяет достичь максимальной эффективности алгоритма .

Теорема 9. Параллельный алгоритм  строит на предфрактальном графе  эйлерову цепь .

Доказательство. По определению, эйлерова цепь покрывает все ребра графа по одному разу, при этом любая вершина графа может состоять в цепи сколь угодно раз. Эйлерова цепь также представляет собой замкнутую цепь. На шаге 2 алгоритма  найдены  эйлеровых цепей . Таким образом на подграф-затравке  найдена эйлерова цепь . Так как смежность старых ребер предфрактального графа  сохраняется, к эйлеровой цепи  добавляются цепи , выделенные на подграф-затравках . В результате получаем эйлерову цепь . Продолжая по данному принципу добавлять эйлеровы цепи подграф-затравок , в итоге получим эйлерову цепь предфрактального графа . ◄

Теорема 10. Время исполнения алгоритма  на предфрактальном графе ,  при использовании  процессоров, равно .

Доказательство. Основой алгоритма является шаг 2, с ним и связано затрата времени на исполнение. Остальные шаги производят простые операции и инициализацию переменных. Алгоритм  выполняет шаг 2 параллельно, каждым из  процессоров. Для выполнения шага 2 потребуется  времени (столько времени [20] требует процедура Eiler для обработки подграф-затравки). Так как это верхняя оценка в наихудшем случае, тогда будем считать что все  процессоров закончат свою работу – выполнение шага 2 – одновременно, за время . Тогда алгоритм   исполняется за время . ◄

Отметим, что  определяет размерность задачи поиска эйлеровой цепи на подграф-затравке, в то время как размерность задачи поиска эйлеровой цепи на предфрактальном графе  равна , . Таким образом время исполнения алгоритма  равно времени затрачиваемому на поиск эйлеровой цепи на подграф-затравке.

Время исполнения последовательного алгоритма поиска эйлеровой цепи на предфрактальном графе ,  равно . Сравнив последовательный алгоритм Эйлера с параллельным алгоритмом , получаем, что время исполнения алгоритма  меньше на порядок: .

Следствие 10.1. Ускорение параллельного алгоритма  на предфрактальном графе ,  при использовании  процессоров, , от последовательного алгоритма Эйлера равно .

Теорема 11. Вычислительная сложность алгоритма  на предфрактальном графе ,  равна .

Доказательство. Алгоритм  представляет собой, по существу многократное выполнение шага 2. Шаг 2 потребует выполнения  операций на каждой подграф-затравке (столько операций требует процедура Eiler). В сумме будет выполнено  операций, . ◄

Тогда, . Вычислительная сложность алгоритма  равна .

Следствие 11.1. Вычислительная сложность алгоритма  равна вычислительной сложности алгоритма Эйлера.

6. Параллельный алгоритм поиска гамильтонова цикла

Алгоритм  производит поиск гамильтонова цикла [19] на заданном предфрактальном графе. Опишем принцип работы алгоритма . Для этого рассмотрим предфрактальный граф  и траекторию , . Алгоритм использует k процессоров . Где  может варьировать в промежутке от одного до .

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

1. Смежность старых ребер предфрактального графа  не сохраняется.

2. На затравке  существует гамильтонов цикл.

3. Между любой парой вершин затравки  существует гамильтонова цепь.

Таким образом, будем предполагать, что алгоритм требует выполнения условий утверждения 3.

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

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

Использование  процессоров, равное числу подграф-затравок  позволяет достичь максимальной эффективности алгоритма .

Теорема 12. Параллельный алгоритм  строит на предфрактальном графе  гамильтонов цикл .

Доказательство. Гамильтонов цикл покрывает все вершины графа строго по одному разу, а покрытие ребер графа определяется вершинами цикла. На шаге 1 алгоритм  производит поиск гамильтонова цикла на подграф-затравке . Затем осуществляется поиск гамильтоновых цепей на подграф-затравках . Поиск проводится между двумя вершинами подграф-затравки , которым инцидентны два старых ребра 1-го ранга, входящих в гамильтонов цикл подграф-затравки . Более простыми словами, на подграф-затравке  находится гамильтонов цикл, а затем вместо вершин вставляются гамильтоновы цепи соответствующих подграф-затравок . Таким образом, получаем гамильтонов цикл предфрактального графа . Продолжая по данному принципу добавлять гамильтоновы цепи подграф-затравок , в итоге получим гамильтонов цикл предфрактального графа . Так как покрыты все вершины предфрактального графа , тогда найденный гамильтонов цикл является искомым. ◄

Заключение

В выполненной работе можно выделить несколько важных аспектов.

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

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

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

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

Литература

1.      Бандман О.Л. Методы параллельного микропрограммирования. - Новосибирск: Наука, 1981.

2.      Горбунова Е.О. Формально-кинетическая модель бесструктурного мелкозернистого параллелизма // Сибирский журнал вычислительной математики. 1999. Т. 2. № 3. С. 239-256.

3.      Бандман О.Л. Мелкозернистый параллелизм в вычислительной математике // Программирование. 2001. №4. С. 5-20.

4.      Бочаров Н.В. Технологии и техника параллельного программирования // Программирование. 2003. №1. С. 5-23.

5.      Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.

6.      Кочкаров А.А., Кочкаров Р.А. Предфрактальные графы в проектировании и анализе сложных структур. Препринт ИПМ им. М.В. Келдыша РАН, №10, 2003.

7.      Кузюрин Н.Н. Параллельный алгоритм для задачи о балансировке множеств. // Дискретная математика. 1991. Т.3. В.4. С. 153-158.

8.      Bader D.A., Illendula A.K., Moret B.M.E., Weisse-Bernstein N.R. Using PRAM algorithms on a uniform-memory-access shared-memory architecture. WAE 2001. LNCS 2141. 2001. P. 129-144.

9.      Agbaria A., Ben-Asher Y., Newman I. Communication–processor tradeoffs in a limited resources PRAM. Algorithmica. 2002. № 34. P. 276–297.

10.  Макконелл Дж. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002.

11.  Metaxas P. Parallel Algorithms for Graph Problems. PhD dissertation, Dartmouth College, 1991.

12.  Han Y., Pan V.Y., Reif J.H. Efficient parallel algorithms for computing all pair shortest paths in directed graphs. Algorithmica. 1997. № 17.  P. 399–415.

13.  King V., Poon Ch.K., Ramachandran V., Sinha S. An optimal EREW PRAM algorithm for minimum spanning tree verification. Information Processing Letters. 1997. № 62. P. 153-159.

14.  Sajith G., Saxena S. Optimal parallel algorithm for Brook's colouring bounded degree graphs in logarithmic time on EREW PRAM. Discrete Applied Mathimatics. 1996. № 64. P. 249-265.

15.  Johnson D.B., Metaxas P. Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree. Algorithmica. 1996. № 16. P.633–648.

16.  Chen Z.-Z., He X. Parallel algorithms for maximal acyclic sets. Algorithmica. 1997. № 19. P. 354-368.

17.  Непомнящая А.Ш. Представление алгоритма Эдмондса для нахождения оптимального ветвления графа на ассоциативном параллельном процессоре // Программирование. 2001. №4. С. 43-52.

18.  Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. - Нижний Архыз: РАН САО, 1998.

19.  Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990.

20.  Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. - Ижевск: НИЦ "РХД", 2001.