Разработка параллельных программ на основе MPI для решения задач линейной алгебры Летняя школа по параллельному программированию 2012 Испольнители проекта: Блинова Екатерина Сидоров Андрей ФПМИ, 1-й курс Руководитель проекта: Черникова Анна

План доклада: Решение СЛАУ методом Гаусса. Использование MPI. (Параллельная реализация метода Гаусса)

Цели: Решить СЛАУ методом Гаусса. Теоретическое освоение методов решения систем линейных алгебраических уравнений прямыми методами. Алгоритм решения СЛАУ методом Гаусса. Параллельная реализация решения СЛАУ методом Гаусса

Метод Гаусса. Требуется найти решение системы линейных алгебраических уравнений: Матрица A называется основной матрицей системы, b столбцом свободных членов. Тогда согласно свойству элементарных преобразований над строками основную матрицу этой системы можно привести к ступенчатому виду(эти же преобразования нужно применять к столбцу свободных членов):элементарных преобразований

Алгоритм метода Гаусса Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа. На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений.

Распределение данных В предложенном алгоритме исходная матрица коэффициентов A и вектор правых частей F разрезаны горизонтальными полосами, как показано на рис. Каждая полоса загружается в соответствующий компьютер: нулевая полоса – в нулевой компьютер, первая полоса – в первый компьютер, и т. д., последняя полоса – в p1-1 компьютер. Здесь, в примере, каждая ветвь генерирует свои части матрицы коэффициентов A и вектор правых частей F. А F

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

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

Реализация Реализация заключается в равномерном распределении данных по всем компьютерам. Распределение происходит с помощью функции Scatter и после вычисления на каждом из компьютеров собираем информацию с помощью Gather A0A1A2A3 Данные ПроцессыПроцессы A0 A1 A2 A3 Scatter Gather

Заключение Размер матрицы А*АВремя работы при последовательном алгоритме (секунд) Время работа на 10 машинах (секунд) Результаты

Спасибо за внимание.

Коллективные взаимодействия Коллективная связь осуществляет взаимодействия типа « один - ко - всем », « все - к - одному », « все - со - всеми ». MPI имеет следующие функции коллективной связи : 1. Синхронизация (barrier) – синхронизирует все процессы группы 2. Глобальные функции связи broadcast – передача данных от одного процесса группы к остальным ( в т. ч. самому себе ) gather – сбор данных от всех процессов группы к одному процессу scatter – разброс данных от одного процесса группы ко всем остальным ( в т. ч. самому себе )