Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Применение технологии Cilk для решения СЛАУ Параллельные численные методы Кутилов Е., Генералова Е.

Содержание Постановка задачи Разложение Холецкого Обратный ход Трудоемкость Оценка эффективности Блочный алгоритм Параллельный алгоритм Результаты вычислительных экспериментов Заключение 2 Применение технологии Cilk для решения СЛАУ

Рассмотрим систему из n линейных алгебраических уравнений вида: В матричном виде: А - вещественная матрица размера n x n, b, x - вектора размерности n. Постановка задачи 3 Применение технологии Cilk для решения СЛАУ

Разложение Холецкого Разложение Холецкого – представление матрицы A в виде A = LL T, где L нижняя треугольная матрица со строго положительными элементами на диагонали (l ij >0). Необходимое условие: Матрица A – симметричная: Матрица А - положительно-определённая: 4 Применение технологии Cilk для решения СЛАУ

Последовательный алгоритм Элементы матрицы L вычисляются по следующим формулам:, если j < i. 5 Применение технологии Cilk для решения СЛАУ

Обратный ход Ly=b, L T x=y Решение этих систем находится по формулам обратного хода метода Гаусса: Если разложение получено, то решение системы сводится к последовательному решению двух линейных систем уравнений с треугольными матрицами: 6 Применение технологии Cilk для решения СЛАУ

Трудоемкость Общее время работы метода оценивается кубической трудоемкостью O(n 3 ). Обратный ход оценивается квадратичной трудоемкостью O(n 2 ). 7 Применение технологии Cilk для решения СЛАУ

Оценка эффективности На практике часто необходимо решить: Ax=B, где B матрица правых частей. Матрицу A необходимо факторизовать один раз для всех правых частей. После факторизации решение каждой системы занимает квадратичное время. Таким образом, трудоемкость становиться близкой к квадратичной (за счет многократного применения обратного хода). 8 Применение технологии Cilk для решения СЛАУ

Блочный алгоритм 9 Применение технологии Cilk для решения СЛАУ Недостаток классического алгоритма – плохая локализация обращения к памяти, как следствие медленная работа алгоритма. Избежать это можно использованием блочного алгоритма работы с матрицами. Это позволяет добиться большей локализации данных, что в дальнейшем поможет в распараллеливании алгоритма.

Блочный алгоритм Фактор матрицы A вычисляется по формулам:, если j < i. Извлечение корня соответствует выполнению разложения Холецкого. Операция L jj -1 соответствует нахождению обратной матрицы для L jj. 10 Применение технологии Cilk для решения СЛАУ где q = n / r - количество блоков

Параллельный алгоритм В основу положен принцип распараллеливания по данным. Распараллеливание возможно для следующих вычислительных процедур: вычисление диагонального элемента L ii вычисление элементов i-ой строки выполнение матричного умножения Параллельная версия выполнена с использованием технологии Intel® Cilk Plus. 11 Применение технологии Cilk для решения СЛАУ

Вычисление диагонального элемента L Распараллеливание: 12 Применение технологии Cilk для решения СЛАУ, где

Вычисление элементов i-ой строки, если j < i, где Распараллеливание: 13 Применение технологии Cilk для решения СЛАУ

Блочное умножение где Пусть дано блочное представление матрицы A и матрицы B, тогда их произведение C может быть также представлено в блочном виде: 14 Применение технологии Cilk для решения СЛАУ

Выполнение матричного умножения х= х х х х = = = = =+++ Распараллеливание: - временная матрица, используемая для хранения промежуточного результата. 15 Применение технологии Cilk для решения СЛАУ

Сilk_for 16 Применение технологии Cilk для решения СЛАУ

Reducer Класс Monoid, реализующий моноид, для работы с редьюсером. Этот класс содержит следующие функции: reduce (T *left, T *right) вычисляет *left = *left OP *right, identity (T *p) создаёт нейтральный элемент в области памяти, на которую указывает p, destroy (T *p) вызывает деструктор для объекта, на который указывает p, 17 Применение технологии Cilk для решения СЛАУ

Сilk_for Применение технологии Cilk для решения СЛАУ 18

Reducer Базовый тип, определяющий необходимые параметры для исходной матрицы, - класс MyStruct. 19 Применение технологии Cilk для решения СЛАУ

Reducer Реализация функции reduce (T *left, T *right) 20 Применение технологии Cilk для решения СЛАУ

Reducer Класс – оболочка, для упрощенной работы с редьюсером, содержит : cilk::reducer * imp Методы доступа и изменения: reducerAddMatrix ( int size_A, double* &A ); void Op ( int sizeBlock, int startIndexA, int numberRowsA, int numberColumnsA, double* temp_A ); 21 Применение технологии Cilk для решения СЛАУ

Reducer Объявление и начальная инициализация редьюсера: reducerAddMatrix C(size, A); 22 Применение технологии Cilk для решения СЛАУ

Reducer Реализация функции Op (): 23 Применение технологии Cilk для решения СЛАУ

Reducer Использование редьюсера на примере нахождения диагонального элемента матрицы L: 24 Применение технологии Cilk для решения СЛАУ

Результаты экспериментов Применение технологии Cilk для решения СЛАУ 25

Тестовая инфраструктура ПроцессорIntel Core 2 Quad Q6600 Память4 GB Операционная системаMicrosoft Windows 7 Среда разработкиMicrosoft Visual Studio 2008 Компилятор, профилировщик, отладчик Intel Parallel Studio XE Библиотеки Intel® MKL Intel® Cilk Plus 26 Применение технологии Cilk для решения СЛАУ

Методы тестирования программной реализации Анализ корректности разработанной программной реализации разложения Холецкого производится путем сравнения с эталонной версией из библиотеки Intel Kernel Library (MKL). Оценкой производительности является общее время решения поставленной задачи. 27 Применение технологии Cilk для решения СЛАУ

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

Результаты вычислительных экспериментов 29 Применение технологии Cilk для решения СЛАУ Сравнение последовательного алгоритма с блочным алгоритмом (размер блока 50) с использованием блочного алгоритма умножения матриц при различных размерах блоков. Размер блока:

Результаты вычислительных экспериментов 30 Применение технологии Cilk для решения СЛАУ Сравнение последовательной и параллельных версий.

Результаты вычислительных экспериментов 31 Применение технологии Cilk для решения СЛАУ Ускорение лучшей параллельной реализации алгоритма относительно последовательного алгоритма на размере 8000.

Заключение Применение технологии Cilk для решения СЛАУ 32 В ходе работы изучены расширенные возможности технологии Cilk Plus – создание собственных редьюсеров данных. Реализовано несколько программных модификаций алгоритма разложения Холецкого. Для параллельной модификации алгоритма Холецкого разработаны собственные редьюсеры. Наиболее эффективная реализация алгоритма показала отставание от MKL в 3 раза.

Вопросы ? Применение технологии Cilk для решения СЛАУ 33