Повторная прогонка, точечный вариант
| Повторная прогонка для нового СЛАУ с трёхдиагональной матрицей, точечный вариант | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ 5n-4 }[/math] |
| Объём входных данных | [math]\displaystyle{ 4n-2 }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ 5n-4 }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ 1 }[/math] |
Основные авторы описания: А.В.Фролов
Свойства и структура алгоритма
Общее описание алгоритма
Повторная прогонка - часть метода прогонки в приложении к решению СЛАУ[1][2] вида[3]
- [math]\displaystyle{ 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} y_{0} \\ y_{1} \\ \vdots \\ y_{N} \\ \end{bmatrix} = \begin{bmatrix} f_{0} \\ f_{1} \\ \vdots \\ f_{N} \\ \end{bmatrix} }[/math]
для того случая, когда ранее уже была выполнена прогонка для СЛАУ с той же матрицей, но с другой правой частью. В этом случае та часть формул прогонки, что связана только с матрицей, уже предвычислена, и повторять её не надо.
Математическое описание алгоритма
В приведённых обозначениях в повторной прогонке сначала выполняют её прямой ход - вычисляют коэффициенты
- [math]\displaystyle{ \beta_{1} = f_{0}/c_{0}, \\ \beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N. }[/math]
после чего вычисляют решение с помощью обратного хода
- [math]\displaystyle{ 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]
В литературе[3] указывается, что данные формулы эквивалентны вычислению решений двухдиагональных систем методом обратной подстановки в условиях предвычисленного [math]\displaystyle{ LU }[/math]-разложения матрицы системы.
Вычислительное ядро алгоритма
Вычислительное ядро алгоритма можно представить из двух частей - прямого и обратного хода. В прямом ходе ядро составляют последовательности операций умножения и сложения (последних вдвое меньше). В обратном ходе в ядре тоже только последовательности умножения и сложения, но в равном количестве.
Макроструктура алгоритма
Макроструктура алгоритма - совокупность прямого и обратного хода.
Схема реализации последовательного алгоритма
Последовательность исполнения метода следующая:
1. Инициализируется прямой ход прогонки:
- [math]\displaystyle{ \beta_{1} = f_{0}/c_{0}, \\ }[/math]
2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:
- [math]\displaystyle{ \beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}). }[/math]
3. Инициализируется обратный ход прогонки:
- [math]\displaystyle{ y_{N} = (f_{N}+a_{N}\beta_{N})/(c_{N}-a_{N}\alpha_{N}) }[/math]
4. Последовательно для всех i с убыванием от N-1 до 0 выполняются формулы обратного хода:
- [math]\displaystyle{ y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}. }[/math]
Для быстрейшей работы повторной прогонки все деления в формулах заменяются умножением на предвычисленные обратные числа ([math]\displaystyle{ 1/c_{0} }[/math] и [math]\displaystyle{ 1/(c_{i}-a_{i}\alpha_{i}) }[/math].
Последовательная сложность алгоритма
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в последовательном (наиболее быстром, с предвычислением обратных чисел) варианте требуется:
- [math]\displaystyle{ 2n-2 }[/math] сложений,
- [math]\displaystyle{ 3n-2 }[/math] умножений.
При классификации по последовательной сложности, таким образом, повторная прогонка относится к алгоритмам с линейной сложностью.
Информационный граф
Информационный граф прогонки без предвычисления обратных чисел изображён на рис.1. Как видно, он последователен. Левая ветвь соответствует прямому, правая - обратному ходу. По рисунку видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход". Вариант с заменой делений на умножения даёт граф, который изображён на рис.2.
Описание ресурса параллелизма алгоритма
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие ярусы:
- [math]\displaystyle{ n }[/math] ярусов умножений (в каждом из ярусов по одному умножению),
- по [math]\displaystyle{ 2n - 2 }[/math] ярусов умножений и сложений (все ярусы - по одной операции).
При классификации по высоте ЯПФ, таким образом, повторная прогонка относится к алгоритмам со сложностью [math]\displaystyle{ O(n) }[/math]. При классификации по ширине ЯПФ его сложность будет [math]\displaystyle{ 1 }[/math].
Входные и выходные данные алгоритма
Свойства алгоритма
Соотношение последовательной и параллельной сложности, как хорошо видно, является константой (причём это единица).
При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – тоже константа.
Алгоритм в рамках выбранной версии полностью детерминирован.
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
В зависимости от нужд вычислений, возможны как разные способы хранения разложения матрицы СЛАУ, так и разные способы хранения вычисляемых коэффициентов.
Локальность данных и вычислений
Как видно по графу алгоритма, локальность данных по пространству хорошая - все аргументы, что нужны операциям, вычисляются "рядом". Однако по времени локальность вычислений не столь хороша. Если данные задачи не помещаются в кэш, то вычисления в "верхнем левом углу" СЛАУ будут выполняться с постоянными промахами кэша. Отсюда может следовать одна из рекомендаций использующим прогонку - организовать все вычисления так, что бы прогонки были "достаточно коротки" для помещения данных в кэш.
Возможные способы и особенности параллельной реализации алгоритма
Как видно по графу алгоритма, его практически (без видоизменений) невозможно распараллелить. Поэтому есть два способа использования повторных прогонок для параллельных вычислительных систем: либо разбивать задачу, где используются прогонки, так, чтобы их было достаточно, чтобы на каждую из повторных прогонок приходился 1 процессор (1 ядро), либо использовать вместо прогонки её параллельные заменители (метод Стоуна, циклическую редукцию, последовательно-параллельные варианты и т.п.). Естественно, будет хорошо распараллеливаться вариант, когда все правые части СЛАУ известны сразу, и когда их много. Тогда каждая повторная прогонка будет вычисляться на отдельном узле вычислительной системы.
Масштабируемость алгоритма и его реализации
О масштабируемости самой повторной прогонки, как непараллельного алгоритма, говорить нельзя в принципе. Однако необходимо указать на то, что сравнение параллельных заменителей прогонки при изучении их масштабируемости должно идти не с однопроцессорными вариантами этих заменителей, а с выполнением на 1 процессоре самой повторной прогонки.
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Повторная прогонка - метод для архитектуры классического, фон-неймановского типа. Для распараллеливания решения СЛАУ с трёхдиагональной матрицей следует взять какой-либо её параллельный заменитель, например, наиболее распространённую циклическую редукцию, или уступающий ей по критическому пути, но имеющий более регулярную структуру графа новый последовательно-параллельный метод.