Пупков К.А., Коньков В.Г. Интеллектуальные системы (1-е изд., 2001) (1245264), страница 26
Текст из файла (страница 26)
Эти методы можнотрактовать, как методы безусловного спуска, т.к. все изменения враспределении вершин графа алгоритма по процессорам ВС происходят толькопри уменьшении функционала J(R). Отмечается, что вследствие этого качествометодов сильно зависит от начального назначения.В [85] рассматривается семейство методов, основанных на построенииприоритетных списков вершин графов алгоритма и ВС. Предлагается трикритерия для вершин графа ГА и три - для ГС.
Списки формируются поубыванию (или возрастанию) одного из критериев, при равенстве критерия длянескольких вершин они упорядочиваются по второму критерию и т.д. Методработает следующим образом. Специальная процедура выбирает одну вершинув ГА и назначает ее на некоторый процессор. Пересчитываются динамическиекритерии (которые зависят от уже проведенного назначения) исоответствующим образом переупорядочиваются списки.
Первая вершина всписке вершин из ГА назначается на первый процессор в списке процессоров.Снова пересчитываются критерии и т.д. Метод работает пока есть еще неназначенные вершины в ГА. Различные комбинации введенных шестикритериев порождают большое число возможных методов, называемыхстратегиями. В работе проведено численное сравнение 12 стратегий, котороепоказало, что каждая из них может оказаться оптимальней других взависимости от типов графа алгоритма и графа ВС (рассмотрены такие графы,как деревья, решетки, гиперкубы).В [86] предлагается быстрый эвристический метод решения задачиназначения, в которой критерием оптимальности служит толькокоммуникационная нагрузка - второе слагаемое в J(R). Дополнительнопредполагается, что на каждый процессор назначается не более вершин из ГА.Метод состоит в преобразовании исходного графа алгоритма в граф, состоящийиз вершин.
Оно осуществляется через последовательное объединение вершин,связанных самым тяжелым ребром, в одну новую вершину, если для последнейне нарушается ограничение на нагрузку процессоров - число ейсоответствующих вершин из ГА не должно превышать n0. Все вершины графаалгоритма, соответствующие одной вершине из построенного таким образомграфа, назначаются на отдельный процессор.86В [87] описывается очень популярный в последнее время методрешения различных дискретных задач оптимизации - метод имитации отжига,являющийся модификацией известного алгоритма Метрополиса.
В [87]решается задача о разбиении графа на два подграфа с равным числом вершин ис минимальным числом ребер, соединяющих эти подграфы. Эта задачасоответствует задаче назначения с p = 2. Вершины графа трактуются какчастицы, совершающие случайные блуждания между этими подграфами впотенциальном силовом поле, роль потенциала которого играет функционалJ(R). Наиболее вероятное распределение частиц соответствует распределению сминимумом потенциала, и, следовательно, минимальному значениюфункционала J(R). Для поиска этого распределения предлагается следующийалгоритм.
Формируется начальное случайное распределение. На каждойитерации t = 1, 2, … в случайном порядке перебираются все вершины графа.Для каждой из них высчитывается приращение функционала DJ при переносеэтой вершины в другой подграф. Если оно отрицательно (функционалпонизился), то вершина переносится, если положительно, то переносится свероятностью exp(-DJ / J), где параметр J играет роль температуры в системечастиц. Имитация отжига заключается в постепенном стремлении температурык нулю.
Если осуществлять его достаточно медленно (как 1 / ln(t)), то всясистема частиц выходит не стационарное распределение, которое являетсяоптимальным. Отмечается, что важным преимуществом метода является егоспособность к получению решения с любой степенью точности.Обзор используемых методов поиска оптимального отображенияграфов алгоритмов на графы ВС с учетом информационного взаимодействия вВС показал, что большинство их к решению больших задач отображения (n >100, p > 10) не подходит из-за большой сложности этих методов. К тому же,точность многих приближенных методов часто сильно падает при увеличенииразмерности задачи. Как отмечается в ряде работ, единственно приемлемымспособом решения больших задач отображения является, по-видимому,использование именно стохастических подходов и алгоритмов.
В этом смысле,интересным подходом является использование метода имитации отжига,хорошо зарекомендовавшего себя при решении многих задач дискретнойоптимизации [87].873.3. Стохастический метод попарной оптимизации подграфов1.погрешностидляэтихдвухслучаев.Описание метода.Для приближенного решения задачи минимизации функционала J(R)был разработан эвристический рандомизированный алгоритм. Общая схемаметода следующая.Алгоритм А1:1. Выбираем случайное начальное разрезание R, вычисляем J = J(R);2. Выбираем пару подграфов с номерами i, j с вероятностьюпропорциональной связности этих подграфов (чем больше связность двухподграфов, тем больше вероятность выбора этой пары);3.
Случайно выбираем пару вершин l и m в этих подграфах (т.о. перебираютсявсе пары вершин в этих подграфах); меняем местами эти вершины, получаемновое разрезание R’, вычисляем J’ = J(R’);4. Если J’ > J, т.е. произошло увеличение функционала, то переходим к 3,иначе за R обозначаем R’ и переходим к 3;5.
Если зафиксирован выход функционала J(R) на стационарное решение, токонец алгоритма, иначе переходим на 2.Описанный алгоритм является итерационным. Внешние итерациисвязаны с попарным просмотром подграфов, а внутренние - с просмотромвершин в этих подграфах. Переход от разрезания к разрезанию происходит,если выполняется условие перехода 5.2.относительнойРис. 42. Зависимость времени работы алгоритмов А1 (1) и А3 (2) от размеровграфа сдваивания N, при p = N.Численное исследование алгоритма.На основе метода А1 была написана программа, с помощью которойбыло проведено численное исследование метода А1.
В качестве графовалгоритма исследовались, в основном, двоичные деревья с числом вершин наверхнем уровне N. В качестве ВС - полносвязные графы, имеющие p вершин.На рис. 42 построена зависимость времени работы программы T (в секундах) отN, при p = N, т.е.
при одновременном увеличении и размерности графа N, ичисла подграфов разрезания. Полученные зависимости позволяют сделатьвывод, что сложность алгоритма А1 есть 0(pN2).Исследование на точность метода проводилось для алгоритмовсдваивания с N = 8 при разрезании их на p = 4, 8 подграфов.
Было проведено по70 опытов для каждого случая. На рис. 43 изображена функция распределения fРис. 43. Функция распределения f относительной погрешности алгоритма А1при разрезании графа сдваивания с n = 15 на 1) p = 4; 2) p = 8 подграфов.88Проведенное исследование позволяет сделать следующие выводы.
Какминимум кубическая (по n и p) сложность метода не позволяет использовать егопри больших графах ГА и большом числе подграфов разрезания. Сходимостьметода к решению не является плохой (плоской), однако, оченьнеудовлетворительной является точность получаемых решений. Этотнедостаток, однако, может быть в некоторой степени сглажен за счетспециального выбора начального разрезания.3.Метод выбора начального разрезания.Алгоритм заканчивает работу, когда все вершины распределены поподграфам. Было проведено аналогичное исследование алгоритма А3 (метод А1с выбором начального разрезания А2) на сложность, сходимость и точность.Результаты исследования представлены на рис.
42, 44. Выигрыш по сравнениюс А1 очевиден. Уменьшилась сложность алгоритма. Улучшилась точностьметода. Зато, оказалась очень плоской зависимость функционала J поитерациям. Это объясняется тем, что алгоритм А2 в большинстве случаев сразуприводит к локальному минимуму.Хотя метод А3 и дает вполне удовлетворительные решения задачираспараллеливания для относительно небольших значений n p, его применениедля отображения графов алгоритмов большой размерности на большое числопроцессоров проблематично, в силу значительного возрастания времени работыметода и ухудшения точности получаемых решений.Рис. 44.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
