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

Обратная подстановка (вещественный вариант): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показано 26 промежуточных версий 4 участников)
Строка 8: Строка 8:
 
}}
 
}}
  
−
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]])
+
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].
  
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
Строка 18: Строка 18:
 
В<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. - М.: Наука, 1984.</ref> методом '''обратной подстановки''' назван также и метод решения СЛАУ с ''нижней треугольной матрицей''. Там же отмечено, что в литературе иногда под ''обратной подстановкой'' имеют в виду, как и здесь, только решения СЛАУ с ''верхней треугольной матрицей'', а решение ''нижних'' треугольных систем называют [[Прямая подстановка (вещественный вариант)|прямой подстановкой]]. Такой же системы названий будем придерживаться и здесь, во избежание одноимённого названия различных алгоритмов. Кроме того, '''обратная подстановка''', представленная здесь, одновременно может быть частью '''метода Гаусса для решения СЛАУ''', а именно - его '''обратным ходом''', чего нельзя сказать про [[Прямая подстановка (вещественный вариант)|прямую подстановку]].
 
В<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. - М.: Наука, 1984.</ref> методом '''обратной подстановки''' назван также и метод решения СЛАУ с ''нижней треугольной матрицей''. Там же отмечено, что в литературе иногда под ''обратной подстановкой'' имеют в виду, как и здесь, только решения СЛАУ с ''верхней треугольной матрицей'', а решение ''нижних'' треугольных систем называют [[Прямая подстановка (вещественный вариант)|прямой подстановкой]]. Такой же системы названий будем придерживаться и здесь, во избежание одноимённого названия различных алгоритмов. Кроме того, '''обратная подстановка''', представленная здесь, одновременно может быть частью '''метода Гаусса для решения СЛАУ''', а именно - его '''обратным ходом''', чего нельзя сказать про [[Прямая подстановка (вещественный вариант)|прямую подстановку]].
  
−
Существует метод со сходным названием - [[Обратная подстановка с нормировкой]]. При том, что он решает, по существу, ту же задачу, что и простая '''обратная подстановка''', его схема несколько сложнее. Это связано со специальными мерами по уменьшению влияния ошибок округления на результат. [[Обратная подстановка с нормировкой]] на данной странице не рассматривается.
+
Существует метод со сходным названием - [[Обратная подстановка с нормировкой]]. При том, что он решает, по существу, ту же задачу, что и простая '''обратная подстановка''', его схема несколько сложнее. Это связано со специальными мерами по уменьшению влияния ошибок округления на результат. Алгоритм обратной подстановки с нормировкой в данном разделе не рассматривается.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Строка 62: Строка 62:
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
  
−
Последовательность исполнения такова:
+
Последовательность действий описываемого алгоритма:
  
 
1. <math>x_{n} = y_{n}/u_{nn}</math>
 
1. <math>x_{n} = y_{n}/u_{nn}</math>
Строка 68: Строка 68:
 
Далее для всех <math>i</math> от <math>n-1</math> до <math>1</math> ''по убыванию'' выполняются
 
Далее для всех <math>i</math> от <math>n-1</math> до <math>1</math> ''по убыванию'' выполняются
  
−
2. <math>x_{i} = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}</math>
+
2. <math>x_{i} = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}</math>.
  
−
Особо отметим, что вычисления сумм вида <math>y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}</math> производят в режиме накопления вычитанием из <math>y_{i}</math> произведений <math>u_{ij} x_{j}</math> для <math>j</math> от <math>n</math> до <math>i + 1</math>, '''''c убыванием''''' <math>j</math>. '''''Другие порядки выполнения суммирования приводят к резкому ухудшению параллельных свойств алгоритма''''', хотя, к сожалению, остаются кое-где в литературе и пакетах программ. В качестве примера такого порядка можно привести фрагмент программы из<ref>Дж.Форсайт, К.Моллер. Численное решение систем линейных алгебраических уравнений. - М.:Мир, 1969.</ref>, где обратная подстановка является обратным ходом в методе Гаусса, а возрастание индекса суммирования связано, в основном, с ограничениями используемого авторами книги старого диалекта Фортрана.
+
Особо отметим, что вычисления сумм вида <math>y_{i} - \sum{}_{j = i+1}^{n} u_{ij} x_{j}</math> производят в режиме накопления вычитанием из <math>y_{i}</math> произведений <math>u_{ij} x_{j}</math> для <math>j</math> от <math>n</math> до <math>i + 1</math>, '''''c убыванием''''' <math>j</math>. '''''Использование другого порядка выполнения суммирования приводит к резкому ухудшению параллельных свойств алгоритма''''', хотя, к сожалению, это кое-где встречается в литературе и пакетах программ. В качестве примера использования другого порядка вычислений можно привести фрагмент программы из<ref>Дж.Форсайт, К.Моллер. Численное решение систем линейных алгебраических уравнений. - М.: Мир, 1969.</ref>, где обратная подстановка является обратным ходом в методе Гаусса, а возрастание индекса суммирования связано, в основном, с ограничениями используемого авторами книги старого диалекта Фортрана.
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
  
−
Для обратной подстановки в случае решения линейной системы с верхней треугольной матрицей порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:
+
Для алгоритма обратной подстановки в случае решения линейной системы с верхней треугольной матрицей порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:
 
 
 
* <math>n</math> делений,
 
* <math>n</math> делений,
 
* <math>\frac{n^2-n}{2}</math> сложений (вычитаний),
 
* <math>\frac{n^2-n}{2}</math> сложений (вычитаний),
 
* <math>\frac{n^2-n}{2}</math> умножений.  
 
* <math>\frac{n^2-n}{2}</math> умножений.  
−
Умножения и сложения (вычитания) — ''основная часть алгоритма''.
+
Выполнение умножений и сложений (вычитаний) составляет ''основную часть алгоритма''.
 
   
 
   
−
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране).
+
При этом использование режима накопления требует выполнения умножений и вычитаний в режиме двойной точности (или использования функции аналогичной DPROD на языке Фортран).
  
−
При классификации по последовательной сложности, таким образом, метод обратной подстановки относится к алгоритмам ''со сложностью'' <math>O(n^2)</math>.
+
Таким образом, при классификации по последовательной сложности, метод обратной подстановки относится к алгоритмам ''со сложностью'' <math>O(n^2)</math>.
  
 
=== Информационный граф ===
 
=== Информационный граф ===
Строка 93: Строка 93:
 
[[Файл:DirectU.png|450px|thumb|left|Рис. 1. Обратная подстановка]]
 
[[Файл:DirectU.png|450px|thumb|left|Рис. 1. Обратная подстановка]]
  
−
'''Первая''' группа вершин расположена в одномерной области, соответствующая ей операция вычисляет функцию деления.  
+
'''Первая''' группа вершин расположена в одномерной области, соответствующая ей операция выполняет функцию деления.  
−
Естественно введённая единственная координата каждой из вершин <math>i</math> меняется в диапазоне от <math>n</math> до <math>1</math>, принимая все целочисленные значения.
+
Естественно введённая единственная координата каждой из вершин <math>i</math> изменяется в диапазоне от <math>n</math> до <math>1</math>, принимая все целочисленные значения.
  
 
Делимое в этой операции:  
 
Делимое в этой операции:  
Строка 103: Строка 103:
 
Делитель для этой операции - элемент ''входных данных'', а именно  <math>u_{nn}</math>.
 
Делитель для этой операции - элемент ''входных данных'', а именно  <math>u_{nn}</math>.
  
−
Результат срабатывания операции является ''выходным данным'' <math>x_{i}</math>.
+
Результат выполнения операции является ''выходным данным'' <math>x_{i}</math>.
  
−
'''Вторая''' группа вершин расположена в двумерной области, соответствующая ей операция <math>a-bc</math>.  
+
'''Вторая''' группа вершин расположена в двумерной области, соответствующая ей операция <math>a-bc</math>.  
−
Естественно введённые координаты области таковы:  
+
Естественно введённые координаты области:
 
* <math>i</math> — меняется в диапазоне от <math>n-1</math> до <math>1</math>, принимая все целочисленные значения;
 
* <math>i</math> — меняется в диапазоне от <math>n-1</math> до <math>1</math>, принимая все целочисленные значения;
 
* <math>j</math> — меняется в диапазоне от <math>n</math> до <math>i+1</math>, принимая все целочисленные значения.
 
* <math>j</math> — меняется в диапазоне от <math>n</math> до <math>i+1</math>, принимая все целочисленные значения.
  
−
Аргументы операции следующие:
+
Аргументы операции:
 
*<math>a</math>:
 
*<math>a</math>:
 
** при <math>j = n</math> элемент ''входных данных'' <math>y_{i}</math>;  
 
** при <math>j = n</math> элемент ''входных данных'' <math>y_{i}</math>;  
−
** при <math>j < n</math> — результат срабатывания операции, соответствующей вершине из второй группы, с координатами <math>i, j+1</math>;
+
** при <math>j < n</math> — результат выполнения операции, соответствующей вершине из второй группы, с координатами <math>i, j+1</math>;
 
*<math>b</math> — элемент ''входных данных'', а именно  <math>u_{ij}</math>;
 
*<math>b</math> — элемент ''входных данных'', а именно  <math>u_{ij}</math>;
 
*<math>c</math> — результат срабатывания операции, соответствующей вершине из первой группы, с координатой <math>j</math>.
 
*<math>c</math> — результат срабатывания операции, соответствующей вершине из первой группы, с координатой <math>j</math>.
Строка 119: Строка 119:
 
Результат срабатывания операции является ''промежуточным данным'' алгоритма.
 
Результат срабатывания операции является ''промежуточным данным'' алгоритма.
  
−
Описанный граф можно посмотреть на рис. 1, выполненном для случая <math>n = 5</math>. Здесь вершины первой группы обозначены жёлтым цветом и знаком деления, вершины второй — зелёным цветом и буквой f. Изображена подача только входных данных из вектора <math>y</math>, подача элементов матрицы <math>U</math>, идущая во все вершины, на рисунке не представлена.
+
Описанный граф представлен на рис. 1, выполненном для случая <math>n = 5</math>. Здесь вершины первой группы обозначены жёлтым цветом и знаком деления, вершины второй — зелёным цветом и буквой f. Изображена только подача входных данных из вектора <math>y</math>, подача элементов матрицы <math>U</math>, идущая во все вершины, на рисунке не представлена.
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
Строка 131: Строка 131:
 
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.
 
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.
  
−
При классификации по высоте ЯПФ, таким образом, метод обратной подстановки относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''линейной''.
+
Таким образом, при классификации по высоте ЯПФ, алгоритм обратной подстановки относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''линейной''.
  
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
Строка 137: Строка 137:
 
'''Входные данные''': верхняя треугольная матрица <math>U</math> (элементы <math>u_{ij}</math>), вектор правой части <math>y</math> (элементы <math>y_{i}</math>).
 
'''Входные данные''': верхняя треугольная матрица <math>U</math> (элементы <math>u_{ij}</math>), вектор правой части <math>y</math> (элементы <math>y_{i}</math>).
  
−
'''Объём входных данных''': :<math>\frac{n (n + 3)}{2}</math> (в силу треугольности достаточно хранить только ненулевые элементы матрицы <math>U</math>).  
+
'''Объём входных данных''': <math>\frac{n (n + 3)}{2}</math> (в силу треугольности достаточно хранить только ненулевые элементы матрицы <math>U</math>).  
  
 
'''Выходные данные''': вектор решения <math>x</math> (элементы <math>x_{i}</math>).
 
'''Выходные данные''': вектор решения <math>x</math> (элементы <math>x_{i}</math>).
  
−
'''Объём выходных данных''': :<math>n~.</math>
+
'''Объём выходных данных''': <math>n</math>.
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
Строка 149: Строка 149:
 
При этом вычислительная мощность алгоритма обратной подстановки, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.
 
При этом вычислительная мощность алгоритма обратной подстановки, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.
  
−
При этом алгоритм обратной подстановки полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается, поскольку в корне меняет структуру алгоритма и меняет сложность с линейной на квадратичную.
+
Представленный алгоритм обратной подстановки является полностью детерминированным. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается, поскольку в корне меняет структуру алгоритма и меняет сложность с линейной на квадратичную.
  
 
Наличие линейного количества ярусов ЯПФ, состоящих из одного-единственного деления, потенциально замедляющее параллельные реализации алгоритма, является его характерным "узким местом", особенно в сравнении со схожей по решаемой математической задаче [[Прямая подстановка (вещественный вариант)|прямой подстановке]], где диагональные элементы единичны. В связи с этим для решения СЛАУ предпочтительны такие разложения, содержащие треугольные матрицы, где в треугольных матрицах диагональные элементы единичны. В тех же случаях, когда получаются неособенные треугольные матрицы, их желательно предварительно, до решения СЛАУ с ними, преобразовать в произведение диагональной и треугольной с единичными диагональными элементами.
 
Наличие линейного количества ярусов ЯПФ, состоящих из одного-единственного деления, потенциально замедляющее параллельные реализации алгоритма, является его характерным "узким местом", особенно в сравнении со схожей по решаемой математической задаче [[Прямая подстановка (вещественный вариант)|прямой подстановке]], где диагональные элементы единичны. В связи с этим для решения СЛАУ предпочтительны такие разложения, содержащие треугольные матрицы, где в треугольных матрицах диагональные элементы единичны. В тех же случаях, когда получаются неособенные треугольные матрицы, их желательно предварительно, до решения СЛАУ с ними, преобразовать в произведение диагональной и треугольной с единичными диагональными элементами.
  
−
У алгоритма обратной подстановки существует несколько блочных вариантов. Граф некоторых из них совпадает с графом точечного варианта, различия связаны в основном с порядком прохождения основных циклов алгоритма, а именно - с их развёртыванием и перестановкой. Эти приёмы могут помочь в оптимизации обменов на конкретных вычислительных системах.
+
У алгоритма обратной подстановки существует несколько блочных вариантов. Граф некоторых из них совпадает с графом точечного варианта, различия связаны в основном с порядком прохождения основных циклов алгоритма, а именно, с их развёртыванием и перестановкой. Эти приёмы могут помочь в оптимизации обменов на конкретных вычислительных системах.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
Строка 162: Строка 162:
  
 
<source lang="fortran">
 
<source lang="fortran">
−
         X(N) = Y(N) / U (N, N)
+
         X(N) = Y(N) / U(N,N)
−
DO  I = N-1, 1, -1
+
        DO  I = N-1, 1, -1
−
S = Y(I)
+
            S = Y(I)
−
DO  J = N, I+1, -1
+
            DO  J = N, I+1, -1
−
S = S - DPROD(U(I,J), X(J))
+
                S = S - DPROD(U(I,J), X(J))
−
END DO
+
            END DO
−
X(I) = S / U(I,I)
+
            X(I) = S / U(I,I)
 
END DO
 
END DO
 
</source>
 
</source>
 
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.
 
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.
−
 
−
=== Локальность данных и вычислений ===
 
−
==== Локальность реализации алгоритма ====
 
−
===== Структура обращений в память и качественная оценка локальности =====
 
−
 
−
[[file:gauss back 1.PNG|thumb|center|700px|Рисунок 2. Обратный ход метода Гаусса решения СЛАУ. Общий профиль обращений в память]]
 
−
 
−
На рис.2 представлен профиль обращений в память для обратного хода метода Гаусса решения СЛАУ. Хорошо видно, что профиль состоит из двух этапов, идущих друг за другом (граница между ними выделена оранжевой линией). Это соответствует двум циклам, из которых собственно состоит исходный код обратного хода метода Гаусса. Из самого рисунка это заметить достаточно сложно, но анализ исходного кода показывает, что профиль образуется из обращений к 4 массивам. Три из них выделены на рис.2 зеленым; к четвертому относятся все остальные обращения. Сразу отметим, что в данном профиле общее число обращений всего в несколько раз больше числа задействованных элементов массивов (4500 против 1000), а в таких условиях сложно добиться высокой локальности.
 
−
 
−
Чтобы выяснить это, перейдем к подробному рассмотрению каждого из массивов в отдельности.
 
−
 
−
На рис.3 представлен фрагмент 1. Оранжевой линей также проведено разделение 2 этапов. Видно, что второй этап устроен очень просто и представляет собой последовательный перебор в обратном порядке. Первый этап имеет итерационный характер, причем на каждой итерации отбрасывается элемент массива с наименьшим номером. Подобный профиль характеризуется высокой пространственной локальностью, поскольку элементы перебираются подряд; достаточно высокой временной локальностью, поскольку на каждой итерации происходит повторное обращение к тем же элементам.
 
−
 
−
[[file:gauss back 2.PNG|thumb|center|700px|Рисунок 3. Фрагмент 1 (профиль обращений к первому массиву)]]
 
−
 
−
На рис.4 представлен фрагмент 2, показывающий обращения ко второму массиву. Сразу заметим, что данный фрагмент еще меньше предыдущего – здесь задействовано всего 600 обращений в память. По сути, данный фрагмент является аналогичным фрагменту 1 (рис.3), с единственной разницей – здесь итерации расположены в обратном порядке. Однако это изменение не оказывает особого влияния ни на пространственную, ни не временную локальность, поэтому данный фрагмент обладает теми же свойствами.
 
−
 
−
[[file:gauss back 3.PNG|thumb|center|700px|Рисунок 4. Фрагмент 2 (профиль обращений ко второму массиву)]]
 
−
 
−
Далее рассмотрим фрагмент 3 (рис.5). Здесь также оранжевой линией проведено разделение между двумя этапами, и также на второй этап приходится совсем немного обращений. Обращения на первом этапе образуют аналог случайного доступа, достаточно часто встречающийся, например, в случае косвенной адресации. При этом в некоторый момент к определенному элементу происходит достаточно много обращений подряд, после чего этот элемент более не используется. Такой профиль обычно характеризуется низкой пространственной и временной локальностью, что, однако, в данном случае в достаточной степени нивелируется малым числом задействованных элементов.
 
−
 
−
[[file:gauss back 4.PNG|thumb|center|700px|Рисунок 5. Фрагмент 3 (профиль обращений к третьему массиву)]]
 
−
 
−
Далее перейдем к фрагменту, занимающему основную часть рис.2. Данный профиль отображен на рис.6. В первую очередь стоит отметить особенность данного профиля – здесь задействовано более 1000 элементов, в то время как в остальных профилям – порядка 30. При этом число обращений даже меньше, чем обращений к первому или третьему массиву.
 
−
 
−
Отметим также, что здесь большая часть обращений сосредоточена на втором этапе. Первый же этап является подобием первого этапа предыдущего массива (рис.5) , за тем лишь исключением, что в данном профиле отсутствуют множественные обращения подряд к одному элементу перед тем, как элемент перестанет использоваться. С учетом того, что первый этап состоит всего из порядка 500 обращений, достаточно равномерно распределенных на отрезке в 1000 элементов, это говорит об очень низкой как пространственной, так и временной локальности.
 
−
 
−
Другой характер обращений можно наблюдать на втором этапе. Видно, что он обладает более высокой пространственной локальностью, так как обращения явно сгруппированы в кластеры, при этом кластеры обладают подобным строением. Однако структура кластера видно плохо, поэтому требуется дальнейшее приближение.
 
−
 
−
[[file:gauss back 5.PNG|thumb|center|700px|Рисунок 6. Фрагмент 4 (профиль обращений к четвертому массиву)]]
 
−
 
−
На рис.7 показаны два кластера, выделенные на рис.6 зеленым цветом. Такой масштаб позволяет сразу увидеть, что каждый кластер представляет собой последовательный перебор с небольшим шагом определенного набора элементов массива.
 
−
 
−
Следовательно, можно говорить о том, что второй этап фрагмента 4 обладает достаточно высокой пространственной локальностью (поскольку каждый кластер содержит последовательный перебор), но низкой временной локальностью (повторные обращения практически отсутствуют).
 
−
 
−
[[file:gauss back 6.PNG|thumb|center|500px|Рисунок 7. Два кластера из фрагмента 4]]
 
−
 
−
В целом по всему профилю можно сделать следующий вывод: первые три рассмотренных массива (особенно №1 и №2) обладают достаточно высокой локальностью, однако достаточно низкая пространственная и очень низкая временная локальность последнего массива в значительной степени снижают общую локальность всей программы.
 
−
 
−
===== Количественная оценка локальности =====
 
−
 
−
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/gauss_back/gauss_back.h здесь] (функция Kernel2). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].
 
−
 
−
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
 
−
 
−
На рис.8 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, в соответствии с высказанным в предыдущем разделе предположением о негативном влиянии одного из массивов, данная программа показывает достаточно низкую производительность, заметно ниже, чем у прямого хода метода Гаусса.
 
−
 
−
[[file:gauss back daps ru.PNG|thumb|center|700px|Рисунок 8. Сравнение значений оценки daps]]
 
−
 
−
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
 
−
 
−
На рис.9 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, профиль обращений обладает низкой локальностью, лишь немногим лучше профиля программы со случайным доступом в память. Это повторяет выводы, сделанные на основе оценки daps.
 
−
 
−
[[file:gauss back cvg.PNG|thumb|center|700px|Рисунок 9. Сравнение значений оценки cvg]]
 
  
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
Строка 232: Строка 178:
  
 
<source lang="fortran">
 
<source lang="fortran">
−
         DO PARALLEL I = 1, N
+
         DO PARALLEL I = 1, N
 
           X(I) = Y(I)
 
           X(I) = Y(I)
 
         END DO
 
         END DO
Строка 245: Строка 191:
 
так и с использованием "скошенного параллелизма" в главном гнезде циклов.
 
так и с использованием "скошенного параллелизма" в главном гнезде циклов.
  
−
=== Масштабируемость алгоритма и его реализации ===
+
Вещественный вариант обратной подстановки реализован как в основных библиотеках программ отечественных организаций, так и в западных пакетах LINPACK, LAPACK, ScaLAPACK и др.
−
 
+
При этом в отечественных реализациях, как правило, выполнены стандартные требования к методу с точки зрения ошибок округления, то есть, реализован режим накопления, и обычно нет лишних операций.
−
==== Масштабируемость алгоритма ====
+
Реализация точечного варианта алгоритма в современных западных пакетах обычно происходит из одной и той же реализации метода в LINPACK, использующей библиотеку BLAS.  
−
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:
 
−
 
 
−
* число процессоров [8, 16. 24, 32, 48, 64, 96, 128, 192, 256];
 
−
* размер матрицы [1024 : 4096] с шагом 1024.
 
−
 
 
−
В результате проведённых экспериментов был получен следующий диапазон [[Глоссарий#Эффективность реализации|эффективности реализации]] алгоритма:
 
−
 
 
−
* минимальная эффективность реализации 1.152e-15%;
 
−
* максимальная эффективность реализации 5.39e-10%.
 
  
−
На следующих рисунках приведены графики [[Глоссарий#Производительность|производительности]] и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.
+
Для большинства современных пакетов имеется также блочный вариант алгоритма обратной подстановки, в том числе и тот, граф которого топологически тождествен графу точечного варианта. Из-за того, что количество читаемых данных примерно равно количеству операций, блочность может дать некоторое ускорение работы благодаря лучшему использованию кэшей процессоров. Именно в направлении оптимизации кэширования и следует сосредоточить основные усилия при оптимизации работы программы.
−
 
 
−
[[file:BS perf.png|thumb|center|700px|Рисунок 8. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
 
−
[[file:BS eff.png|thumb|center|700px|Рисунок 9. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]
 
−
 
 
−
==== Масштабируемость реализации алгоритма ====
 
−
 
 
−
=== Динамические характеристики и эффективность реализации алгоритма ===
 
  
 +
=== Результаты прогонов ===
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
  
 
Если исходить из структуры алгоритма, то при реализации на суперкомпьютерах следует выполнить две вещи. Во-первых, для минимизации обменов между узлами следует избрать блочный вариант, в котором или все элементы матрицы доступны на всех узлах, или заранее распределены по узлам. В таком случае количество передаваемых между узлами данных будет невелико по сравнению с количеством арифметических операций. Но при такой организации работы получится, что наибольшие временные затраты будут связаны с неоптимальностью обработки отдельных блоков. Поэтому, видимо, следует сначала оптимизировать не блочный алгоритм в целом, а подпрограммы, используемые на отдельных процессорах: точечный метод обратной подстановки, перемножения матриц и др. подпрограммы. Ниже содержится информация о возможном направлении такой оптимизации.
 
Если исходить из структуры алгоритма, то при реализации на суперкомпьютерах следует выполнить две вещи. Во-первых, для минимизации обменов между узлами следует избрать блочный вариант, в котором или все элементы матрицы доступны на всех узлах, или заранее распределены по узлам. В таком случае количество передаваемых между узлами данных будет невелико по сравнению с количеством арифметических операций. Но при такой организации работы получится, что наибольшие временные затраты будут связаны с неоптимальностью обработки отдельных блоков. Поэтому, видимо, следует сначала оптимизировать не блочный алгоритм в целом, а подпрограммы, используемые на отдельных процессорах: точечный метод обратной подстановки, перемножения матриц и др. подпрограммы. Ниже содержится информация о возможном направлении такой оптимизации.
  
−
=== Существующие реализации алгоритма ===
+
== Литература ==
  
−
Вещественный вариант обратной подстановки реализован как в основных библиотеках программ отечественных организаций, так и в западных пакетах LINPACK, LAPACK, ScaLAPACK и др.
 
−
При этом в отечественных реализациях, как правило, выполнены стандартные требования к методу с точки зрения ошибок округления, то есть, реализован режим накопления, и обычно нет лишних операций.
 
−
Реализация точечного варианта алгоритма в современных западных пакетах обычно происходит из одной и той же реализации метода в LINPACK, а та использует пакет BLAS.
 
−
 
−
Для большинства пакетов существует блочный вариант обратной подстановки, в том числе и тот, граф которого топологически тождествен графу точечного варианта. Из-за того, что количество читаемых данных примерно равно количеству операций, блочность может дать некоторое ускорение работы благодаря лучшему использованию кэшей процессоров. Именно в направлении оптимизации кэширования и следует сосредоточить основные усилия при оптимизации работы программы.
 
−
 
−
== Литература ==
 
 
<references />
 
<references />
  
 
[[En:Backward substitution]]
 
[[En:Backward substitution]]
  
−
[[Категория:Статьи в работе]]
+
[[Категория:Законченные статьи]]

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


Обратная подстановка для неособенной верхней треугольной матрицы
Последовательный алгоритм
Последовательная сложность [math]O(n^2)[/math]
Объём входных данных [math]O(n^2)[/math]
Объём выходных данных [math]n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(n)[/math]
Ширина ярусно-параллельной формы [math]O(n)[/math]


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

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

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

Обратная подстановка - решение системы линейных алгебраических уравнений (СЛАУ) [math]Ux = y[/math] с верхней треугольной матрицей [math]U[/math]. Матрица [math]U[/math] может быть одной из составляющих матрицы [math]A[/math] в каких-либо разложениях и получается либо из [math]LU[/math]-разложения последней каким-либо из многочисленных способов (например, простое разложение Гаусса, разложение Гаусса с выбором ведущего элемента, компактная схема Гаусса, разложение Холецкого и др.), либо из других (например из QR-разложения). В силу треугольности [math]U[/math] решение СЛАУ является одной из модификаций общего метода подстановки и записывается простыми формулами.

В[1] методом обратной подстановки назван также и метод решения СЛАУ с нижней треугольной матрицей. Там же отмечено, что в литературе иногда под обратной подстановкой имеют в виду, как и здесь, только решения СЛАУ с верхней треугольной матрицей, а решение нижних треугольных систем называют прямой подстановкой. Такой же системы названий будем придерживаться и здесь, во избежание одноимённого названия различных алгоритмов. Кроме того, обратная подстановка, представленная здесь, одновременно может быть частью метода Гаусса для решения СЛАУ, а именно - его обратным ходом, чего нельзя сказать про прямую подстановку.

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

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

Исходные данные: верхняя треугольная матрица [math]U[/math] (элементы [math]u_{ij}[/math]), вектор правой части [math]y[/math] (элементы [math]y_{i}[/math]).

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

Формулы метода:

[math] \begin{align} x_{n} & = y_{n}/u_{nn} \\ x_{i} & = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}, \quad i \in [1, n - 1]. \end{align} [/math]

Существует также блочная версия метода, однако в данном описании разобран только точечный метод.

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

Вычислительное ядро алгоритма обратной подстановки можно составить из множественных (всего их [math]n-1[/math]) вычислений скалярных произведений строк матрицы [math]U[/math] (за исключением диагонального элемента) на уже вычисленную часть вектора [math]x[/math]:

[math] \sum_{j = i+1}^{n} u_{ij} x_{j} [/math]

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

[math] y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} [/math]

в которых и встречаются скалярные произведения, ведутся не в порядке «вычислили скалярное произведение, а потом вычли его из элемента вектора», а путём вычитания из элемента покомпонентных произведений, являющихся частями скалярных произведений. Поэтому вычислительным ядром алгоритма следует считать не вычисления скалярных произведений, а вычисления выражений

[math] y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} [/math]

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

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

Как уже упоминалось в описании ядра алгоритма, основную часть метода обратной подстановки составляют множественные (всего их [math]n-1[/math]) вычисления сумм

[math]y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} [/math]

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

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

Последовательность действий описываемого алгоритма:

1. [math]x_{n} = y_{n}/u_{nn}[/math]

Далее для всех [math]i[/math] от [math]n-1[/math] до [math]1[/math] по убыванию выполняются

2. [math]x_{i} = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}[/math].

Особо отметим, что вычисления сумм вида [math]y_{i} - \sum{}_{j = i+1}^{n} u_{ij} x_{j}[/math] производят в режиме накопления вычитанием из [math]y_{i}[/math] произведений [math]u_{ij} x_{j}[/math] для [math]j[/math] от [math]n[/math] до [math]i + 1[/math], c убыванием [math]j[/math]. Использование другого порядка выполнения суммирования приводит к резкому ухудшению параллельных свойств алгоритма, хотя, к сожалению, это кое-где встречается в литературе и пакетах программ. В качестве примера использования другого порядка вычислений можно привести фрагмент программы из[2], где обратная подстановка является обратным ходом в методе Гаусса, а возрастание индекса суммирования связано, в основном, с ограничениями используемого авторами книги старого диалекта Фортрана.

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

Для алгоритма обратной подстановки в случае решения линейной системы с верхней треугольной матрицей порядка [math]n[/math] в последовательном (наиболее быстром) варианте требуется:

  • [math]n[/math] делений,
  • [math]\frac{n^2-n}{2}[/math] сложений (вычитаний),
  • [math]\frac{n^2-n}{2}[/math] умножений.

Выполнение умножений и сложений (вычитаний) составляет основную часть алгоритма.

При этом использование режима накопления требует выполнения умножений и вычитаний в режиме двойной точности (или использования функции аналогичной DPROD на языке Фортран).

Таким образом, при классификации по последовательной сложности, метод обратной подстановки относится к алгоритмам со сложностью [math]O(n^2)[/math].

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

Опишем граф алгоритма как аналитически, так и в виде рисунка.

Граф алгоритма обратной подстановки состоит из двух групп вершин, расположенных в целочисленных узлах двух областей разной размерности.

Рис. 1. Обратная подстановка

Первая группа вершин расположена в одномерной области, соответствующая ей операция выполняет функцию деления. Естественно введённая единственная координата каждой из вершин [math]i[/math] изменяется в диапазоне от [math]n[/math] до [math]1[/math], принимая все целочисленные значения.

Делимое в этой операции:

  • при [math]i = n[/math] — элемент входных данных, а именно [math]y_{n}[/math];
  • при [math]i \lt n[/math] — результат срабатывания операции, соответствующей вершине из второй группы, с координатами [math]i[/math], [math]i+1[/math].

Делитель для этой операции - элемент входных данных, а именно [math]u_{nn}[/math].

Результат выполнения операции является выходным данным [math]x_{i}[/math].

Вторая группа вершин расположена в двумерной области, соответствующая ей операция [math]a-bc[/math]. Естественно введённые координаты области:

  • [math]i[/math] — меняется в диапазоне от [math]n-1[/math] до [math]1[/math], принимая все целочисленные значения;
  • [math]j[/math] — меняется в диапазоне от [math]n[/math] до [math]i+1[/math], принимая все целочисленные значения.

Аргументы операции:

  • [math]a[/math]:
    • при [math]j = n[/math] элемент входных данных [math]y_{i}[/math];
    • при [math]j \lt n[/math] — результат выполнения операции, соответствующей вершине из второй группы, с координатами [math]i, j+1[/math];
  • [math]b[/math] — элемент входных данных, а именно [math]u_{ij}[/math];
  • [math]c[/math] — результат срабатывания операции, соответствующей вершине из первой группы, с координатой [math]j[/math].

Результат срабатывания операции является промежуточным данным алгоритма.

Описанный граф представлен на рис. 1, выполненном для случая [math]n = 5[/math]. Здесь вершины первой группы обозначены жёлтым цветом и знаком деления, вершины второй — зелёным цветом и буквой f. Изображена только подача входных данных из вектора [math]y[/math], подача элементов матрицы [math]U[/math], идущая во все вершины, на рисунке не представлена.

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

Для обратной подстановки в случае решения линейной системы с верхней треугольной матрицей порядка [math]n[/math] в параллельном варианте требуется последовательно выполнить следующие ярусы:

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

Таким образом, в параллельном варианте, в отличие от последовательного, вычисления делений будут определять довольно значительную долю требуемого времени. При реализации на конкретных архитектурах наличие в отдельных ярусах ЯПФ отдельных делений может породить и другие проблемы. Например, при реализации метода обратной подстановки на ПЛИСах остальные вычисления (умножения и сложения/вычитания) могут быть конвейеризованы, что даёт экономию и по ресурсам на программируемых платах; деления из-за их изолированности приведут к занятию ресурсов на платах, которые будут простаивать большую часть времени.

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

Входные данные: верхняя треугольная матрица [math]U[/math] (элементы [math]u_{ij}[/math]), вектор правой части [math]y[/math] (элементы [math]y_{i}[/math]).

Объём входных данных: [math]\frac{n (n + 3)}{2}[/math] (в силу треугольности достаточно хранить только ненулевые элементы матрицы [math]U[/math]).

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

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

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейным (отношение квадратической к линейной).

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

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

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

У алгоритма обратной подстановки существует несколько блочных вариантов. Граф некоторых из них совпадает с графом точечного варианта, различия связаны в основном с порядком прохождения основных циклов алгоритма, а именно, с их развёртыванием и перестановкой. Эти приёмы могут помочь в оптимизации обменов на конкретных вычислительных системах.

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

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

В простейшем варианте метод обратной подстановки на Фортране можно записать так: 

        X(N) = Y(N) / U(N,N)
        DO  I = N-1, 1, -1
            S = Y(I)
            DO  J = N, I+1, -1
                S = S - DPROD(U(I,J), X(J))
            END DO
            X(I) = S / U(I,I)
	END DO

При этом для реализации режима накопления переменная [math]S[/math] должна быть двойной точности.

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

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

        DO PARALLEL I = 1, N
           X(I) = Y(I)
        END DO
        DO J = N, 1, -1
           X(J) = X(J) / U(J,J)
           DO PARALLEL I = 1, J-1
              X(I) = X(I) - U(I,J)*X(J)
           END DO
        END DO

так и с использованием "скошенного параллелизма" в главном гнезде циклов.

Вещественный вариант обратной подстановки реализован как в основных библиотеках программ отечественных организаций, так и в западных пакетах LINPACK, LAPACK, ScaLAPACK и др. При этом в отечественных реализациях, как правило, выполнены стандартные требования к методу с точки зрения ошибок округления, то есть, реализован режим накопления, и обычно нет лишних операций. Реализация точечного варианта алгоритма в современных западных пакетах обычно происходит из одной и той же реализации метода в LINPACK, использующей библиотеку BLAS.

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

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

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

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

3 Литература

  1. ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. - М.: Наука, 1984.
  2. ↑ Дж.Форсайт, К.Моллер. Численное решение систем линейных алгебраических уравнений. - М.: Мир, 1969.
Источник — https://algowiki-project.org/w/ru/index.php?title=Обратная_подстановка_(вещественный_вариант)&oldid=29162