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

01.10.2018

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

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

Аннотация:
В данной статье рассматривается возможность применения и использования метода Гаусса в качестве одного из способов решения систем линейных алгебраических уравнений, рассматривается его , эффективность для двух типов задач и возможность его реализации в многопоточных приложениях на языке C#.

Abstract:
The article considers the possibility of using and using the Gaussian method as one of the methods for solving systems of linear algebraic equations; we consider it, the efficiency for two types of problems, and the possibility of its implementation in multithreaded applications in C#.

Ключевые слова:
программа; метод Гаусса; распараллеливание; обработка данных; потоки; параллелизм; многопоточность; модели решений

Keywords:
program; Gauss method; parallelization; data processing; flows; parallelism; multithreading; decision models

УДК 004.421.2
Введение. Параллельные вычислительные системы — это такие программные системы, которые осуществляют параллельную обработку данных различными способами на большинстве многопроцессорных компьютерах. Одновременное вычисление нескольких параллельных потоков может занять разное время, поэтому необходимо выполнять синхронизацию. Какие бывают виды синхронизации и модели решения рассматривается в данной статье.
Актуальность темы исследования заключается в том, что в современном мире информационные технологии играют важную роль. Появляется все больше мощных вычислительных машин, которые в значительной мере сокращают время выполнения различных задач. Распараллеливание данных – как один из вариантов уменьшения времени работы.
Целью работы является разработка и реализация последовательной и параллельной программы для решения методом Гаусса.
Задачами исследованияявляются изучение метода Гаусса, изучение потоков на C# и сравнение времени выполнения задач.
Наиболее мощным, простым и универсальным инструментом для нахождения решения любой системы линейных уравнений (СЛАУ) является метод Гаусса. Этот метод хорош тем, что для решения задач потребуется минимум знаний и навыков: нужно уметь складывать, умножать и делить числа. Задачи, решаемые методом Гаусса, являются последовательными. Такие задачи под силу решить каждому, вооружившись лишь ручкой и бумагой. Однако, такие задачи можно оптимизировать и усовершенствовать и решать параллельно, но уже при помощи вычислительных машин.
Данный метод включает в себя прямой и обратный ходы. Задача прямого хода заключается в приведении расширенной матрицы к ступенчатому виду, то есть получение нулей под главной диагональю. Метод Гаусса также имеет название – прямой ход, а обратный ход называется методом Гаусса-Жордана, который отличается от первого только тем, что переменные исключаются последовательно.
Для решения систем, содержащих более трех линейных уравнений, и для решения систем уравнений, которые не являются квадратными метод Гаусса подходит наилучшим образом. Таким образом, метод Гаусса – это самый универсальный метод для нахождения решения любой системы линейных уравнений. Этот метод работает даже в том случае, когда система имеет бесконечно много решений или вообще несовместна.
На первом шаге необходимо записать расширенную матрицу системы. Расширенная матрица системы – это такая матрица, которая составлена только из коэффициентов при неизвестных, плюс столбец свободных членов. Далее необходимо выполнить определенные действия, которые называются элементарными преобразованиями. С помощью элементарных преобразований исходную матрицу необходимо привести к ступенчатому виду:
Для приведения матрицы к подобному виду необходимо:
Разделить первую строку на первый элемент первой строки для получения единицы.
Умножить первую строку на такое число, чтобы при сложении со второй строкой первый элемент второй строки стал равен нулю.
Разделить первую строку на умноженное в п.2 число.
Перейти к п.1, применяя те же действия относительно 2го столбца. Повторять до тех пор, пока последний элемент последней строки не будет равен единице.
2. Потоки в C#
Параллельная программа содержит в себе несколько процессов, которые работают одновременно над выполнением определенной задачи. Каждый процесс является последовательной программой, а именно — последовательностью операторов, которые выполняются друг за другом. В последовательной программе существует только один поток управления, а в параллельном — несколько.
Поток – это некая независимая последовательность инструкций для выполнения того или иного действия в программе. В одном конкретном потоке выполняется одна конкретная последовательность действий. Способность операционной системы поддерживать выполнение нескольких таких потоков, выполняемых в программе параллельно, в рамках одного процесса называется многопоточностью.
Язык C# имеет встроенную поддержку многопоточности, а среда .NET Framework предоставляет сразу несколько классов для работы с потоками. В целом, это очень помогает правильно и гибко настраивать и реализовывать многопоточность в проектах.
Для того, чтобы начать работу с потоками, необходимо подключить пространство имен System.Threading. Пространство имен System.Threading содержит различные типы, которые позволяют создать многопоточные приложения.
using System.Threading;
Любой поток в C# это функция. Функции не могут быть сами по себе, они обязательно являются методами класса. Поэтому, что бы создать отдельный поток, нам понадобится класс с необходимым методом. Самый простой вариант метода возвращает void и не принимает аргументов:
static void ParallelMetodGaussa() {…}
Пример запуска такого потока:
Thread thread = new Thread(() => RecursionGetFirstElement(i - 1, 0, file[i], ref matrix, resetEvent));
thread.Start();
В данном случае, RecursionGetFirstElement показывает, что будет выполнять данная функция с указанными параметрами.
После вызова метода Start() управление у объекта потока вернется сразу, но в этот момент уже начнет работать наш новый поток. Новый поток выполнит тело функции RecursionGetFirstElement и завершится.
Применяя распараллеливание решения задачи к методу Гаусса можно использовать рекурсию в парсинге как одну из моделей решения. Под словом парсинг понимается автоматическая обработка данных с целью получения нужной информации программным методом. Для реализации данной модели сперва необходимо считать исходные данные, вызвать функцию, которая будет совершать поиск первого элемента (RecursionGetFirstElement), а затем функцию, которая будет делить одновременно каждую строку на первый элемент (ParallelDivideFirstRow). Одновременно запустить все потоки можно при помощи threads[j].Start(). Таким образом, происходит разбиение одной последовательной задачи на множество параллельных процессов (подзадач), что в разы сокращает время вычислений.
При каждом виде взаимодействия между собой, процессам требуется взаимная синхронизация.
Все части разделяемых данных должны быть защищены от возможности изменения их значений множеством потоков при построении многопоточного приложения. Если в любой момент к объекту обращается только один поток, можно гарантировать, что каждый метод завершится до того, как будет вызван следующий метод. Это означает, что объект всегда пребывает в активном состоянии для своих клиентов. Однако, легко можно получить ситуации, где процессор переключается на другой поток, в то время как объект находится в недействительном состоянии. Такое может произойти в случае, если несколько потоков работают одновременно. Более того, результат будет абсолютно непредсказуем, если этот поток попытается использовать тот же самый объект. Именно поэтому термин "безопасность потоков" означает постоянное поддержание членов объекта в активном состоянии при их одновременном использовании несколькими потоками.
Существует 4 вида синхронизации:
Блокировка вызывающего кода;
Неблокирующая блокировка;
Сигнализирующие конструкции;
Конструкции, ограничивающие доступ к кускам кода.
Рассмотрим 2 из них.
Blocking. Под блокировкой понимается нахождение в режиме ожидания в течение некоего времени или ожидание одним потоком завершения другого. Чаще всего они реализуется с помощью метода класса EndInvoke() асинхронных делегатов, методов Thread: Sleep() и Join() или при помощи тасков (Task) и их механизмов ожидания [4].
t.Join();
Приостанавливаем текущий поток до тех пор, пока поток t не будет завершен.
Locking. Блокировка особого вида, которая используется для того, чтобы убедиться, что определенный участок кода будет выполнять только один поток. Это необходимо с целью предоставления гарантии актуальности данных в каждый момент времени [4].
lock(matrix) {…}
Функция lock ограничивает синхронизацию потоков. Matrix является ссылкой на синхронизируемый объект. После того, как поток войдет в контекст lock, маркер блокировки (текущий объект) будет недоступным для других потоков до тех пор, пока не будет снята блокировка на выходе из контекста lock.
3. Модели решений
Существует множество параллельных программных приложений, однако, в них используется лишь малое число моделей решений, или парадигм. В частности, существует пять основных парадигм:
1) Итеративный параллелизм;
2) Рекурсивный параллелизм;
3) «Производители и потребители»;
4) «Клиенты и серверы»;
5) Взаимодействующие равные.
Рассмотрим подробнее каждый из них.
Итеративный параллелизм используется в том случае, когда в программе есть несколько процессов (часто схожих), каждый из которых содержит один или несколько циклов. Таким образом, каждый процесс является итеративной программой. Процессы программы работают одновременно над решением одной и той же задачи: они взаимодействуют и синхронизируются с помощью передачи сообщений или разделяемых переменных [5].
Рекурсивный параллелизм может применяться в случае, если в программе есть одна или несколько рекурсивных процедур, и вызовы их независимы, т.е. каждый из них работает с конкретной подзадачей из общих данных. Рекурсия часто применяется в императивных языках программирования, особенно при реализации алгоритмов типа “разделяй и властвуй” или “перебор с возвращением” (backtracking) [5].
Следует отметить, что рекурсия дуальна итерации в том смысле, что рекурсивные программы можно преобразовать в итеративные и наоборот. Однако, термин «рекурсия» означает вызов функции (или же процедуры) непосредственно из самой себя, а в итеративном параллелизме каждый процесс вычисляет результаты для подмножества данных, а затем эти результаты собираются вместе.
Производители и потребители — это взаимодействующие между собой процессы. Чаще всего они организуются в конвейер, через который передается информация. Поставщик скрывает информацию в задаче, которую надо исполнить, а с противоположной стороны располагается потребитель, отвечающий за извлечение данных и их обработку.
Клиенты и серверы. Клиент обращается к серверу и ожидает ответа. Сервер ожидает запросов от клиентов, а затем действует в соответствии с этими запросами. Затем, получив определенные данные от сервера, клиент может ими воспользоваться. Сервер может быть реализован как одиночный процесс, который не может обрабатывать одновременно несколько клиентских запросов, так и как многопоточная программа (при необходимости параллельного обслуживания запросов). Клиенты и серверы представляют собой параллельное программное обобщение процедур и их вызовов: сервер играет роль процедуры, а клиенты ее вызывают [5].
Взаимодействующие равные. Данная модель встречается в распределенных программах, где несколько процессов выполняют один и тот же код и обмениваются сообщениями для решения поставленной задачи [5].
Заключение. Благодаря многопоточности задачи можно делить на несколько подзадач и каждую из них решать независимо друг от друга, при этом максимально эффективно используя время процессора. Несмотря на это, многопоточность не всегда является правильным выбором и иногда может замедлить работу приложения. На языке С# создание и управление потоками осуществляется с помощью класса System. Threading. Thread. Одним из основных понятий, которое связанно с созданием и использованием потоков, является безопасность потоков и означает, что при одновременном использовании несколькими потоками, члены объекта всегда поддерживаются в действительном состоянии.
Изучая различные модели решений, можно сделать вывод, что метод Гаусса удобнее реализовать двумя методами распараллеливания: итеративным и рекурсивным параллелизмом.
Следует отметить, что параллельный алгоритм работает гораздо эффективнее при больших исходных данных, в то время как последовательный выполняет нахождение корней быстрее при небольших объемах данных.
Библиографический список
1. Богачёв К., Основы параллельного программирования. / К. Богачёв – М.: Бином. Лаборатория знаний, 2010. – 344 с.
2. Воеводин В., Параллельные вычисления. /В.Воеводин  - БХВ-Петербург, 2004. – 608 с.
3. Немнюгин С., Параллельное программирование для многопроцессорных вычислительных систем. / С. Немнюгин  - СПб. БХВ-Петербург, 2002. – 171с.
4. Основы многопоточности в .NET Framework. URL: https://habr.com/company/nixsolutions/blog/260745/ (дата обращения 02.06.2018) 5. Обзор области параллельных вычислений // http://www.williamspublishing.com/ [Электронный ресурс]. – Дата обращения 08.06.2018.

http://sci-article.ru/stat.php?i=1528024937