Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

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

Слайд 2 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

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

градиентов
Последовательный алгоритм
Параллельный алгоритм
Заключение

Содержание


Слайд 3 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Постановка задачи
Линейное уравнение с n неизвестными


Множество n линейных уравнений называется системой линейных уравнений или линейной системой


В матричной форме:



Слайд 4 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Постановка задачи
Под задачей решения системы линейных

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

Слайд 5 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Основная идея метода - приведение матрицы

А посредством эквивалентных преобразований к треугольному виду, после чего значения искомых неизвестных могут быть получены непосредственно в явном виде
Эквивалентные преобразования:
Умножение любого из уравнений на ненулевую константу,
Перестановка уравнений,
Прибавление к уравнению любого другого уравнения системы.

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


Слайд 6 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод Гаусса – последовательный алгоритм…
На первом

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



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


Слайд 7 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Прямой ход
Метод Гаусса – последовательный алгоритм…
На

итерации i, 0≤ iВсе необходимые вычисления определяются при помощи соотношений:

Слайд 8 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Общая схема состояния данных на i-ой

итерации прямого хода алгоритма Гаусса

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



Слайд 9 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Обратный ход
Метод Гаусса – последовательный алгоритм
После

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

Слайд 10 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Определение подзадач
Все вычисления сводятся к однотипным

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

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


Слайд 11 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Выделение информационных зависимостей…
Каждая итерация i

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

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


Слайд 12 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод Гаусса – параллельный алгоритм…
Выделение

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

Слайд 13 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Масштабирование и распределение подзадач по процессорам…
В

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

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


Использование циклического способа формирования полос позволяет обеспечить лучшую балансировку вычислительной нагрузки между подзадачами


Слайд 14 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Масштабирование и распределение подзадач по процессорам
Основным

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

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


Слайд 15 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод Гаусса – параллельный алгоритм…
Анализ эффективности
Общая

оценка показателей ускорения и эффективности

Балансировка вычислительной нагрузки между процессорами, в целом, является достаточно равномерной


Слайд 16 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод Гаусса – параллельный алгоритм…
Анализ эффективности

(уточненные оценки)…

Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, состоит из:

Времени выполнения прямого хода алгоритма Гаусса (n-1 итерация).

Времени выполнения обратного хода алгоритма Гаусса (n-1 итерация).

выбор максимального значения в столбце с исключаемой неизвестной,
вычитание ведущей строки из каждой строки оставшейся части полосы матрицы A

обновление значения правых частей после рассылки вычисленного значения очередной неизвестной


Слайд 17 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод Гаусса – параллельный алгоритм…
Анализ эффективности

(уточненные оценки)…

При выполнении прямого хода алгоритма Гаусса

рассылка выбранной ведущей строки

При выполнении обратного хода алгоритма Гаусса

на каждой итерации осуществляется рассылка между всеми процессорами вычисленного значения очередной неизвестной

для определения ведущей строки процессоры обмениваются локально найденными максимальными значениями в столбце с исключаемой переменной (MPI_Allreduce)

Оценка затрат на выполнение операций передачи данных между процессорами:


Слайд 18 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод Гаусса – параллельный алгоритм…
Анализ эффективности

(уточненные оценки)

Общее время выполнения параллельного алгоритма:


Слайд 19 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Программная реализация…
Главная функция программы main.

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

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


Слайд 20 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод Гаусса – параллельный алгоритм…
Программная

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

Слайд 21 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Программная реализация…
Функция GaussianElimination выполняет параллельный вариант

прямого хода алгоритма Гаусса

Программа

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

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


Слайд 22 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Программная реализация…
Функция BackSubstitution реализует параллельный вариант

обратного хода Гаусса.

Программа

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


Слайд 23 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод Гаусса – параллельный алгоритм…
Результаты вычислительных

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




Слайд 24 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Результаты вычислительных экспериментов
Ускорение вычислений
Метод Гаусса –

параллельный алгоритм

Слайд 25 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Итерационные методы решения систем линейных уравнений


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

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

Метод сопряженных градиентов – один из наиболее известных итерационных методов решения систем линейных уравнений


Слайд 26 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Метод сопряженных градиентов может быть применен

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

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


Слайд 27 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Если матрица A симметричная и положительно

определенная, то функция

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

имеет единственный минимум, который достигается в точке x*, совпадающей с решением системы линейных уравнений.

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


Слайд 28 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Итерация метода сопряженных градиентов состоит в

вычислении очередного приближения к точному решению

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

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


Слайд 29 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Перед выполнением первой итерации вектора x0

и d0 полагаются равными нулю, а для вектора g0 устанавливается значение равное –b.

Шаг 1: Вычисление градиента

Шаг 2: Вычисление вектора направления

Шаг 3: Вычисление величины смещения по выбранному направлению

Шаг 4: Вычисление нового приближения


Вычислительная сложность алгоритма T1 = 2n3+13n2

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


Слайд 30 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44

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

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

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


Слайд 31 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Организация параллельных вычислений
Выполнение итераций метода осуществляется

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

При организации параллельных вычислений может быть полностью использован материал, изложенный в разделе "Параллельные методы умножения матрицы на вектор"

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


Слайд 32 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Анализ эффективности…
(при использовании параллельного алгоритма

умножения матрицы на вектор при ленточном горизонтальном разделении матрицы и при полном дублировании всех обрабатываемых векторов)

Вычислительная сложность параллельных операций умножения матрицы на вектор при использовании схемы ленточного горизонтального разделения матрицы

Как результат, при условии дублирования всех вычислений над векторами общая вычислительная сложность параллельного варианта метода сопряженных градиентов является равной

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


Слайд 33 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Анализ эффективности…
Общая оценка показателей ускорения и

эффективности

Балансировка вычислительной нагрузки между процессорами является достаточно равномерной

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


Слайд 34 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Анализ эффективности (уточненные оценки)
Коммуникационная сложность рассматриваемых

параллельных вычислений (см. раздел 7)

Общее время выполнения параллельного варианта метода сопряженных градиентов для решения систем линейных уравнений

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


Слайд 35 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Результаты вычислительных экспериментов
Сравнение теоретических оценок и

экспериментальных данных

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


Слайд 36 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Результаты вычислительных экспериментов
Ускорение вычислений
Метод сопряженных градиентов

– параллельный алгоритм

Слайд 37 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Заключение
Рассмотрены два параллельных алгоритма решения систем

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

Слайд 38 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Ускорение параллельных алгоритмов решения системы линейных

уравнений с размером матрицы 2000×2000

Заключение


Слайд 39 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Оцените, на каком этапе метода Гаусса

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

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


Слайд 40 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Выполните разработку параллельного варианта метода Гаусса

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

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


Слайд 41 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 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.

Литература


Слайд 42 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Параллельные методы сортировки
Следующая тема


Слайд 43 Н.Новгород, 2005 г.
Основы параллельных вычислений: Матричное умножение ©

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

Гергель В.П.
из 44
Гергель В.П., профессор, д.т.н., руководитель
Гришагин В.А.,

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

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


  • Имя файла: parallelnye-metody-resheniya-sistem-lineynyh-uravneniy.pptx
  • Количество просмотров: 96
  • Количество скачиваний: 0