Решение правой двухдиагональной СЛАУ с единичной диагональю, вещественная версия, последовательный вариант
Содержание
- 1 Описание свойств и структуры алгоритма
- 1.1 Словесное описание алгоритма
- 1.2 Математическое описание
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Описание схемы реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Описание ресурса параллелизма алгоритма
- 1.9 Описание входных и выходных данных
- 1.10 Свойства алгоритма
- 2 Программная реализация
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Описание локальности данных и вычислений
- 2.3 Возможные способы и особенности реализации параллельного алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
1 Описание свойств и структуры алгоритма
1.1 Словесное описание алгоритма
1.1.1 Решаемая задача
Дана система линейных алгебраических уравнений (СЛАУ) с верхней (правой) двухдиагональной матрицей, в которой диагональные элементы равны 1:
- [math] \begin{align} x_1 + a_1 x_2 & = b_1, \\ x_2 + a_2 x_3 & = b_2, \\ \vdots \\ x_k + a_k x_{k + 1} & = b_k, \\ \vdots \\ x_{n - 1} + a_{n - 1} x_n & = b_{n - 1}, \\ x_n & = b_n \end{align} [/math]
Нужно найти все компоненты вектора [math]\vec{x}[/math].
1.1.2 Общая схема
Фактически последовательная схема решения задачи реализует последовательное решение одного уравнения за другим, с последующей подстановкой полученных компонент искомого вектора в следующие уравнения.
1.2 Математическое описание
Исходные данные: одномерный массив [math]n - 1[/math] чисел [math]a_k[/math] и одномерный массив [math]n[/math] чисел [math]b_k[/math].
Вычисляемые данные: одномерный массив [math]n[/math] чисел [math]x_k[/math].
Формулы метода:
- [math] \begin{align} x_n & = b_n, \\ x_k & = b_k - a_k x_{k + 1}, \quad k = n - 1, \dots, 1 \end{align} [/math]
1.3 Вычислительное ядро алгоритма
Вычислительное ядро последовательной схемы решения задачи можно представить в качестве последовательного набора [math]n - 1[/math] «двойных» операций (умножение элементов получаемого массива на элемент одного из входных массивов и вычитание результата из следующего элемента другого входного массива).
1.4 Макроструктура алгоритма
Как уже записано в описании ядра алгоритма, основную часть вычисления составляет массовый последовательный набор «двойных» операций (умножение элементов получаемого массива на элемент одного из входных массивов и вычитание результата из следующего элемента другого входного массива).
1.5 Описание схемы реализации последовательного алгоритма
Формулы метода описаны выше. Последовательность исполнения — по убыванию индексов.
1.6 Последовательная сложность алгоритма
Для вычисления решения для СЛАУ порядка [math]n[/math], количество операций умножения равно количеству операций вычитания и равно [math]n - 1[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.
1.7 Информационный граф
Опишем граф алгоритма в виде рисунка. Изображён граф для [math]n = 7[/math]. Как видно, граф чисто последовательный.
1.8 Описание ресурса параллелизма алгоритма
Последовательный вариант вычисления не имеет ресурсов параллелизма. Его ЯПФ единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна [math]n - 1[/math] операций умножения плюс [math]n - 1[/math] операций вычитания. В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности по высоте параллельной формы. Ширина параллельной формы равна [math]1[/math], что даёт нам постоянную сложность по ширине параллельной формы.
1.9 Описание входных и выходных данных
Входные данные: массив [math]a[/math] (элементы [math]a_i[/math] с номерами от [math]1[/math] до [math]n - 1[/math]), массив [math]b[/math] (элементы [math]b_i[/math] с номерами от [math]1[/math] до [math]n[/math]).
Дополнительные ограничения: отсутствуют.
Объём входных данных: [math]2n - 1[/math].
Выходные данные: массив [math]x[/math] (элементы [math]x_k[/math] с номерами от [math]1[/math] до [math]n[/math]).
Объём выходных данных: [math]n[/math].
1.10 Свойства алгоритма
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является константой (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных почти столько же, сколько операций; если точнее — даже больше в полтора раза). При этом алгоритм полностью детерминирован. Дуги информационного графа локальны.
2 Программная реализация
На Фортране можно записать так:
x(N) = b(N)
DO I = N-1,1,-1
x(I) = b(I)-a(I)*x(I+1)
END DO
2.1 Особенности реализации последовательного алгоритма
2.2 Описание локальности данных и вычислений
2.2.1 Описание локальности алгоритма
2.2.2 Описание локальности реализации алгоритма
2.2.2.1 Описание структуры обращений в память и качественная оценка локальности
2.2.2.2 Количественная оценка локальности
2.2.2.3 Анализ на основе теста Apex-Map
2.3 Возможные способы и особенности реализации параллельного алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Описание масштабируемости алгоритма
2.4.2 Описание масштабируемости реализации алгоритма
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Помимо выписанной выше простейшей реализации, существуют коды, реализующие алгоритм для одновременного решения многих систем с разной правой частью, но одинаковыми матрицами. В основном это происходит потому, что такая задача и её решения обычно и используют там, где могут появляться наборы однотипных СЛАУ, что даёт возможность распараллеливания если не решения одной СЛАУ, то коллективного алгоритма, который объединяет решение многих систем.