Разработка параллельных программ на основе MPI для решения задач линейной алгебры Летняя школа по параллельному программированию 2012 Испольнители проекта: - презентация

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

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

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

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

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

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

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

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

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

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

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

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