Решение СЛАУ прямым методом Гаусса (или любым другим)

Размещено на http://allbest.ru

Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Тольяттинский государственный университет»

Институт Математики, физики и информационных технологий

Кафедра «Прикладная математика и информатика»

02.03.03 Математическое обеспечение и администрирование информационных систем

Компьютерные технологии и математическое моделирование

курсовая работа

на тему:

Решение СЛАУ прямым методом Гаусса (или любым другим)

по дисциплине (учебному курсу):

«Многопоточное программирование»

Студент С.А. Скоков

Руководитель: Копша О.Ю

Тольятти, 2019



Содержание

Введение

1. Постановка задачи на исследование

1.1 Место задачи в современном естествознании

1.2 Математическое описание решения систем линейных алгебраических уравнений методом Гаусса и матричным методом

1.3 Создание последовательных программ

2. Проектирование и разработка параллельных программ

2.1 Обзор технологий разработки параллельного программного обеспечения

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

3. Анализ эффективности параллельных алгоритмов и методов решения СЛАУ

3.1 Теоретическое исследование эффективности параллельного алгоритма

3.2 Проведение эксперимента и анализ эффективности работы параллельных алгоритмов

Заключение

Список используемых источников

Приложение А



Введение

Параллельное программирование - это техника программирования, которая использует преимущества многоядерных компьютеров и является частью более широкого понятия - многопоточности.

Многопоточность - это одно из свойств современных компьютеров, состоящее в том, что выполнение заданного процесса может делиться на определенное количество потоков, выполнение которых будет проходить «параллельно», то есть без определенного порядка во времени. Используется при решении некоторых объемных задач, так как подобное разделение потоков позволяет более эффективно использовать ресурсы нашей вычислительной машины, то есть ускорять время выполнения задачи.

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

Объектом исследования данной курсовой работы является программное решение систем линейный алгебраических уравнений.

Предметом исследования является параллельная программа нахождения решения систем линейных алгебраических уравнений.

Обозначим задачи, необходимые для достижение цели данной курсовой работы.

1) Изучить существующие технологии создания параллельных программ.

2) Выбрать среди этих технологий одну для дальнейшего использования при разработке параллельной программы.

3) Рассмотреть алгоритмы решения систем линейных алгебраических уравнений методом Гаусса и матричным метод.

4) Реализовать последовательные программы.

5) Реализовать параллельные программы с использованием выбранной технологии

6) Провести теоретическое изучение эффективности параллельного алгоритма.

Структура данной курсовой работы состоит из трех основных глав.

В первой главе рассмотрим решение систем линейных уравнений методом Гаусса и матричным методом, изучим математическое описание алгоритма и реализуем последовательную программу.

Во второй главу рассмотрим технологии разработки параллельных программ, разработаем параллельные алгоритмы и реализуем параллельные программы.

В третьей главе проведем теоретическое исследование эффективности алгоритмов, сравним их между собой, и сделаем выводы, какой метод эффективнее для решения СЛАУ и для какого метода будет эффективные применять параллельные технологии.



1. Постановка задачи на исследование

1.1 Место задачи в современном естествознании

В результате развития аппаратной составляющей вычислительных систем последовало и развитие программного обеспечения для данных систем.

Таким образом возникновение новых технический возможностей приводило к потребности разрабатывать новые технологии построения программного обеспечения для решения некоторых проблем и несоответствий, последовавших за стремительным ростом технических возможностей электронно-вычислительных машин

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

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

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

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

1.2 Математическое описание решения систем линейных алгебраических уравнений методом Гаусса и матричным методом

Система линейных алгебраических уравнений (используемая аббревиатура - СЛАУ) - это система уравнений, в которой все уравнения являются линейными и алгебраическими. Общая форма записи системы представлена на рисунке 1, где m - количество уравнений, n - количество переменных, x₁,x₂,x₃…x_n - искомые неизвестные, a₁₁, a₁₂, a₁₃,…, a_mn - коэффициенты и свободные члены a_1m+1,…, a_mm+1 известны. Индексы при коэффициентов обозначают: первый индекс - номер уравнения, второй индекс - номер переменной.

Рисунок 1 - общая форма записи СЛАУ

Так же СЛАУ зачастую представляется в матричной форме, приведенной на рисунке 2.



Рисунок 2 - Матричная форма записи СЛАУ

Для решения СЛАУ существует множество разных методов, которые делятся на прямые и итерационные.

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

Темой данной курсовой является решения СЛАУ прямым методом Гаусса и матричным методом, поэтому рассмотрим данный методы.

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

Таким образом можно сказать, что алгоритм метода Гаусса состоит из 2 двух этапов:

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

2) Обратная подстановка найденной неизвестной в другие уравнения с целью нахождения остальных неизвестных, называемая обратным ходом.

Для Решения СЛАУ матричным методом необходимо представить систему в матричном виде Ax=b (рисунок 2), где А - основная матрица, b- столбец свободных членов и x - решения системы, также для решения понадобится единичная матрица E.

Если умножить матричное уравнение на обратную матрицу, то получим: A^-1(Ax)=A^-1b.

Так как AA^-1=E, то получаем, x=A^-1b. Таким образом для решения СЛАУ матричным методом достаточно найти матрицу A^-1, обратную основной матрице A для системы и умножить её на матрицу свободных членов b.

Таким образом можно сказать, что алгоритм матричного метода так же состоит из двух этапов:

1) Нахождение обратной матрицы для основной матрицы системы.

2) Перемножение обратной матрицы с матрицей свободных членов.

1.3 Создание последовательных программ

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

В начале рассмотрим метод Гаусса. Для решения поставленной задачи определим последовательность действий:

1) Ввести СЛАУ, которую необходимо решить.

2) Привести СЛАУ к трапецевидной форме.

3) Провести обратную подстановку.

4) Вывести ответ.

На основе данной последовательности создадим блок-схему программы в целом и отдельную блок-схему алгоритма метода Гаусса. Данные блок-схемы приведены на рисунке 3 и 4 соответственно.

В программе предусмотрена возможность ввода СЛАУ как вручную для контроля правильности расчетов, так и генерация СЛАУ со случайными коэффициентами для решения объемных СЛАУ, необходимых нам для дальнейшего анализа.

Рисунок 3 - Блок-схема последовательной программы метода Гаусса.

Рисунок 4 - Блок-схема алгоритма метода Гаусса.



Далее, опираясь на данную последовательность действий и блок-схемы реализуем последовательный алгоритм на языке C++. С полным кодом программы можно ознакомиться в приложение А под именем «Method_Gauss.сpp». матричный параллельный алгоритм программирование

Теперь рассмотрим матричный метод. Для решения поставленной задачи определим последовательность действий:

1) Ввести СЛАУ, которую необходимо решить.

2) Найти обратную матрицу.

3) Перемножить обратную матрицу и матрицу свободных коэффицентов.

4) Вывести ответ.

На основе данной последовательности создадим общую блок-схему программы и отдельную блок-схему алгоритма матричного метода. Данные блок-схема приведены на рисунке 5 и 6 соответственно.

Рисунок 5 - Блок-схема последовательной программы матричного метода.



Рисунок 6 - Блок-схема алгоритма нахождения обратной матрицы.

Рисунок 6 - Блок-схема алгоритма нахождения обратной матрицы



В данной программе так же как и для прошлого метода предусмотрены разные методы инициализации СЛАУ.

Далее, опираясь на данную последовательность действий и блок-схемы реализуем последовательный алгоритм на языке C++. С полным кодом программы можно ознакомиться в приложение А в файле под именем «Method_Matrix.сpp». Для того, чтобы удостовериться в правильность работы программ проведем тестирование, подавая различные СЛАУ и сверяя выходные данные с правильными решениями. Примеры входных данных приведены в таблице 1, а результаты вывода на рисунках 7, 8, и 9 соответственно. В левой части рисунка представлен вывод решения методом Гаусса, а в правой матричным методом. СЛАУ выбраны разной размерности чтобы удостовериться, что программа верно подстраивается под размеры матриц.

Как видно из рисунков и таблиц нахождение ответов программой совпадает с ответами

Таблица 1. Входные данные

СЛАУ	Верное решение СЛАУ
	X1 = 5 X2 = -1 X3 = -5
	X1 =-0,5 X2 = 4 X3 = 3,5 X4 = 3
	X1 =-4 X2 = 1



Рисунок 7 - Вывод решения для первого СЛАУ

Рисунок 8 - Вывод решения для второго СЛАУ



Рисунок 9 - Вывод решения для третьего СЛАУ

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



2. Проектирование и разработка параллельных программ

2.1 Обзор технологии разработки параллельного программного обеспечения

Рассмотрим основные технологии разработки параллельных программ:

1) MPI.

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

Достоинства: MPI помогает решить проблему переносимости параллельных программ между разными компьютерными системами; содействует повышению эффективности параллельных вычислений: практически для каждого типа вычислительных систем существуют реализации библиотек MPI, учитывающие возможности используемого коммуникационного оборудования; облегчает процесс написания параллельных программ, когда при разработке используются библиотеки программных модулей, написанных с использованием этого интерфейса; позволяет создавать хорошо масштабируемые параллельные программы.

Недостатки: не существует реализаций MPI, в полной мере обеспечивающих совмещение обменов с вычислениями; MPI не предоставляет механизмов задания начального размещения процессов по процессорам; полномасштабная отладка MPI-программ затруднительна вследствие одновременного исполнения нескольких программных ветвей.

2) OpenMP.

OpenMP - это API-интерфейс, который является отраслевым стандартом для создания параллельных приложений для компьютеров с совместным использованием памяти. Главная задача OpenMP - облегчить написание программ, ориентированных на циклы. Такие программы часто создаются для высокопроизводительных вычислений.

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

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

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

Достоинства: возможность постепенного, "инкрементного" распараллеливания программы. Взяв за основу последовательный код, пользователь шаг за шагом добавляет новые директивы, описывающие новые параллельные секции. Нет необходимости сразу писать параллельную программу, ее создание ведется последовательно, что упрощает и процесс программирования, и отладку .

Недостатки: OpenMP рассчитан на мультипроцессоры и DSM-системы (системы с распределенной памятью, на которых смоделирована общая память) и изначально не ориентирован на кластеры; невысокая эффективность OpenMP-программ на DSM-системах большого размера; организация взаимодействия потоков через общие переменные, а не через передачу сообщений, часто приводит к трудно обнаруживаемым ошибкам, а необходимые для поиска таких ошибок средства отладки - либо отсутствуют вообще, либо мало доступны.

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

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

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

Рассмотрим по очереди данные методы.

Как уже было сказано, алгоритм решения СЛАУ методом Гаусса состоит из прямого и обратного хода, которые содержат простые операции обработки строк и элементов матрицы, заключенных в циклы. В последовательном коде программы имеются циклы с регулярной структурой, распараллеливание которых средствами OpenMP не вызывает затруднений, с единственным исключением, что для избежание «гонки» потоков и использования общей памяти для каждого потока необходимо создать локальные копии переменных. На рисунке 10 приведен пример кода параллельного алгоритма метода Гаусса, где omp_set_num_threads() задает число создаваемых в параллельных областях потоков, pragma omp parallel for создает параллельную область выполнения для последующего цикла, private () - создает для каждого потока локальные переменные, перечисленные в скобках. Также используется функция omp_get_wtime() для замера времени выполнения алгоритма, что понадобится для дальнейшего анализа эффективности.



Рисунок 10. Пример кода параллельного метода Гаусса.

Далее для проверки работоспособности параллельного алгоритма проведем тестирование, подав для последовательного и параллельного кода одинаковые входные данные и сверив результаты выполнения.

Результаты тестирования параллельного алгоритма метода Гаусса приведены на рисунке 11. С полным кодом программы можно ознакомиться в приложении А в файле под именем «Method_Gaussa.cpp».



Рисунок 11 - Результаты тестирования параллельного метода Гаусса

Для матричного метода создадим схожий параллельный алгоритм. Так как с данном методе также применяется алгоритм приведения матрицы к треугольному виду, который так же содержит циклы с простыми операциями, проведем схожее распараллеливание с помощью директивы OpenMP. В данном случае это сделать ещё проще, так как здесь отсутствует обращение потоков к общей памяти и нет необходимости в создании локальных переменных. Также распараллелим цикл нахождения окончательного результата. На рисунке 12 и 13 приведены примеры кода для данного метода.

Рисунок 12. Параллельный алгоритм вычисления окончательного результата



Рисунок 13. Параллельный алгоритм приведения матрицы к треугольному виду

Далее проведем тестирование работоспособности параллельного матричного метода таким же образом, как и для метода Гаусса. Результаты тестирования приведены на рисунке 14.



Рисунок 14 - Тестирование параллельного метода Гаусса.

Таким образом были разработаны и реализованы параллельные алгоритмы для метода Гаусса и матричного метода с использованием технологии OpenMP, приведены примеры параллельного кода и тестирования данных алгоритмов на работоспособность.



3. Анализ эффективности параллельных алгоритмов и методов решения СЛАУ

3.1 Теоретическое исследование эффективности параллельного алгоритма

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

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

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

1) Вычисляется количество операций, затрачиваемые на выполнение последовательного алгоритма F₁(n), где n - размерность задачи.

2) Определяется время, затраченное на реализацию последовательного алгоритма T₁(n).

3) Вычисляется количество операций и время, затрачиваемых на выполнение параллельного алгоритма F_p(n) и T_p(n).

4) Вычисляется коэффицент ускорения параллельных вычислений по формуле: R_p(n)=T₁(n)/T_p(n), для различного числа потоков p.

5) Вычисляется коэффицент эффективности распараллеливания по формуле E_p(n)=R_p(n)/p, для различного числа потоков p.

Согласно источникам для алгоритма решения СЛАУ методом Гаусса количество операций будет равно F₁(n)=(2/3)*n³, а время выполнения соответственно T₁(n)=(2/3)*n³ * t, где t- время выполнения одной операции [1,139]. Количество выполняемые операций для параллельного алгоритма остается тем же благодаря тому, что технология OpenMP позволяет распараллеливать алгоритм, не изменяя количество или последовательность операций, используемых в последовательном алгоритме.

При разработке параллельного алгоритма вычислительные операции, выполняемые во время решения методом Гаусса, были распределены между потоками. Следовательно, время выполнения параллельного метода Гаусса можно описать как T_p(n)=(2*n³*t)/(3*p).

Теперь вычислим коэффициенты ускорения и эффективноcти:

1) R_p(n)=T₁(n)/T_p(n) => R_p(n)=(2/3)*n³ * t/(2*n³*t)/(3*p). = p.

2) R_p(n)= p

3) E_p(n)=R_p(n)/p => E_p(n)=p/p=1.

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

Также можно сказать, что данные результаты справедливы и для матричного метода решения СЛАУ, так как было проведено схожее распараллеливание в обоих метода, а именно был распараллелен блок приведения матриц к треугольному виду и блок нахождения окончательного результата (обратный ход для метода Гаусса), а, следовательно, они содержат равное количество операций и время их выполнения.



3.2 Проведение эксперимента и анализ эффективности работы параллельных алгоритмов

Проведем эксперимент на эффективность работы параллельных алгоритмов для данных методов с разным количеством потоков (2-8) и разной размерностью матриц (250-1500).

Для проведем замеры времени выполнения последовательных и параллельных алгоритмов с помощью функции OpenMP omp_get_wtime() и изменения количества создаваемых потоков с помощью omp_set_num_threads().

Результаты эксперимента приведены в таблице 2 и 3 соответственно.

Таблица 2. Метод Гаусса

Размер матрицы	Последовательный алгоритм	Параллельный алгоритм
		2 потока	4 потока	8 потоков
		Время	Ускорение	Время	Ускорение	Время	Ускорение
250	0,041	0,047	0,872	0,035	1,171	0,042	0,976
500	0,323	0,255	1,267	0,154	2,097	0,152	2,152
750	1,086	0,780	1,392	0,495	2,194	0,419	2,592
1000	2,577	1,757	1,467	1,033	2,495	0,847	3,043
1250	5,135	3,571	1,438	1,816	2,828	1,569	3,273

Таблица 3. Матричный метод

Размер матрицы	Последовательный алгоритм	Параллельный алгоритм
		2 потока	4 потока	8 потоков
		Время	Ускорение	Время	Ускорение	Время	Ускорение
250	0,504	0,371	1,358	0,273	1,843	0,282	1,787
500	4,012	2,479	1,618	1,405	2,856	1,312	3,058
750	13,682	8,162	1,676	4,747	2,882	4,14	3,305
1000	32,23	19,258	1,674	10,765	2,994	9,532	3,381
1250	62,851	37,398	1,681	19,365	3,246	18,073	3,478

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

Если же сравнивать между собой методы решения СЛАУ, становится очевидным что метод решения Гаусса выполняется гораздо быстрее чем матричный метод. Причиной этой является то, что определение обратной матрицы во втором методе весьма трудоёмко, а метод Гаусса в этом не нуждается. Также можно заметить, что параллельный алгоритм для матричного метода получился немного эффективнее, чем в методе Гаусса.



Заключение

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

Таким образом, в результате выполнения данной курсовой работы можно сделать выводы, что прямой метод Гаусса для решения СЛАУ, реализованный средствами языка С++ гораздо эффективные матричного метода решения СЛАУ, реализованного теми же средствами, несмотря на то, что теоретический анализ позволял рассчитывать на более эффективное применение параллельного алгоритма.

Также можно сказать что в результате сравнения технологий параллельного программирования MPI и OpenMP, сделан вывод что последняя технология лучше подходит для постепенного распараллеливания алгоритма, так как не требует создания нового алгоритма или переписывания последовательного кода, позволяя распараллелить его посредством директив.

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

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



Список используемой литературы

1) Амосов А.А., Вычислительные методы для инженеров: учебное пособие / А.А. Амосов - М.: Высш. шк., 1994. -- 544 с.

2) Антонов А.С. Параллельное программирование с использованием технологии OpenMP : учебное пособие / А.С. Антонов. - М. : Изд-во МГУ, 2012. - 77 с.

3) Карпов В. Е. Введение в распараллеливание алгоритмов и программ: учебное пособие/ В.Е. Карпов- М.: Изд-во МФТИ, 2014. - 272 с.

4) OpenMP Application Program Interface. Version 4.0 July 2013 [Электронный ресурс]: Режим доступа:: http://www.openmp.org

5) Bjarne Stroustrup. The C++ Programming Language. Fourth Edition. Addison Wesley, 2013.

6) Gregoire. Professional C++. Third Edition. John Wiley & Sons, Inc. ,2014.

7) Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J. MPI: The Complete Reference.[Электронный ресурс]: -MIT Press, Boston, 2011. Режим доступа: http://www.netlib.org/utk/papers/mpi-book/node1.html

8) Quinn, M. J. Parallel Programming in C with MPI and OpenMP. -New York, NY: McGraw-Hill, 2012.



Приложение А

Приложение содержит диск, на котором записаны исходные коды программ, а также электронная версия пояснительной записки.

Исходные код программы, реализующий метод гаусса находится в файле «Method_Gaussa.cpp», а матричного метода в файле «Matrix_Method.cpp».

Размещено на Allbest.ru