ВВЕДЕНИЕ 4
1. СОВРЕМЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ 7
1.1 Основные понятия и определения 7
1.2 Практическое применение СЛАУ 9
1.3 Прямые методы решения СЛАУ 10
1.3.1 Метод Крамера 11
1.3.2 Метод Гаусса 12
1.3.3 Метод обратной матрицы 14
1.4 Итерационные методы решения СЛАУ 15
1.4.1 Метод Якоби и метод Зейделя 16
1.4.2 Метод сопряженных градиентов 20
1.5 Способы хранения разреженных матриц в памяти вычислительных
устройств 22
1.5.1 Координатный формат хранения 23
1.5.2 Разреженный строчный формат 26
2. РАЗРАБОТКА МОДИФИЦИРОВАННОГО АЛГОРИТМА РЕШЕНИЯ
СЛАУ МЕТОДОМ СТАБИЛИЗИРОВАННЫХ БИСОПРЯЖЕННЫХ ГРАДИЕНТОВ 28
2.1 Стабилизированный метод бисопряженных градиентов 28
2.2 Итерационный алгоритм стабилизированного метода бисопряженных
градиентов 30
2.3 Использование CSR формата для хранения разреженных матриц
при решении СЛАУ стабилизированным методом бисопряженных градиентов 35
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СТАБИЛИЗИРОВАННОГО
МЕТОДА БИСОПРЯЖЕННЫХ ГРАДИЕНТОВ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ CUDA 38
3.1 Программная реализация последовательной версии алгоритма 38
3.2 Программная реализация параллельной версии алгоритма 43
3.3 Оценка эффективности модификации итерационного алгоритма на
основе проведения вычислительных экспериментов 48
ЗАКЛЮЧЕНИЕ 55
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 57
ПРИЛОЖЕНИЕ 61
На сегодняшний день, с активным ростом потребности в решении сложных вычислительных задач, наблюдается высокий спрос на разработку программного обеспечения, позволяющего корректно производить точные расчеты с использованием современной вычислительной техники.
Применение программного обеспечения, разработанного для автоматизации решения различных технических задач, и в частности, для произведения сложных и трудоемких вычислительных расчетов, наблюдается в строительстве, машиностроении, авиастроении, а также в системах автоматизированного проектирования.
Из известных математических проблем и задач, наибольшую потребность в оптимизации использования вычислительных ресурсов представляют задачи, в которых присутствуют многочисленные однотипные вычислительные операции, выполняемые над предельно большими массивами данных, и в частности над матрицами.
В трудоемких математических задачах, обычно, в качестве входных или промежуточных данных, выступают матрицы больших размерностей. С точки зрения условий подобных задач, матрицы представляются в виде систем алгебраических линейных уравнений (СЛАУ). Очевидно, что корректным результатом такой задачи, является нахождение решения промежуточной или входной СЛАУ.
Среди многочисленных методов решения систем алгебраических линейных уравнений, выделяется один из часто используемых и устойчивых методов - стабилизированный метод бисопряженных градиентов (англ. Biconjugate gradient stabilized method, BiCGStab).
Основное преимущество BiCGStab, помимо устойчивости, заключается в том, что данный метод, использует, в основном, стандартные вычислительные операции, производимые над векторами и матрицами, которые в целом, можно оптимизировать, посредством их программной параллелизации.
Основной целью данной выпускной квалификационной работы является разработка и программная реализация итерационного алгоритма решения СЛАУ на основе модифицированного стабилизированного метода бисопряженных градиентов с использованием технологии NVIDIA CUDA. Поставленная цель достигается решением следующих задач:
• Обзор существующих методов решения систем линейных алгебраических уравнений;
• Разработка модифицированного алгоритма стабилизированного метода биспоряженных градиентов с экономией видеопамяти;
• Программная реализация разработанного алгоритма с использованием технологии CUDA;
• Оценка эффективности разработанного алгоритма на основе проведения вычислительных экспериментов;
Выпускная квалификационная работа включает в себя: введение, три главы, и заключение.
В первой главе производится сравнительный анализ, существующих итерационных методов предназначенных для решения систем линейных алгебраических уравнений. Подробно описываются и сравниваются оптимизированные форматы хранения разреженных матриц в памяти вычислительных устройств.
Вторая глава посвящена подробному описанию стабилизированного метода биспоряженных градиентов. Приводится описание модификаций метода, связанных со значительной оптимизацией вычислений при работе с разреженными матрицами. С использованием языка блок-схем описывается итерационный процесс предлагаемого метода.
В третьей главе описываются аспекты разработки программного средства с использованием технологии CUDA. Производится анализ результатов вычислительного эксперимента, полученных в ходе тестирования последовательной и параллельной версии разработанного приложения с использованием данных, представленных в виде разреженных матриц различной размерности и плотности.
В заключении приводится краткий анализ полученных в ходе работы результатов. Подробно описываются итоги проделанной работы, а также преимущества и недостатки разработанного программного средства.
Выпускная квалификационная работа состоит из 78 страниц, 14 рисунков, 9 таблиц и приложения.
Цель данной выпускной квалификационной работы заключалась в разработке и программной реализации итерационного алгоритма решения СЛАУ на основе модифицированного стабилизированного метода биспоряженных градиентов с использованием технологии NVIDIA CUDA.
В первой главе были проанализированы основные современные методы решения систем линейных алгебраических уравнений. Исходя из результатов полученного анализа, было выявлено, что большинство предлагаемых прямых и итерационных методов, являются не оптимизированными, с точки зрения расхода памяти.
Во второй главе был предложен итерационный алгоритм решения несимметричных систем линейных алгебраических уравнений, а также его модификации, позволяющие значительно сократить общий объем памяти, выделяемый под результаты промежуточных вычислений.
В третьей главе был подробно описан процесс реализации последовательной и параллельной версии программ, позволяющих решать системы линейных алгебраических уравнений посредством модифицированного и стабилизированного метода биспоряженных градиентов. Результаты проведенных вычислительных экспериментов, а в частности, полученное в ходе расчетов среднее ускорение равное 3, доказывают, что разработанная параллельная версия приложения значительно оптимизирует итерационный процесс разработанного метода.
Исходя из общих данных, полученных путем проведения многочисленных вычислительных экспериментов над разработанным приложением, можно сделать вывод, что параллельная версия реализованного приложения корректно выполняет задачу решения систем алгебраических уравнений, при этом минимально расходуя аппаратные ресурсы вычислительного устройства.
Стоит отметить, что использование GPU, в качестве основного инструмента повышения производительности разработанной программы, в целом, положительно скажется на скорости работы приложения, при использовании новых, актуальных и соответственно более мощных видеокарт. Стремительное совершенствование графических процессоров, предполагает значительное повышение оптимизации и скорости работы приложений разработанных, на базе технологии NVIDIA CUDA.
Таким образом, можно отметить, что разработанное программное приложение, исходя из корректности полученных результатов и очевидной скорости вычисления конечного решения с минимальными затратами памяти и в общем, рациональным расходом аппаратных ресурсов, можно использовать для решения различных прикладных задач.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
