Министерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Тольяттинский государственный университет»
Институт Математики, физики и информационных технологий
Кафедра «Прикладная математика и информатика»
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 - количество переменных, x1,x2,x3…xn - искомые неизвестные, a11, a12, a13,…, amn - коэффициенты и свободные члены a1m+1,…, amm+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 является одним из самых распространенных стандартов интерфейсов обмена данными в параллельном программировании на системах с распределенной памятью, существуют его реализации для большого числа компьютерных платформ.