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

Содержание

• 
  Слайд 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.