|
|
| (не показаны 3 промежуточные версии 3 участников) |
| Строка 1: |
Строка 1: |
| {{algorithm
| | #REDIRECT [[Классическая монотонная прогонка, повторный вариант]] |
| | name = Повторная прогонка для нового СЛАУ с трёхдиагональной матрицей,<br /> точечный вариант
| |
| | serial_complexity = <math>5n-4</math>
| |
| | pf_height = <math>5n-4</math>
| |
| | pf_width = <math>1</math>
| |
| | input_data = <math>4n-2</math>
| |
| | output_data = <math>n</math>
| |
| }}
| |
| | |
| Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]
| |
| | |
| == Свойства и структура алгоритма ==
| |
| | |
| [[file:ProgonkaRep.png|thumb|right|200px|Рисунок 1. Граф алгоритма повторной прогонки при n=8 без отображения входных и выходных данных. '''/''' - деление, '''''f''''' - операция '''''a+bc'''''.]] | |
| === Общее описание алгоритма ===
| |
| | |
| '''Повторная прогонка''' - часть метода [[Прогонка, точечный вариант|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида<ref name="SETKI">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref>
| |
| | |
| {{Шаблон:Трёхдиагональная_СЛАУ_в_сеточном_виде}}
| |
| | |
| для того случая, когда ранее уже была выполнена прогонка для СЛАУ с той же матрицей, но с другой правой частью. В этом случае та часть формул прогонки, что связана только с матрицей, уже предвычислена, и повторять её не надо.
| |
| [[file:ProgonkaRepMul.png|thumb|left|200px|Рисунок 2. Граф алгоритма повторной прогонки с предвычислением обратных чисел при n=8 без отображения входных и выходных данных. '''m''' - умножение на предвычисленное обратное число, '''''f''''' - операция '''''a+bc'''''.]]
| |
| | |
| === Математическое описание алгоритма ===
| |
| | |
| В приведённых обозначениях в повторной прогонке сначала выполняют её прямой ход - вычисляют коэффициенты
| |
| | |
| <math>\beta_{1} = f_{0}/c_{0}</math>,
| |
| | |
| <math>\beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i})</math>, <math>\quad i = 1, 2, \cdots , N</math>.
| |
| | |
| после чего вычисляют решение с помощью обратного хода
| |
| | |
| <math>y_{N} = \beta_{N+1}</math>,
| |
| | |
| <math>y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}</math>, <math>\quad i = N-1, N-2, \cdots , 1, 0</math>.
| |
| | |
| В литературе<ref name="SETKI" /> указывается, что данные формулы эквивалентны вычислению решений двухдиагональных систем методом обратной подстановки в условиях предвычисленного <math>LU</math>-разложения матрицы системы.
| |
| | |
| === Вычислительное ядро алгоритма ===
| |
| | |
| Вычислительное ядро алгоритма можно представить из двух частей - прямого и обратного хода. В прямом ходе ядро составляют последовательности операций умножения и сложения (последних вдвое меньше). В обратном ходе в ядре тоже только последовательности умножения и сложения, но в равном количестве.
| |
| | |
| === Макроструктура алгоритма ===
| |
| | |
| Макроструктура алгоритма - совокупность прямого и обратного хода.
| |
| | |
| === Схема реализации последовательного алгоритма ===
| |
| | |
| Последовательность исполнения метода следующая:
| |
| | |
| 1. Инициализируется прямой ход прогонки:
| |
| | |
| <math>\beta_{1} = f_{0}/c_{0}</math>,
| |
| | |
| 2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:
| |
| | |
| :<math>
| |
| \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>
| |
| | |
| Для быстрейшей работы повторной прогонки все деления в формулах заменяются умножением на предвычисленные обратные числа (<math>1/c_{0}</math> и <math>1/(c_{i}-a_{i}\alpha_{i})</math>.
| |
| | |
| === Последовательная сложность алгоритма ===
| |
| | |
| Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в последовательном (наиболее быстром, с предвычислением обратных чисел) варианте требуется:
| |
|
| |
| * <math>2n-2</math> сложений,
| |
| * <math>3n-2</math> умножений.
| |
| | |
| При классификации по последовательной сложности, таким образом, повторная прогонка относится к алгоритмам ''с линейной сложностью''.
| |
| | |
| === Информационный граф ===
| |
| | |
| Информационный граф прогонки без предвычисления обратных чисел изображён на рис.1. Как видно, он последователен. Левая ветвь соответствует прямому, правая - обратному ходу. По рисунку видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход".
| |
| Вариант с заменой делений на умножения даёт граф, который изображён на рис.2.
| |
| | |
| === Описание ресурса параллелизма алгоритма ===
| |
| | |
| Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие ярусы:
| |
| | |
| * <math>n</math> ярусов умножений (в каждом из ярусов по одному умножению),
| |
| * по <math>2n - 2</math> ярусов умножений и сложений (все ярусы - по одной операции).
| |
|
| |
| При классификации по высоте ЯПФ, таким образом, повторная прогонка относится к алгоритмам со сложностью <math>O(n)</math>. При классификации по ширине ЯПФ его сложность будет <math>1</math>.
| |
| | |
| === Входные и выходные данные алгоритма ===
| |
| | |
| | |
| === Свойства алгоритма ===
| |
| | |
| Соотношение последовательной и параллельной сложности, как хорошо видно, является ''константой'' (причём это единица).
| |
| | |
| При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – тоже ''константа''.
| |
| | |
| Алгоритм в рамках выбранной версии полностью детерминирован.
| |
| | |
| == Программная реализация алгоритма ==
| |
| | |
| === Особенности реализации последовательного алгоритма ===
| |
| | |
| В зависимости от нужд вычислений, возможны как разные способы хранения разложения матрицы СЛАУ, так и разные способы хранения вычисляемых коэффициентов.
| |
| | |
| Вот пример подпрограммы, реализующей повторную прогонку, где предвычисленные коэффициенты хранятся на месте ненужных элементов матрицы. Предполагается, что уже однажды выполнена первая прогонка (см. [[Прогонка, точечный вариант#Особенности реализации последовательного алгоритма|пример из статьи о прогонке]]).
| |
| | |
| <source lang="fortran">
| |
| subroutine prorep (a,x,N)
| |
| real a(3,0:N), x(0:N)
| |
| x(0)=x(0)*a(2,0) ! beta 1
| |
| do 10 i=1,N-1
| |
| x(i)=(x(i)-a(1,i)*x(i-1))*a(2,i) ! beta i+1
| |
| 10 continue
| |
| x(N)=(x(N)-a(1,N)*x(N-1))*a(2,N) ! y N
| |
| do 20 i=N-1,0,-1
| |
| x(i)=a(3,i)*x(i+1)+x(i) ! y i
| |
| 20 continue
| |
| return
| |
| end
| |
| </source>
| |
| | |
| === Локальность данных и вычислений ===
| |
| | |
| Как видно по графу алгоритма, локальность данных по пространству хорошая - все аргументы, что нужны операциям, вычисляются "рядом". Однако по времени локальность вычислений не столь хороша. Если данные задачи не помещаются в кэш, то вычисления в "верхнем левом углу" СЛАУ будут выполняться с постоянными промахами кэша. Отсюда может следовать одна из рекомендаций использующим прогонку - организовать все вычисления так, что бы прогонки были "достаточно коротки" для помещения данных в кэш.
| |
| | |
| === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| | |
| Как видно по графу алгоритма, его практически (без видоизменений) невозможно распараллелить. Поэтому есть два способа использования повторных прогонок для параллельных вычислительных систем: либо разбивать задачу, где используются прогонки, так, чтобы их было достаточно, чтобы на каждую из повторных прогонок приходился 1 процессор (1 ядро), либо использовать вместо прогонки её параллельные заменители (метод Стоуна, циклическую редукцию, последовательно-параллельные варианты и т.п.). Естественно, будет хорошо распараллеливаться вариант, когда все правые части СЛАУ известны сразу, и когда их много. Тогда каждая повторная прогонка будет вычисляться на отдельном узле вычислительной системы.
| |
| | |
| === Масштабируемость алгоритма и его реализации ===
| |
| | |
| О масштабируемости самой повторной прогонки, как непараллельного алгоритма, говорить нельзя в принципе. Однако необходимо указать на то, что сравнение параллельных заменителей прогонки при изучении их масштабируемости должно идти не с однопроцессорными вариантами этих заменителей, а с выполнением на 1 процессоре самой повторной прогонки.
| |
| | |
| === Динамические характеристики и эффективность реализации алгоритма ===
| |
| === Выводы для классов архитектур ===
| |
| | |
| Повторная прогонка - метод для архитектуры классического, фон-неймановского типа. Для распараллеливания решения СЛАУ с трёхдиагональной матрицей следует взять какой-либо её параллельный заменитель, например, наиболее распространённую [[Метод циклической редукции|циклическую редукцию]], или уступающий ей по критическому пути, но имеющий более регулярную структуру графа новый [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками|последовательно-параллельный метод]].
| |
| | |
| === Существующие реализации алгоритма ===
| |
| | |
| == Литература ==
| |
| | |
| <references />
| |
| | |
| [[Категория:Алгоритмы с низким уровнем параллелизма]]
| |
| [[Категория:Статьи в работе]]
| |