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

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

---

Пишем диссертации на заказ стоимость в Хабаровске можете узнать на сайте Work5.

---

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

В этой работе был рассмотрен один из способов решения систем линейных уравнений, а именно метод сопряженных градиентов, который представляет собой численный итеративный алгоритм. Для этого метода возможно параллельное выполнение отдельных его участков. В рамках данной работы был реализован однопоточный алгоритм, а также вариации алгоритма, использующая параллельные выполнение операций на отдельных участках. Изучена гибридная модель программирования, предполагающая использование гетерогенной аппаратной среды. В частности, для реализации гибридной модели, изучалась связка технологий CUDA и OpenMP. Таким образом, реализация алгоритма предполагает исполнение как на центральном процессоре, так и на графическом оборудовании. Проведены эксперименты с обоими реализациями, в ходе которых наблюдалась предсказуемое увеличение времени выполнения для однопоточного алгоритма, а также многопоточного алгоритма, исполняемого на центральном процессоре, и весьма хаотичное поведение для гибридной реализации метода, использующий ресурсы графического оборудования. Тем не менее, на основе полученных результатов можно утверждать, что существует некоторый предел сложности задачи, когда гибридная реализация становится эффективнее, чем однопоточная. В данном случае было выявлено, что для систем линейных уравнений с размером приблизительно меньше чем 1500 эффективнее однопоточный алгоритм, а для задач большего размера – гибридный. Однако, если центральный процессор имеет большой потенциал для параллельного выполнения, то почти всегда многопоточный алгоритм, исполняемый на CPU будет эффективнее однопоточного алгоритма, исполняемого на CPU.

1. Решение СЛУ методом сопряженных градиентов [Электронный ресурс]. - Режим доступа: http://www.hpcc.unn.ru/?dir=847 / (дата обращения: 14.06.2021). 2. Барахнин В.Б., Шапеев В.Б. Введение в численный анализ. – Санкт-Петербург–Москва–Краснодар: Лань, 2005. – 99с 3. CUDA LLVM Compiler [Электронный ресурс]. - Режим доступа: https://developer.nvidia.com/cuda-llvm-compiler / (дата обращения: 02.12.2021). 4. Clang, Введение [Электронный ресурс]. - Режим доступа: https://habr.com/ru/post/354718/ / (дата обращения: 14.06.2021). 5. CUDA Toolkit Documentation [Электронный ресурс]. - Режим доступа: https://docs.nvidia.com/cuda/index.html / (дата обращения: 14.06.2021). 6. Henk A. van der Vorst. Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. 7. Parallel Processing via MPI & OpenMP, M. Firuziaan, O. Nommensen. Linux Enterprise, 2007. — 245 с.