РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ ХОЛЕЦКОГО

IMPLEMENTATION OF A PARALLEL ALGORITHM FOR SOLVING SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS BY THE CHOLETSKY METHOD

Anton Gavrunov

Student, Institute of Engineering and Digital Technologies, Belgorod State National Research University,

Russia, Belgorod

АННОТАЦИЯ

Цели. реализации параллельного алгоритма решения систем линейных алгебраических уравнений методом Холецкого. Методы. Методы исследования алгоритма решения задачи. Использовались теоретические и эмпирические методы Результаты. Были разработаны два алгоритма решения задачи: последовательный и для систем с общей памятью. На основе полученных алгоритмов были разработаны программы, выполняющие поставленную задачу. Обсуждение. В ходе работы был сделан вывод, что данная задача показывает лучший результат только в том случае, если расчеты будут проходить на большом количестве данных.

ABSTRACT

Goals. implementation of a parallel algorithm for solving systems of linear algebraic equations by the Cholesky method. Methods. Methods for studying the algorithm for solving the problem. Theoretical and empirical methods were used. Results. Two algorithms for solving the problem were developed: sequential and for systems with shared memory. Based on the obtained algorithms, programs were developed that perform the task. Discussion. In the course of the work, it was concluded that this task shows the best result only if the calculations are carried out on a large amount of data.

Ключевые слова: декомпозиция, матрица, алгоритм, система уравнений, объем памяти, процессор, openmp.

Keywords: decomposition, matrix, algorithm, ownership system, memory size, processor, openmp.

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

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

Разложение Холецкого (метод квадратного корня) - это представление симметричной положительно определенной матрицы A в виде

A = LL^Т                                                        (1)

где L - нижнетреугольная матрица со строго положительными элементами на диагонали.

Иногда разложение записывают в эквивалентной форме:

A = U^TU                                                      (2)

Где U = LТ - верхнетреугольная матрица.

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

Рисунок 1. Нижнетреугольная матрица L.

Это разложение можно использовать для решения системы линейных уравнений Ax = b, если матрица A симметрична и положительно определена.

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

Выполнив разложение A = LLТ (1), решение x можно получить, последовательно решая две треугольные системы уравнений: Ly = b и LТx = y.

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

Чтобы найти коэффициенты матрицы L, неизвестные коэффициенты матрицы L приравниваются к соответствующим элементам матрицы A.

Элементы матрицы L можно вычислить, начиная с левого верхнего угла матрицы, в соответствии с формулами на рисунке 2.

Рисунок 2. Формулы для вычисления элементов матрицы L.

Выражение под корнем всегда положительно, если A - вещественная положительно определенная матрица. Расчет происходит сверху вниз, слева направо, то есть сначала Lij, а затем Lii.

Симметрия матрицы дает возможность хранить и вычислять чуть больше половины ее элементов, это вдвое экономит как необходимый для вычислений объем памяти, так и количество операций по сравнению с разложением по Гауссу [3]. В этом случае аналогичное (без вычисления квадратных корней) LU-разложение с применением симметрии матрицы становится быстрее, чем метод Холецкого (метод не использует извлечение квадратного корня), но требует сохранения в памяти всей матрицы.

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

Рисунок 3. Система с общей памятью.

В простейшей схеме построения системы с общей памятью используют общую шину для соединения всех вычислительных мощностей. Эта конфигурация называется Uniform Memory Access (UMA) – одинаковый(равный) доступ к памяти. Производительность подобных, многопроцессорных систем ограничивается пропускной способностью шины разделяемой памяти, и с повышение числа процессоров, производительность системы перестает увеличиваться [4]. Это связано с увеличением ожидания доступа к шине разделяемой памяти.

Для распараллеливания алгоритмов используется механизм создания потоков или нитей, для которых не создается отдельное адресное пространство, но которые на многопроцессорных системах также распределяются между процессорами. В языке программирования C можно напрямую использовать этот механизм для распараллеливания программ путем вызова соответствующих системных функций, а в компиляторах FORTRAN это решение используется для автоматического распараллеливания мощностей, или в режиме инсталляции специальных директив распараллеливания напрямую в компилятор (такой подход также поддерживается компиляторами Си) [2].

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

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

Разработка алгоритмов с использованием OpenMP. Объем вычислений будет зависеть от размерности исходной матрицы коэффициентов A и вектора свободных членов b. Чем больше их размер, тем больше будут матрицы L и LT, вектор y и вспомогательные массивы для вычислений.

Программа будет работать только с положительной симметричной матрицей A, поэтому для ее создания требуется алгоритм.

Количество потоков, а также размер матриц будут вручную записаны в коде. Циклы for, отвечающие за вычисление элементов матриц, результирующих и вспомогательных векторов, а также за транспонирование, будут подвергаться распараллеливанию [5].

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

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

Программная реализация параллельного алгоритма решения СЛАУ методом Холецкого Выбор технологии и средств реализации

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

1. Язык программирования C ++ для написания последовательных и параллельных алгоритмов.
2. Библиотека OpenMP для реализации алгоритма для систем с общей памятью

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

Рисунок 4. Блок-схемы функций.

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

Затем была создана блок-схема алгоритма решения СЛАУ. (Рисунок 5)

Рисунок 5. Блок-схема последовательного алгоритма.

A - матрица коэффициентов системы уравнений, s - верхний треугольник

матрица, элементы которой вычисляются по формулам, s_t - транспонированная матрица s, d - буферный вектор, y - вспомогательный вектор, x - результирующий вектор. Перечисленные выше структуры будут иметь размеры n и n * n, где n - переменная, значение которой будет расти с каждым экспериментом.

Список литературы:

1. Воеводин В.В. Курс лекций «Параллельная обработка».
2. Букатов А.А., Дацюк В.Н. Жегуло А.И. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону: CVVR, 2003.
3. Антонов А.С. Технологии параллельного программирования MPI и OpenMP / А.С. Антонов. Антонов. - Москва 2012.
4. Малышкин В.Е. Параллельное программирование мультикомпьютеров, Новосибирск, 2006.
5. Гергель В.П. Параллельное программирование с использованием OpenMP, Новосибирск, 2007 г.