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

Достоинства: 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. Метод Гаусса

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

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

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

Заключение

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

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