Пупков К.А., Коньков В.Г. Интеллектуальные системы (1-е изд., 2001) (1245264), страница 28

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

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

Кривые 2 и 3 соответствуют методунаискорейшего спуска для различных значений a и b - кривая 2 – a = 10, b = 10;кривая 3 – a = 20, b = 2.Применение стохастических методов к распараллеливанию базовыхалгоритмов линейной алгебры.Общая характеристика исследования.93Было проведено тестирование разработанных стохастических методовна распараллеливании некоторых базовых алгоритмов линейной алгебры [88].Все исследованные алгоритмы определялись двумя параметрами,которые задают некоторое разбиение на блоки матриц и векторов, участвующихв алгоритме.

Пусть N обозначает размер задачи, т.е. все матрицы имеют размерNxN, а вектора имеют длину N. Первый параметр nb определяет блочный размер(nbxnb) матриц и число векторных блоков в разбиении векторов. Второйпараметр mb = N/nb определяет размер самих блоков. Т.о. mb - это либо размерквадратных блоков (mbxmb) в разбиении матриц, либо длина векторных блоков.соответствуют перечисленным выше пяти методам.соответствует максимально возможному ускорению S(p) = p.ПрямаялинияИсследовались графы следующих алгоритмов:1.2.3.4.5.Блочный алгоритм скалярного умножения векторов;Блочный алгоритм умножения матрицы на вектор;LU - разложение блочной матрицы;Решение системы линейных уравнений с блочно-треугольной матрицей;Метод декомпозиции области решения трехдиагональнойсистемылинейных уравнений [88].Первые 4 метода являются блочными вариантами обычных методов, а впоследнем методе производится специальное (несколько отличное от блочного)разбиение векторов и матриц, приводящее к системе уравнений состреловидной матрицей, метод решения которой обладает достаточно большимпараллелизмом.В качестве графов ВС, на которые производилось распараллеливаниеэтих методов, были выбраны однородные полносвязные графы с весамивершин, равными 1.

Эти графы также определяются двумя параметрами числом процессоров p и временем передачи единицы информации .Анализ зависимости распараллеливания алгоритмов линейнойалгебры от параметров ВС.В настоящем пункте описываются результаты численного исследованияотображения графов алгоритмов линейной алгебры на полносвязныеоднородные графы ВС в зависимости от числа транспьютеров и скоростиработы каналов мультитранспьютерной ВС. Для всех вышеуказанных методовзафиксированы следующие параметры – nb = 0 и mb = 100.Результаты проведенного исследования отражены на рис. 46, 47.

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

Последним свойствомобладает и граф скалярного умножения векторов, однако он имеет в десять разменьше вершин, что приводит к более плохой балансировке загрузкипроцессоров, и следовательно, к снижению ускорения. Наихудшим ускорениемобладает метод решения блочно-треугольной системы линейных уравнений, т.к.граф этого метода имеет наименьшую среднюю степень параллелизма, чтоопять же приводит к очень плохой балансировке загрузки процессоров.94Нарис.51изображенызависимостидостигнутогоприраспараллеливании алгоритмов ускорения S от блочной размерности nb при mb =100, p = 6,  = 1.Рис.

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

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

51. Зависимость ускорения S от числа блоков nb для некоторых алгоритмовлинейной алгебры.Видно, что ускорение S в среднем возрастает при увеличении nb, т.к.при этом увеличивается число вершин в графе алгоритма и его степеньпараллелизма, что при фиксированном p4 ведет к лучшей балансировкепроцессоров. Хотя при увеличении nb растет и число обменов, однако, какследует из рисунка, этот рост в меньшей степени влияет на ускорение, чемувеличение числа вершин.

Немонотонность S(nb) для некоторых методовобъясняется небольшим количеством вершин в соответствующих графах.На рис.52 построены графики зависимости ускорения S от размеровблоков mb при nb = 8, p = 8, = 1. В данном случае, рост ускорения приувеличении mb объясняется уже уменьшением относительной доли времениобменов по сравнению со временем счета. Например, для LU - разложениямаксимальный вес вершин есть 0(mb3), в то время как максимальный вес дуг0(mb2). Следовательно, при увеличении mb доля обменов в общем временистремится к нулю.95Видно, что матрицы Q и F являются блочно-трехдиагональными. (159)~можно привести к виду Y  AY t , где матрица А является решением матричногоуравнения QA = F.

Это уравнение может быть решено с помощью метода четнонечетной редукции [88]. Т.о. общая схема алгоритма поиска одной собственнойфункции (при фиксированном параметре ) выглядит следующим образом.1.2.3.5.Составление матриц Q и F по формулам (159);Решение матричного уравнения QA = F методом четно-нечетной редукции;t = 0, выбор начального приближения Y0;~Умножение матрицы А на вектор Y t : Y  AY t ;~Нахождение нормы Y ;6.~ ~Определение вектора Y t 1  Y Y ;7.Если Y t 1  Y t > , то t = t+1 и переход на 4, иначе конец алгоритма.4.Рис. 52. Зависимость ускорения S от блочной размерности mb для некоторыхалгоритмов линейной алгебры.Распараллеливание метода обратной итерации поискасобственных функций.При решении некоторых задач в линейной алгебре возникает задачаопределения собственных чисел и соответствующих им собственных функций,операторов с блочно-трехдиагональной матрицей L.

Сложность задачиопределяется, как правило, плохой обусловленностью матрицы, когдамаксимальное и минимальное собственные числа отличаются на несколькопорядков. Для решения этой задачи используется метод обратной итерации.Итерационный процесс строится следующим образом~Y Y t~~ ~  LY  (1   ) LY t , Y t 1  Y Y(158)Известно, что при t   Yt стремится к собственной функции,отвечающей собственному значению, наиболее близкому к величине 2 / Приведем (158) к виду11~QY  FY t , где Q  I  L, F  I  (1   ) L (159)Для проведения исследования параметры метода - блочная размерностьnb матрицы L и размер ее блоков mb - были зафиксированы следующими – nb =10 и mb = 30.

Исследовалось распараллеливание алгоритма на следующиетопологии многопроцессорных ВС:1. полносвязная топология;2. гиперкуб;3. двумерный тор;4. двумерная квадратная решетка;5. кольцо;6. линейный массив процессоров.Результаты проведенного исследования отражены на рис.

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

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

Распараллеливание явного метода решения нелинейной динамическойсистемы1.Общая схема метода.уровне находятся вершины, соответствующие операциям по пересчету вектораu по формулам (161). Их веса равны (3N3, 3N3, 3N3, 3N3, 2N3, 2N3, 2N3). Каждаяиз дуг графа обозначает пересылку одного трехмерного массива, поэтому весвсех дуг равен N слов, и если положить, что 1 слово = 4 байта, то вес дуг равен64N Бт.Рассмотрим систему трехмерных уравнений магнитной гидродинамики,описывающих течение жидкости, способной проводить электрический ток [90].Система имеет следующий вид u div ( F )  0 t u( x, 0)   ( x )Здесь u   , Vx , V y , Vz , B x , B y , Bz(160)- вектор решения, тензор системы F,определяющий плотности потоков, имеет видVx 21 Vx    Bx2  B22 V V  B Bx yx y VxVz  Bx Bz0  (Vx By Vy Bx )  (Vx Bz Vz Bx )VyVzVxVy  Bx By12Vy2    By2  B2VyVz  By BzVx By Vy Bx0 (Vy Bz Vz By )VxVz  Bx Bz VyVz  By Bz 22 1 2Vz    Bz  B 2 Vx Bz Vz Bx (Vy Bz Vz By ) 0Из 21 элемента этого тензора только 12 являются различными.Явная разностная схема для выписанной системы имеет вид Pi1, j,k  Pi1, j,k Qi, j1,k  Qi, j1,k Ri, j, k1  Ri, j,k1 (161)ui j k  ui j k  2x2x2xгде P, Q, R - столбцы тензора F.На рис.54 изображен граф такой вычислительной модели на одномвременном шаге.

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

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