Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами

Рассматриваются блочные алгоритмы прямых методов исследования и решения систем линейных алгебраических уравнений с разреженными (ленточными, профильными, блочно-диагональными с окаймлением) симметричными матрицами на компьютерах MIMD-архитектуры. Исследуется эффективность рассматриваемых алгоритмов....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
1. Verfasser:	Попов, А.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут програмних систем НАН України 2008
Schlagworte:	Паралельне програмування Розподілені системи та мережі
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/1444
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами / А.В. Попов // Пробл. програмув. — 2008. — N 2-3. — С. 111-118. — Бібліогр.: 9 назв. — рус.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-1444
record_format	dspace
spelling	Попов, А.В. 2008-07-31T10:24:41Z 2008-07-31T10:24:41Z 2008 Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами / А.В. Попов // Пробл. програмув. — 2008. — N 2-3. — С. 111-118. — Бібліогр.: 9 назв. — рус. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1444 519.6 Рассматриваются блочные алгоритмы прямых методов исследования и решения систем линейных алгебраических уравнений с разреженными (ленточными, профильными, блочно-диагональными с окаймлением) симметричными матрицами на компьютерах MIMD-архитектуры. Исследуется эффективность рассматриваемых алгоритмов. Приводятся некоторые результаты численных экспериментов на MIMD-компьютере. The block algorithms of direct methods for the investigating and solving of systems of linear algebraic equations with sparse (band, profile, block-diagonal with bordering) symmetric matrices on the computers of MIMD-architecture are dealt with. The performance of algorithms being studied is investigated. Some results of numeral tests carried out on MIMD computer are given. ru Інститут програмних систем НАН України Паралельне програмування Розподілені системи та мережі Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами Parallel algorithms of the linear systems with sparse symmetric matrices solving Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами
spellingShingle	Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами Попов, А.В. Паралельне програмування Розподілені системи та мережі
title_short	Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами
title_full	Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами
title_fullStr	Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами
title_full_unstemmed	Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами
title_sort	параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами
author	Попов, А.В.
author_facet	Попов, А.В.
topic	Паралельне програмування Розподілені системи та мережі
topic_facet	Паралельне програмування Розподілені системи та мережі
publishDate	2008
language	Russian
publisher	Інститут програмних систем НАН України
format	Article
title_alt	Parallel algorithms of the linear systems with sparse symmetric matrices solving
description	Рассматриваются блочные алгоритмы прямых методов исследования и решения систем линейных алгебраических уравнений с разреженными (ленточными, профильными, блочно-диагональными с окаймлением) симметричными матрицами на компьютерах MIMD-архитектуры. Исследуется эффективность рассматриваемых алгоритмов. Приводятся некоторые результаты численных экспериментов на MIMD-компьютере. The block algorithms of direct methods for the investigating and solving of systems of linear algebraic equations with sparse (band, profile, block-diagonal with bordering) symmetric matrices on the computers of MIMD-architecture are dealt with. The performance of algorithms being studied is investigated. Some results of numeral tests carried out on MIMD computer are given.
issn	1727-4907
url	https://nasplib.isofts.kiev.ua/handle/123456789/1444
citation_txt	Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами / А.В. Попов // Пробл. програмув. — 2008. — N 2-3. — С. 111-118. — Бібліогр.: 9 назв. — рус.
work_keys_str_mv	AT popovav parallelʹnyealgoritmyrešeniâlineinyhsistemsrazrežennymisimmetričnymimatricami AT popovav parallelalgorithmsofthelinearsystemswithsparsesymmetricmatricessolving
first_indexed	2025-11-25T23:55:24Z
last_indexed	2025-11-25T23:55:24Z
_version_	1850589419242782720
fulltext	Паралельне програмування. Розподілені системи і мережі © А.В. Попов, 2008 ISSN 1727-4907. Проблеми програмування. 2008. № 2-3. Спеціальний випуск 111 УДК 519.6 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ С РАЗРЕЖЕННЫМИ СИММЕТРИЧНЫМИ МАТРИЦАМИ А.В. Попов Институт кибернетики им. В.М. Глушкова НАН Украины, 03680, Киев, проспект Академика Глушкова, 40. Тел.: 526 1196, dept150@insyg.kiev.ua Рассматриваются блочные алгоритмы прямых методов исследования и решения систем линейных алгебраических уравнений с разреженными (ленточными, профильными, блочно-диагональными с окаймлением) симметричными матрицами на компьютерах MIMD- архитектуры. Исследуется эффективность рассматриваемых алгоритмов. Приводятся некоторые результаты численных экспериментов на MIMD-компьютере. The block algorithms of direct methods for the investigating and solving of systems of linear algebraic equations with sparse (band, profile, block-diagonal with bordering) symmetric matrices on the computers of MIMD-architecture are dealt with. The performance of algorithms being studied is investigated. Some results of numeral tests carried out on MIMD-computer are given. Введение При численном решении научно-технических задач во многих случаях возникает необходимость решать задачу (или несколько задач) линейной алгебры – линейную систему (систему линейных алгебраических уравнений, СЛАУ) или алгебраическую проблему собственных значений. Причем, как правило, решение задач линейной алгебры занимает значительную часть (50 % и более) времени решения всей задачи в целом. Например, задачи линейной алгебры возникают при дискретизации краевых задач или задач на собственные значения проекционно-разностным методом (конечных разностей, конечных элементов). Важной особенностью задач линейной алгебры, возникающих при дискретизации, является высокий порядок их матриц – до миллионов, а то и до десятков миллионов. Это вызвано желанием оперировать более точными дискретными моделями, позволяющими получать приближенные решения более близкие к решениям исходных задач, лучше учитывать локальные особенности рассматриваемого процесса или явления. Другой важной особенностью является то, что количество ненулевых элементов матриц таких задач составляет kn, где k << n, а n – порядок матрицы. Разреженная структура матрицы определяется нумерацией неизвестных задачи и зачастую является ленточной, профильной, блочно-диагональной с окаймлением и т.п. Во многих случаях матрицы дискретных задач симметричны и положительно определены или полуопределены. Из-за высоких порядков, несмотря на разреженную структуру матриц, решение таких задач требует значительных вычислительных ресурсов, которые могут быть предоставлены современными параллельными компьютерами, в частности компьютерами MIMD-архитектуры. Поэтому является актуальной проблема создания для MIMD-компьютеров эффективных параллельных алгоритмов решения задач линейной алгебры, с разреженными матрицами. Под эффективным алгоритмом решения понимается алгоритм, позволяющий получить достоверное решение задачи с минимальным использованием ресурсов компьютера – процессоров, памяти, времени. Эффективность параллельных алгоритмов оценивается, как правило, с помощью коэффициентов ускорения и эффективности [1]. Важно также определить, какой алгоритм наиболее эффективен для решения конкретной задачи. Эффективность параллельных алгоритмов в значительной мере зависит от сбалансированности загрузки процессоров, которая при решении задач линейной алгебры во многом определяется способами распределения по процессорам, хранения и обработки матриц и векторов решаемой задачи. При этом необходимо стремиться к равномерной загрузке всех участвующих в решении задачи процессоров в каждый момент времени, минимизируя время пребывания процессоров в состоянии ожидания. Среди множества задач линейной алгебры с разреженными матрицами ключевое место занимает решение симметричных положительно определенных СЛАУ. Эта задача является составной частью более сложных задач, например, решения СЛАУ с полуопределенной матрицей [2], частичной обобщенной алгебраической проблемы собственных значений [3] и т.д. При решении линейных систем с симметричными положительно определенными матрицами на компьютерах традиционной архитектуры хорошо зарекомендовали себя прямые методы, в том числе метод Холецкого. Здесь рассматриваются параллельные алгоритмы решения СЛАУ с разреженными симметричными матрицами методом Холецкого. Постановка и метод решения задачи Для решения методом Холецкого линейной системы порядка n с q правыми частями Ax = b (1) Паралельне програмування. Розподілені системи і мережі 112 с симметричной матрицей, как правило, используется разложение исходной матрицы A = LLT, где L – нижняя треугольная матрица, или его модификация A = LDLT, (2) где L – нижняя треугольная матрица с единичной главной диагональю, D – диагональная матрица [4]. LDLT-факторизация открывает более широкие возможности для исследования и решения задач линейной алгебры. Например, использование LDLT-факторизации позволяет получать решение СЛАУ со знаконеопределенной симметричной матрицей. Другим примером использования LDLT-разложения является определение количества отрицательных собственных значений действительной симметричной матрицы с помощью свойства последовательности Штурма. Кроме того, при LDLT-факторизации исключаются операции извлечения квадратных корней при вычислении диагональных элементов нижней треугольной матрицы. В случае использования LDLT-разложения решение задачи (1) может быть получено в четыре этапа: − факторизация (2) исходной матрицы СЛАУ; − прямой ход – решение линейной системы с нижней треугольной матрицей Lz = b; (3) − решение СЛАУ с диагональной матрицей Dy = z; (4) − обратный ход – решение СЛАУ с верхней треугольной матрицей LTx = y. (5) Необходимо отметить, что в случае LDLT-разложения разреженной матрицы нижняя треугольная матрица L также является разреженной. Причем матрица L сохраняет характерные особенности структуры исходной матрицы A, хотя общее количество ненулевых элементов, как правило, увеличивается. Так сохраняется количество поддиагоналей ленточной матрицы и профиль матрицы профильной матрицы. Схемы распределения по процессорам разреженных матриц Все прямые методы решения СЛАУ базируются на разложении матрицы задачи в произведение матриц стандартных видов, например, нижней и верхней треугольных матриц, LDLT-разложение (2). Для алгоритмов таких разложений характерен постепенно уменьшающий от шага к шагу размер обрабатываемой части матрицы. Достаточно хорошую сбалансированность загрузки процессоров обеспечивают параллельные версии этих алгоритмов, в которых используются так называемые циклические схемы распределения и обработки матриц (см. напр. [5]). Такие циклические алгоритмы во многих случаях позволяют добиться примерно равного объема вычислений и обменов, выполняемых каждым процессором (параллельным процессом), и практически исключить влияние эффекта Гайдна. Примером циклической схемы распределения по процессорам элементов матрицы является строчная циклическая схема. В этом случае элементы строк матрицы располагаются циклически в p процессорах, участвующих в вычислениях: если в процессоре с логическим номером q располагаются элементы r-й строки матрицы, то в следующем (q+1)-м – (r+1)-й строки. Обобщением данной схемы является одномерная (строчная) блочная циклическая схема: если в q-м процессоре располагаются элементы строк матрицы с номерами sr+1,…, sr+r , то в (q+1)-м – строк с номерами s(r+1)+1,…, s(r+1)+s, где s – количество строк в блоке (можно говорить о r-й и (r+1)-й строках квадратных матричных блоков порядка s). С целью уменьшения количества арифметических операций для решения СЛАУ (1) с разреженной симметричной матрицей методом Холецкого путем перестановки строк и столбцов (т.е. перенумерации неизвестных) такую матрицу приводят к одному из стандартных видов: ленточному, профильному и т.п.. Существует множество алгоритмов оптимизации структуры разреженной матрицы и приведения ее к соответствующему стандартному виду. Их рассмотрение выходит за рамки данной работы. Будем предполагать, что разреженная матрица уже приведена к одному из таких компактных видов. Рассмотрим линейные системы с матрицами следующих структур: ленточной, профильной или блочно-диагональной с окаймлением. В случае регулярной структуры разреженной матрицы параллельные алгоритмы, в которых используется одномерная блочная циклическая схема распределения элементов матриц, позволяют добиться примерно равного объема вычислений и обменов, выполняемых каждым параллельным процессом в каждый момент времени. Такой регулярной структурой является в первую очередь ленточная структура матрицы при очевидном условии, что полуширина ленты матрицы m превосходит произведение sp. В случае регулярной профильной структуре матрицы системы, варьируя значения s и p, можно также практически сбалансировать загрузку параллельных процессов в каждый момент времени, если также ce/n > sp, где ce – общее количество поддиагональных элементов в профиле матрицы. Однако использование циклических схем распределения и обработки разреженных матриц далеко не всегда позволяет исключить эффект Гайдна. Например, в случае узких ленточных матриц при достаточно большом количестве параллельных процессов невозможно сбалансировать загрузку процессов в каждый Паралельне програмування. Розподілені системи і мережі 113 момент времени, так как количество арифметических операций, выполняемых каждым процессом, существенно отличается и может оказаться равным нулю для некоторых процессов. Также в случае блочно-диагональных матриц с окаймлением циклические схемы распределения не позволяют сбалансировать загрузку процессов. На рис. 1 показан вид блочно-диагональной матрицы с окаймлением. Дискретные задачи с матрицами такого вида получаются при решении краевых задач методом конечных элементов или методом конечных разностей. Для этого область разбивается на подобласти, число которых равно количеству процессоров и проводится дискретизация. Неизвестные дискретной задачи нумеруются в следующем порядке: вначале неизвестные, принадлежащие только одной подобласти, последовательно по подобластям, затем в таком же порядке нумеруются неизвестные, принадлежащие двум подобластям, далее трем и т.д.. Таким образом, квадратные блоки Ai (рис. 1) связаны с неизвестными, принадлежащими одной подобласти, а блоки окаймления (Bij, Ci, Vij) – с остальными неизвестными (часть блоков окаймления может быть нулевыми). В каждый процессор (с логическим номером i) помещаются по одному квадратному блоку Ai, квадратному блоку Ci, и ненулевые внедиагональные прямоугольные блоки Bji , Vki, второй индекс которых совпадает с индексом диагональных блоков. Для эффективного распараллеливания необходимо чтобы размеры квадратных блоков Ai на порядок или более превосходили размеры квадратных блоков Ci. Рассмотрим также случай СЛАУ с узкими ленточными матрицами. Для эффективного распараллеливания решения таких задач необходимо провести виртуальное переупорядочивание матрицы. Для этого узкая ленточная матрица разбивается на p (количество процессоров) приблизительно равных блоков строк, каждый из которых помещается в отдельный процессор. Соответствующим образом распределяется по процессорам и правая часть. На рис. 2 показано такое распределение для случая p = 4 (блоки разделены пунктирными линиями). После этого в каждом процессоре проводится разбиение на блоки помещенной в него подматрицы (части матрицы A). В общем случае для процессора с логическим номером k выделяется четыре блока (рис. 2): один (обозначим его Ak) порядка nk – ленточный симметричный с полушириной ленты m, второй (Ck) порядка m – квадратный симметричный, два верхних треугольных блока порядка m – Sk и Uk. Исключение составляют нулевой (нет одного из треугольных блоков) и последний (нет квадратного и одного треугольного блока) процессоры. Такое разбиение проводится так, чтобы ленточные блоки были независимы один от другого. Заметим, что как обычно хранятся только диагональные и поддиагональные элементы матрицы. Следующим шагом является виртуальное переупорядочивание матрицы – перестановка строк и столбцов, содержащих элементы блоков Ck (k = 2,0 −p ). Соответствующим образом виртуально переупорядочивается и правая часть. В результате вместо (1) получаем задачу A′x′ = b′ (6) с переупорядоченными матрицей A′ = PAP, правой частью b′ = Pb и решением x′ = Px. Матрица A′ получается блочно-диагональной с окаймлением (рис. 3), квадратные блоки Ak, которой являются ленточными матрицами, а из внедиагональных блоков ненулевыми являются только блоки Bk+1,k, Bk+1,k+1. При этом справа в блоке Bk+1,k расположен треугольный блок Sk и все остальные элементы равны нулю, а в блоке Bk+1,k+1 слева расположен нижний треугольный блок Uk T и все остальные элементы равны нулю. Еще раз заметим, что переупорядочивание виртуальное, так как реально никакие перестановки не проводятся. Поэтому в дальнейшем не потребуется переупорядочивать полученное решение. Рис. 1 Рис. 2 Рис. 3 Параллельный блочно-циклический алгоритм метода Холецкого В работе [6] предложен параллельный блочно-циклический алгоритм метода Холецкого для решения СЛАУ с ленточными симметричными матрицами, который использует вышеописанную одномерную блочно- циклическую схему распределения элементов матрицы, правой части и решения системы (1). Этот алгоритм можно использовать и для решения СЛАУ с профильными симметричными матрицами. Паралельне програмування. Розподілені системи і мережі 114 Вычислительная схема параллельного блочно-циклического алгоритма разложения (2) как ленточной, так и профильной матрицы одна и та же, отличаясь только определением величины mi (см. далее). Итак, для I = 0, 1, 2, …, N, где n = Ns+t, st ≤≤1 , выполняются следующие шаги (действия): − при I > 0 вычисляются в соответствующем процессоре элементы gi+rs,j (gi,j ≡ l i,jdj; i, j = Is–s+1,…, Is; r = 1,..., p); − вычисление в процессоре, где хранится (I+1)-я строка квадратных блоков (порядка s) матрицы A, элементов l i, i-k (k = 1,..., mi) и di, где i = Is+1,…, Is+s; − при I > 0 вычисление ненулевых элементов gi,j (i = Is+ps+1,…, n; j = Is-s+1,…, Is) квадратных блоков (порядка s) I-го столбца блоков в соответствии с их распределением по процессорам; − рассылка из процессора, где хранится (I+1)-я строка блоков матрицы A, во все остальные процессоры диагональных элементов di (i = Is+1,…, Is+s) и элементов (I+1)-й строки блоков матрицы L; − проверка положительной определенности ( di > 0 ) или невырожденности (. \|di\| > masheps ), i = Is+1,…, Is+s, матрицы A. Здесь в случае ленточной матрицы m i = min { m, i-1 }, а в случае профильной матрицы m i = i-k, где k – второй индекс первого (крайнего левого) элемента i-й строки матрицы. Приведенная вычислительная схема позволяет сохранить одномерную блочно-циклическую схему распределение по процессорам элементов матриц L и D. Элементы результата разложения (матриц L и D) сохраняются в одном массиве: значение 1/di хранится на месте элемента l i,i≡1 матрицы L. Так как все элементы матриц L и D передаются в каждый из процессоров, то для этих матриц можно изменить (увеличить) количество строк в блоках – величину s. Если эта величина не изменяется, то результат может быть помещен на место исходной матрицы. Правые части и решение задачи (1) распределяются циклически в соответствии с распределением матриц L и D. Параллельные алгоритмы решения систем (3) и (5) с треугольными матрицами для случая профильных матриц такие же, как в [6], но в вычислениях участвуют лишь ненулевые элементы матрицы. Решение системы (4) с диагональной матрицей выполняется без обменов, так как соответствующие компоненты диагональной матрицы, правых частей и решения хранятся в одном и том же процессоре. Критериями эффективности параллельного алгоритма, как правило, служат коэффициенты ускорения Sp и эффективности Ep [1, 5]: p S E T T S p p p 1 p , == , (7) где T1 – время решения задачи на одном процессоре, Tp – время решения той же задачи с использованием p параллельных процессов (процессоров). Оценив количество арифметических операций на одном процессоре в однопроцессорном и многопроцессорном вариантах и количество операций обмена и объем передаваемой и принимаемой информации, можно получить априорные оценки этих коэффициентов. В этих оценках используются величины: τс – отношение среднего времени синхронизации процессов при обмене к среднему времени выполнения процессором одной арифметической операции с плавающей запятой, τо – отношение среднего времени обмена одним машинным словом между двумя процессами к среднему времени выполнения процессором одной арифметической операции с плавающей запятой. Эффективность параллельного алгоритма решения СЛАУ с ленточной или с профильной матрицей определяется в основном эффективностью алгоритма LDLT-разложения ленточной симметричной матрицы, так как количество арифметических операций при факторизации матрицы оценивается величиной O(nm2), а при вычислении решения – O(nm). Для ленточных матриц оценки коэффициентов эффективности приведены в [6]. Эти же оценки справедливы и для случая профильных матриц, если понимать под m введенную в предыдущем разделе величину ce/n. Таким образом, ускорение и эффективность вышеприведенного параллельного алгоритма LDLT-разложения при условиях, что n ≥ sp2 и m ≥ sp, оценивается величинами ( ) ( ) Bcast2 p log122 2 τpppsm mp S +−++ +≈ , −1       + + −+≈ Bcast 2 p log 2 )1(2 1 τ m pp m ps E , (8) где sm τ τ c oBcast +=τ . Оценки (8) свидетельствует, что коэффициенты ускорения и эффективности не зависят от порядка матрицы. Параллельный блочный алгоритм метода Холецкого Из оценок (8) следует, что коэффициенты ускорения и эффективности блочно-циклического алгоритма уменьшаются с уменьшением ширины ленты. Для узких ленточных матриц (когда ширина ленты намного меньше порядка матрицы) время решения СЛАУ при росте числа используемых процессоров практически не сокращается. Оказалось, что для узких ленточных матриц целесообразно вернуться к вышеописанному нециклическому распределению элементов матрицы по процессорам. Такое распределение проводится путем виртуального Паралельне програмування. Розподілені системи і мережі 115 приведения узкой ленточной матрицы к блочно-диагональной матрице с окаймлением. Такой подход получил название “дели и побеждай” (divide-and-conquer) [7]. На рис. 4 показаны блоки распределенной в k-й процессор подматрицы матрицы A′ преобразованной задачи (6); причем в нулевом процессоре отсутствует блок U0, а в последнем – блоки Cp-1 и Sp-1. На рис. 5 показана структура нижней треугольной матрицы разложения L, а на рис. 6 – структура вычисляемой в k-м процессоре подматрицы матрицы L (в нулевом процессоре присутствуют только блоки L0, T0, а в последнем отсутствуют блоки Qp-1 и Tp-1; блоки Ek и Hk участвуют только в промежуточных вычислениях и не входят в матрицу L). Важной особенностью LDLT-разложения такой преобразованной матрицы является появление ненулевых блоков: Qk – квадратного порядка m – и Rk – прямоугольного размера m×nk – вместо треугольного блока Uk. Рис. 4 Рис. 5 Рис. 6 Рассмотрим алгоритм LDLT-разложения симметричной блочно-диагональной матрицы с окаймлением n-го порядка. Обозначим Bk – столбец блоков Bik, а C – квадратный блок, состоящий из блоков Ck и Vjk. Тогда в соответствии с (2) имеем: 1,0,, kkkkkkkk −=== pkBLDRALDL TT , (9) 1,0,kkkk −== pkRDRW T . (10) Учитывая структуру блочно-диагональной матрицы с окаймлением, при вычислении блока разложения Rk используются только размещенные в том же процессоре, что и блок Rk, блок исходной матрицы Bk и блоки разложения Lk и Dk. При этом если является нулевой одна из строк блока Bk, то нулевой оказывается соответствующая строка блока Rk, что позволяет уменьшить количество арифметических операций для разложения исходной матрицы. Аналогичные замечания справедливы относительно промежуточного блока Wk из (10). Вычисления (9), (10) проводятся параллельно и без обменов. Кроме того, структура квадратных блоков Ak и прямоугольных блоков Bk может быть оптимизирована с целью минимизации в каждом процессоре количества арифметических операций для выполнения вычислений (9), (10). Дальнейшие вычисления требуют выполнения операций обмена как для получения приведенной симметричной матрицы G, в общем случае плотной, порядок которой обозначим nr, так и ее LDLT-разложения: GFDFWСG p k =−= ∑ − = T, 1 0 k . (11) Структура симметричной матрицы G и нижней треугольной матрицы ее LDLT-разложения F определяется структурой исходной матрицы с учетом оптимизации структур блоков Ak и Bk ( 1,0 −= pk ). Так в случае узкой ленточной исходной матрицы, т.е. решения системы (6), приведенная матрица G является блочно-трех- диагональной симметричной матрицей, порядок которой nr = (p–1)m (в этом случае все матрицы из (11) являются двумерными блочными и состоят из (p–1)×(p–1) квадратных блоков). Если nr << n, то распараллеливать процесс LDLT-разложения приведенной матрицы нецелесообразно. В этом случае можно, например, сформировать приведенную матрицу в одном из процессоров и в нем же провести ее LDLT-разложение. В случае узкой ленточной исходной матрицы диагональные блоки Gk,k приведенной матрицы – это разности расположенных в соседних процессорах блоков Ck-1-Ek-1 и Ek, а поддиагональными являются блоки Pk (здесь блоки Ck и Ek являются блоками с индексами (k,k) матриц C и Wk соответственно, а блок Pk – блоком с индексом (k–1,k) матрицы Wk). Тогда, если nr << n, то далее последовательно для 1,1 −= pk в процессоре с логическим номером k выполняется: − прием от процессора с логическим номером k – 1 блока Hk-1, где ,, k1-kkkk00 TQDQEHEH −=≡ ,2,1 −= pk − факторизация диагонального блока ,k1-k1-k1-k1-k GHFDF +=T Паралельне програмування. Розподілені системи і мережі 116 − вычисление блока Qk из k1-k1-kk PFDQ =T , если k < p – 1, − вычисление блока Hk, − передача блока Hk процессору с логическим номером k + 1, если k < p – 1. В таком случае выполняется минимальное количество обменов, причем только между парами процессоров, логические номера которых отличаются на единицу. Такие обмены достаточно хорошо выполняются в большинстве используемых на MIMD-компьютерах коммуникационных средах. Если условие nr << n не выполняется, то процесс разложения приведенной матрицы необходимо распараллеливать. При этом выбор параллельного алгоритма определяется как параметрами задачи (1), так и математическими и коммуникационными свойствами MIMD-компьютера, на котором эта задача решается. Вычисление решения системы (1) или (6) с блочно-диагональной матрицей с окаймлением согласно (3)-(5) распадается на следующие подзадачи: 10,,, k -1 kkkkkkkk p-,kzDyzRwbzL ==== , (12) yxFzDygzFwbg p k ===−= − − = ∑ T,,, 1 1 0 k , (13) 0,1,kkkk −=−= pkxRyxL TT , (14) где bk, xk, yk, zk – блоки размера nk×q, а zyxb ,,, – блоки размера nr×q правой части и решений систем (5), (4), (3) соответственно, g – правая часть приведенной системы gxG = . Аналогично разложению матрицы системы все вычисления (12) выполняются параллельно для каждого k в процессоре с логическим номером k и без обменов. После этого, как и в алгоритме разложения матрицы, формируется правая часть g и вычисляется решение x приведенной системы согласно (13). Полученное решение x или его части рассылается всем процессорам, а вычисления (14) для получения блоков решения xk, как и (12), выполняются параллельно и без обменов для каждого k в процессоре с логическим номером k. Алгоритм формирования правой части и вычисления решения приведенной системы аналогичен алгоритму LDLT-разложении. Если nr << n, то решение приведенной системы проводится или в одном процессоре после формирования в нем правой части g, или последовательно в процессоре с логическим номером k для 1,1 −= pk и 1,1−= pk с использованием обменов между парами процессоров, логические номера которых отличаются на единицу. В противном случае вычисления (13) необходимо распараллеливать и параллельные алгоритмы аналогичны используемому параллельному алгоритму LDLT-разложении приведенной матрицы. Как и в случае блочно-циклического алгоритма решение СЛАУ с ленточными или профильными матрицами эффективность рассматриваемого параллельного блочного алгоритма решения СЛАУ с блочно- диагональными матрицами с окаймлением определяется эффективностью LDLT-разложения матрицы системы. Если блочно-диагональной матрицей с окаймлением является матрица задачи (1), то операции (9),(10) распараллеливаются полностью, т.е. для данных операций коэффициент эффективности распараллеливания равен 1. Коэффициент эффективности распараллеливания формирования и разложения матрицы приведенной системы, т.е. операций (11), зависит от выбранного алгоритма и всегда меньше 1. Коэффициенты ускорения и эффективности рассматриваемого параллельного блочного алгоритма LDLT-разложения можно оценить так ( )( ) 1 p 11 −+−+≈ кп pppS ττ , ( )( ) 1 p 11 −+−+≈ кп ppE ττ , (15) где τп – отношение времени LDLT-разложения матрицы приведенной системы на p процессорах ко времени LDLT-разложения матрицы системы (1) на одном процессоре, τк – отношение времени затрачиваемого на операции обмена данными между p процессорами ко времени LDLT-разложения матрицы системы (1) на одном процессоре. Рассмотрим теперь оценки коэффициентов ускорения и эффективности рассматриваемого параллельного блочного алгоритма LDLT-разложения узкой ленточной матрицы. Следствием переупорядочивания исходной матрицы является значительный рост числа арифметических операций – примерно в четыре раза. Поэтому коэффициент эффективности алгоритма не может превысить величины 0,25. В однопроцессорном случае количество арифметических операций при LDLT-разложении оценивается величиной nm2+ O(nm), а при вычислении решения СЛАУ – величиной 2nmq + O(nq). Соответственно, в многопроцессорном случае количество арифметических операций, выполняемых одним процессором, оценивается как 4(nk+m)m2+ O(nm) + O(m3) для LDLT-разложении и 4(nk+m)mq + O(nq) + O(m2q) для вычисления решения. Кроме того, при использовании p процессоров для LDLT-разложения выполняется p–1 передач и приемов по (m+1)m/2 64-битовых машинных слов, а для вычисления решения 2(p–1) передач и приемов по mq слов. Тогда коэффициент ускорения для LDLT-разложения оценивается величиной Паралельне програмування. Розподілені системи і мережі 117 1 o2 c p 412 )187( )1( 1 1 1 4 −                       ++−−+ + −≈ τ τ mn p n mp p m p S , (16) а для вычисления решения 1 o c p 224 )43( )1( 28 1 1 2 −                       ++ − −+ + −≈ τ τ mqn p n mp p m p S . (17) Коэффициенты эффективности легко получить, используя второю формулу из (7). Оценки (15) свидетельствуют, что в случае блочно-диагональной с окаймлением исходной матрицы основное влияние на эффективность рассматриваемого параллельного алгоритма оказывает формирование и решение приведенной системы. Если же исходная матрица является узкой ленточной, то повысить эффективность алгоритма можно за счет организации вычислений (в том числе обращений к памяти различного быстродействия) с прямоугольными блоками Rk, так как на эти вычисления приходится приблизительно ¾ всех арифметических операций. Результаты численных экспериментов Рассматриваемые параллельные алгоритмы метода Холецкого для решения СЛАУ с разреженными симметричными матрицами – блочно-циклические для ленточных или профильных матриц и блочный для узкой ленточной матрицы – программно реализованы на языке C в среде параллельного программирования MPI [8]. Для экспериментального исследования эффективности этих алгоритмов проведены численные эксперименты на MIMD-компьютере кластерного типа – интеллектуальной рабочей станции Инпарком-16 (разработка Института кибернетики им. В.М. Глушкова НАН Украины и ГНПП „Электронмаш“). В работе [9] приведены некоторые результаты экспериментального исследования эффективности блочно- циклического алгоритма для ленточных матриц, которые хорошо согласуются с оценками (8). Для экспериментального исследования эффективности блочно-циклического алгоритма для профильных матриц осуществлялось решение ряда задач с различной степенью заполненности матрицы ненулевыми элементами. Далее на диаграммах (рис. 7) показаны ускорения, получаемые при решении СЛАУ с профильной матрицей на различном количестве процессоров или при различном количестве строк в блоке. Параметры системы: порядок n = 44 436, максимальная полуширина ленты m = 4 476, заполненность ленты матрицы – 21 %. Использование блочно-циклического алгоритма для профильных матриц вместо этого же алгоритма для ленточных матриц для решения СЛАУ, порядок которой 1 332 000, максимальная полуширина ленты 1 005, заполненность ленты матрицы 85 %, позволило сократить время решения в 1,32 раза. Рис. 7 Для экспериментального исследования эффективности блочного алгоритма решения СЛАУ с узкими ленточными матрицами осуществлялось решение нескольких СЛАУ с одной правой частью. На рис. 8 показаны графики зависимости от числа используемых процессоров ускорений, получаемых при решении четырех СЛАУ: задача 1 – n = 150 000, m = 151; задача 2 – n = 150 000, m = 301; задача 3 – n = 600 000, m = 151; задача 4 – n = 56 942, m = 143. На левой диаграмме (рис. 9) представлены отношения времени решения на 1, 8, 12 и 16 процессорах к времени решения на 4 процессорах одной и той же СЛАУ (q = 1, m = 151) при различных порядках матрицы. А на правой диаграмме (рис. 9) – отношения времени решения на 1, 8, 12 и 16 процессорах к времени решения на 4 процессорах одной и той же СЛАУ (q = 1, n = 600 000) при различных значениях полуширины ленты матрицы. Для некоторых вариантов решение на одном процессоре не проводилось, так как для размещения данных не хватало оперативной памяти процессора. Полученные результаты хорошо согласуются с априорными оценками (16) и (17), что позволяет оценить значения выражений τс + m2τо и τс + 2mqτо для конкретного MIMD-компьютера. В дальнейшем данные значения 0,0 2,0 4,0 6,0 8,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Количество процессоров 0,0 2,0 4,0 6,0 8,0 1 2 3 4 5 6 8 10 12 14 16 20 24 30 Количество строк в блоке Паралельне програмування. Розподілені системи і мережі 118 могут использоваться при оптимизации количества процессоров для эффективного решения конкретной задачи с помощью рассматриваемого алгоритма, а также при выборе самого алгоритма решения. Так приведенные результаты свидетельствуют, что использование рассматриваемого алгоритма для решения задачи 2 малоэффективно. Для задач с таким соотношением порядка и полуширины ленты матрицы целесообразно использовать циклический алгоритм, например описанный в [6]. 0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 5,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 количество процессоров задача 1 задача 2 задача 3 задача 4 Рис. 8 0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 5,0 56 942 300 000 600 000 900 000 1 200 000 1 500 000 порядок СЛАУ 1 проц. 4 проц. 8 проц. 12 проц. 16 проц. 0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 5,0 51 101 151 201 251 301 полуширина ленты матрицы СЛАУ 1 проц. 4 проц. 8 проц. 12 проц. 16 проц. Рис. 9 Выводы Рассмотренные в работе параллельные алгоритмы позволяют эффективно решать на MIMD-компьютере линейные системы с разреженными симметричными матрицы с регулярной структурой трех видов – ленточными с различной шириной ленты, профильными и блочно-диагональными с окаймлением. Для задач с такими матрицами можно уменьшить количество арифметических операций, если исключить вычисление всех априорно нулевых элементов нижней треугольной матрицы LDLT-разложения исходной матрицы. Однако это часто приводит к существенному нарушению сбалансированности рассмотренных параллельных алгоритмов. Поэтому целесообразно продолжить разработку эффективных параллельных алгоритмов для решения СЛАУ с матрицами нерегулярной разреженной структуры, что позволит как расширить множество эффективно решаемых на MIMD-компьютере задач, так и повысить эффективность решения рассмотренных здесь задач. 1. Молчанов И.Н., Химич А.Н., Попов А.В. и др. Об эффективной реализации вычислительных алгоритмов на MIMD-компьютерах // Искусственный интеллект. – 2005. – № 3. – С. 175–184. 2. Попов А.В., Химич А.Н. Исследование и решение первой основной задачи теории упругости // Компьютерная математика. – 2003. – № 2. – С. 105–114. 3. Молчанов И.Н., Попов А.В., Химич А.Н., Алгоритм решения частичной проблемы собственных значений для больших ленточных матриц // Кибернетика и системный анализ. – 1992. – № 2. – С. 141–147. 4. Уилкинсон Дж. Х., Райнш К. Справочник алгоритмов на языке Алгол. Линейная алгебра. – М.: Машиностроение, 1976. – 389 с. 5. Численные методы для многопроцессорного вычислительного комплекса ЕС / В.С. Михалевич, Н.А. Бик, …, А.Н. Химич и др. / Под редакцией И.Н. Молчанова. – М.: Изд. ВВИА им. Н.Е. Жуковского, 1986. – 401 с. 6. Попов А.В., Химич А.Н. Параллельный алгоритм решения системы линейных алгебраических уравнений с ленточной симметричной матрицей // Компьютерная математика. – 2005. – № 2. – С. 52–59. 7. http://www.netlib.org/scalapack 8. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХП-Петербург, 2004. – 608 с. 9. Зубатенко В.С., Майстренко А.С., Молчанов И.Н. и др. Исследование некоторых параллельных алгоритмов решения задач линейной алгебры на MIMD-компьютерах // Искусственный интеллект. – 2006. – № 3. – С. 129–138.

Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами

Institution

Ähnliche Einträge