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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!