'

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

Понравилась презентация – покажи это...





Слайд 0

Применение технологии Cilk для решения СЛАУ Параллельные численные методы Кутилов Е., Генералова Е.


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

Тестовая инфраструктура 26 Применение технологии Cilk для решения СЛАУ


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

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


Слайд 32

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


×

HTML:





Ссылка: