Пупков К.А., Коньков В.Г. - Интеллектуальные исследования (Современнаяя теория управления) (1072100), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

На рис. 46 построена зависимость E(t), которая демонстрирует способность метода выходить из локальных минимумов функционала J(R). В этом случае ГА = В(100, 1), p = 10. В момент t = 0 - ₀ =0, поэтому алгоритм достаточно быстро приводит систему в локальный минимум. В момент t = 50 полагается ₅₀ = J₅₀, после чего наблюдается выход из локального минимума.

Были проведены расчеты по определению сложности метода, которые показали, что время достижения методом заданной точности E имеет порядок 0(pn²).

Рис. 46. Сходимость ошибки Е, показывающая способность метода Монте-Карло выходить из локальных минимумов функционала J.

Рис. 47. Время достижения одинаковой точности алгоритмов 1) А3 и 2) Монте-Карло от p при n = 16p - 1.

На рис.47 отражены результаты сравнительного анализа предложенного алгоритма и алгоритма попарной оптимизации подграфов А3. Изображена зависимость времени работы алгоритмов от p при ГА = В(8p, 1). Кривая 1 соответствует времени работы алгоритма попарной оптимизации, а кривая 2 - времени работы алгоритма Монте-Карло по достижении точности достигнутой при реализации метода А3. Видно преимущество подхода, основанного на методе Монте-Карло, при решении больших задач распараллеливания.

1. Стохастический метод наискорейшего спуска

1. Описание метода.

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

1. Полагаем начальную температуру равной  = a.

2. Выбираем равновероятно начальное расположение вершин R и вычисляем его эффективность J = J(R).

3. На каждой итерации t случайным образом перебираем все частицы-вершины. Для каждой из вершин определяем вектор значений функционала J_i при переносе данной вершины во все подграфы. Случайным образом перемещаем вершину в другой подграф, при этом вероятность переноса вершины в i - ый подграф равна .

4. Понижаем температуру по закону  = 1 / (a + t / b).

5. Если зафиксирован выход системы части на стационарное значение функционала J, то конец алгоритма, иначе переход на 3.

При больших значениях температуры все переходы в системe частиц-вершин являются равновероятными. При уменьшении же температуры системы увеличивается вероятность перехода в подграф с максимальным уменьшением функционала J(R). При достаточно низких значениях температуры вероятность только одного перехода становится равной 1. Этот механизм гарантирует сходимость метода. Параметры a и b позволяют регулировать скорость сходимости метода (подобно значению начальной температуры в методе Монте-Карло).

Рис. 48. Сходимость функционала в методе Монте-Карло (1) и методе наискорейшего спуска (2, 3) при решении задачи с n = 27 и p = 8.

1. Реализация метода.

На основе метода была создана программа, с помощью которой было проведено численное исследование метода. Это исследование показало более высокую скорость сходимости, чем в методе Монте-Карло. На рис. 48 построены графики зависимости функционала J по итерациям алгоритма Монте-Карло и стохастического алгоритма наискорейшего спуска. Кривая 1 соответствует наиболее методу Монте-Карло в случае наиболее быстрого получения оптимального решения. Кривые 2 и 3 соответствуют методу наискорейшего спуска для различных значений a и b - кривая 2 – a = 10, b = 10; кривая 3 – a = 20, b = 2.

Применение стохастических методов к распараллеливанию базовых

алгоритмов линейной алгебры.

Общая характеристика исследования.

Было проведено тестирование разработанных стохастических методов на распараллеливании некоторых базовых алгоритмов линейной алгебры [88].

Все исследованные алгоритмы определялись двумя параметрами, которые задают некоторое разбиение на блоки матриц и векторов, участвующих в алгоритме. Пусть N обозначает размер задачи, т.е. все матрицы имеют размер NxN, а вектора имеют длину N. Первый параметр n_b определяет блочный размер (n_bxn_b) матриц и число векторных блоков в разбиении векторов. Второй параметр m_b = N/n_b определяет размер самих блоков. Т.о. m_b - это либо размер квадратных блоков (m_bxm_b) в разбиении матриц, либо длина векторных блоков.

Исследовались графы следующих алгоритмов:

1. Блочный алгоритм скалярного умножения векторов;

2. Блочный алгоритм умножения матрицы на вектор;

3. LU - разложение блочной матрицы;

4. Решение системы линейных уравнений с блочно-треугольной матрицей;

5. Метод декомпозиции области решения трехдиагональной системы линейных уравнений [88].

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

В качестве графов ВС, на которые производилось распараллеливание этих методов, были выбраны однородные полносвязные графы с весами вершин, равными 1. Эти графы также определяются двумя параметрами - числом процессоров p и временем передачи единицы информации .

Анализ зависимости распараллеливания алгоритмов линейной алгебры от параметров ВС.

В настоящем пункте описываются результаты численного исследования отображения графов алгоритмов линейной алгебры на полносвязные однородные графы ВС в зависимости от числа транспьютеров и скорости работы каналов мультитранспьютерной ВС. Для всех вышеуказанных методов зафиксированы следующие параметры – n_b = 0 и m_b = 100.

Результаты проведенного исследования отражены на рис. 46, 47. На рис. 49 построены графики зависимости достигнутого при распараллеливании ускорения S от числа процессоров p, при  = 1. Пять изображенных кривых соответствуют перечисленным выше пяти методам. Прямая линия соответствует максимально возможному ускорению S(p) = p.

Рис. 49. Зависимость ускорения S от числа процессоров p для различных алгоритмов линейной алгебры.

Следует отметить, что поведение этих кривых - линейный рост, выход на плоский максимум, и затем некоторое снижение ускорения - совпадает с поведением экспериментально полученных зависимостей, описанным в ряде работ [89]. Наилучшим ускорением обладает алгоритм умножения матрицы на вектор, что объясняется тем, что, во-первых, граф данного метода состоит из 10 (в данном случае) независимых подграфов, во-вторых, этот граф имеет наименьшее число дуг в расчете на одну вершину. Последним свойством обладает и граф скалярного умножения векторов, однако он имеет в десять раз меньше вершин, что приводит к более плохой балансировке загрузки процессоров, и следовательно, к снижению ускорения. Наихудшим ускорением обладает метод решения блочно-треугольной системы линейных уравнений, т.к. граф этого метода имеет наименьшую среднюю степень параллелизма, что опять же приводит к очень плохой балансировке загрузки процессоров.

Рис. 50. Зависимость ускорения S от времени передачи единицы информации по каналам в ВС при распараллеливании некоторых алгоритмов линейной алгебры.

На рис.50 построены графики зависимости ускорения S от времени  передачи единицы информации по каналам связи в ВС при p = 8. Вполне естественно, что с ростом tau ускорение стремится к 1, т.к. в общем времени выполнения алгоритма возрастает доля обменов по сравнению со временем вычислений. Вместе с тем, для разных методов ускорение падает по-разному. Наилучший результат, опять же, наблюдается для метода умножения матрицы на вектор. Наиболее чувствительны к этому параметру оказались методы LU - разложения и декомпозиции области решения трехдиагональных систем. Величина ускорения S при   0 обусловлена только балансировкой вычислительной нагрузки процессоров, т.к. соответствует ситуации, когда время на выполнение обменов стремится к 0.

Зависимость распараллеливания алгоритмов линейной алгебры

от параметров самих алгоритмов.

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

На рис.51 изображены зависимости достигнутого при распараллеливании алгоритмов ускорения S от блочной размерности n_b при m_b = 100, p = 6,  = 1.

Рис. 51. Зависимость ускорения S от числа блоков n_b для некоторых алгоритмов линейной алгебры.

Видно, что ускорение S в среднем возрастает при увеличении n_b, т.к. при этом увеличивается число вершин в графе алгоритма и его степень параллелизма, что при фиксированном p4 ведет к лучшей балансировке процессоров. Хотя при увеличении n_b растет и число обменов, однако, как следует из рисунка, этот рост в меньшей степени влияет на ускорение, чем увеличение числа вершин. Немонотонность S(n_b) для некоторых методов объясняется небольшим количеством вершин в соответствующих графах.

На рис.52 построены графики зависимости ускорения S от размеров блоков m_b при n_b = 8, p = 8, = 1. В данном случае, рост ускорения при увеличении mb объясняется уже уменьшением относительной доли времени обменов по сравнению со временем счета. Например, для LU - разложения максимальный вес вершин есть 0(m_b³), в то время как максимальный вес дуг 0(m_b²). Следовательно, при увеличении m_b доля обменов в общем времени стремится к нулю.

Рис. 52. Зависимость ускорения S от блочной размерности m_b для некоторых алгоритмов линейной алгебры.

Распараллеливание метода обратной итерации поиска

собственных функций.

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

Итерационный процесс строится следующим образом

(158)

Известно, что при t   Y_t стремится к собственной функции, отвечающей собственному значению, наиболее близкому к величине 2 / 

Приведем (158) к виду

(159)

Видно, что матрицы Q и F являются блочно-трехдиагональными. (159) можно привести к виду , где матрица А является решением матричного уравнения QA = F. Это уравнение может быть решено с помощью метода четно-нечетной редукции [88]. Т.о. общая схема алгоритма поиска одной собственной функции (при фиксированном параметре ) выглядит следующим образом.

1. Составление матриц Q и F по формулам (159);

2. Решение матричного уравнения QA = F методом четно-нечетной редукции;

3. t = 0, выбор начального приближения Y⁰;

4. Умножение матрицы А на вектор ;

5. Нахождение нормы ;

6. Определение вектора ;

7. Если > , то t = t+1 и переход на 4, иначе конец алгоритма.

Для проведения исследования параметры метода - блочная размерность n_b матрицы L и размер ее блоков m_b - были зафиксированы следующими – n_b = 10 и m_b = 30. Исследовалось распараллеливание алгоритма на следующие топологии многопроцессорных ВС:

1. полносвязная топология;

2. гиперкуб;

3. двумерный тор;

4. двумерная квадратная решетка;

5. кольцо;

6. линейный массив процессоров.

Результаты проведенного исследования отражены на рис. 53, на котором построена зависимость ускорения S от числа процессоров p для перечисленных выше топологий. Прямая S(p) = p показывает максимально возможное ускорение. В общем, изображенные на рисунке кривые соответствуют общепринятой иерархии рассмотренных топологий [88]. Наилучшим ускорением обладает архитектура с полносвязной топологией, т.к. при одинаковом p все остальные топологии являются ее некоторыми подмножествами. Однако, на практике ВС с подобной топологией практически не используются, т.к. соединение большого числа процессоров каждый с каждым сопряжено с большими техническими трудностями. Из реально используемых в современных ВС топологий наилучшее ускорение для анализируемой задачи соответствует гиперкубическая топология. Затем идут двухмерный тор и решетка, причем последняя проигрывает тору ха счет наличия у того дополнительных связей, замыкающих границы решетки и делающих максимальное расстояние между двумя процессорами в два раза меньшим. Замыкают список кольцевой и линейный массивы. Последняя топология характерна тем, что имеет максимальную среду всех анализируемых топологий длину (p - 1) пути между самыми удаленными процессорами, что и делает ее наименее подходящей для выполнения анализируемого алгоритма.

Характеристики

Список файлов книги