решение разреженных симметричных слау на суперкомпьютерах
| Вид материала | Решение |
- Тема задания, 96.02kb.
- Решение слау методом Зейделя, 30.35kb.
- Лабораторная работа 1 Методы решения задач линейной алгебры, 32.21kb.
- Нелинейными называются электрические цепи, содержащие нелинейные элементы, т е. элементы, 272.94kb.
- Решение слау с разреженными матрицами, 32.92kb.
- Ускорение решения задачи оптимизации дозового распределения при лучевой терапии с применением, 29.69kb.
- Параллельные алгоритмы решения трехмерных упруго-пластических задач, 98.53kb.
- Тема: «теория матриц» Основная задача линейной алгебры, 28.88kb.
- Темы рефератов аспирантов и соискателей (2011) фио, 318.75kb.
- Зазеркалье Льюиса Кэрролла. Симметричные фигуры Тип урок, 151.59kb.
РЕШЕНИЕ РАЗРЕЖЕННЫХ СИММЕТРИЧНЫХ СЛАУ НА СУПЕРКОМПЬЮТЕРАХ
САФОНОВА Я.Ю.
Нижегородский государственный университет им. Н.И. Лобачевского
Введение
Системы линейных алгебраических уравнений
с симметричной положительно определенной матрицей 
возникают в различных прикладных областях, в том числе при численном решении дифференциальных уравнений в задачах математической физики. Для решения систем такого рода используют разложение Холецкого. Верхнетреугольная матрица 
будет являться разложением исходной матрицы, если выполняется условие:
.Тогда искомый вектор можно найти решением двух систем:
Для отыскания разложения матрицы существуют известные алгоритмы, описанные в [1,2]. В дальнейших рассуждениях будем опираться на алгоритм, формирующий матрицу
по строкам. В общем случае нельзя организовать параллельное вычисление строк матрицы , поскольку значения в строке с номером 
зависят от значений в строках с номерами 
. Однако возникающие на практике системы часто являются разреженными, т.е. матрица содержит 
ненулевых элементов. При этом строгая зависимость между строками может нарушаться и, если строка не «зависит» от строки 
, значения в них можно вычислять параллельно. В [3] и [4] дано определения дерева исключения как структуры зависимости между строками разреженной матрицы. В [5] приведено описание параллельного алгоритма на основе такой структуры. Однако дерево исключения произвольной матрицы может иметь структуру, не допускающую распараллеливание. В этом случае разумно применять алгоритмы переупорядочивания матрицы, формирующие дерево исключения «хорошего» с точки зрения параллельного расчета вида. В качестве такого переупорядочивания предлагается использовать метод вложенных сечений. В данной статье предлагается технология решения СЛАУ, использующая структуру разреженности матрицы с ее предварительным переупорядочиванием.Дерево исключения и связь с параллельным алгоритмом Холецкого
Определение 1. Пусть
- граф матрицы . Деревом исключения 
матрицы называется дерево с множеством вершин, совпадающим с множеством 
, причем 
является родителем 
тогда и только тогда, когда первый ненулевой наддиагональный элемент в строке располагается в столбце . Пусть
- дерево исключения. Тогда верны следующие теоремы [3].Теорема 1. Для
числовые значения в строке зависят от числовых значений в строке тогда и только тогда, когда в существуют путь из в .Теорема 2. Если в
существуют путь из в и 
, то - предок в .Теорема 3. Вершина
в дереве исключения будет листом, если строка матрицы не содержит недиагональных элементов.Обозначим за
поддерево дерева с вершиной 
в корне.Теорема 4. Пусть
и 
- непересекающиеся поддеревья дерева , ни одна вершина из не является предком какой-либо вершины из и наоборот, тогда 
и 
ребро 
, и строки, соответствующие вершинам в и , могут вычисляться независимо.Следовательно, если
- предок в дереве исключения , то при вычислении матрицы строка должна быть определена перед строкой . Порядок вычисления должен соответствовать обходу дерева исключения «снизу - вверх» и начинаться со строк, соответствующих листьям в . При этом по теореме 4 дерево исключения можно разбить таким образом, что некоторые строки будут вычисляться параллельно. Распределение вычислений между процессорами
Распределение данных в параллельном алгоритме Холецкого должно быть таким, чтобы соблюдалась балансировка загрузки вычислителей.
Предлагается разбивать дерево исключения на независимые поддеревья и обрабатывать параллельно те из них, которые удовлетворяют условиям теоремы 4, приведенной в предыдущей главе. Один из способов разбиения – разбиение на поддеревья фиксированной высоты.
Связь вида дерева исключения с эффективностью применения параллельного алгоритма
Дерево исключения произвольной матрицы иметь может как «хороший» (рис. 1, а), так и «плохой» (рис. 1, b) вид с точки зрения распараллеливания.
| a)  b) Рис. 1. Виды деревьев исключения |
Поскольку построение дерева исключения и определение его свойств – достаточно трудоемкая задача, по сложности равносильная символической факторизации матрицы
[3], на практике применяют приведение исходной матрицы к виду, для которого дерево исключения становится известно. В качестве такого способа приведения матрицы дальше будет рассматриваться переупорядочивание матрицы.Переупорядочивание матриц и связь с деревом исключения
Переупорядочивание матрицы часто используется для уменьшения заполнения фактора. При этом решение исходной системы сводится к решению эквивалентной системы:
, где 
- матрица перестановок. На практике применяют различные способы поиска матрицы перестановок. Остановимся подробнее на методе вложенных сечений. Главная идея метода заключается поиске разделителя в графе матрицы, после удаления которого граф распадается на два несвязных между собой подграфа. Полученные подграфы обрабатываются по этой же схеме. Процедура продолжается до тех пор, пока поиск разделителя возможен. Матрица перестановок составляется следующим образом: для текущего графа 
с разделителем 
и подграфами 
и 
сначала нумеруются вершины подграфов , , а затем вершины разделителя . Поскольку между полученными графами и нет связей, соответствующие им строки могут обрабатываться независимо. Так как разделитель связан с обоими графами, а его вершины имеют индексы большие, чем вершины графов, то вершины должны обрабатываться после того, как обработаны вершины и . Таким образом, можно составить дерево исключения переупорядоченной матрицы. В корне будут находиться вершины разделителя, выбранного на первой итерации. Его потомками будут вершины образованных подграфов. Полученное дерево будет бинарным и хорошо сбалансированным, если получаемые каждый раз подграфы и сравнимы по мощности.Программная реализация
На основе выводов из теоретической части реализована схема распараллеливания решения разреженных симметричных СЛАУ
, включающая следующие шаги:- Переупорядочивание матрицы методом вложенных сечений. Итогом этого шага должны быть матрица перестановок и дерево исключения для матрицы
.
- Разбиение дерева на поддеревья и определение порядка их обработки, допускающего параллельное выполнение.
- Факторизация матрицы . Этот шаг может быть разделен на символическую и численную части. Символическая часть определяет объем памяти, требуемый для хранения фактора, численная – вычисляет его значения.
- Решение треугольных систем.
Шаги 3 и 4 могут допускать распараллеливание с помощью разбиения дерева исключения, построенного на шаге 2.
Экспериментальная часть
В первой серии экспериментов проверялось качество метода вложенных сечений по отношению к другим известным способам переупорядочивания по критериям заполнение фактора и высота дерева исключения. В качестве тестов были выбраны типовые матрицы из различных прикладных областей [7]. В таблице 1 приведены их характеристики.
Таблица 1. Характеристики тестовых матриц для серии 1
| Название матрицы | Порядок | Количество ненулевых элементов |
| bcsstk24 | 3562 | 159910 |
| ex13 | 2568 | 75628 |
| ex9 | 3363 | 99471 |
| nasa2146 | 2146 | 72250 |
| nasa2910 | 2910 | 174296 |
| nasa4704 | 4704 | 104756 |
| plat1919 | 1919 | 32399 |
| s1rmq4m1 | 5489 | 281111 |
Каждая матрица была переупорядочена следующими алгоритмами:
- прямой (CM) и обратный (RCM) алгоритмы Катхилла-Макки,
- алгоритм Кинга (King),
- алгоритм Слоана (Sloan),
- метод вложенных сечений (ND).
В скобках указаны используемые далее сокращения.
Во второй таблице приведена высота дерева исключения для каждого переупорядочивания:
Таблица 2. Высота дерева исключения для разных способов переупорядочивания
| | CM | RCM | King | Sloan | ND |
| bcsstk24 | 3561 | 3331 | 3561 | 3366 | 636 |
| ex13 | 2567 | 2507 | 2567 | 2395 | 412 |
| ex9 | 3361 | 3348 | 3362 | 3206 | 401 |
| nasa2146 | 2145 | 2145 | 2145 | 2143 | 369 |
| nasa2910 | 2886 | 2595 | 2909 | 2615 | 856 |
| nasa4704 | 4703 | 4658 | 4703 | 4656 | 785 |
| plat1919 | 1918 | 1694 | 1918 | 1911 | 198 |
| s1rmq4m1 | 5488 | 5488 | 5488 | 5487 | 646 |
Видно, что метод вложенных сечений дает высоту дерева исключения существенно меньшую, чем прочие алгоритмы переупорядочивания. Это наглядно иллюстрирует рисунок 2, где приведены мера высоты каждого дерева исключения. Под мерой высоты дерева исключения будем понимать отношение его высоты к максимально возможной высоте для данного количества вершин.
Рис. 2. Статистика по методам переупорядочивания с точки зрения высоты дерева исключения
В таблице 3 приведены результаты по заполнению, возникшему в результате разложения переупорядоченной матрицы
Таблица 3. Заполнение фактора для разных способов переупорядочивания
| | CM | RCM | King | Sloan | ND |
| bcsstk24 | 0,108542 | 0,076171 | 0,242667 | 0,074419 | 0,070044 |
| ex13 | 0,072224 | 0,038567 | 0,39992 | 0,038236 | 0,060245 |
| ex9 | 0,050996 | 0,028501 | 0,402983 | 0,027406 | 0,043347 |
| nasa2146 | 0,0869 | 0,085057 | 0,149437 | 0,071491 | 0,066504 |
| nasa2910 | 0,30594 | 0,111008 | 0,662818 | 0,103957 | 0,115775 |
| nasa4704 | 0,09564 | 0,082721 | 0,217902 | 0,075596 | 0,044584 |
| plat1919 | 0,059571 | 0,050495 | 0,122758 | 0,133724 | 0,046445 |
| s1rmq4m1 | 0,087188 | 0,086186 | 0,116613 | 0,06871 | 0,042296 |
Полученные результаты по заполнению показывают, что заполнение, возникшее после применения метода вложенных сечений не хуже прочих показателей. Это проиллюстрировано на рисунке 3.
Рис. 3. Статистика по методам переупорядочивания с точки зрения заполнения фактора
Таким образом, применение метода вложенных сечений дает хорошее для распараллеливания дерево исключения и заполнение, сравнимое с показателями других известных методов.
Во второй серии экспериментов испытывалась предложенная в программной реализации схема. Продемонстрируем распараллеливание с помощью разбиения дерева исключения на примере численной факторизации и решения треугольных систем для матрицы parabolic_fem [7]. Для ее дерева исключения было построено разбиение на поддеревья высоты 50, 75 и 100. В качестве технологии распараллеливания выбрана библиотека Intel TBB [6]. Рисунки 5 и 6 показывают результаты ускорения для численной факторизации и решения систем соответственно. Количество потоков на приведенных графиках меняется от 1 до 8.
Рис. 5. Ускорение, полученное при численной факторизации матрицы parabolic_fem
Рис. 6. Ускорение, полученное при решении треугольных систем для СЛАУ с матрицей parabolic_fem в левой части
Заключение
В статье сформулирована параллельная схема решения симметричных разреженных СЛАУ с помощью предварительного переупорядочивания матрицы в левой части методом вложенных сечений. Собранная статистика по различным методикам переупорядочивания показывает, что предложенный метод дает существенный выигрыш при распараллеливании и заполнение, сравнимое с прочими алгоритмами, что говорит в пользу его применимости, а применение параллельного расчета дает ускорение до 2-3 раз на 8 потоках.
Литература
- Писсанецки С. Технология разреженных матриц: Пер. с англ. – М.: Мир, 1988. С. 76-80.
- А. Джордж, Дж. Лю. Численное решение больших разреженных систем уравнений. 1984. М.: Мир.
- J. van Grondelle. Symbolic Sparse Cholesky Factorization Using Elimination Trees. Master’s thesis, Utrecht University, 1999. P. 3-6.
- P. Heggernes. Minimizing fill-in size and elimination tree height in parallel Cholesky factorization. Thesis for the degree of Cand. Scient, University of Bergen, 1992. P. 15-17.
- H. Hafsteinsson. Parallel Sparse Cholesky Factorization. Ph. D. thesis, Department of Computer Cormell University Ithaca, NY. 1989, P. 53-58.
- Intel® Threading Building Blocks. Tutorial. Version 3.0 – Intel Corporation, 2011.
Интернет-источники:
- The University of Florida Sparse Matrix Collection
[ufl.edu/research/sparse/matrices/]