А.В. ПОПОВ Институт кибернетики им. В.М. Глушкова НАН Украины Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами dept150@insyg.kiev.ua. - презентация

1 А.В. ПОПОВ Институт кибернетики им. В.М. Глушкова НАН Украины Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами

2 Параллельные алгоритмы 2 Во многих случаях при численном решении научно-технических задач разрешающая система уравнений является задачей (несколькими задачами) или сводится к задачам линейной алгебры: линейная система (система линейных алгебраических уравнений, СЛАУ) Ax = b, алгебраическая проблема собственных значений Ax = λBx. Часто задачи линейной алгебры возникают при дискретизации краевых задач или задач на собственные значения проекционно-разностным методом (конечных разностей, конечных элементов). Как правило, решение задач линейной алгебры занимает значительную часть (50 % и более) времени решения всей задачи в целом.

3 Параллельные алгоритмы 3 Особенности задач линейной алгебры, полученных в результате дискретизации Высокий порядок разрешающих дискретных задач – до десятков миллионов. Матрицы задач имеют разреженную структуру – количество ненулевых элементов матрицы составляет величину kn, где k

4 Параллельные алгоритмы 4 Примеры разреженных матриц порядок матрицы максимальная полуширина ленты матрицы плотность матрицы 5% порядок матрицы максимальная полуширина ленты матрицы плотность матрицы 1%

5 Параллельные алгоритмы 5 В LDL T -варианте метода Холецкого выделяются три подзадачи: разложение матрицы системы A = LDL T,O(nm 2 ) операций; решение СЛАУ с нижней треугольной матрицей Ly = b, O(nm) операций; решение СЛАУ с верхней треугольной матрицей L T x = D -1 y, O(nm) операций.

6 Параллельные алгоритмы 6 Циклические схемы распределения между процессами элементов матриц Строчно-циклическая схема процессу с логическим номером r (r = 0, 1,…, p-1) распределяются элементы строк матрицы с номерами k+1, p+k+1, 2p+k+1,..., где p – количество используемых процессов, а k равно остатку от деления r+l на p при одном и том же 0 l p-1 для всех процессов Одномерная блочная циклическая схема если процесс с логическим номером r оперирует с элементами строк матрицы с номерами sI+1,…,sI+s, то процесс с номером r+1 – с элементами строк с номерами s(I+1)+1,…,s(I+1)+s Численные методы для многопроцессорного вычислительного комплекса ЕС / В.С. Михалевич, Н.А. Бик, …, А.Н. Химич и др. / Под редакцией И.Н. Молчанова. – М.: Изд. ВВИА им. Н.Е. Жуковского, – 401 с.

7 Параллельные алгоритмы 7 Одномерная блочная циклическая схема распределения и обработки элементов ленточной матрицы

8 Параллельные алгоритмы 8 Одномерный блочно-циклический алгоритм Для I = 0, 1, 2, …, N, где n = Ns+t, 1ts, выполняются следующие операции: при I > 0 соответствующий процесс вычисляет элементы g i+rs,j (g i,j l i,j d j ; i, j = Is–s+1,…, Is; r = 1,..., p) ; вычисление процессором, содержащим (I+1)-ю строку квадратных блоков (порядка s) матрицы A, элементов l i,i-k (k = 1,..., m i ) и d i, где i = Is+1,…, Is+s ; при I > 0 вычисление ненулевых элементов g i,j (i = Is+ps+1,…, n; j = Is s+1,…, Is) квадратных блоков (порядка s) I-го столбца блоков в соответствии с их распределением между процессами; рассылка всем процессам диагональных элементов di (i = Is+1,…, Is+s) и элементов (I+1)-й строки блоков матрицы L; проверка положительной определенности ( d i > 0 ) или невырожденности ( |d i | > masheps ), i = Is+1,…, Is+s, матрицы A. В случае ленточной матрицы m i = min{ m, i-1 }, а в случае профильной матрицы m i = i-k, где k – второй индекс первого (крайнего левого) элемента i-й строки матрицы. Попов А.В., Химич А.Н. Параллельный алгоритм решения системы линейных алгебраических уравнений с ленточной симметричной матрицей // Компьютерная математика. – – 2. – С. 52–59

9 Параллельные алгоритмы 9 Эффективность одномерного блочного циклического алгоритма Коэффициент ускорения при n sp 2 и m sp где Коэффициент эффективности Если, то

10 Параллельные алгоритмы 10 Блочные схемы распределения Блочно-диагональная матрица с окаймлением Узкая ленточная матрица исходная и переупорядоченная в блочно-диагональную матрицу с окаймлением

11 Параллельные алгоритмы 11 Блочный алгоритм

12 Параллельные алгоритмы 12 Эффективность блочного алгоритма Коэффициент ускорения при pm

13 Параллельные алгоритмы 13 Результаты численных экспериментов порядок матрицы полуширина ленты матрицы плотность матрицы 100% полуширина ленты матриц порядок матриц

14 Параллельные алгоритмы 14 Результаты численных экспериментов порядок матрицы максимальная полуширина ленты матрицы плотность матрицы 21%

15 Параллельные алгоритмы 15 Результаты численных экспериментов Задача 1Задача 2Задача 3Задача 4 Порядок матрицы Полуширина ленты

16 Параллельные алгоритмы 16 Результаты численных экспериментов полуширина ленты матриц 151 порядок матриц

17 17 Анализ прочности строительных конструкций Результаты тестирования

18 9-этажное здание (10_U) КЭ-сетка: - количество элементов количество узлов Структура матрицы Параметры задачи: - порядок СЛАУ плотность матрицы жесткостей 9% - полуширина ленты матрицы

19 Фундамент здания (Gmot2) КЭ-сетка: - количество элементов количество узлов Параметры задачи: - порядок СЛАУ плотность матрицы жесткостей 7% - полуширина ленты матрицы Структура переупорядоченной матрицы Исходная структура матрицы

20 Промышленное здание (Frs5) Структуры матрицы до переупорядочивания и после КЭ-сетка: - количество элементов количество узлов Параметры разрешающей задачи: - порядок СЛАУ для ленточной структуры - плотность матрицы жесткостей 21% - полушиpина ленты матрицы для профильной структуры - плотность матрицы жесткостей 2% - полушиpина ленты матрицы37 580

21 21 Анализ прочности строительных конструкций Задача RAZMER КЭ-сетка: - количество элементов количество узлов Параметры задачи: - порядок СЛАУ плотность матрицы жесткостей 1% - полушиpина ленты матрицы размер файла данных задачи 76 Гб Структура переупорядоченной матрицы Решение задачи: - ввод и распределение данных 33 мин. - разложение матрицы 8 час. 53 мин. - решение СЛАУ с нижней и верхней треугольными матрицами 38 мин. Всего10 час. 04 мин. Оценка времени решения на ПК около 115 час.