Презентация на тему "Параллельные методы решения систем линейных уравнений"

Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5

Рецензии

Добавить свою рецензию

Аннотация к презентации

Презентация на тему "Параллельные методы решения систем линейных уравнений" рассказывает об основных методах решения линейных уравнений.

Краткое содержание

  • Постановка задачи
  • Метод Гаусса
  • Метод сопряженных градиентов
  • Заключение

Содержание

  • Слайд 1

    Параллельные методы решения систем линейных уравнений

    Гергель В.П., профессор, д.т.н.
    Кафедра математического обеспечения ЭВМ

  • Слайд 2

    Содержание

    • Постановка задачи
    • Метод Гаусса
      Последовательный алгоритм
      Параллельный алгоритм
    • Метод сопряженных градиентов
      Последовательный алгоритм
      Параллельный алгоритм
    • Заключение

  • Слайд 3

    Постановка задачи


  • Слайд 4

     

    Под задачей решения системы линейных уравнений для заданных матрицы А и вектора bпонимается нахождение значения вектора неизвестныхx, при котором выполняются все уравнения системы.

  • Слайд 5

    Метод Гаусса – последовательный алгоритм

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


  • Слайд 6

     

    • На первом этапе – прямой ход метода Гаусса – исходная система линейный уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному вду
    • На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных

  • Слайд 7

     


  • Слайд 8

     

    Общая схема состояния данных на i-ой итерации прямого хода алгоритма Гаусса

  • Слайд 9

     

    • Обратный ход
    • После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных:
    • Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1,
    • Из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д.
    • В общем виде, выполняемые вычисления при обратном ходе метода Гаусса могут быть представлены при помощи соотношений:

  • Слайд 10

    Метод Гаусса – параллельный алгоритм

    • Определение подзадач
    • Все вычисления сводятся к однотипным вычислительным операциям над строками матрицы коэффициентов системы линейных уравнений,
    • Следовательно, в основу параллельной реализации алгоритма Гаусса может быть положен принцип распараллеливания по данным,
    • В качестве базовой подзадачи примем все вычисления, связанные с обработкой одной строки матрицы A и соответствующего элемента вектора b.

  • Слайд 11

     

    • Выделение информационных зависимостей
    • Каждая итерация i выполнения прямого хода алгоритма Гаусса включает:
    • Выбор ведущей строки, для выполнения которого подзадачи с номерами k, k>i, должны обменяться своими элементами при исключаемой переменной xiдля нахождения максимального по абсолютной величине значения. Строка, которой принадлежит выбранное значение, выбирается в качестве ведущей строки для выполняемой итерации метода,
    • Рассылку выбранной ведущей строки матрицы A и соответствующего элемента вектора bвсем подзадачам с номерами k, k>i,
    • Вычитание строк для всех подзадачи k (k>i), обеспечивая тем самым исключение соответствующей неизвестной xi.

  • Слайд 12

     

    • Выделение информационных зависимостей
    • При выполнении обратного хода метода Гаусса подзадачи выполняют необходимые вычисления для нахождения значения неизвестных:
    • Как только какая-либо подзадача i, 0i

  • Слайд 13

     

    • Масштабирование и распределение подзадач по процессорам…
    • В случае, когда размер матрицы, описывающей систему линейных уравнений, оказывается большим, чем число доступных процессоров (т.е., n>p), базовые подзадачи можно укрупнить, объединив в рамках одной подзадачи несколько строк матрицы.
    • Использование циклического способа формирования полос позволяет обеспечить лучшую балансировку вычислительной нагрузки между подзадачами

  • Слайд 14

     

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

  • Слайд 15

     

    • Анализ эффективности
    • Общая оценка показателей ускорения и эффективности
    • Балансировка вычислительной нагрузки между процессорами, в целом, является достаточно равномерной

  • Слайд 16

     

    • Анализ эффективности (уточненные оценки)
    • Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, состоит из:
    • Времени выполнения прямого хода алгоритма Гаусса (n-1итерация).
    • Времени выполнения обратного хода алгоритма Гаусса (n-1итерация).
    • выбор максимального значения в столбце с исключаемой неизвестной,
    • вычитание ведущей строки из каждой строки оставшейся части полосы матрицы A
    • обновление значения правых частей после рассылки вычисленного значения очередной неизвестной

  • Слайд 17

     

    • Анализ эффективности (уточненные оценки)
    • При выполнении прямого хода алгоритма Гаусса
    • рассылка выбранной ведущей строки
    • При выполнении обратного хода алгоритма Гаусса
    • на каждой итерации осуществляется рассылка между всеми процессорами вычисленного значения очередной неизвестной
    • для определения ведущей строки процессоры обмениваются локальнонайденными максимальными значениями в столбце с исключаемой переменной (MPI_Allreduce)
    • Оценка затрат на выполнение операций передачи данных между процессорами:

  • Слайд 18

     

    • Анализ эффективности (уточненные оценки)
    • Общее время выполнения параллельного алгоритма:

  • Слайд 19

     

    • Программная реализация
    • Главная функция программы main. Реализует логику работы алгоритма, последовательно вызывает необходимые подпрограммы:
    • ProcessInitializationопределяет исходные данные решаемой задачи,
    • GaussianEliminationвыполняет прямой ход метода Гаусса,
    • BackSubstitutionреализует обратный ход метода Гаусса,
    • ResultCollectionосуществляет сбор со всех процессов отдельных частей вычисленного вектора неизвестных,
    • ProcessTerminationвыполняет необходимый вывод результатов решения задачи и освобождает всю ранее выделенную память для хранения данных.

  • Слайд 20

     

    • Программная реализация
    • Главная функция программы main. Использует массивы:
    • pPivotPos определяют номера строк матрицы, выбираемых в качестве ведущих, по итерациям прямого хода метода Гаусса – определяет далее порядок выполнения итераций для обратного хода (массив является глобальным и любое его изменение требует выполнения операции рассылки измененных данных),
    • pProcPivotIterопределяют номера итераций прямого хода метода Гаусса, на которых строки процесса использовались в качестве ведущих – нулевое значение элемента означает, что соответствующая строка должна обрабатываться при исключении неизвестных (массив является локальным для каждого процесса).


  • Слайд 21

     

    • Программная реализация
    • Функция GaussianElimination выполняет параллельный вариант прямого хода алгоритма Гаусса
    • Программа
    • Функция EliminateRowsпроводит вычитание ведущей строки из строк процесса, которые еще не использовались в качестве ведущих (т.е. для которых элементы массива pProcPivotIterравны нулю)

  • Слайд 22

     

    • Программная реализация
    • Функция BackSubstitution реализует параллельный вариант обратного хода Гаусса.


  • Слайд 23

     

    • Результаты вычислительных экспериментов
    • Сравнение теоретических оценок и экспериментальных данных

  • Слайд 24

     

    • Результаты вычислительных экспериментов
    • Ускорение вычислений

  • Слайд 25

    Метод сопряженных градиентов

    • Итерационные методы решения систем линейных уравнений
    • к искомому точному решению x* системы Ax=bстроится последовательность приближенных решений x0, x1,…, xk,…,
    • каждое очередное приближение дает оценку точного решения со все уменьшающейся погрешностью,
    • оценка точного решения может быть получена с любой требуемой точностью
    • Метод сопряженных градиентов – один из наиболее известных итерационных методов решения систем линейных уравнений

  • Слайд 26

     

    • Метод сопряженных градиентов может быть применен для решения системы линейных уравнений с симметричной, положительно определенной матрицей
    • Матрица А является симметричной, если она совпадает со своей транспонированной матрицей, т.е. А=АТ,
    • Матрица А называется положительно определенной, если для любого вектора xсправедливо: xTAx>0.
    • После выполнения n итераций метода сопряженных градиентов (n есть порядок решаемой системы линейных уравнений), очередное приближение xn совпадает с точным решением.

  • Слайд 27

    Метод сопряженных градиентов – последовательный алгоритм

    • Если матрица Aсимметричная и положительно определенная, то функция
    • имеет единственный минимум, который достигается в точке x*, совпадающей с решением системы линейных уравнений.
    • Метод сопряженных градиентов является одним из широкого класса итерационных алгоритмов, которые позволяют найти решение путем минимизации функции q(x)

  • Слайд 28

    Метод сопряженных градиентов –последовательный алгоритм

    • Итерация метода сопряженных градиентов состоит в вычислении очередного приближения к точному решению где
    • xk– очередное приближение,
    • xk-1 – приближение, построенное на предыдущем шаге,
    • sk– скалярный шаг,
    • dk– вектор направления

  • Слайд 29

     

    • Перед выполнением первой итерации вектора x0 и d0 полагаются равными нулю, а для вектора g0 устанавливается значение равное –b.
    • Шаг 1: Вычисление градиента
    • Шаг 2: Вычисление вектора направления
    • Шаг 3: Вычисление величины смещения по выбранному направлению
    • Шаг 4: Вычисление нового приближения
    • Вычислительная сложность алгоритмаT1 = 2n3+13n2

  • Слайд 30

    Метод сопряженных градиентов – последовательный алгоритм

    Итерации метода сопряженных градиентов при решении системы линейных уравнений второго порядка:

  • Слайд 31

    Метод сопряженных градиентов – параллельный алгоритм

    • Организация параллельных вычислений
    • Выполнение итераций метода осуществляется последовательно, следовательно наиболее целесообразный подход состоит в распараллеливании вычислений, реализуемых в ходе выполнения отдельных итераций,
    • Основные вычисления, выполняемые в соответствии с методом, состоят в умножении матрицы A на вектора x и d,
    • Дополнительные вычисления, имеющие меньший порядок сложности, представляют собой различные операции обработки векторов (скалярное произведение, сложение и вычитание, умножение на скаляр).
    • При организации параллельных вычислений может быть полностью использован материал, изложенный в разделе "Параллельные методы умножения матрицы на вектор"

  • Слайд 32

     

    • Анализ эффективности
    • (при использовании параллельного алгоритма умножения матрицы на вектор при ленточном горизонтальном разделении матрицы и при полном дублировании всех обрабатываемых векторов)
    • Вычислительная сложность параллельных операций умножения матрицы на вектор при использовании схемы ленточного горизонтального разделения матрицы
    • Как результат, при условии дублирования всех вычислений над векторами общая вычислительная сложность параллельного варианта метода сопряженных градиентов является равной

  • Слайд 33

    Метод сопряженных градиентов –параллельный алгоритм

    • Анализ эффективности
    • Общая оценка показателей ускорения и эффективности
    • Балансировка вычислительной нагрузки между процессорами является достаточно равномерной

  • Слайд 34

    Метод сопряженных градиентов – параллельный алгоритм

    • Анализ эффективности (уточненные оценки)
    • Коммуникационная сложность рассматриваемых параллельных вычислений (см. раздел 7)
    • Общее время выполнения параллельного варианта метода сопряженных градиентов для решения систем линейных уравнений

  • Слайд 35

    Метод сопряженных градиентов –параллельный алгоритм

    • Результаты вычислительных экспериментов
    • Сравнение теоретических оценок и экспериментальных данных

  • Слайд 36

    Метод сопряженных градиентов – параллельный алгоритм

    • Результаты вычислительных экспериментов
    • Ускорение вычислений

  • Слайд 37

    Заключение

    • Рассмотрены два параллельных алгоритма решения систем линейных уравнений:
    • Метод Гаусса
    • Метод сопряженных градиентов
    • Представлена программная реализация метода Гаусса
    • Теоретические оценки и результаты экспериментов показывают большую эффективность метода сопряженных градиентов

  • Слайд 38

     

    Ускорение параллельных алгоритмов решения системы линейных уравнений с размером матрицы 2000×2000

  • Слайд 39

    Вопросы для обсуждения

    • Оцените, на каком этапе метода Гаусса (прямой и обратный ход) происходит большее снижение показателей эффективности.
    • В чем причина столь низких показателей ускорения и эффективности параллельного алгоритма Гаусса?
    • Существуют ли способ улучшения этих показателей?
    • Какой из рассмотренных алгоритмов обладает большей вычислительной сложностью?
    • В чем состоит основное преимущество итерационных методов решения систем линейных уравнений?

  • Слайд 40

    Темы заданий для самостоятельной работы

    • Выполните разработку параллельного варианта метода Гаусса при вертикальном разбиении матрицы по столбцам
    • Выполните разработку параллельных вариантов методов Якоби и Зейделя решения систем линейных уравнений
    • Постройте теоретические оценки времени работы этих алгоритмов с учетом параметров используемой вычислительной системы. Проведите вычислительные эксперименты и сравните полученные результаты с ранее полученными теоретическими оценками

  • Слайд 41

    Литература

    • Гергель В.П. (2007). Теория и практика параллельных вычислений. – М.: Интернет-Университет, БИНОМ. Лаборатория знаний.
    • Бахвалов Н.С., Жидков Н.П., Кобельков Г.М (1987) Численные методы. – М.: Наука.
    • Самарский А.А., Гулин А.В. (1989). Численные методы – М.: Наука.
    • Bertsekas, D.P., Tsitsiklis, J.N. (1989). Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey.
    • Kumar V., Grama, A., Gupta, A., Karypis, G. (1994). Introduction to Parallel Computing. - The Benjamin/Cummings Publishing Company, Inc. (2nd edn., 2003)
    • Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. – New York, NY: McGraw-Hill.

  • Слайд 42

    Следующая тема

    Параллельные методы сортировки

  • Слайд 43

    Авторский коллектив

    • Гергель В.П., профессор, д.т.н., руководитель
    • Гришагин В.А., доцент, к.ф.м.н.
    • Сысоев А.В., ассистент (раздел 1)
    • Лабутин Д.Ю., ассистент (система ПараЛаб)
    • Абросимова О.Н., ассистент (раздел 10)
    • Гергель А.В., аспирант (раздел 12)
    • Лабутина А.А., магистр (разделы 7,8,9, система ПараЛаб)
    • Сенин А.В. (раздел 11)


  • Слайд 44

    О проекте

    • Целью проекта является создание образовательного комплекса "Многопроцессорные вычислительные системы и параллельное программирование", обеспечивающий рассмотрение вопросов параллельных вычислений, предусматриваемых рекомендациями Computing Curricula 2001 Международных организаций IEEE-CS и ACM. Данный образовательный комплекс может быть использован для обучения на начальном этапе подготовки специалистов в области информатики, вычислительной техники иинформационных технологий.
    • Образовательный комплекс включает учебный курс "Введение в методы параллельного программирования" и лабораторный практикум "Методы и технологии разработки параллельных программ", что позволяет органично сочетать фундаментальное образование в области программирования и практическое обучение методам разработки масштабного программного обеспечения для решения сложных вычислительно-трудоемких задач на высокопроизводительных вычислительных системах.
    • Проект выполнялся в Нижегородском государственном университете им. Н.И. Лобачевского на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики (http://www.software.unn.ac.ru). Выполнение проекта осуществлялось при поддержке компании Microsoft.


Посмотреть все слайды
Презентация будет доступна через 45 секунд