LU-разложение матрицы. Сценарий распределенного LU-разложения на основе блочной декомпозиции и дополнения Шура.



Использование разложения (первый вариант)

Пусть M - матрица [N×N]. LU-разложение {L, U, P}: L - нижне-треугольная; U -верхне-треугольная; P - перестановочная матрица.

L⋅U=P⋅Μ .

Пусть EN единичная матрица. Для вычисления M^(-1) нужно решить уравнение (прямой и обратной прогонкой) L⋅U⋅X=P⋅EN ⇒ X=M^(-1) (M⋅X=P^(-1)⋅(L⋅U⋅X)=P^(-1)⋅P⋅EN=EN).

Процедура Maxima lu_backsub(LU,B), где LU - результат lu_factor(M), позволяет решать L⋅U⋅X=P⋅B для произвольной прямоугольной матрицы B[N×M].

 

Если «расслоить» матрицу EN на K не пересекающихся «вертикальных полос»                                              , где                                         ,

то параллельное выполнение lu_backsub(LU,      позволяет одновременно получить K «групп столбцов» M-1[nk-1:nk] обратной матрицы M-1.

При K=N такая схема означает параллельное вычисление столбцов M-1.

Блочное распараллеливание (два блока)


Обращение мартиц с помощью дополниения Шура

 

Известный алгоритм обращения матриц, основанный на «блочной декомпозиции» и дополнении Шура.

Вычисления отдельными блоками позволяют получить более гибкий для дальнейшей оптимизации «рекурсивный» алгоритм (т.к. вычисление A-1 и S-1 и умножение распараллеливаются).

 

Пусть M[N×N] разделена на четыре блока [N/2×N/2]. Стоимость параллельного вычисления блоков обратной матрицы (символ «||»):


Концепция грид-вычислений, область применения и типы грид-систем. Понятие виртуальной организации.

Концепция грид

Грид является географически распределённой инфраструктурой, объединяющей множество ресурсов разных типов (процессоры, долговременная и оперативная память, хранилища и базы данных, сети), доступ к которым пользователь может получить из любой точки, независимо от места их расположения.

Идея грид-компьютинга возникла вместе с распространением персональных компьютеров, развитием интернета и технологий пакетной передачи данных на основе оптического волокна (SONET, SDH и ATM), а также технологий локальных сетей (Gigabit Ethernet). Полоса пропускания коммуникационных средств стала достаточной, чтобы при необходимости привлечь ресурсы другого компьютера. Учитывая, что множество подключенных к глобальной сети компьютеров большую часть рабочего времени простаивает и располагает ресурсами, большими, чем необходимо для решения их повседневных задач, возникает возможность применить их неиспользуемые ресурсы в другом месте.

• Повсеместный, стандартный, надежный и дешевый доступ к ресурсам

• Сложность инфраструктуры скрыта от пользователя (прозрачность)

• Легкость интеграции новых ресурсов

• Динамическое перераспределение нагрузки иотказоустойчивость

• Управление сложным ансамблем ресурсов

Типы грид-систем

В настоящее время выделяют три основных типа грид-систем:

• Добровольные гриды — гриды на основе использования добровольно предоставляемого свободного ресурса персональных компьютеров;

• Научные гриды — хорошо распараллеливаемые приложения программируются специальным образом (например, с использованием Globus Toolkit);

• Гриды на основе выделения вычислительных ресурсов по требованию (коммерческий грид, англ. enterprise grid) — обычные коммерческие приложения работают на виртуальном компьютере, который, в свою очередь, состоит из нескольких физических компьютеров, объединённых с помощью грид-технологий.

Понятие виртуальной организации

В компьютерных Грид-системах различные организации, имеющие общие научные или практические интересы, на добровольной основе создают объединение, которое в грид-технологиях называется виртуальной организацией (ВО). Участники ВО связаны между собой с помощью Интернета таким образом, что их вычислительные мощности объединяются. Система включает в себя вычислительные ресурсы и ресурсы хранения данных, но при этом каждая организация контролирует использование своих ресурсов. Пользователи могут получать практически неограниченные ресурсы для вычислений и хранения данных, не задумываясь об их происхождении. Каждый из участников ВО предоставляет свои вычислительные ресурсы (или их часть) для использования другими участниками и, в тоже время, получает доступ к ресурсам других участников ВО.


Дата добавления: 2018-02-18; просмотров: 1142; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!