Решение СЛАУ на графическом процессоре

Курсовая работа

на тему

«Решение СЛАУ на графическом процессоре»

Содержание

ВВЕДЕНИЕ        3

1. Решение системы линейных уравнений методом сопряженных градиентов        4

2. Гибридная модель программирования OpenMP и CUDA        10

3. Реализация метода сопряженных градиентов        16

ЗАКЛЮЧЕНИЕ        30

СПИСОК ЛИТЕРАТУРЫ        31

Приложение 1 – Реализация однопоточного метода        32

Приложение 2 – Реализация гибридного метода        36

Приложение 3 – Реализация многопоточного алгоритма для CPU        44

ВВЕДЕНИЕ

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

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

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

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

Таким образом основными методами исследования в данной работе является программирование (реализация) алгоритма и эксперимент, для проверки эффективности реализации.

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

1. Решение системы линейных уравнений методом сопряженных градиентов

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

То же самое в матричном виде выглядит так:

Ax = b                                                (2)

Задачей решения системы линейных алгебраических уравнений для матрицы А и вектора b это процесс нахождения значения вектора неизвестных x, при котором выполняются все уравнения системы [1].

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

Метод сопряженных градиентов обычно реализуется как итерационный алгоритм, который применяется к разреженным системам. К таким системам, которые слишком велики для обработки с помощью прямых методов, таких как разложение Холецкого. Большие разреженные системы часто возникают при численном решении уравнений в частных производных или задач оптимизации. Метод сопряженных градиентов также может использоваться для решения задач неограниченной оптимизации, например, для задачи минимизация энергии [2].