Определение собственных чисел и собственных векторов с использованием технологии CUDA

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

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение

высшего образования

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

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

(наименование института полностью)

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

(наименование кафедры полностью)

КУРСОВАЯ РАБОТА

по дисциплине (учебному курсу) «Технологии массивно-параллельных вычислений»

на тему«Определение собственных чисел и собственных векторов с использованием технологии CUDA»

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

С.А. Скоков

Руководитель

А.П.Тонких

Тольятти, 2020



ЗАДАНИЕ

на выполнение курсовой работы

Студент 4 курса группы МОп-1702а Скоков Сергей Александрович

1. Тема «Определение собственных чисел и собственных векторов с использованием технологии CUDA.»

2. Срок сдачи студентом законченной курсовой работы «25» декабря 2020

3. Исходные данные: программа должна быть написанана языке с++ с использованием технологии CUDA, последовательный алгоритм решения задачи.

4. Содержание курсовой работы (перечень подлежащих разработке вопросов, разделов): постановка задачи на исследование, проектирование и разработка последовательной и параллельных программ, анализ эффективности работы последовательного и параллельного алгоритмов.

5. Ориентировочный перечень графического и иллюстративного материала: блок-схема степенного метода нахождения собственных значений и векторов, пример последовательного кода с основными вычислениями,пример параллельного кода с основными вычислениями с использование технологии OpenMP, блок-схема параллельного степенного метода нахождения собственных значений и векторов, пример параллельного CUDA кода с основными вычислениями, результаты тестирования программ,график эффективности работы алгоритмов.

6. Рекомендуемая учебно-методические материалы:

Долгополов Д.В. Методы нахождения собственных значений и собственных векторов матриц / Д.В. Долгополов. -Санкт-Петербург: СПбГТИ(ТУ), 2005. - 39с.Фаддеев Д.К. Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н. Фаддеева. - Москва: Физматгиз, 1963. - 734с.Параллельные вычисления на GPU. Архитектура и программная модель CUDA: Учебное пособие / Боресков А.В., Марковский Н.Д., Микушин Д.Н. и др. - Москва: МГУ, 2012. - 336 с. NVIDIADeveloperDocumentation // Электрон. дан. - Режим доступа https://docs.nvidia.com



Содержание

Введение

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

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

1.2 Постановка задачи нахождения собственных значений и собственных векторов

1.3 Алгоритм решения частичной проблемы поиска собственных значений и собственных векторов

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

2.1 Реализация последовательной программы

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

2.3 Реализация параллельных программ с использованием технологий OpenMP и CUDA

3. Анализ эффективности работы последовательного и параллельного алгоритмов

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

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

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

Заключение

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

Приложение А



Введение

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

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

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

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

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

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

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

Задачи, которые необходимо решить для достижения указанной цели, это:

1) выбрать метод решения данной задачи, рассмотрев математическое описание задачи и существующие методы решения;

2) рассмотреть технологии параллельного программирования и выбрать технологии, которые используем при разработке;

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

4) провести изучение эффективности работы последовательной и параллельной программы, сравнить их и сделать выводы;

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

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

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

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



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

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

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

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

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

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

1.2 Постановка задачи нахождения собственных значений и собственных векторов

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

Понятно, что методы решения частичной проблемы собственных значений должны быть более простыми. Мы рассмотрим примеры именно этих методов. Но для начала дадим определение собственному значению и собственным вектору матрицы А, где A-заданная квадратная матрица размерностью nЧn.

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

Собственным значением матрицы A называется такое число л, что для некоторого ненулевого вектора x имеет место равенство 1.1:



Любой ненулевой вектор x, удовлетворяющий данному равенству, называется собственным вектором матрицы А, соответствующим собственному значению л.

Условием существования собственных значений матрицы является требование 1.2:

где E-единичная матрица.

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

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

где л₁,л_2,… л_k- корни многочлена кратности n₁ , n₂ ,…, n_k

1.3 Алгоритм решения частичной проблемы поиска собственных значений и собственных векторов

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

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

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

где - собственные вектора. Предположим, что максимальное по модулю собственное число единственно.

Умножим уравнение (1.1) на исходную матрицу Аи получим 1.5:

Проведя умножение k раз, получим 1.6:

Выполнив преобразования в 1.6, получим 1.7:

Поскольку л₁-самое большое по модулю число, то все члены в 1.6, кроме первого, стремятся к 0 при k стремящейся к бесконечности. Из данного утверждения можно сделать вывод, что по сравнению с первым членом суммы при росте значения k все остальные члены суммы уменьшаются, и вектор близок к собственному вектору .

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

1) выбрать вектор начального приближения;

2) построить приближение по формулам 1.8 и 1.9:

3)

где a_n+1 выбирается из условия

4) повторять итерации до тех пор, пока не будет достигнуто условие сходимости 1.10:

где е - заданная точность;

5) последнее приближение x_n+1является собственным вектором, а собственное значение вычисляется по формуле 1.11:

поскольку .

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

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

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

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



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

2.1 Реализация последовательной программы

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

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

1) сгенерировать матрицу размером nЧn;

2) сгенерировать вектор начального приближения;

3) вычислить норму вектора;

4) построить приближение до тех пор, не достигнем заданной точности.

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

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

С полным кодом программы можно ознакомиться в приложении А под именем «Posl_Stepennoy_Method.cpp».



Рисунок 2.1 - Блок-схема степенного метода нахождения собственных значений и векторов

Рисунок 2.2 - Пример последовательного кода с основными вычислениями

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

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

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

1) MPI.

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

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

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

2) OpenMP.

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

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

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

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

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

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

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

3) CUDA.

CUDA - это программно-аппаратная архитектура параллельных вычислений на графических процессорах (GPU) от NVIDIA, позволяющая многократно увеличить вычислительную производительность за счёт параллельных вычислений на ядрах GPU

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

Кроме того, CUDA открывает некоторые аппаратные возможности, недоступные из графических API, такие как разделяемая память. Это память небольшого объёма (16 килобайт на мультипроцессор), к которой имеют доступ блоки потоков. Она позволяет кэшировать наиболее часто используемые данные и может обеспечить более высокую скорость, по сравнению с использованием текстурных выборок для этой задачи. Что, в свою очередь, снижает чувствительность к пропускной способности параллельных алгоритмов во многих приложениях. Например, это полезно решения задач линейной алгебры

Основные недостатки CUDA: отсутствие поддержки рекурсии для выполняемых функций. Минимальная ширина блока в 32 потока.Закрытая архитектура CUDA, принадлежащая Nvidia.

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

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

1) cublasSnrm2(cublasHandle_thandle, intn, constfloat *x, intincx, float *result) - эта функция вычисляет евклидову норму вектораx.

Параметры:handle - дексрипторконтекстабиблиотеки CuBlas , n- количество элементов в векторе x , x -передаваемый вектор, incx- шаг между последовательными элементами вектора x , result-результат.

2) cublasSscal(cublasHandle_thandle, intn, constfloat *alpha, float *x, intincx)-эта функция масштабирует вектор x на скаляр б и заменяет его результатом.

Параметры: alpha - скаляр, используемый для умножения, остальные по аналогии с первой приведенной функцией.

3) cublasSgemv(cublasHandle_t handle, cublasOperation_t trans, int m, int n , const float *alpha, const float *A, int lda, const float *x,int incx, const float *beta, float *y, int incy) - этафункциявыполняетумножениематрицынавектор.

Параметры: m,n - количество строк и столбцов матрицы Aсоответственно, A-матрица,lda - ведущее измерение двумерного массива, используемого для хранения матрицы A,incx-шаг между последовательными элементами x, остальные параметры по аналогии.

4) cublasSaxpy(cublasHandle_thandle, intn, constfloat *alpha, float *x, intincx, float *y, intincy) -эта функция умножает вектор x на скаляр б и добавляет его к вектору y, перезаписывая последний вектор результатом.

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

5) cublasScopy(cublasHandle_t handle, int n, const float *alpha, float *x, int incx, float *y, int incy) - эта функция копирует вектор x в вектор y.

6) cublasSdot(cublasHandle_t handle, int n, const float *alpha, float *x, int incx, float *y, int incy, float *result) - эта функция вычисляет скалярное произведение векторов x и y.

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

2.3 Реализация параллельных программ с использованием технологийOpenMP и CUDA

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

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

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

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

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

Рисунок 2.3 - Пример параллельного кода с основными вычислениями с использование технологии OpenMP

С полным кодом программы можно ознакомиться в приложении А под именем «OpenMP_Stepennoy_Method.cpp».

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

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

1) cгенерировать матрицу размером nЧn;

2) cгенерировать вектор начального приближения;

3) вычислить норму вектора;

4) построить приближение;

5) вычислить норму приближения;

6) строить приближение до тех пор, не достигнем заданной точности.

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

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

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

Пример кода с основными вычислениями метода приведён на рисунке 2.5. В программе предусмотрена возможность замера времени выполнения алгоритма с использование функции cudaEventElapsedTime.

Рисунок 2.5 - Пример параллельного CUDA кода с основными вычислениями

С полным кодом программы можно ознакомиться в приложении А под именем «Parallel_Stepennoy_Method.sln».

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

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)=n

Задача умножения матрицы на вектор определяется соотношением 3.1

Тем самым, получение результирующего вектора «y» предполагает повторенияn однотипных операций по умножению строк матрицы A и вектора x. Получение каждой такой операции включает поэлементное умножение элементов строки матрицы и вектора x и последующее суммирование полученных произведений.

Общее количество необходимых скалярных операций оценивается величинойF₁(n)=2*n², где n- размерность задачи.Таким образом общее количество операций составит F₁(n)=2*n²+n.

Соответственно:

1) ;

2)

3) ;

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

4) ;

5)

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

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

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

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

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

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

Проведем замеры времени выполнения алгоритма при матрица размерностью n= 100, 200, …, 700. Сведем полученные результаты в таблицу 3.1. Замеры времени проводятся в миллисекундах. Замеры приводились на видеокарте NVIDIAGeForceGTX 1660s и процессоре Ryzen 5 2600.

Как видно из таблицы 3.1, на малых значения матрицы (100-300) OpenMPработает даже медленнее последовательного алгоритма. Связано это с тем, что неэффективно использовать параллельные алгоритмы на недостаточно больших объемах данных, так как создание и управление потоками занимает дополнительные ресурсы.

Таблица 3.1-Время выполнения алгоритмов (в мс)

T\n	100	200	300	400	500	600	700
Последовательный алгоритм	1	2	3	5	7	10	14
Параллельный алгоритмcиспользованием OpenMP	3	3	3	5	4	3	2
Параллельный алгоритмcиспользованием CuBLAS	0,9	1	0,83	0,83	0,84	0,9	0,92

Как видно из приведенной таблицы, на малых значения матрицы (100-300) OpenMPработает даже медленнее последовательного алгоритма. Связано это с тем, что неэффективно использовать параллельные алгоритмы на недостаточно больших объемах данных, так как создание и управление потоками занимает дополнительные ресурсы.

Опираясь на полученные результаты, проведем анализ эффективности использования параллельного алгоритма, реализованного с использование технологии СUDA.

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

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



Таблица 3.2. - Ускорение при использовании параллельных алгоритмов

n	100	200	300	400	500	600	700
Ускорение OpenMP	-	-	-	0	1,75	3,3	7
Ускорение Cuda	1,1	2	3,61	6,02	8,33	11,1	15,2

Также, для большей наглядностипостроим график по данным, приведенным в таблице 3.1. и приведем его на рисунке 3.2

Рисунок 3.2 - График эффективности работы алгоритмов

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

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

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

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

В ходе выполнения курсовой работы был сделан вывод, что для решения объемных задач линейной алгебры лучше всего подходит параллельный алгоритм с использованием технологии CUDA, так как в данной технологий реализована библиотека CUBLAS для выполнения основных операций линейной алгебры и данная технология даёт наилучшие показатели эффективности работы алгоритма.



Заключение

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

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

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

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

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



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

1. Боресков А.В.Параллельные вычисления на GPU. Архитектура и программная модель CUDA: Учебное пособие / Боресков А.В., Марковский Н.Д., Микушин Д.Н. и др. - Москва: МГУ, 2012. - 336 с.

2. Долгополов Д.В. Методы нахождения собственных значений и собственных векторов матриц / Д.В. Долгополов. -Санкт-Петербург: СПбГТИ(ТУ), 2005. - 39с.

3. Козин Р.Г. Алгоритмы численных методов линейной алгебры и их программная реализация: Учебно-методическое пособие / Р.Г. Козин. - М.: НИЯУ МИФИ, 2012. - 192 с.

4. Фаддеев Д.К. Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н. Фаддеева. - Москва: Физматгиз, 1963. - 734с.

5. NVIDIA Developer Documentation // Электрон. дан. - Режимдоступа: https://docs.nvidia.com

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

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



Приложение А

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

Исходные код программ, реализующихпоследовательный и параллельный степенной метод для нахождения максимального по модулю собственного значения и соответствующего собственного вектора матрицы, последовательный код в файле «Posl_Stepennoy_Method.cpp», апараллельный в файле «OpenMP_Stepennoy_Method.cpp» и ««Parallel_Stepennoy_Method.sln» с технологиями OpenMPи CUDA соответственно.

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

...