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

Содержание

Введение

1. Обзор существующих методов решения задач

1.1 LU-разложение

1.2 LDU - разложение

1.3 Метод Гаусса

1.4 Метод Гаусса с выбором главного элемента

2. Основы параллельного программирования

2.1 Организация параллельных программ как системы потоков

2.2 Параллельное программирование с использованием TPL

2.2.1 Роль класса Parallel

2.2.2 Обеспечение параллелизма данных с помощью класса Parallel

2.2.3 Запросы Parallel LINQ (PLINQ)

2.2.4 Выполнение запроса PLINQ

2.2.5 Отмена запроса PLINQ

3. Алгоритммический анализ задачи

3.1 Постановка задачи, анализ исходных данных и результатов

3.2 Алгоритм обработки исходных данных

3.3 Алгоритм решения системы линейных алгебраических уравнений методом LDU-разложения

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

4. Разработка программного кода

5. Анализ результатов и выводы

Заключение

Список использованных источников

Приложение 1



Введение

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

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

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

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

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



1. Обзор существующих методов решения задач

1.1 LU-разложение

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

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

(1)

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

(2)

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

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

На втором этапе выполняют следующие действия:

1) Преобразуют правую часть по формулам прямого хода; необходимые вычисления коэффициенты берут из матрицы .

2) С помощью обратной подстановки решают систему .

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

(3)

где

(4)

где ,

Для элементы матриц находятся по формулам

где

где

1.2 LDU - разложение

Можно доказать, что существование LU-разложения для матрицы гарантирует, что и матрица допускает LU-разложение: главные миноры матриц и совпадают. Из разложения

(7)

при матрице нижнетреугольной и -- верхнетреугольной следует, что

(8)

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

(9)

при -- верхнетреугольной с единицами на главной диагонали.

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

(10)

Компактная схема LDU - разложения:

(11)

1.3 Метод Гаусса

Согласно источнику [5], вычисления с помощью метода Гаусса (который называют также методом последовательного исключения неизвестных) состоят из двух основных этапов: прямого хода и обратного хода. Прямой ход метода заключается в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с треугольной матрицей. На этапе обратного хода производят вычисления значений неизвестных. Рассмотрим простейший вариант метода Гаусса, называемый схемой единственного деления.

Прямой ход метода 1-й шаг. Предположим, что . Поделим первое уравнение на этот элемент, который назовем ведущим элементом первого шага:

(12)

Остальные уравнения системы (1) запишем в виде

(13)

где .

Система (1) имеет матрицу вида:

Дальше осуществляется работа с укороченной системой, т.к. входит только в 1-ое уравнение

(14)

2-й шаг. На этом шаге исключается неизвестное из уравнений с номерами . Если ведущий элемент второго шага , то из укороченной системы аналогично исключается неизвестное и получается матрица коэффициентов такого вида:



Это система с верхней треугольной матрицей.

Обратный ход метода. Из последнего уравнения системы (1) находим , из предпоследнего из первого уравнения - .

Общая формула для вычислений:

(15)

(16)

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

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

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

1.4 Метод Гаусса с выбором главного элемента

Из источника [5] сказано, что может оказаться так, что система (1) имеет единственное решение, хотя какой либо из миноров матрицы равен нулю. Заранее неизвестно, что все угловые миноры матрицы не равны нулю. В этом случае можно использовать метод Гаусса с выбором главного элемента.

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

Пусть дана система второго порядка

Предположим, что , тогда переставим уравнения

и применяем первый шаг прямого хода метода Гаусса. В этом случае имеет место перенумерация строк.

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

При , на первом шаге вместо неизвестного исключают :

К этой системе применяется первый шаг прямого хода метода Гаусса.

Поиск главного элемента по всей матрице заключается в совместном применении методов 1 и 2. Всё это приводит к уменьшению вычислительной погрешности, но может замедлить процесс решения задачи.

2. Основы параллельного программирования

2.1 Организация параллельных программ как системы потоков

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

Существование нескольких одновременно выполняемых потоков приводит к появлению дополнительных соотношений, которые должны выполняться для величин временных траекторий потоков. Согласно [7], возможные типовые варианты таких соотношений на примере двух потоков p и q состоят в следующем (см. рисунок 1):

Рисунок 1 - Варианты взаиморасположения траекторий одновременно исполняемых потоков (отрезки линий изображают фрагменты командных последовательностей потоков)

- выполнение потоков осуществляется строго последовательно, т. е. поток начинает свое выполнение только после полного завершения потока (однопрограммный режим работы ЭВМ - см. рисунок 1 пункт а);

- выполнение потоков может осуществляться одновременно, но в каждый момент времени могут исполняться команды только какого-либо одного потока (режим разделения времени или многопрограммный режим работы ЭВМ - см. рисунок 1 пункт б);

- параллельное выполнение потоков, когда одновременно могут выполняться команды нескольких потоков (данный режим исполнения потоков осуществим только при наличии в вычислительной системе нескольких процессоров - см. рисунок 1 пункт в).

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

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

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

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

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

В котором следует положить , если команда получена из потока (иначе ). Порядок следования команд потоков в должен соответствовать порядку расположения этих команд в исходных потоках

где есть команда потока , соответствующая команде в .

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

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

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

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

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

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

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

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

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

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

2.2 Параллельное программирование с использованием TPL

Начиная с версии .NET 4.0, в Microsoft ввели новый подход к разработке многопоточных приложений, предусматривающий использование библиотеки параллельного программирования, которая называется TPL (Task Parallel Library -- библиотека параллельных задач). С помощью типов из System.Threading.Tasks можно строить мелкомодульный масштабируемый параллельный код без необходимости напрямую иметь дело с потоками или пулом потоков. Однако это не означает, что разработчик не будет применять типы из System.Threading при работе с TPL. В реальности эти два инструментальных набора могут вполне естественно работать вместе. Это особенно верно потому, что, согласно [8], пространство имен System.Threading по-прежнему предоставляет большинство примитивов синхронизации, таких как Monitor, Interlocked и т.д. В итоге работать с TPL предпочтительнее, чем с исходным пространством имен System.Threading, учитывая то, что те же самые задачи могут быть решены гораздо проще. Общий обзор архитектуры параллельного программирования представлен на рисунке 2.

Рисунок 2 - Общий вид архитектуры параллельного программирования в .NET Framework 4

2.2.1 Роль класса Parallel

Ключевым классом в TPL является System.Threading.Tasks.Parallel. Этот класс поддерживает набор методов, которые позволяют осуществлять итерацию по коллекции данных, т.е. по объекту, реализующему интерфейс IEnumerable<T>, в параллельном режиме. В документации .NET Framework 4.5 SDK указано, что упомянутый класс поддерживает два основных статических метода, Parallel.For() и Parallel.ForEach(), каждый из которых имеет множество перегруженных версий.

Эти методы позволяют создавать тело операторов кода, которое будет выполняться в параллельном режиме. Концептуально эти операторы представляют собой логику того же рода, которая была бы написана в нормальной циклической конструкции (с применением ключевых слов for и foreach языка С#). Преимущество заключается в том, что класс Parallel самостоятельно будет брать потоки из пула потоков (и управлять параллелизмом). Оба метода требуют указания совместимого с IEnumerable или IEnumerable<T> контейнера, хранящего данные, которые нужно обработать в параллельном режиме. Контейнер может быть простым массивом, необобщенной коллекцией (такой как ArrayList), обобщенной коллекцией (наподобие List<T>) или результатом запроса LINQ. Вдобавок с помощью делегатов System.Func<T> и System.Action<T> понадобится задать целевой метод, который будет вызываться для обработки данных. Делегат Func<T> представляет метод, который возвращает значение и принимает различное количество аргументов. Делегат Action<T> очень похож на Func<T> в том, что позволяет задавать метод, принимающий несколько параметров. Однако Action<T> указывает метод, который может возвращать только void. Хотя можно было бы вызывать методы Parallel.For() и Parallel.ForEach () и передавать им строго типизированный объект делегата Func<T> или Action<T>, задача программирования упрощается за счет использования подходящих анонимных методов и лямбда-выражений языка С#.



2.2.2 Обеспечение параллелизма данных с помощью класса Parallel

Библиотека TPL также может применяться для запуска любого количества асинхронных задач с помощью метода Parallel.Invoke(). Этот подход немного проще, чем использование делегатов или типов из пространства имен System.Threading.

Тем не менее, если нужна более высокая степень контроля над выполняемыми задачами, следует отказаться от Parallel.Invoke () и напрямую работать с классом Task.

Метод Parallel.Invoke () ожидает в качестве параметра массива делегатов Action, который передается неявно с помощью лямбда-выражения. Хотя вывод идентичен, преимущество библиотеки TPL состоит в использовании всех доступных процессоров машины для вызова каждого метода параллельно, если это возможно.

2.2.3 Запросы Parallel LINQ (PLINQ)

Существует ещё один способ встраивания параллельных задач в приложения .NET. При желании можно использовать набор расширяющих методов, которые позволяют конструировать запрос LINQ, распределяющий свою нагрузку по параллельным потокам (если это возможно). Неудивительно, что запросы LINQ, которые спроектированы для параллельного выполнения, называются запросами Parallel LINQ (PLINQ). Подобно параллельному коду, написанному с использованием класса Parallel, в PLINQ имеется опция игнорирования запроса на обработку коллекции в параллельном режиме. Согласно [8], библиотека PLINQ оптимизирована во многих отношениях, включая определение того, не будет ли запрос на самом деле эффективнее выполняться в синхронном режиме. Во время выполнения PLINQ анализирует общую структуру запроса, и, если есть вероятность, что запрос выиграет от параллелизма, он будет выполнен параллельно. Однако если это ухудшит производительность, PLINQ выполнит запрос последовательно. Если возникает выбор между потенциально дорогостоящим (в смысле ресурсов) параллельным алгоритмом и недорогим последовательным, предпочтение по умолчанию отдается последовательному алгоритму. Необходимые расширяющие методы находятся в классе ParallelEnumerable пространства имен:

- AsParallel() указывает, что остаток запроса должен быть выполнен параллельно, если это возможно;

- WithCancellation() указывает, что PLINQ должен периодически следить за состоянием предоставленного признака отмены и, если понадобится, отменять выполнение;

- WithDegreeOfParallelism() указывает максимальное количество процессоров, которое PLINQ должен использовать для распараллеливания запроса;

- ForAll() позволяет обрабатывать результаты параллельно, без предварительного слияния с потоком потребителя, как это происходит при перечислении результата LINQ посредством ключевого слова foreach.

2.2.4 Выполнение запроса PLINQ

Чтобы заставить TPL выполнить этот запрос в параллельном режиме (по возможности), для этого придется воспользоваться расширяющим методом AsParallel(). Однако при включенном вызове AsParallel() библиотека TPL попытается распределить рабочую нагрузку по всем доступным процессорам.

2.2.5 Отмена запроса PLINQ

С помощью объекта CancellationTokenSource можно заставить запрос PLINQ прекращать обработку при определенных условиях (обычно из-за вмешательства пользователя). Для этого потребуется объявить объект CancellationTokenSource, определить условия, когда вызывается метод Cancel() на этом объекте.

Теперь необходимо информировать запрос PLINQ о том, что он должен ожидать входящего запроса на отмену выполнения, добавив в цепочку расширяющий метод WithCancellation () и передав признак отмены. Кроме того, этот запрос PLINQ нужно поместить в контекст try/catch и обработать возможные исключения.



3. Алгоритммический анализ задачи

3.1 Постановка задачи, анализ исходных данных и результатов

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

Исходными данными являются:

- матрица ;

- матрица ;

Исходные данные должны удовлетворять следующим условиям:

- матрица квадратная;

- количество строк матриц и одинаково;

- матрица должна быть невырожденной.

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

- ввод исходных данных из файла с форматом .xlsx;

- вычисление системы распределенным и линейным -разложением и распределенным методом Гаусса;

- вывод результатов вычисления и времени выполнения.

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



3.2 Алгоритм обработки исходных данных

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

3.3 Алгоритм решения системы линейных алгебраических уравнений методом -разложения

Данный метод является прородителем метода Гаусса, однако он используется по сей день по двум причинам:

- существуют формы данного метода, которые идеально поддаются распределению, что позволяет при его реализации использовать все ресурсы ЭВМ;

- при изменении значений вектора-столбца свободных членов ?? нет необходимости полностью повторять вычисления, ведь матрицы L и U от этого не изменяются, что позволяет сэкономить время на вычислениях [4].

Данный алгоритм можно разделить на 4 составляющие части:

- нахождение матриц L, D и U;

- нахождение вектора-столбца Z;

- нахождение вектора-столбца Y;

- нахождение вектора-столбца X.

Соответствующие блок-схемы изображены на рисунках 3-7 и в приложении В.

Рисунок 3 - Общая схема метода LDU-разложения

Рисунок 4 - Детальная схема нахождения матриц L, D и U

Рисунок 5 - Детальная схема метода нахождения вектора-столбца Z

Рисунок 6 - Детальная схема метода нахождения вектора-столбца Y

Рисунок 7 - Детальная схема метода нахождения вектора-столбца X



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

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

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

Рисунок 8 - Детальная схема метода Гаусса (два этапа)



4. Разработка программного кода

Функции, предназначенные работы с файлами вынесены в класс Data, который определен в файле Data.cs. Список функций и их описание отображено в таблице 1.

Таблица 1 - Функции файла Data.cs

Функция	Описание
OpenFile	Открытие выбранного файла в приложении MS Excel
ReadFile	Считывание данных из .xlsx документа
GetCellValue	Получение данных из ячейки .xlsx документа

Для хранения методов решения системы линейных алгебраических уравнений создан файл MatrixDecomposition.cs. Блок-схемы алгоритмов приведены в приложении Б. Список функций и их описание приведен в таблице 2.

Таблица 2 - Функции файла MatrixDecomposition.cs

Функция	Описание
LDU	Линейное решение СЛАУ с помощью -разложения
LDUParallel	Параллельное решение СЛАУ с помощью -разложения
GaussianElimination	Параллельное решение СЛАУ методом Гаусса

Главная форма приложения описана в файле MainForm.cs, MainForm.Designer.cs и MainForm.resx. Главная форма отображена на рисунках 9 - 10.

Файл MainForm.Designer.cs создается автоматически. В нем хранится описание элементов управления и их свойтва.

Также автоматически создается файл MainForm.resx. Это файл ресурсов, необходимый для корректной работы формы.

В файле MainForm.cs находятся обработчики событий и некоторые функции для манипулирования данными. Полный список функций приведен в таблице 3.

Таблица 3 - Функции файла MainForm.cs

Функция	Описание
Form	Инициализация формы
btnRead_Click	Обработка события нажатия на кнопку «Считать матрицу из файла»
btnInput_Click	Обработка события нажатия на кнопку «Ввод»
btnResult_Click	Обработка события нажатия на кнопку «Рассчет»
btnRandom_Click	Обработка события нажатия на кнопку «Рандомная матрица размерностью»
OutputResults	Вывод результатов

Рисунок 9 - Главное окно программы

Рисунок 10 - Вкладка «Корни СЛАУ»

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

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



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

- время вычисления;

- массив значений ;

В классе также присутствуют следующие методы:

- IsCorrected();

- Clear();

Метод IsCorrected() комплексно проверяет корректность всей системы линейных алгебраических уравнений:

- матрицы и не пустые;

- матрица является квадратной

- количество строк матрицы равняется количеству элементов массива ;

Метод Clear() предназначен для очистки матриц и .



5. Анализ результатов и выводы

Вычислим несколько СЛАУ с большим количеством неизвестных.

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

- процессор Intel(R) Core(TM) i5-4200M CPU @ 2.50GHz 2.50GHz;

- 8.00 ГБ ОЗУ;

- ОС Windows 10 Pro;

Используемый процессор имеет 2 ядра и 4 логических процессора. Это позволяет задействовать в программе параллельность.

Поочередно вычисляя каждую сгенерированную СЛАУ получили время выполнения каждого метода, которое отображено в таблице 4.

Таблица 4 - Время выполнения вычислений

	Линейное -разложение	Параллельное -разложение	Параллельный метод Гаусса
	00:00:10.2831410	00:00:11.6724780	00:00:05.8111088
	00:01:13.1950061	00:01:22.3137263	00:00:20.3733056
	00:04:15.4319632	00:04:56.8671661	00:00:57.6410400
	00:13:58.8525794	00:17:41.3231619	00:02:31.3233725
	00:25:05.1613303	00:28:08.9888109	00:04:59.6103004

Во время выполнения линейных вычислений процессор нагружается до , оперативная память до 820 МБ. Состояние процессора отображено на рисунке 11.

Рисунок 11 - Использование ЦП и ОП при линейном решении СЛАУ размерностью

Во время выполнения параллельных вычислений -разложением процессор нагружается до , оперативная память до 825 МБ. Состояние процессора отображено на рисунке 12.



Рисунок 12 -Использование ЦП и ОП при параллельном вычислении СЛАУ -разложением

Во время выполнения параллельных вычислений методом Гаусса процессор нагружается до оперативная память до 970 МБ. Состояние процессора отображено на рисунке 13.



Рисунок 13 - Использование ЦП при параллельном вычислении СЛАУ методом Гаусса

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



Заключение

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

- Распределенное -разложение;

- Распределенный метод Гаусса;

- Линейное -разложение.

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

Помимо основного функционала, была реализована интеграция с приложением Microsoft Office Excel.

Разработка программы производилась в интегрированной среде разработки Microsoft Visual Studio Community 2015 с использованием платформы .NET Framework версии 4.5.2 на языке программирования высокого уровня - C#.

Для интегрирования разрабатываемой программы с Microsoft Excel были использованы следующие модули:

- DocumentFormat.OpenXML;

- Microsoft.Interop.Office.Excel.

Поставленная задача курсового проекта выполнена в полном объеме.



Список использованных источников

1. Численные методы решения СЛАУ [Электронный ресурс]. - Режим доступа: http://mathhelpplanet.com/static.php?p=chislennyye-metody-resheniya-slau - Дата доступа: 02.04.2017.

2. LU-разложение [Электронный ресурс]. - Режим доступа: https://ru.wikipedia.org/wiki/LU-разложение - Дата доступа: 02.04.2017.

3. Task Parallel Library (TPL) [Электронный ресурс]. - Режим доступа: https://msdn.microsoft.com/ru-ru/library/dd460717(v=vs.110).aspx - Дата доступа: 08.04.2017.

4. Основы параллельного программирования [Электронный ресурс]. - Режим доступа: http://www.hpcc.unn.ru/file.php?id=423 - Дата доступа: 13.05.2017.

5. Основы параллельного программирования [Электронный ресурс]. - Режим доступа: http://files.pilotlz.ru/pdf/cC0939-9-ch.pdf - Дата доступа: 13.05.2017

6. Parallel Programming in the .NET Framework [Электронный ресурс]. - Режим доступа: https://msdn.microsoft.com/ru-ru/library/dd460693.aspx - Дата доступа: 13.05.2017.

7. Гергель В.П. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие / Гергель В.П., Стронгин, Р.Г. - Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. 184 с.

8. Куксенко С. П. Итерационные методы решения системы линейных алгебраических уравнений с плотной матрицей./ Куксенко С. П., Газизов Т. Р. -- Томск: Томский государственный университет, 2007. -- 208 с.



Приложение 1

Исходный код программы

Program.cs

using System;

using System.Collections.Generic;

using System.Linq;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace SLAEParallelSolver

{

static class Program

{

/// <summary>

/// Главная точка входа для приложения.

/// </summary>

[STAThread]

static void Main()

{

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false);

Application.Run(new Form());

}

}

}

Data.cs

using System;

using System.Collections.Generic;

using System.Linq;

using DocumentFormat.OpenXml.Packaging;

using DocumentFormat.OpenXml.Spreadsheet;

using MExcel = Microsoft.Office.Interop.Excel;

namespace SLAY

{

static class Data

{

public static void OpenFile(string fileName)

{

MExcel.Application ExcelApp = new MExcel.Application();

MExcel.Workbook workbook = ExcelApp.Workbooks.Open(fileName, 0, true);

ExcelApp.Visible = true;

ExcelApp.UserControl = true;

}

public static void ReadFile(string fileName, SystemOfLinearEquations SLE)

{

using (SpreadsheetDocument document = SpreadsheetDocument.Open(fileName, false))

{

var sheets = document.WorkbookPart.Workbook.Sheets.Elements<Sheet>();

Worksheet worksheetMatrix = (document.WorkbookPart.GetPartById(sheets.First().Id.Value) as WorksheetPart).Worksheet;

IEnumerable<Row> matrixRows = worksheetMatrix.GetFirstChild<SheetData>().Descendants<Row>();

int matrixLength = matrixRows.Count();

SLE.A = new double[matrixLength, matrixLength];

for (int i = 0; i < matrixLength; i++)

{

IEnumerable<Cell> cells = matrixRows.ElementAt(i).Descendants<Cell>();

if (cells.Count() == matrixLength)

for (int j = 0; j < cells.Count(); j++)

{

SLE.A[i, j] = GetCellValue(document, cells.ElementAt(j));

}

}

Worksheet worksheetArray = (document.WorkbookPart.GetPartById(sheets.Last().Id.Value) as WorksheetPart).Worksheet;

IEnumerable<Row> arrayRows = worksheetArray.GetFirstChild<SheetData>().Descendants<Row>();

int arrayLength = arrayRows.Count();

if (arrayLength != matrixLength)

throw new Exception("Количество строк матрицы B не соответствует кол-ву строк матрицы A");

SLE.B = new double[arrayLength];

for (int i = 0; i < arrayLength; i++)

{

Cell cell = arrayRows.ElementAt(i).Descendants<Cell>().First();

SLE.B[i] = GetCellValue(document, cell);

}

}

}

private static double GetCellValue(SpreadsheetDocument doc, Cell cell)

{

string value = cell.CellValue.InnerText;

return double.Parse(value);

}

}

}

MainForm.cs

using System;

using System.Data;

using System.Linq;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace SLAY

{

public partial class MainForm : Form

{

SystemOfLinearEquations SLE = new SystemOfLinearEquations();

public int n = 0;

public int i;

public int j;

public MainForm()

{

InitializeComponent();

}

private void btnRead_Click(object sender, EventArgs e)

{

if (openFileDialog.ShowDialog() == DialogResult.OK)

{

string fileName = openFileDialog.FileName;

Task performTask = Task.Run(() =>

{

Data.OpenFile(openFileDialog.FileName);

Data.ReadFile(fileName, SLE);

}).ContinueWith((task) =>

{

if (SLE.IsCorrected())

btnResult.Enabled = true;

else

{

MessageBox.Show("Система линейных алгебраических уравнений задана неверно", "Некорректные данные", MessageBoxButtons.OK, MessageBoxIcon.Hand);

SLE.Clear();

}

}, TaskScheduler.FromCurrentSynchronizationContext());

}

}

private void btnInput_Click(object sender, EventArgs e)

{

string[] str = richTextBox1.Lines;

string[] strB = richTextBox2.Lines;

n = str.Length;

SLE.A = new double[n, n];

SLE.B = new double[n];

for (int i = 0; i < n; i++)

{

int[] m = str[i].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s)).ToArray();

int[] k = strB[i].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s)).ToArray();

for (int j = 0; j < n; j++)

SLE.A[i, j] = m[j];

SLE.B[i] = k[0];

}

richTextBox1.Clear();

richTextBox2.Clear();

}

private void btnResult_Click(object sender, EventArgs e)

{

dgvResults.Rows.Clear();

Task performTask = Task.Run(() =>

{

MatrixDecomposition.LDU(SLE);

MatrixDecomposition.LDUParallel(SLE);

MatrixDecomposition.GaussianEliminationParallel(SLE);

MessageBox.Show("Решение системы выполнено!", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Information);

}).ContinueWith((task) => OutputResults(), TaskScheduler.FromCurrentSynchronizationContext());

}

private void OutputResults()

{

for (int i = 0; i < SLE.LDU.X.Length; i++)

dgvResults.Rows.Add(SLE.LDU.X[i], SLE.LDUParallel.X[i], SLE.GaussianEliminationParallel.X[i]);

tslTimeLDLT.Text = $"LDU: {SLE.LDU.Time.Elapsed}";

tslTimeLDLTParallel.Text = $"Параллельное LDU: {SLE.LDUParallel.Time.Elapsed}";

tslTimeGEParallel.Text = $"Параллельный метод Гаусса: {SLE.GaussianEliminationParallel.Time.Elapsed}";

}

private void btnRandom_Click(object sender, EventArgs e)

{

n = Convert.ToInt32(textBox1.Text);

SLE.A = new double[n, n];

SLE.B = new double[n];

Random rnd = new Random();

for (i = 0; i < n; i++)

{

for (j = 0; j < n; j++)

{

SLE.A[i,j] = rnd.Next(-100, 101);

}

SLE.B[i] = rnd.Next(-100, 101);

}

}

}

}

MatrixDecomposition.cs

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace SLAY

{

class MatrixDecomposition

{

// Линейное решение СЛАУ с помощью LDU - разложения

public static double[] LDU(SystemOfLinearEquations SLE)

{

SLE.LDU = new Result();

double[,] A = SLE.A;

double[] B = SLE.B;

int n = A.GetLength(0);

double[] D = new double[n];

double[,] L = new double[n, n];

double[,] U = (double[,])(A.Clone());

int i, j, k;

double sum;

for (i = 0; i < n; i++)

{

for (j = i; j < n; j++)

for (k = j; k < n; k++)

L[k, j] = U[k, j] / U[j, j];

for (j = i + 1; j < n; j++)

for (k = i; k < n; k++)

U[j, k] = U[j, k] - L[j, i] * U[i, k];

D[i] = U[i, i];

for (j = i; j < n; j++)

{

U[i, j] = U[i, j] / D[i];

}

}

Stopwatch time = SLE.LDU.Time = Stopwatch.StartNew();

double[] Z = new double[n];

for (i = 0; i < Z.Length; i++)

{

sum = 0;

for (j = 0; j < i; j++)

sum += L[i, j] * Z[j];

Z[i] = B[i] - sum;

}

double[] Y = new double[n];

for (i = 0; i < Y.Length; i++)

{

Y[i] = Z[i] / D[i];

}

double[] X = new double[n];

for (i = n - 1; i >= 0; i--)

{

sum = 0;

for (j = i; j < n; j++)

sum += U[i, j] * X[j];

X[i] = Y[i] - sum;

}

SLE.LDU.X = X;

time.Stop();

return X;

}

// Параллельное решение СЛАУ с помощью LDU - разложения

public static double[] LDUParallel(SystemOfLinearEquations SLE)

{

SLE.LDUParallel = new Result();

double[,] A = SLE.A;

double[] B = SLE.B;

int n = A.GetLength(0);

double[] D = new double[n];

double[,] L = new double[n, n];

double[,] U = (double[,])(A.Clone());

double sum;

for (int i = 0; i < n; i++)

for (int j = i; j < n; j++)

L[j, i] = U[j, i] / U[i, i];

for (int k = 0; k < n; k++)

{

for (int i = k; i < n; i++)

for (int j = i; j < n; j++)

L[j, i] = U[j, i] / U[i, i];

for (int i = k + 1; i < n; i++)

for (int j = k; j < n; j++)

U[i, j] = U[i, j] - L[i, k] * U[k, j];

D[k] = U[k, k];

for (int j = k; j < n; j++)

{

U[k, j] = U[k, j] / D[k];

}

}

Stopwatch time = SLE.LDUParallel.Time = Stopwatch.StartNew();

double[] Z = new double[n];

for (int i = 0; i < Z.Length; i++)

{

sum = 0;

for (int k = 0; k < i; k++)

sum += L[i, k] * Z[k];

Z[i] = B[i] - sum;

}

double[] Y = new double[n];

Parallel.For(0, Y.Length, i => Y[i] = Z[i] / D[i]);

double[] X = new double[n];

for (int i = n - 1; i >= 0; i--)

{

sum = 0;

for (int k = i; k < n; k++)

sum += U[i, k] * X[k];

X[i] = Y[i] - sum;

}

SLE.LDUParallel.X = X;

time.Stop();

return X;

}

// Параллельное решение СЛАУ методом Гаусса

public static double[] GaussianEliminationParallel(SystemOfLinearEquations SLE)

{

SLE.GaussianEliminationParallel = new Result();

double[,] A = (double[,])SLE.A.Clone();

double[] B = (double[])SLE.B.Clone();

Stopwatch time = SLE.GaussianEliminationParallel.Time = Stopwatch.StartNew();

int n = B.Length;

for (int p = 0; p < n; p++)

{

// Нахождение строки и последующий обмен строк

int max = p;

for (int i = p + 1; i < n; i++)

{

if (Math.Abs(A[i, p]) > Math.Abs(A[max, p]))

max = i;

}

if (A.GetLength(0) > 1000)

Parallel.For(0, A.GetLength(0), (i) =>

{

double temp = A[p, i];

A[p, i] = A[max, i];

A[max, i] = temp;

});

else

for (int i = 0; i < A.GetLength(0); i++)

{

double temp = A[p, i];

A[p, i] = A[max, i];

A[max, i] = temp;

}

double t = B[p];

B[p] = B[max];

B[max] = t;

// Проверка матрицы на вырожденность

if (Math.Abs(A[p, p]) <= 1e-10)

{

throw new ArithmeticException("Матрица является вырожденной или почти вырожденной");

}

// Преобразование матриц A и B

if (n - (p + 1) > 1000)

Parallel.For(p + 1, n, (i) =>

{

double alpha = A[i, p] / A[p, p];

B[i] -= alpha * B[p];

for (int j = p; j < n; j++)

A[i, j] -= alpha * A[p, j];

});

else

for (int i = p + 1; i < n; i++)

{

double alpha = A[i, p] / A[p, p];

B[i] -= alpha * B[p];

for (int j = p; j < n; j++)

A[i, j] -= alpha * A[p, j];

}

}

// Обратный ход

double[] X = new double[n];

for (int i = n - 1; i >= 0; i--)

{

double sum = 0;

if (n - (i + 1) > 1000)

{

List<double> elementsToSum = new List<double>();

for (int j = i + 1; j < n; j++)

{

elementsToSum.Add(A[i, j] * X[j]);

}

sum = elementsToSum.AsParallel().Sum();

elementsToSum.Clear();

}

else

for (int j = i + 1; j < n; j++)

{

sum += (A[i, j] * X[j]);

}

X[i] = (B[i] - sum) / A[i, i];

}

SLE.GaussianEliminationParallel.X = X;

time.Stop();

return X;

}

}

}

SystemOfLinearEquations.cs

using System;

using System.Diagnostics;

namespace SLAY

{

class Result

{

public Stopwatch Time { get; set; }

public double[] X { get; set; }

}

class SystemOfLinearEquations

{

public double[,] A

{ get; set; }

public double[] B

{ get; set; }

public Result LDU { get; set; }

public Result LDUParallel { get; set; }

public Result GaussianEliminationParallel { get; set; }

public bool IsCorrected()

{

bool isCorrected = false;

if (A.GetLength(0) == A.GetLength(1))

if (A.GetLength(0) == B.Length)

isCorrected = true;

return isCorrected;

}

public void Clear()

{

A = null;

B = null;

GC.Collect(2, GCCollectionMode.Optimized);

}

}

}

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

...