Уровень алгоритма

Прогонка, точечный вариант: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[выверенная версия][досмотренная версия]
м
 
(не показаны 73 промежуточные версии 6 участников)
Строка 8: Строка 8:
 
}}
 
}}
  
−
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]
+
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].
  
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
Строка 14: Строка 14:
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
−
'''Прогонка''' - один из вариантов метода исключения неизвестных в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где  
+
'''Прогонка''' - один из вариантов метода исключения неизвестных, применяемого к решению СЛАУ<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>
 
−
 
 
−
Здесь рассматривается тот вариант прогонки, когда проходится вся СЛАУ сверху вниз и обратно. Суть метода - в исключении из уравнений неизвестных, сначала - сверху вниз - под диагональю, а потом - снизу вверх - над диагональю.  
 
  
 
[[file:Progonka.png|thumb|right|200px|Рисунок 1. Граф алгоритма прогонки при n=8 без отображения входных и выходных данных. '''/''' - деление, '''''f''''' - операция '''''a+bc''''' или '''''a-bc'''''.]]
 
[[file:Progonka.png|thumb|right|200px|Рисунок 1. Граф алгоритма прогонки при n=8 без отображения входных и выходных данных. '''/''' - деление, '''''f''''' - операция '''''a+bc''''' или '''''a-bc'''''.]]
Строка 71: Строка 24:
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
  
−
В приведённых обозначениях в прогонке сначала выполняют её прямой ход - вычисляют коэффициенты
+
В приведённых выше обозначениях в прогонке сначала выполняют её прямой ход - вычисляют коэффициенты
 +
 
 +
<math>\alpha_{1} = b_{0}/c_{0}</math>,
 +
 +
<math>\beta_{1} = f_{0}/c_{0}</math>,
 +
 
 +
<math>\alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i})</math>, <math>\quad i = 1, 2, \cdots , N-1</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>
 
−
\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>-разложений матрицы системы с последующим решением двухдиагональных систем методом обратной подстановки.
+
<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>-разложения матрицы системы с последующим решением двухдиагональных систем посредством прямой и обратной подстановок.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
  
−
Вычислительное ядро алгоритма можно представить из двух частей - прямого и обратного хода. В прямом ходе ядро составляют последовательности операций деления, умножения и сложения/вычитания. В обратном ходе в ядре остаются только последовательности умножения и сложения.  
+
Вычислительное ядро алгоритма можно считать состоящим из двух частей - прямого и обратного хода прогонки. В прямом ходе вычислительное ядро составляют последовательности операций деления, умножения и сложения/вычитания. В обратном ходе в вычислительном ядре остаются только последовательности умножения и сложения.
 +
 +
[[file:ProgonkaInv.png|thumb|left|420px|Рисунок 2. Детальный граф алгоритма прогонки с однократным вычислением обратных чисел при n=4 без отображения входных и выходных данных. '''inv''' - вычисление обратного числа, '''mult''' - операция перемножения чисел.]]
  
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
  
−
Кроме представления макроструктуры алгоритма как совокупности прямого и обратного хода, прямой ход также может быть разложен на две макроединицы - разложения матрицы и прямого хода решения двухдиагональной СЛАУ, которые выполняются "одновременно", т.е., параллельно друг другу. При этом решение двухдиагональной СЛАУ использует результаты разложения.
+
В дополнение к возможности представления макроструктуры алгоритма как совокупности прямого и обратного хода, прямой ход также может быть разложен на две макроединицы - треугольного разложения матрицы и прямого хода решения двухдиагональной СЛАУ, которые выполняются "одновременно", т.е. параллельно друг другу. При этом решение двухдиагональной СЛАУ использует результаты треугольного разложения.
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
Строка 101: Строка 58:
 
1. Инициализируется прямой ход прогонки:
 
1. Инициализируется прямой ход прогонки:
  
−
:<math>
+
<math>\alpha_{1} = b_{0}/c_{0}</math>,
−
\alpha_{1} = b_{0}/c_{0},\\
+
−
\beta_{1} = f_{0}/c_{0}, \\
+
<math>\beta_{1} = f_{0}/c_{0} </math>
−
</math>
 
  
−
2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:
+
2. Последовательно для всех <math>i</math> от <math>1</math> до <math>N-1</math> выполняются формулы прямого хода:
  
−
:<math>
+
<math>\alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i})</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>\beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i})</math>.
−
</math>
 
  
 
3. Инициализируется обратный ход прогонки:
 
3. Инициализируется обратный ход прогонки:
  
−
:<math>
+
<math>y_{N} = (f_{N}+a_{N}\beta_{N})/(c_{N}-a_{N}\alpha_{N})</math>
−
y_{N} = (f_{N}+a_{N}\beta_{N})/(c_{N}-a_{N}\alpha_{N})
+
 
−
</math>
+
4. Последовательно для всех <math>i</math> с убыванием от <math>N-1</math> до <math>0</math> выполняются формулы обратного хода:
 +
<math>y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}</math>.
  
−
4. Последовательно для всех i с убыванием от N-1 до 0 выполняются формулы обратного хода:
+
В формулах прямого хода присутствуют пары делений на одно и то же выражение. Их можно заменить вычислением обратных чисел и последующим умножением на эти числа.
−
:<math>
 
−
y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}.
 
−
</math>
 
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
  
−
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в последовательном (наиболее быстром) варианте требуется:
+
Для выполнения прогонки в трёхдиагональной СЛАУ из <math>n</math> уравнений с <math>n</math> неизвестными в последовательном (наиболее быстром) варианте требуется:
 
 
 
* <math>2n-1</math> делений,
 
* <math>2n-1</math> делений,
Строка 132: Строка 85:
 
* <math>3n-3</math> умножений.
 
* <math>3n-3</math> умножений.
  
−
При классификации по последовательной сложности, таким образом, прогонка относится к алгоритмам ''с линейной сложностью''.
+
Таким образом, при классификации по последовательной сложности, прогонка относится к алгоритмам ''с линейной сложностью''.
  
 
=== Информационный граф ===
 
=== Информационный граф ===
  
−
Информационный граф прогонки изображён на рис.1. Как видно, он почти последователен: при выполнении прямого хода две ветви (левая - разложение матрицы, центральная - решение первой из двухдиагональных систем) могут выполняться параллельно друг другу. Правая ветвь соответствует обратному ходу. По рисунку видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход".  
+
Информационный граф прогонки представлен на рис.1. Как следует из анализа графа, он является практически последовательным, при выполнении прямого хода две ветви (левая - разложение матрицы, центральная - решение первой из двухдиагональных систем) могут выполняться параллельно друг другу. Правая ветвь соответствует обратному ходу. Из рисунка видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход".
 +
Вариант с заменой делений сводится к графу, который изображён на рис.2.
  
 
=== Описание ресурса параллелизма алгоритма ===
 
=== Описание ресурса параллелизма алгоритма ===
  
−
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие ярусы:
+
Для выполнения прогонки в трёхдиагональной СЛАУ из <math>n</math> уравнений с <math>n</math> неизвестными в параллельном варианте требуется последовательно выполнить следующие ярусы:
  
−
* <math>n</math> ярусов делений (в каждом из ярусов, кроме одного, по 2 деления),
+
* <math>n</math> ярусов делений (в каждом из ярусов, кроме одного, по <math>2</math> деления),
−
* по <math>2n - 2</math> ярусов умножений и сложений/вычитаний (в n-1 ярусах - по 2 операции, в n-1 - по одной).
+
* по <math>2n - 2</math> ярусов умножений и сложений/вычитаний (в <math>n-1</math> ярусах - по <math>2</math> операции, в <math>n-1</math> - по одной).
 
   
 
   
−
При классификации по высоте ЯПФ, таким образом, прогонка относится к алгоритмам со сложностью <math>O(n)</math>. При классификации по ширине ЯПФ его сложность будет <math>2</math>.
+
Таким образом, при классификации по высоте ЯПФ, прогонка относится к алгоритмам со сложностью <math>O(n)</math>. При классификации по ширине ЯПФ её сложность будет равна <math>2</math>.
  
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
  
 
'''Входные данные''': трёхдиагональная матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>b</math> (элементы <math>b_{i}</math>).
 
'''Входные данные''': трёхдиагональная матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>b</math> (элементы <math>b_{i}</math>).
 +
 +
'''Объём входных данных''': <math>4n-2</math>.
  
 
'''Выходные данные''': вектор <math>x</math> (элементы <math>x_{i}</math>).
 
'''Выходные данные''': вектор <math>x</math> (элементы <math>x_{i}</math>).
Строка 157: Строка 113:
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
  
−
Соотношение последовательной и параллельной сложности, как хорошо видно, является ''константой'' (причём менее 2).  
+
Соотношение последовательной и параллельной сложности, как хорошо видно, является ''константой'' (причём менее <math>2</math>).  
  
−
При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – тоже ''константа''.
+
При этом вычислительная мощность алгоритма как отношение числа операций к суммарному объему входных и выходных данных также является ''константой''.
  
−
Алгоритм полностью детерминирован.
+
Алгоритм в рамках выбранной версии полностью детерминирован.
  
−
Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. Тогда гарантируется устойчивость алгоритма.
+
Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. В этом случае гарантируется устойчивость алгоритма.
−
В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунок с графом алгоритма) можно не повторять. Это связано с тем, что <math>LU</math>-разложение матрицы системы не нужно перевычислять.  
+
 
 +
В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунки с графом алгоритма) можно не повторять. Это связано с тем, что <math>LU</math>-разложение матрицы системы не нужно перевычислять. Тогда будет более предпочтителен вариант с заменой делений.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
Строка 170: Строка 127:
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
  
−
В зависимости от нужд вычислений, возможны как разные способы хранения матрицы СЛАУ (в виде одного массива с 3 строками или в виде 3 разных массивов), так и разные способы хранения вычисляемых коэффициентов (на месте использованных уже элементов матрицы либо отдельно).
+
В зависимости от способа хранения матрицы СЛАУ (в виде одного массива с <math>3</math> строками или в виде <math>3</math> разных массивов) и способа хранения вычисляемых коэффициентов (на месте уже использованных элементов матрицы либо отдельно) возможны различные реализации алгоритма.
 +
 
 +
Приведем пример подпрограммы на языке Fortran, реализующей прогонку, где все элементы матрицы хранятся в одном массиве, причём соседние элементы матричной строки размещаются рядом, а вычисляемые коэффициенты --- на месте элементов исходной матрицы. Вариант без предварительного обращения:
 +
 
 +
<source lang="fortran">
 +
      subroutine progm (a,x,N)
 +
      real a(3,0:N), x(0:N)
 +
      a(3,0)=-a(3,0)/a(2,0) ! alpha 1
 +
      x(0)=x(0)/a(2,0) ! beta 1
 +
      do 10 i=1,N-1
 +
        a(3,i)=-a(3,i)/(a(2,i)+a(1,i)*a(3,i-1)) ! alpha i+1
 +
        x(i)=(x(i)-a(1,i)*x(i-1))/(a(2,i)+a(1,i)*a(3,i-1)) ! beta i+1
 +
  10  continue
 +
      x(N)=(x(N)-a(1,N)*x(N-1))/(a(2,N)+a(1,N)*a(2,N-1)) ! 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>
 +
 
 +
Вариант с предварительным обращением числа:
  
−
=== Локальность данных и вычислений ===
+
<source lang="fortran">
 +
      subroutine progm (a,x,N)
 +
      real a(3,0:N), x(0:N)
 +
      a(2,0) = 1. /a(2,0)
 +
      a(3,0)=-a(3,0)*a(2,0) ! alpha 1
 +
      x(0)=x(0)*a(2,0) ! beta 1
 +
      do 10 i=1,N-1
 +
        a(2,i)=1./(a(2,i)+a(1,i)*a(3,i-1))
 +
        a(3,i)=-a(3,i)*a(2,i) ! alpha i+1
 +
        x(i)=(x(i)-a(1,i)*x(i-1))*a(2,i) ! beta i+1
 +
  10  continue
 +
      a(2,N)=1./(a(2,N)+a(1,N)*a(2,N-1))
 +
      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>
  
−
Как видно по графу алгоритма, локальность данных по пространству хорошая - все аргументы, что нужны операциям, вычисляются "рядом". Однако по времени локальность вычислений не столь хороша. Если данные задачи не помещаются в кэш, то вычисления в "верхнем левом углу" СЛАУ будут выполняться с постоянными промахами кэша. Отсюда может следовать одна из рекомендаций использующим прогонку - организовать все вычисления так, что бы прогонки были "достаточно коротки" для помещения данных в кэш.
+
В Сети имеется много простых реализаций метода, например в [https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D1%80%D0%BE%D0%B3%D0%BE%D0%BD%D0%BA%D0%B8 Викиучебник - Реализации алгоритмов - Метод прогонки].
  
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
  
−
Как видно по графу алгоритма, его практически (без видоизменений) невозможно распараллелить. Поэтому есть два способа использования прогонок для параллельных вычислительных систем: либо разбивать задачу, где используются прогонки, так, чтобы их было достаточно, чтобы на каждую. из прогонок приходился 1 процессор (1 ядро), либо использовать вместо прогонки её параллельные заменители (циклическую редукцию, последовательно-параллельные варианты и т.п.)
+
Как видно из анализа графа алгоритма, его (без существенных модификаций) практически невозможно распараллелить. Поэтому есть два способа использования прогонок для параллельных вычислительных систем: либо разбивать задачу, где используются прогонки, так, чтобы их было достаточно много, например, так, чтобы на каждую из прогонок приходился 1 процессор (1 ядро), либо использовать вместо прогонки её параллельные варианты (циклическую редукцию, последовательно-параллельные варианты и т.п.).
  
−
=== Масштабируемость алгоритма и его реализации ===
+
Алгоритм прогонки является настолько простым, что, несмотря на его "дежурное" присутствие в стандартных пакетах программ решения задач линейной алгебры, большинство использующих его исследователей-прикладников часто пишут соответствующий фрагмент программы самостоятельно. Однако надо отметить, что, как правило, метод прогонки в пакетах реализуют не в его "чистом виде", а в виде пары "разложение на две двухдиагональные матрицы" и "решение СЛАУ с предварительно факторизованной трёхдиагональной матрицей". Так обстоит дело, например, в пакете SCALAPACK и его предшественниках.
  
−
О масштабируемости самой прогонки, как непараллельного алгоритма, говорить нельзя в принципе. Однако необходимо указать на то, что сравнение параллельных заменителей прогонки при  изучении их масштабируемости должно идти не с однопроцессорными вариантами этих заменителей, а с выполнением на 1 процессоре самой прогонки.
+
=== Результаты прогонов ===
−
 
 
−
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
  
−
Прогонка - метод для архитектуры классического, фон-неймановского типа. Для распараллеливания решения СЛАУ с трёхдиагональной матрицей следует взять какой-либо её параллельный заменитель, например, наиболее распространённую [[Метод циклической редукции|циклическую редукцию]], или уступающий ей по критическому пути, но имеющий более регулярную структуру графа новый [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками|последовательно-параллельный метод]].
+
Прогонка - метод для архитектуры классического, фон-неймановского типа, непригодный даже для эффективной загрузки одноядерных систем, поддерживающих суперскалярность. Для распараллеливания решения СЛАУ с трёхдиагональной матрицей следует использовать какой-либо её параллельный заменитель, например, наиболее распространённую [[Метод циклической редукции|циклическую редукцию]] или уступающий ей по критическому пути графа, но имеющий более регулярную структуру графа новый [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками|последовательно-параллельный вариант]].
−
 
 
−
=== Существующие реализации алгоритма ===
 
  
 
== Литература ==
 
== Литература ==
Строка 196: Строка 188:
  
 
[[Категория:Законченные статьи]]
 
[[Категория:Законченные статьи]]
 +
[[Категория:Алгоритмы с низким уровнем параллелизма]]
 +
 +
 +
[[En:Thomas algorithm, pointwise version]]

Текущая версия на 09:19, 14 июля 2022


Прогонка для трёхдиагональной матрицы,
точечный вариант
Последовательный алгоритм
Последовательная сложность [math]8n-7[/math]
Объём входных данных [math]4n-2[/math]
Объём выходных данных [math]n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]5n-4[/math]
Ширина ярусно-параллельной формы [math]2[/math]


Основные авторы описания: А.В.Фролов.

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Прогонка - один из вариантов метода исключения неизвестных, применяемого к решению СЛАУ[1][2] вида [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]

Часто, однако, при изложении сути методов решения трёхдиагональных СЛАУ[3] элементы правой части и матрицы системы обозначают и нумеруют по-другому, например СЛАУ может иметь вид ([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} y_{0} \\ y_{1} \\ \vdots \\ y_{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}[/math],

[math]-a_{i} y_{i-1} + c_{i} y_{i} - b_{i} y_{i+1} = f_{i}, 1 \le i \le N-1[/math],

[math]-a_{N} y_{N-1} + c_{N} y_{N} = f_{N}[/math].

Здесь рассматривается тот вариант прогонки, когда обрабатывается вся СЛАУ сверху вниз и обратно - так называемая правая прогонка. Суть метода состоит в исключении из уравнений неизвестных, сначала - сверху вниз - под диагональю, а затем - снизу вверх - над диагональю. Вариант, когда СЛАУ "проходится" наоборот, снизу вверх и обратно вниз - левая прогонка - принципиально ничем не отличается от рассматриваемого, поэтому нет смысла включать его отдельное описание.

Рисунок 1. Граф алгоритма прогонки при n=8 без отображения входных и выходных данных. / - деление, f - операция a+bc или a-bc.

1.2 Математическое описание алгоритма

В приведённых выше обозначениях в прогонке сначала выполняют её прямой ход - вычисляют коэффициенты

[math]\alpha_{1} = b_{0}/c_{0}[/math],

[math]\beta_{1} = f_{0}/c_{0}[/math],

[math]\alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i})[/math], [math]\quad i = 1, 2, \cdots , N-1[/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].

В литературе[3] указывается, что данные формулы эквивалентны вычислению одного из вариантов [math]LU[/math]-разложения матрицы системы с последующим решением двухдиагональных систем посредством прямой и обратной подстановок.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма можно считать состоящим из двух частей - прямого и обратного хода прогонки. В прямом ходе вычислительное ядро составляют последовательности операций деления, умножения и сложения/вычитания. В обратном ходе в вычислительном ядре остаются только последовательности умножения и сложения.

Рисунок 2. Детальный граф алгоритма прогонки с однократным вычислением обратных чисел при n=4 без отображения входных и выходных данных. inv - вычисление обратного числа, mult - операция перемножения чисел.

1.4 Макроструктура алгоритма

В дополнение к возможности представления макроструктуры алгоритма как совокупности прямого и обратного хода, прямой ход также может быть разложен на две макроединицы - треугольного разложения матрицы и прямого хода решения двухдиагональной СЛАУ, которые выполняются "одновременно", т.е. параллельно друг другу. При этом решение двухдиагональной СЛАУ использует результаты треугольного разложения.

1.5 Схема реализации последовательного алгоритма

Последовательность исполнения метода следующая:

1. Инициализируется прямой ход прогонки:

[math]\alpha_{1} = b_{0}/c_{0}[/math],

[math]\beta_{1} = f_{0}/c_{0} [/math]

2. Последовательно для всех [math]i[/math] от [math]1[/math] до [math]N-1[/math] выполняются формулы прямого хода:

[math]\alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i})[/math],

[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. Последовательно для всех [math]i[/math] с убыванием от [math]N-1[/math] до [math]0[/math] выполняются формулы обратного хода: [math]y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}[/math].

В формулах прямого хода присутствуют пары делений на одно и то же выражение. Их можно заменить вычислением обратных чисел и последующим умножением на эти числа.

1.6 Последовательная сложность алгоритма

Для выполнения прогонки в трёхдиагональной СЛАУ из [math]n[/math] уравнений с [math]n[/math] неизвестными в последовательном (наиболее быстром) варианте требуется:

  • [math]2n-1[/math] делений,
  • [math]3n-3[/math] сложений/вычитаний,
  • [math]3n-3[/math] умножений.

Таким образом, при классификации по последовательной сложности, прогонка относится к алгоритмам с линейной сложностью.

1.7 Информационный граф

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

1.8 Описание ресурса параллелизма алгоритма

Для выполнения прогонки в трёхдиагональной СЛАУ из [math]n[/math] уравнений с [math]n[/math] неизвестными в параллельном варианте требуется последовательно выполнить следующие ярусы:

  • [math]n[/math] ярусов делений (в каждом из ярусов, кроме одного, по [math]2[/math] деления),
  • по [math]2n - 2[/math] ярусов умножений и сложений/вычитаний (в [math]n-1[/math] ярусах - по [math]2[/math] операции, в [math]n-1[/math] - по одной).

Таким образом, при классификации по высоте ЯПФ, прогонка относится к алгоритмам со сложностью [math]O(n)[/math]. При классификации по ширине ЯПФ её сложность будет равна [math]2[/math].

1.9 Входные и выходные данные алгоритма

Входные данные: трёхдиагональная матрица [math]A[/math] (элементы [math]a_{ij}[/math]), вектор [math]b[/math] (элементы [math]b_{i}[/math]).

Объём входных данных: [math]4n-2[/math].

Выходные данные: вектор [math]x[/math] (элементы [math]x_{i}[/math]).

Объём выходных данных: [math]n[/math].

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности, как хорошо видно, является константой (причём менее [math]2[/math]).

При этом вычислительная мощность алгоритма как отношение числа операций к суммарному объему входных и выходных данных также является константой.

Алгоритм в рамках выбранной версии полностью детерминирован.

Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. В этом случае гарантируется устойчивость алгоритма.

В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунки с графом алгоритма) можно не повторять. Это связано с тем, что [math]LU[/math]-разложение матрицы системы не нужно перевычислять. Тогда будет более предпочтителен вариант с заменой делений.

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

В зависимости от способа хранения матрицы СЛАУ (в виде одного массива с [math]3[/math] строками или в виде [math]3[/math] разных массивов) и способа хранения вычисляемых коэффициентов (на месте уже использованных элементов матрицы либо отдельно) возможны различные реализации алгоритма.

Приведем пример подпрограммы на языке Fortran, реализующей прогонку, где все элементы матрицы хранятся в одном массиве, причём соседние элементы матричной строки размещаются рядом, а вычисляемые коэффициенты --- на месте элементов исходной матрицы. Вариант без предварительного обращения: 

      subroutine progm (a,x,N)
      real a(3,0:N), x(0:N)
      a(3,0)=-a(3,0)/a(2,0) ! alpha 1
      x(0)=x(0)/a(2,0) ! beta 1
      do 10 i=1,N-1
        a(3,i)=-a(3,i)/(a(2,i)+a(1,i)*a(3,i-1)) ! alpha i+1
        x(i)=(x(i)-a(1,i)*x(i-1))/(a(2,i)+a(1,i)*a(3,i-1)) ! beta i+1
  10  continue
      x(N)=(x(N)-a(1,N)*x(N-1))/(a(2,N)+a(1,N)*a(2,N-1)) ! 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

Вариант с предварительным обращением числа: 

      subroutine progm (a,x,N)
      real a(3,0:N), x(0:N)
      a(2,0) = 1. /a(2,0)
      a(3,0)=-a(3,0)*a(2,0) ! alpha 1
      x(0)=x(0)*a(2,0) ! beta 1
      do 10 i=1,N-1
        a(2,i)=1./(a(2,i)+a(1,i)*a(3,i-1))
        a(3,i)=-a(3,i)*a(2,i) ! alpha i+1
        x(i)=(x(i)-a(1,i)*x(i-1))*a(2,i) ! beta i+1
  10  continue
      a(2,N)=1./(a(2,N)+a(1,N)*a(2,N-1))
      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

В Сети имеется много простых реализаций метода, например в Викиучебник - Реализации алгоритмов - Метод прогонки.

2.2 Возможные способы и особенности параллельной реализации алгоритма

Как видно из анализа графа алгоритма, его (без существенных модификаций) практически невозможно распараллелить. Поэтому есть два способа использования прогонок для параллельных вычислительных систем: либо разбивать задачу, где используются прогонки, так, чтобы их было достаточно много, например, так, чтобы на каждую из прогонок приходился 1 процессор (1 ядро), либо использовать вместо прогонки её параллельные варианты (циклическую редукцию, последовательно-параллельные варианты и т.п.).

Алгоритм прогонки является настолько простым, что, несмотря на его "дежурное" присутствие в стандартных пакетах программ решения задач линейной алгебры, большинство использующих его исследователей-прикладников часто пишут соответствующий фрагмент программы самостоятельно. Однако надо отметить, что, как правило, метод прогонки в пакетах реализуют не в его "чистом виде", а в виде пары "разложение на две двухдиагональные матрицы" и "решение СЛАУ с предварительно факторизованной трёхдиагональной матрицей". Так обстоит дело, например, в пакете SCALAPACK и его предшественниках.

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

Прогонка - метод для архитектуры классического, фон-неймановского типа, непригодный даже для эффективной загрузки одноядерных систем, поддерживающих суперскалярность. Для распараллеливания решения СЛАУ с трёхдиагональной матрицей следует использовать какой-либо её параллельный заменитель, например, наиболее распространённую циклическую редукцию или уступающий ей по критическому пути графа, но имеющий более регулярную структуру графа новый последовательно-параллельный вариант.

3 Литература

  1. ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. ↑ 3,0 3,1 Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.
Источник — https://algowiki-project.org/w/ru/index.php?title=Прогонка,_точечный_вариант&oldid=29124