Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Лекция 11. Параллельные методы решения систем линейных уравнений Образовательный комплекс Введение в методы параллельного программирования Гергель В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 2 из 44 Постановка задачи Метод Гаусса –Последовательный алгоритм –Параллельный алгоритм Метод сопряженных градиентов –Последовательный алгоритм –Параллельный алгоритм Заключение Содержание

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 3 из 44 Постановка задачи Линейное уравнение с n неизвестными Множество n линейных уравнений называется системой линейных уравнений или линейной системой В матричной форме:

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 4 из 44 Постановка задачи Под задачей решения системы линейных уравнений для заданных матрицы А и вектора b понимается нахождение значения вектора неизвестных x, при котором выполняются все уравнения системы.

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 5 из 44 Основная идея метода - приведение матрицы А посредством эквивалентных преобразований к треугольному виду, после чего значения искомых неизвестных могут быть получены непосредственно в явном виде Эквивалентные преобразования: –Умножение любого из уравнений на ненулевую константу, –Перестановка уравнений, –Прибавление к уравнению любого другого уравнения системы. Метод Гаусса – последовательный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 6 из 44 Метод Гаусса – последовательный алгоритм… На первом этапе – прямой ход метода Гаусса – исходная система линейный уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 7 из 44 Прямой ход Метод Гаусса – последовательный алгоритм… На итерации i, 0 i

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 8 из 44 Общая схема состояния данных на i-ой итерации прямого хода алгоритма Гаусса Метод Гаусса – последовательный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 9 из 44 Обратный ход Метод Гаусса – последовательный алгоритм После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных : Из последнего уравнения преобразованной системы может быть вычислено значение переменной x n-1, Из предпоследнего уравнения становится возможным определение переменной x n-2 и т.д. В общем виде, выполняемые вычисления при обратном ходе метода Гаусса могут быть представлены при помощи соотношений :

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 10 из 44 Определение подзадач –Все вычисления сводятся к однотипным вычислительным операциям над строками матрицы коэффициентов системы линейных уравнений, –Следовательно, в основу параллельной реализации алгоритма Гаусса может быть положен принцип распараллеливания по данным, –В качестве базовой подзадачи примем все вычисления, связанные с обработкой одной строки матрицы A и соответствующего элемента вектора b. Метод Гаусса – параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 11 из 44 Выделение информационных зависимостей… –Каждая итерация i выполнения прямого хода алгоритма Гаусса включает: Выбор ведущей строки, для выполнения которого подзадачи с номерами k, k>i, должны обменяться своими элементами при исключаемой переменной x i для нахождения максимального по абсолютной величине значения. Строка, которой принадлежит выбранное значение, выбирается в качестве ведущей строки для выполняемой итерации метода, Рассылку выбранной ведущей строки матрицы A и соответствующего элемента вектора b всем подзадачам с номерами k, k>i, Вычитание строк для всех подзадачи k (k>i), обеспечивая тем самым исключение соответствующей неизвестной x i. Метод Гаусса – параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 12 из 44 Метод Гаусса – параллельный алгоритм… Выделение информационных зависимостей –При выполнении обратного хода метода Гаусса подзадачи выполняют необходимые вычисления для нахождения значения неизвестных: Как только какая-либо подзадача i, 0 i

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 13 из 44 Масштабирование и распределение подзадач по процессорам… –В случае, когда размер матрицы, описывающей систему линейных уравнений, оказывается большим, чем число доступных процессоров (т.е., n>p), базовые подзадачи можно укрупнить, объединив в рамках одной подзадачи несколько строк матрицы. Метод Гаусса – параллельный алгоритм… Использование циклического способа формирования полос позволяет обеспечить лучшую балансировку вычислительной нагрузки между подзадачами

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 14 из 44 Масштабирование и распределение подзадач по процессорам –Основным видом информационного взаимодействия подзадач является операция передачи данных от одного процессора всем процессорам вычислительной системы, –Как результат, для эффективной реализации требуемых информационных взаимодействий между базовыми подзадачами, топология сети передачи данных должны иметь структуру гиперкуба или полного графа. Метод Гаусса – параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 15 из 44 Метод Гаусса – параллельный алгоритм… Анализ эффективности –Общая оценка показателей ускорения и эффективности Балансировка вычислительной нагрузки между процессорами, в целом, является достаточно равномерной

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 16 из 44 Метод Гаусса – параллельный алгоритм… Анализ эффективности ( уточненные оценки )… - Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, состоит из: Времени выполнения прямого хода алгоритма Гаусса (n-1 итерация). Времени выполнения обратного хода алгоритма Гаусса (n-1 итерация ). выбор максимального значения в столбце с исключаемой неизвестной, вычитание ведущей строки из каждой строки оставшейся части полосы матрицы A обновление значения правых частей после рассылки вычисленного значения очередной неизвестной

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 17 из 44 Метод Гаусса – параллельный алгоритм… Анализ эффективности ( уточненные оценки )… При выполнении прямого хода алгоритма Гаусса рассылка выбранной ведущей строки При выполнении обратного хода алгоритма Гаусса на каждой итерации осуществляется рассылка между всеми процессорами вычисленного значения очередной неизвестной для определения ведущей строки процессоры обмениваются локально найденными максимальными значениями в столбце с исключаемой переменной (MPI_Allreduce) - Оценка затрат на выполнение операций передачи данных между процессорами :

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 18 из 44 Метод Гаусса – параллельный алгоритм… Анализ эффективности ( уточненные оценки ) Общее время выполнения параллельного алгоритма:

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 19 из 44 Программная реализация… –Главная функция программы main. Реализует логику работы алгоритма, последовательно вызывает необходимые подпрограммы: ProcessInitialization определяет исходные данные решаемой задачи, GaussianElimination выполняет прямой ход метода Гаусса, BackSubstitution реализует обратный ход метода Гаусса, ResultCollection осуществляет сбор со всех процессов отдельных частей вычисленного вектора неизвестных, ProcessTermination выполняет необходимый вывод результатов решения задачи и освобождает всю ранее выделенную память для хранения данных. Метод Гаусса – параллельный алгоритм…

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 21 из 44 Программная реализация… –Функция GaussianElimination выполняет параллельный вариант прямого хода алгоритма Гаусса Программа Функция EliminateRows проводит вычитание ведущей строки из строк процесса, которые еще не использовались в качестве ведущих (т.е. для которых элементы массива pProcPivotIter равны нулю) Метод Гаусса – параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 22 из 44 Программная реализация… –Функция BackSubstitution реализует параллельный вариант обратного хода Гаусса. Программа Метод Гаусса – параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 23 из 44 Метод Гаусса – параллельный алгоритм… Результаты вычислительных экспериментов –Сравнение теоретических оценок и экспериментальных данных Размер системы 2 процессора4 процессора Т p (модель) 5001,25581,34440,93761, ,887910,16375,20256, ,173432,861115,932619, ,389377,412136,266545,9435

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 24 из 44 Результаты вычислительных экспериментов –Ускорение вычислений Размер системы Последовательный алгоритм Параллельный алгоритм 2 процессора4 процессора ВремяУскорениеВремяУскорение 500 2,0251,34441,50621,05731, ,800110,16371,65296,37332, ,962832,86111,733419,99172, ,54777,41211,750945,94352,9503 Метод Гаусса – параллельный алгоритм

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 25 из 44 Итерационные методы решения систем линейных уравнений –к искомому точному решению x* системы Ax=b строится последовательность приближенных решений x 0, x 1,…, x k,…, –каждое очередное приближение дает оценку точного решения со все уменьшающейся погрешностью, –оценка точного решения может быть получена с любой требуемой точностью Метод сопряженных градиентов… Метод сопряженных градиентов – один из наиболее известных итерационных методов решения систем линейных уравнений

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 26 из 44 Метод сопряженных градиентов может быть применен для решения системы линейных уравнений с симметричной, положительно определенной матрицей –Матрица А является симметричной, если она совпадает со своей транспонированной матрицей, т.е. А=А Т, –Матрица А называется положительно определенной, если для любого вектора x справедливо: x T Ax>0. После выполнения n итераций метода сопряженных градиентов (n есть порядок решаемой системы линейных уравнений), очередное приближение x n совпадает с точным решением. Метод сопряженных градиентов…

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 27 из 44 Если матрица A симметричная и положительно определенная, то функция Метод сопряженных градиентов – последовательный алгоритм... имеет единственный минимум, который достигается в точке x*, совпадающей с решением системы линейных уравнений. Метод сопряженных градиентов является одним из широкого класса итерационных алгоритмов, которые позволяют найти решение путем минимизации функции q(x)

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 28 из 44 Итерация метода сопряженных градиентов состоит в вычислении очередного приближения к точному решению где x k – очередное приближение, x k-1 – приближение, построенное на предыдущем шаге, s k – скалярный шаг, d k – вектор направления Метод сопряженных градиентов – последовательный алгоритм...

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 29 из 44 Перед выполнением первой итерации вектора x 0 и d 0 полагаются равными нулю, а для вектора g 0 устанавливается значение равное –b. Шаг 1: Вычисление градиента Шаг 2: Вычисление вектора направления Шаг 3: Вычисление величины смещения по выбранному направлению Шаг 4: Вычисление нового приближения Вычислительная сложность алгоритма T 1 = 2n 3 +13n 2 Метод сопряженных градиентов – последовательный алгоритм...

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 30 из 44 Итерации метода сопряженных градиентов при решении системы линейных уравнений второго порядка : Метод сопряженных градиентов – последовательный алгоритм...

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 32 из 44 Анализ эффективности… (при использовании параллельного алгоритма умножения матрицы на вектор при ленточном горизонтальном разделении матрицы и при полном дублировании всех обрабатываемых векторов) – Вычислительная сложность параллельных операций умножения матрицы на вектор при использовании схемы ленточного горизонтального разделения матрицы – Как результат, при условии дублирования всех вычислений над векторами общая вычислительная сложность параллельного варианта метода сопряженных градиентов является равной Метод сопряженных градиентов – параллельный алгоритм...

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 33 из 44 Анализ эффективности… –Общая оценка показателей ускорения и эффективности Балансировка вычислительной нагрузки между процессорами является достаточно равномерной Метод сопряженных градиентов – параллельный алгоритм...

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 34 из 44 Анализ эффективности ( уточненные оценки ) –Коммуникационная сложность рассматриваемых параллельных вычислений (см. раздел 7) –Общее время выполнения параллельного варианта метода сопряженных градиентов для решения систем линейных уравнений Метод сопряженных градиентов – параллельный алгоритм...

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 35 из 44 Результаты вычислительных экспериментов –Сравнение теоретических оценок и экспериментальных данных Размер системы 2 процессора4 процессора Т p (модель) 5003,06331,39511,70291, ,904614,225211,923111, ,143157,913038,970441, , ,072191, ,7042 Метод сопряженных градиентов – параллельный алгоритм...

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 36 из 44 Результаты вычислительных экспериментов –Ускорение вычислений Размер системы Последовательный алгоритм Параллельный алгоритм 2 процессора4 процессора ВремяУскорениеВремяУскорение 5002,07661,39511,48851,23031, ,638914,22521,450911,09891, ,267157,91301,558741,95212, , ,07211, ,70422,1824 Метод сопряженных градиентов – параллельный алгоритм

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 37 из 44 Заключение Рассмотрены два параллельных алгоритма решения систем линейных уравнений: –Метод Гаусса, –Метод сопряженных градиентов Представлена программная реализация метода Гаусса Теоретические оценки и результаты экспериментов показывают большую эффективность метода сопряженных градиентов

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 38 из 44 Ускорение параллельных алгоритмов решения системы линейных уравнений с размером матрицы 2000×2000 Заключение

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 40 из 44 Выполните разработку параллельного варианта метода Гаусса при вертикальном разбиении матрицы по столбцам Выполните разработку параллельных вариантов методов Якоби и Зейделя решения систем линейных уравнений Постройте теоретические оценки времени работы этих алгоритмов с учетом параметров используемой вычислительной системы. Проведите вычислительные эксперименты и сравните полученные результаты с ранее полученными теоретическими оценками Темы заданий для самостоятельной работы

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 41 из 44 Гергель В.П. (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. Литература

Н.Новгород, 2005 г. Основы параллельных вычислений: Матричное умножение © Гергель В.П. 42 из 44 Параллельные методы сортировки Следующая тема

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

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