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

Содержание

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

Слайд 1Применение технологии Cilk для решения СЛАУ
Параллельные численные методы

Кутилов Е., Генералова Е.

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

для решения СЛАУ

Слайд 3Рассмотрим систему из n линейных алгебраических уравнений вида:
В матричном виде:
А -

вещественная матрица размера n x n,
b, x - вектора размерности n.

Постановка задачи

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

Слайд 4Разложение Холецкого
Разложение Холецкого – представление матрицы A в виде A =

LLT, где L — нижняя треугольная матрица со строго положительными элементами на диагонали (lij >0).

Необходимое условие:
Матрица A – симметричная:
Матрица А - положительно-определённая:


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

Слайд 5Последовательный алгоритм
Элементы матрицы L вычисляются по следующим формулам:







, если j < i.






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

Слайд 6Обратный ход
Ly=b, LTx=y
Решение этих систем находится по формулам обратного хода метода

Гаусса:


Если разложение получено, то решение системы сводится к последовательному решению двух линейных систем уравнений с треугольными матрицами:

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

Слайд 7Трудоемкость
Общее время работы метода оценивается кубической трудоемкостью O(n3).

Обратный ход оценивается

квадратичной трудоемкостью O(n2).



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

Слайд 8Оценка эффективности
На практике часто необходимо решить: Ax=B, где B матрица правых

частей.

Матрицу A необходимо факторизовать один раз для всех правых частей.

После факторизации решение каждой системы занимает квадратичное время.

Таким образом, трудоемкость становиться близкой к квадратичной (за счет многократного применения обратного хода).

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

Слайд 9Блочный алгоритм
Применение технологии Cilk для решения СЛАУ
Недостаток классического алгоритма – плохая

локализация обращения к памяти, как следствие медленная работа алгоритма.

Избежать это можно использованием блочного алгоритма работы с матрицами.

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


Слайд 10Блочный алгоритм
Фактор матрицы A вычисляется по формулам:

, если j

i.





Извлечение корня соответствует выполнению разложения Холецкого.
Операция Ljj-1 соответствует нахождению обратной матрицы для Ljj.

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

где q = n / r - количество блоков

Слайд 11Параллельный алгоритм
В основу положен принцип распараллеливания по данным.
Распараллеливание возможно для следующих

вычислительных процедур:

вычисление диагонального элемента Lii
вычисление элементов i-ой строки
выполнение матричного умножения


Параллельная версия выполнена с использованием технологии Intel® Cilk Plus.

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

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

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

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

Слайд 14Блочное умножение
где
Пусть дано блочное представление матрицы A и матрицы B,

тогда их произведение C может быть также представлено в блочном виде:

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

Слайд 15Выполнение матричного умножения

Распараллеливание:
- временная матрица, используемая для хранения промежуточного результата.
Применение

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

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

Слайд 17Reducer
Класс Monoid, реализующий моноид, для работы с редьюсером. Этот класс содержит

следующие функции:
reduce (T *left, T *right) вычисляет *left = *left OP *right,
identity (T *p) создаёт нейтральный элемент в области памяти, на которую указывает p,
destroy (T *p) вызывает деструктор для объекта, на который указывает p,

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

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

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


Применение

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

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

СЛАУ

Слайд 21Reducer
Класс – оболочка, для упрощенной работы с редьюсером, содержит :
cilk::reducer

myMonoid > * imp

Методы доступа и изменения:
reducerAddMatrix ( int size_A, double* &A );
void Op ( int sizeBlock, int startIndexA,
int numberRowsA, int numberColumnsA, double* temp_A );

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

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

СЛАУ

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

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

для решения СЛАУ

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

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

Слайд 27Методы тестирования программной реализации
Анализ корректности разработанной программной реализации разложения Холецкого

производится путем сравнения с эталонной версией из библиотеки Intel Kernel Library (MKL).

Оценкой производительности является общее время решения поставленной задачи.


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

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

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

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

с блочным алгоритмом (размер блока 50) с использованием блочного алгоритма умножения матриц при различных размерах блоков.

Размер блока:

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

параллельных версий.

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

реализации алгоритма относительно последовательного алгоритма на размере 8000.

Слайд 32Заключение
Применение технологии Cilk для решения СЛАУ
В ходе работы изучены расширенные

возможности технологии Cilk Plus – создание собственных редьюсеров данных.

Реализовано несколько программных модификаций алгоритма разложения Холецкого.

Для параллельной модификации алгоритма Холецкого разработаны собственные редьюсеры.

Наиболее эффективная реализация алгоритма показала отставание от MKL в 3 раза.

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

Похожие презентации

Милль Джон Стюарт (1806-1873) 256
Квест Мангуш бібліотечний 260
Коммуникации в социальных медиа как инструмент для привлечения частных пожертвований 238
Ю́рий Фёдорович Лися́нский 230
Коммуникации для программистовили Как объяснить заказчику, что он не прав? 226
Как оформить социальный проект 294

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика