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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21 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 для решения СЛАУ

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

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

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

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

26 Тестовая инфраструктура Процессор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 для решения СЛАУ

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

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

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

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

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

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

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