В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 7
Текст из файла (страница 7)
22 2. Схемы параллельных алгоритмов задач 2.4. Параллельные алгоритмы решения систем линейных алгебраических уравнений методом Гаусса Требуется найти решение системы линейных алгебраических уравнений; амх1+ а1зхз +... + аг„х„= 1ы аз1хз + аззхз + ° . ° + азнхн лз1 а„,х1+ а„,ха+... + а„„х„= 1„. Метод Гаусса основан на последовательном исключении неизвестных. Здесь рассматриваются два алгоритма решения СЛАУ методом Гаусса.
Они связаны с разными способами представления данных (матрицы коэффициентов и правых частей) в распределенной памяти мультикомпьютера. 2.4.1. Первый алгоритм решения СЛАУ' методом Гаусса В алгоритме, представленном здесь, исходная матрица коэффициентов А и вектор правых частей Р разрезаны горизонтальными полосами, как показано на рис. 2.11. Каждая полоса загружается в соответствующий компьютер: нулевая полоса — в нулевой компьютер, первая — в первый компьютер и т.д., последняя полоса — в р1 компьютер, р1 Рис.
2.11. Разрезание данных для параллельного алгоритма 1 решения СЛАУ методом Гаусса При прямом ходе матрица приводится к треугольному виду последовательно по компьютерам. Вначале к треугольному виду приводятся строки в нулевом компьютере, при этом нулевой компьютер последовательно, строка за строкой, передает свои сроки остальным компьютерам, начиная с первого. Затем к треугольному виду приводятся строки в первом компьютере, передавая свои строки остальным компьютерам, начиная со второго, т.
е. компьютерам с большими номерами, и т. д. Процесс деления строк на коэффициенты при х; не требует информации от других компьютеров. После прямого хода полосы матрицы А в каждом узле будут иметь вид 1рис. 2.12) Рнс. 2.12. Вид полос после прямого хода в алгоритме 1 решения СЛАУ метсдом Гаусса.
Пример приведен для четырех узлов, 8 — вешвственныв числа Аналогично, последовательно по компьютерам, начиная с последнего, по номеру компьютера осуществляется обратный ход. 84, Па авввлвнмв алев ингам вшвния сисгпвд линвднесе «ввеб аичвснии авнвнип... 23 Особенностью этого алгоритма является то, что как при прямом, так и при обратном ходе, компьютеры, завершившие свою часть работы, переходят в состокние ожидания, пока не завершат эту работу другие компьютеры. Таким образом, вычислительная нагрузка распрепедяется по компьютерам неравномерно, не смотря па то, что данные изначельно распределяются по компьютерам прибдизитедьио одинаково, Простои компьютеров значительно ум6пьшВются при распределении матрицы циклич6скими горизонтальными подо" сами. Этот метод представдеи в п.
2.4,2. 2.4.2. Второй алгоритм решения СЛАУ методом Гаусса В алгоритме, представленном здесь, исходная матрица коэффициентов распредедяется цо компьютерам циклическими горизонтальными полосами с шириной поносы в одну строку, как показано ниже на рис. 2.13. Первая строка матрицы помещается в компьютер О, вторая строка — в компьютер 1 и т,д,, Рг - 1-Я стРока - в Узел Рг (где Рг — количество Умов в системе). Затем Рг-Я стРока снова помещается в узел О, рг+1-я строка- в узел 1 и т,д.
Рис. 2,13. Разрезание данная для параллельного алгоритма 2 решении СЛАУ метсдом Гаусса При таком распределении данных, соответствующим этому распределению должен быть и алгоритм. Строку, которая вычитается из всех остяльных строк (после предварительного деления на нужные коэффициенты), назовем текущей строкой. Алгоритм прямого хада заключается в следующем, Сначала текущей строкой является строка с индексом 0 в компьютере О, затем строка с индексом 0 в компьютере 1 (здесь не нужно путать общую нумерацию строк во всей матрице и индексацию строк в каждом компьютере, в каждом компьют6р6 индексация строк в мессине начинается с пуни) и т.
д., и НВкоп6Ц, строка с индексом О в последнем по номеру компьютере. После чего цикл по компьютерам повторяется и текущей строкой становится строка с индексом 1 в компьютере О, затем строка с индексом 1 в компьютере 1 и т.д. Посла прямого хода полосы матрицы в каждом компьютере будут иметь вид, показанный на рис, 2.14, Пример приведен ддя четырех узлов; 3 — вещественные числа. Рмс, 2.14. Вид полос после прямого хола в алгоритме 2 решения СЛАУ методом Гаусса Аналогично, поспедоиатепьио по узлам, начиная с последнего но номеру компьютера, жушестнляется обратный ход, л'. Схемы параллельных алгоритамов задач Особенностью этого алгоритма является то, что как при прямом, так и при обратном ходе компьютеры более равномерно загружены, чем в первом методе.
Значит и вычислительная нагрузка распределяется по компьютерам более равномерно, чем в первом методе. Например, нулевой компьютер, завершив обработку своих строк при прямом ходе, ожидает пока другие компьютеры обработают только по одной, оставшейся у них не обработанной строке, а не полностью обработают полосы, как в первом алгоритме.
Сравним второй алгоритм с первым. При более равномерной загрузке компьютеров при вычислении одного алгоритма по сравнению с другим алгоритмом следует предположить и большую эффективность алгоритма с более равномерной загрузкой компьютеров. Загрузка компьютеров во втором алгоритме является более равномерной. Но большая его эффективность, по сравнению с первым, может проявиться только на исходных матрицах большого размера (например, начиная с исходных матриц 400 х 400 и более, но это зависит от конкретной системы).
Это обстоятельство связано с тем, что в первом методе в процессе вычислений активных компьютеров становится все меньше, а значит и уменьшается количество пересылок своих строк другим компьютерам. С уменьшением числа активных компьютеров будет уменьшаться и общее время, затрачиваемое на пересылку строк в активные компьютеры. И это частично компенсирует неравномерность вычислительной загрузки компьютеров. Во втором методе компьютеры активны в течение всего времени вычислений и пересылка строк осуществляется всегда во все компьютеры. Затраты на пересылку одной строки из разных компьютеров в этом случае будут всегда максимальны.
2.5. Параллельный алгоритм решения СЛАУ' методом простой итерации Здесь рассматривается параллельный алгоритм решения СЛАУ методом простой итера- ции. Приближенные решения (итерации) системы линейных уравнений последовательно находятся по формуле: у(~~И = у( ~ — т ~ ~а, у( ~ — о( 1 , 1 = 1, 2,..., Ю. Лля решения этой задачи на параллельной системе исходную матрицу коэффициентов А разрезаем на р1 горизонтальных полосы по строкам, где р1 — количество компьютеров в системе. Аналогично, горизонтальными полосами разрезаются вектор а (правая часть) и векторы уа (начэльное приближение), у" (текущее приближение) и у"+' (следующее приближение). Полосы последовательно распределяются по соответствующим компьютерам системы, как и в описанном выше первом алгоритме умножения матрицы на матрицу.
Здесь выражение 2 а; у есть умножение матрицы на вектор, параллельный алгоритм 00 '=1 которого представлен в п. 9.2.1. Таким образом, этот алгоритм является составной частью, описываемого в данном пункте алгоритма. В каждом компьютере системы вычисляется "свое" подмножество корней. Поэтому после нахождения приближенных значений корней на очередном шаге итерации в каждом компьютере проверяется выполнение следующего условия для "своих" подмножеств корней." /~у, — и; /!Сг.
(2) Это условие в некоторых компьютерах системы в текущий момент может выполняться, а в некоторых нет. Но условием завершения работы каждого компьютера является безусловное выполнение условия (2) во всех компьютерах. Таким образом, прежде чем завершить работу, при выполнении условия (2), каждый компьютер должен предварительно узнать." во всех ли компьютерах выполнилось условие (2)? И если условие (2) не выполнилось хотя бы в одном компьютере, то все компьютеры должны продолжить работу. Это обстоятельство связано с тем, что в операции умножения матрицы на вектор участвуют все компъютеры, йБ.
Параллельный алгоритм решения СЛАУ методом простой итерации 25 взаимодействуя друг с другом. И цепочку этих взаимодействий прерывать нельзя, если хотя бы в одном из компьютеров не выполнится условие (2). При не выполнении условия (2), каждый процесс передает всем остальным процессам полученную итерацию своих корней. И тем самым вектор у полностью восстанавливается в каждом процессе для выполнения операции его умножения на матрицу коэффициентов на следующем шаге итерации.
3. Переключатели каналов 3.1. Введение Системные программные средства, рассматриваемые в этой главе, увеличивают мощность и полноценность ро1п~-1о-ро1п1 и коллективных взаимодействий между процессами. Они способствуют созданию переносимых, эффективных и безопасных библиотек и программ на МР1.
Эти средства помогают преодолеть отдельные ограничения во многих системах передачи сообщений. Разделение процессов. В некоторых приложениях желательно делить процессы на группы для того, чтобы различные группы процессов могли делать независимую работу. Например, в задачах, в которых одна группа процессов делает подготовительную работу для другой группы процессов. Или другой пример. Время выполнения коллективных операций увеличивается с числом процессов, участвующих в операции, тем самым увеличивая время выполнения коллективных операций тех процессов, которые должны быть вовлечены в эти конкретные операции. Например, если в матричных вычислениях нужно передать информацию только процессам вдоль диагонали матрицы операцией Ьгоадсэв1 (один передает всем), то операция выполнится быстрее, если в ней будут участвовать только диагональные процессы.
'Уход от конфликтов сообщений между модулями. Библиотечные программы исторически имели трудности в изолировании их собственных запросов передачи сообщений от запросов других библиотечных или пользовательских программ. При многоподпроцессном выполнении (см. гл. 5) использование только тегов для обмениваемых данных недостаточно для надежного обмена данными между процессами.
Решение этой проблемы состоит в изолировании запросов передачи сообщений в рамках одной группы процессов от запросов других групп процессов. Безопасность. Система разбиения процессов на группы, используемая в МР1, обеспечивает достаточную безопасность при передаче сообщений. 3.2. Краткий обзор Вышеупомянутые атрибуты обеспечиваются в МР1 через переключатели каналов. Концепция переключателей каналов охватывает несколько центральных и фундаментальных идей в МР!. Значение переключателей каналов отражено тем фактом, что они присутствуют чаще всего в вызовах МР1. Имеется два типа переключателей каналов: группа (Егопр) и коммуникатор (совпапйсасог), выделяющие процессы в независимые замкнутые поцмножества.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
