|
|
| (не показано 14 промежуточных версий 4 участников) |
| Строка 1: |
Строка 1: |
| − | {{algorithm
| + | #REDIRECT [[Классическая монотонная прогонка, повторный вариант]] |
| − | | name = Повторная прогонка для нового СЛАУ с трёхдиагональной матрицей,<br /> точечный вариант
| |
| − | | serial_complexity = <math>O(n)</math>
| |
| − | | pf_height = <math>O(n)</math>
| |
| − | | pf_width = <math>1</math>
| |
| − | | input_data = <math>O(n)</math>
| |
| − | | output_data = <math>n</math>
| |
| − | }}
| |
| − | | |
| − | Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]
| |
| − | | |
| − | == Свойства и структура алгоритма ==
| |
| − | | |
| − | [[file:ProgonkaRep.png|thumb|right|200px|Рисунок 1. Граф алгоритма повторной прогонки при n=8 без отображения входных и выходных данных. '''/''' - деление, '''''f''''' - операция '''''a+bc''''' или '''''a-bc'''''.]]
| |
| − | === Общее описание алгоритма ===
| |
| − | | |
| − | '''Прогонка''' - один из вариантов метода исключения неизвестных в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где
| |
| − | :<math>
| |
| − | A = \begin{bmatrix}
| |
| − | a_{11} & a_{12} & 0 & \cdots & \cdots & 0 \\
| |
| − | a_{21} & a_{22} & a_{23}& \cdots & \cdots & 0 \\
| |
| − | 0 & a_{32} & a_{33} & \cdots & \cdots & 0 \\
| |
| − | \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\
| |
| − | 0 & \cdots & \cdots & a_{n-1 n-2} & a_{n-1 n-1} & a_{n-1 n} \\
| |
| − | 0 & \cdots & \cdots & 0 & a_{n n-1} & a_{n n} \\
| |
| − | \end{bmatrix}, x = \begin{bmatrix}
| |
| − | x_{1} \\
| |
| − | x_{2} \\
| |
| − | \vdots \\
| |
| − | x_{n} \\
| |
| − | \end{bmatrix}, b = \begin{bmatrix}
| |
| − | b_{1} \\
| |
| − | b_{2} \\
| |
| − | \vdots \\
| |
| − | b_{n} \\
| |
| − | \end{bmatrix}
| |
| − | </math>
| |
| − | | |
| − | Часто, однако, при изложении сути метода прогонки<ref name="SETKI">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref> элементы правой части и матрицы системы обозначают и нумеруют по-другому, например СЛАУ может иметь вид (<math>N=n+1</math>)
| |
| − | | |
| − | :<math>
| |
| − | A = \begin{bmatrix}
| |
| − | c_{0} & -b_{0} & 0 & \cdots & \cdots & 0 \\
| |
| − | -a_{1} & c_{1} & -b_{1} & \cdots & \cdots & 0 \\
| |
| − | 0 & -a_{2} & c_{2} & \cdots & \cdots & 0 \\
| |
| − | \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\
| |
| − | 0 & \cdots & \cdots & -a_{N-1} & c_{N-1} & -b_{N-1} \\
| |
| − | 0 & \cdots & \cdots & 0 & -a_{N} & c_{N} \\
| |
| − | \end{bmatrix}\begin{bmatrix}
| |
| − | x_{0} \\
| |
| − | x_{1} \\
| |
| − | \vdots \\
| |
| − | x_{N} \\
| |
| − | \end{bmatrix} = \begin{bmatrix}
| |
| − | f_{0} \\
| |
| − | f_{1} \\
| |
| − | \vdots \\
| |
| − | f_{N} \\
| |
| − | \end{bmatrix}
| |
| − | </math>
| |
| − | или, если записывать отдельно по уравнениям, то
| |
| − | :<math>
| |
| − | c_{0} y_{0} - b_{0} y_{1} = f_{0},\\
| |
| − | -a_{i} y_{i-1} + c_{i} y_{i} - b_{i} y_{i+1} = f_{i}, 1 \le i \le N-1, \\
| |
| − | -a_{N} y_{N-1} + c_{N} y_{N} = f_{N}
| |
| − | </math>
| |
| − | | |
| − | Здесь рассматривается тот вариант прогонки, когда проходится вся СЛАУ сверху вниз и обратно. Суть метода - в исключении из уравнений неизвестных, сначала - сверху вниз - под диагональю, а потом - снизу вверх - над диагональю.
| |
| − | | |
| − | === Математическое описание алгоритма ===
| |
| − | | |
| − | В приведённых обозначениях в прогонке сначала выполняют её прямой ход - вычисляют коэффициенты
| |
| − | | |
| − | :<math>
| |
| − | \alpha_{1} = b_{0}/c_{0},\\
| |
| − | \beta_{1} = f_{0}/c_{0}, \\
| |
| − | \alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N-1, \\
| |
| − | \beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N.
| |
| − | </math>
| |
| − | после чего вычисляют решение с помощью обратного хода
| |
| − | :<math>
| |
| − | y_{N} = \beta_{N+1}, \\
| |
| − | y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}, \quad i = N-1, N-2, \cdots , 1, 0.
| |
| − | </math>
| |
| − | | |
| − | В литературе<ref name="SETKI" /> указывается, что данные формулы эквивалентны вычислению одного из <math>LU</math>-разложений матрицы системы с последующим решением двухдиагональных систем методом обратной подстановки.
| |
| − | | |
| − | === Вычислительное ядро алгоритма ===
| |
| − | | |
| − | Вычислительное ядро алгоритма можно представить из двух частей - прямого и обратного хода. В прямом ходе ядро составляют последовательности операций деления, умножения и сложения/вычитания. В обратном ходе в ядре остаются только последовательности умножения и сложения.
| |
| − | [[file:ProgonkaRepMul.png|thumb|left|200px|Рисунок 2. Граф алгоритма повторной прогонки с предвычислением обратных чисел при n=8 без отображения входных и выходных данных. '''m''' - умножение на предвычисленное обратное число, '''''f''''' - операция '''''a-bc''''' или '''''a+bc'''''.]] | |
| − | | |
| − | === Макроструктура алгоритма ===
| |
| − | | |
| − | Кроме представления макроструктуры алгоритма как совокупности прямого и обратного хода, прямой ход также может быть разложен на две макроединицы - разложения матрицы и прямого хода решения двухдиагональной СЛАУ, которые выполняются "одновременно", т.е., параллельно друг другу. При этом решение двухдиагональной СЛАУ использует результаты разложения.
| |
| − | | |
| − | === Схема реализации последовательного алгоритма ===
| |
| − | | |
| − | Последовательность исполнения метода следующая:
| |
| − | | |
| − | 1. Инициализируется прямой ход прогонки:
| |
| − | | |
| − | :<math>
| |
| − | \alpha_{1} = b_{0}/c_{0},\\
| |
| − | \beta_{1} = f_{0}/c_{0}, \\
| |
| − | </math>
| |
| − | | |
| − | 2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:
| |
| − | | |
| − | :<math>
| |
| − | \alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i}), \\
| |
| − | \beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}).
| |
| − | </math>
| |
| − | | |
| − | 3. Инициализируется обратный ход прогонки:
| |
| − | | |
| − | :<math>
| |
| − | y_{N} = (f_{N}+a_{N}\beta_{N})/(c_{N}-a_{N}\alpha_{N})
| |
| − | </math>
| |
| − | | |
| − | 4. Последовательно для всех i с убыванием от N-1 до 0 выполняются формулы обратного хода:
| |
| − | :<math>
| |
| − | y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}.
| |
| − | </math>
| |
| − | | |
| − | В связи с тем, что почти во всех формулах есть пары делений на одно и то же выражение, можно поменять их на последовательности вычисления обратных чисел с последующими умножениями на них.
| |
| − | | |
| − | === Последовательная сложность алгоритма ===
| |
| − | | |
| − | Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в последовательном (наиболее быстром) варианте требуется:
| |
| − |
| |
| − | * <math>2n-1</math> делений,
| |
| − | * <math>3n-3</math> сложений/вычитаний,
| |
| − | * <math>3n-3</math> умножений.
| |
| − | | |
| − | При классификации по последовательной сложности, таким образом, прогонка относится к алгоритмам ''с линейной сложностью''.
| |
| − | | |
| − | === Информационный граф ===
| |
| − | | |
| − | Информационный граф прогонки изображён на рис.1. Как видно, он почти последователен: при выполнении прямого хода две ветви (левая - разложение матрицы, центральная - решение первой из двухдиагональных систем) могут выполняться параллельно друг другу. Правая ветвь соответствует обратному ходу. По рисунку видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход".
| |
| − | Вариант с заменой делений даёт граф, который изображён на рис.2.
| |
| − | | |
| − | === Описание ресурса параллелизма алгоритма ===
| |
| − | | |
| − | Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие ярусы:
| |
| − | | |
| − | * <math>n</math> ярусов делений (в каждом из ярусов, кроме одного, по 2 деления),
| |
| − | * по <math>2n - 2</math> ярусов умножений и сложений/вычитаний (в n-1 ярусах - по 2 операции, в n-1 - по одной).
| |
| − |
| |
| − | При классификации по высоте ЯПФ, таким образом, прогонка относится к алгоритмам со сложностью <math>O(n)</math>. При классификации по ширине ЯПФ его сложность будет <math>2</math>.
| |
| − | | |
| − | === Входные и выходные данные алгоритма ===
| |
| − | | |
| − | '''Входные данные''': трёхдиагональная матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>b</math> (элементы <math>b_{i}</math>).
| |
| − | | |
| − | '''Выходные данные''': вектор <math>x</math> (элементы <math>x_{i}</math>).
| |
| − | | |
| − | '''Объём выходных данных''': <math>n</math>.
| |
| − | | |
| − | === Свойства алгоритма ===
| |
| − | | |
| − | Соотношение последовательной и параллельной сложности, как хорошо видно, является ''константой'' (причём менее 2).
| |
| − | | |
| − | При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – тоже ''константа''.
| |
| − | | |
| − | Алгоритм в рамках выбранной версии полностью детерминирован.
| |
| − | | |
| − | Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. Тогда гарантируется устойчивость алгоритма.
| |
| − | В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунки с графом алгоритма) можно не повторять. Это связано с тем, что <math>LU</math>-разложение матрицы системы не нужно перевычислять. Тогда предпочтителен вариант с заменой делений.
| |
| − | | |
| − | == Программная реализация алгоритма ==
| |
| − | | |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − | | |
| − | В зависимости от нужд вычислений, возможны как разные способы хранения матрицы СЛАУ (в виде одного массива с 3 строками или в виде 3 разных массивов), так и разные способы хранения вычисляемых коэффициентов (на месте использованных уже элементов матрицы либо отдельно).
| |
| − | | |
| − | === Локальность данных и вычислений ===
| |
| − | | |
| − | Как видно по графу алгоритма, локальность данных по пространству хорошая - все аргументы, что нужны операциям, вычисляются "рядом". Однако по времени локальность вычислений не столь хороша. Если данные задачи не помещаются в кэш, то вычисления в "верхнем левом углу" СЛАУ будут выполняться с постоянными промахами кэша. Отсюда может следовать одна из рекомендаций использующим прогонку - организовать все вычисления так, что бы прогонки были "достаточно коротки" для помещения данных в кэш.
| |
| − | | |
| − | === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| − | | |
| − | Как видно по графу алгоритма, его практически (без видоизменений) невозможно распараллелить. Поэтому есть два способа использования прогонок для параллельных вычислительных систем: либо разбивать задачу, где используются прогонки, так, чтобы их было достаточно, чтобы на каждую. из прогонок приходился 1 процессор (1 ядро), либо использовать вместо прогонки её параллельные заменители (циклическую редукцию, последовательно-параллельные варианты и т.п.)
| |
| − | | |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | | |
| − | О масштабируемости самой прогонки, как непараллельного алгоритма, говорить нельзя в принципе. Однако необходимо указать на то, что сравнение параллельных заменителей прогонки при изучении их масштабируемости должно идти не с однопроцессорными вариантами этих заменителей, а с выполнением на 1 процессоре самой прогонки.
| |
| − | | |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | === Выводы для классов архитектур ===
| |
| − | | |
| − | Прогонка - метод для архитектуры классического, фон-неймановского типа. Для распараллеливания решения СЛАУ с трёхдиагональной матрицей следует взять какой-либо её параллельный заменитель, например, наиболее распространённую [[Метод циклической редукции|циклическую редукцию]], или уступающий ей по критическому пути, но имеющий более регулярную структуру графа новый [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками|последовательно-параллельный метод]].
| |
| − | | |
| − | === Существующие реализации алгоритма ===
| |
| − | | |
| − | == Литература ==
| |
| − | | |
| − | <references />
| |
| − | | |
| − | [[Категория:Алгоритмы с низким уровнем параллелизма]]
| |
| − | [[Категория:Статьи в работе]]
| |
