Встречная прогонка, блочный вариант - История изменений

ASA в 06:45, 18 июля 2022

2022-07-18T06:45:54Z

← Предыдущая версия		Версия от 06:45, 18 июля 2022
Строка 147:		Строка 147:
	В зависимости от нужд вычислений, возможны как разные способы хранения матрицы СЛАУ (в виде одного массива с 3 блочными строками или в виде 3 разных массивов), так и разные способы хранения вычисляемых коэффициентов (на месте использованных уже элементов матрицы либо отдельно).		В зависимости от нужд вычислений, возможны как разные способы хранения матрицы СЛАУ (в виде одного массива с 3 блочными строками или в виде 3 разных массивов), так и разные способы хранения вычисляемых коэффициентов (на месте использованных уже элементов матрицы либо отдельно).



	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

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

	=== ~~Масштабируемость алгоритма и его реализации~~ ===		=== Результаты прогонов ===

	~~=== Динамические характеристики и эффективность реализации алгоритма ===~~

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

	~~=== Существующие реализации алгоритма ===~~

	== Литература ==		== Литература ==

ASA в 12:42, 14 марта 2018

2018-03-14T12:42:40Z

← Предыдущая версия		Версия от 12:42, 14 марта 2018
Строка 169:		Строка 169:
	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]
	[[Категория:Блочные алгоритмы]]		[[Категория:Блочные алгоритмы]]


			[[en:Two-sided Thomas algorithm, block variant]]

Frolov: /* Свойства алгоритма */

2016-03-24T07:19:07Z

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

← Предыдущая версия		Версия от 07:19, 24 марта 2016
Строка 134:		Строка 134:

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

			Соотношение последовательной и параллельной сложности, как хорошо видно, является ''константой'' ('''зависящей от размера блоков''').

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

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

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

Frolov: /* Макроструктура алгоритма */

2016-03-24T07:16:52Z

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

← Предыдущая версия		Версия от 07:16, 24 марта 2016
Строка 62:		Строка 62:

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

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

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

Frolov: /* Вычислительное ядро алгоритма */

2016-03-24T07:14:36Z

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

← Предыдущая версия		Версия от 07:14, 24 марта 2016
Строка 58:		Строка 58:

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

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

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

Frolov в 09:24, 23 декабря 2015

2015-12-23T09:24:26Z

← Предыдущая версия		Версия от 09:24, 23 декабря 2015
Строка 1:		Строка 1:
	{{algorithm		{{algorithm
	\| name = Встречная прогонка ~~для~~ трёхдиагональной матрицы,<br /> ~~точечный вариант~~		\| name = Встречная прогонка блочно-трёхдиагональной матрицы<br />
	\| serial_complexity = <math>8n-2</math>		\| serial_complexity = <math>8n-2</math> макроопераций
	\| pf_height = <math>2.5n-1</math>		\| pf_height = <math>2.5n-1</math> макроопераций
	\| pf_width = <math>4</math>		\| pf_width = <math>4</math> макроопераций
	\| input_data = <math>4n-2</math>		\| input_data = <math>4n-2</math> блоков
	\| output_data = <math>n</math>		\| output_data = <math>n</math> блоков
	}}		}}

Frolov: /* Схема реализации последовательного алгоритма */

2015-12-23T09:17:01Z

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

← Предыдущая версия		Версия от 09:17, 23 декабря 2015
Строка 96:		Строка 96:

	<math>Y_{i+1} = \boldsymbol{\xi}_{i+1} Y_{i} + \boldsymbol{\eta}_{i+1}</math>, <math>\quad i = m, m+1, \cdots , N-1</math>.		<math>Y_{i+1} = \boldsymbol{\xi}_{i+1} Y_{i} + \boldsymbol{\eta}_{i+1}</math>, <math>\quad i = m, m+1, \cdots , N-1</math>.

	В связи с тем, что почти во всех формулах есть пары делений на одно и то же выражение, можно поменять их на последовательности вычисления обратных чисел с последующими умножениями на ниx (см. Рисунок 2)

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

Frolov: /* Информационный граф */

2015-12-23T09:16:31Z

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

← Предыдущая версия		Версия от 09:16, 23 декабря 2015
Строка 111:		Строка 111:
	=== Информационный граф ===		=== Информационный граф ===
	Информационный '''макро'''граф встречной блочной прогонки изображён на рис.1. Как видно, он параллелен на прямом ходе со степенью не более 4, на обратном - не более 2. При выполнении прямого хода не только ветви, но и две подветви каждой из ветвей (левая - разложение матрицы, правая - решение первой из двухдиагональных систем) могут выполняться параллельно друг другу. Правые подветви соответствуют обратному ходу. По рисунку видно, что не только математическая суть обработки подвекторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход".		Информационный '''макро'''граф встречной блочной прогонки изображён на рис.1. Как видно, он параллелен на прямом ходе со степенью не более 4, на обратном - не более 2. При выполнении прямого хода не только ветви, но и две подветви каждой из ветвей (левая - разложение матрицы, правая - решение первой из двухдиагональных систем) могут выполняться параллельно друг другу. Правые подветви соответствуют обратному ходу. По рисунку видно, что не только математическая суть обработки подвекторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход".
	На рис.2 изображена версия встречной блочной прогонки, в которой благодаря малоразмерности блоков сразу можно вычислить обратный блок.

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

Frolov: /* Схема реализации последовательного алгоритма */

2015-12-23T09:16:13Z

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

← Предыдущая версия		Версия от 09:16, 23 декабря 2015
Строка 62:		Строка 62:

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	[[file:VstrProgonkaInv.png\|thumb\|left\|600px\|Рисунок 2. Детальный граф алгоритма встречной блочной прогонки с однократным вычислением обратных блоков при n=6 без отображения входных и выходных данных. '''inv''' - вычисление обратного блока, '''mult''' - операция перемножения блоков. Серым выделены операции, повторяющиеся при замене правой части СЛАУ]]
	Последовательность исполнения метода следующая:		Последовательность исполнения метода следующая:

Frolov: Новая страница: «{{algorithm | name = Встречная прогонка для трёхдиагональной матрицы,
точечный вариан…»

2015-12-23T09:15:15Z

Новая страница: «{{algorithm | name = Встречная прогонка для трёхдиагональной матрицы,<br /> точечный вариан…»

Новая страница

{{algorithm
| name = Встречная прогонка для трёхдиагональной матрицы,<br /> точечный вариант
| serial_complexity = <math>8n-2</math>
| pf_height = <math>2.5n-1</math>
| pf_width = <math>4</math>
| input_data = <math>4n-2</math>
| output_data = <math>n</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].

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

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

'''Встречная блочная прогонка''' - один из вариантов метода исключения неизвестных в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где

{{Шаблон:Блочно-трёхдиагональная СЛАУ}}

'''Блочная встречная прогонка''', как и [[Блочная прогонка|монотонная]], заключается в исключении из уравнений неизвестных, однако, в отличие от монотонной, в ней исключение ведут одновременно с обоих "краёв" СЛАУ (верхнего и нижнего). В принципе, её можно считать самым простейшим вариантом [[Метод редукции|метода редукции]] (при m=1 и встречных направлениях монотонных блочных прогонок).

[[file:VstrProgonka.png|thumb|right|600px|Рисунок 1. Граф алгоритма встречной прогонки при n=14 без отображения входных и выходных данных. '''/''' - операция <math>X^{-1}Y</math>, '''''f''''' - операция <math>A+BC</math> или <math>A-BC</math>.]]

=== Математическое описание алгоритма ===
<math>m</math> здесь - номер уравнения, на котором "встречаются" две ветви прямого хода - "сверху" и "снизу".

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

"сверху":

<math>\boldsymbol{\alpha}_{1} = C_{0}^{-1} B_{0}</math>,

<math>\boldsymbol{\beta}_{1} = C_{0}^{-1} F_{0}</math>,

<math>\boldsymbol{\alpha}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1} B_{i}</math>, <math>\quad i = 1, 2, \cdots , m-1</math>,

<math>\boldsymbol{\beta}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1}(F_{i}+A_{i}\boldsymbol{\beta}_{i})</math>, <math>\quad i = 1, 2, \cdots , m-1</math>,

и "снизу":

<math>\boldsymbol{\xi}_{N} = C_{N}^{-1} A_{N}</math>,

<math>\boldsymbol{\eta}_{1} = C_{N}^{-1} F_{N}</math>,

<math>\boldsymbol{\xi}_{i} = (C_{i}-B_{i}\boldsymbol{\xi}_{i+1})^{-1} A_{i}</math>, <math>\quad i = N-1, N-2, \cdots , m</math>,

<math>\boldsymbol{\eta}_{i} = (C_{i}-B_{i}\boldsymbol{\xi}_{i+1})^{-1}(F_{i}+B_{i}\boldsymbol{\eta}_{i+1})</math>, <math>\quad i = N-1, N-2, \cdots , m</math>,

после чего вычисляют решение с помощью обратного хода

<math>Y_{m} = (E-\boldsymbol{\xi}_{m}\boldsymbol{\alpha}_{m})^{-1}(\boldsymbol{\eta}_{m}+\boldsymbol{\xi}_{m}\boldsymbol{\beta}_{m})</math>,

<math>Y_{m-1} = (E-\boldsymbol{\alpha}_{m}\boldsymbol{\xi}_{m})^{-1}(\boldsymbol{\beta}_{m}+\boldsymbol{\alpha}_{m}\boldsymbol{\eta}_{m})</math>,

<math>Y_{i} = \boldsymbol{\alpha}_{i+1} Y_{i+1} + \boldsymbol{\beta}_{i+1}</math>, <math>\quad i = m-1, m-2, \cdots , 1, 0</math>,

<math>Y_{i+1} = \boldsymbol{\xi}_{i+1} Y_{i} + \boldsymbol{\eta}_{i+1}</math>, <math>\quad i = m, m+1, \cdots , N-1</math>.

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

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

=== Схема реализации последовательного алгоритма ===
[[file:VstrProgonkaInv.png|thumb|left|600px|Рисунок 2. Детальный граф алгоритма встречной блочной прогонки с однократным вычислением обратных блоков при n=6 без отображения входных и выходных данных. '''inv''' - вычисление обратного блока, '''mult''' - операция перемножения блоков. Серым выделены операции, повторяющиеся при замене правой части СЛАУ]]
Последовательность исполнения метода следующая:

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

<math>\boldsymbol{\alpha}_{1} = C_{0}^{-1} B_{0}</math>,

<math>\boldsymbol{\beta}_{1} = C_{0}^{-1} F_{0}</math>,

<math>\boldsymbol{\xi}_{N} = C_{N}^{-1} A_{N}</math>,

<math>\boldsymbol{\eta}_{1} = C_{N}^{-1} F_{N}</math>.

2. Последовательно выполняются формулы прямого хода:

<math>\boldsymbol{\alpha}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1} B_{i}</math>, <math>\quad i = 1, 2, \cdots , m-1</math>,

<math>\boldsymbol{\beta}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1}(F_{i}+A_{i}\boldsymbol{\beta}_{i})</math>, <math>\quad i = 1, 2, \cdots , m-1</math>,

<math>\boldsymbol{\xi}_{i} = (C_{i}-B_{i}\boldsymbol{\xi}_{i+1})^{-1} A_{i}</math>, <math>\quad i = N-1, N-2, \cdots , m</math>,

<math>\boldsymbol{\eta}_{i} = (C_{i}-B_{i}\boldsymbol{\xi}_{i+1})^{-1}(F_{i}+B_{i}\boldsymbol{\eta}_{i+1})</math>, <math>\quad i = N-1, N-2, \cdots , m</math>.

3. Инициализируется обратный ход:

<math>Y_{m} = (E-\boldsymbol{\xi}_{m}\boldsymbol{\alpha}_{m})^{-1}(\boldsymbol{\eta}_{m}+\boldsymbol{\xi}_{m}\boldsymbol{\beta}_{m})</math>

<math>Y_{m-1} = (E-\boldsymbol{\alpha}_{m}\boldsymbol{\xi}_{m})^{-1}(\boldsymbol{\beta}_{m}+\boldsymbol{\alpha}_{m}\boldsymbol{\eta}_{m})</math>

4. Последовательно выполняются формулы обратного хода:

<math>Y_{i} = \boldsymbol{\alpha}_{i+1} Y_{i+1} + \boldsymbol{\beta}_{i+1}</math>, <math>\quad i = m-1, m-2, \cdots , 1, 0</math>,

<math>Y_{i+1} = \boldsymbol{\xi}_{i+1} Y_{i} + \boldsymbol{\eta}_{i+1}</math>, <math>\quad i = m, m+1, \cdots , N-1</math>.

В связи с тем, что почти во всех формулах есть пары делений на одно и то же выражение, можно поменять их на последовательности вычисления обратных чисел с последующими умножениями на ниx (см. Рисунок 2)

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

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

* <math>2n+2</math> умножений обратного одному блока на другой,
* <math>3n-2</math> сложений/вычитаний блоков,
* <math>3n-2</math> умножений блоков.

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

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

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

Обе ветви прямого хода выполняются одновременно для <math>N=2m-1</math>, т.е. для <math>n=2m</math>. Тогда для выполнения встречной блочной прогонки требуется последовательно выполнить следующие ярусы:

* <math>m+1</math> ярусов умножения блока, обратного к одному, на другой или на вектор (в каждом из ярусов, кроме одного, по 4 таких операции, в одном - 2),
* по <math>2m-1</math> ярусов умножений и сложений/вычитаний блоков (в <math>m-1</math> ярусах - по 4 операции, в <math>m-1</math> - по две, в одном - три операции).

При классификации по высоте ЯПФ, таким образом, блочная встречная прогонка относится к алгоритмам со сложностью <math>O(n</math> макропераций. При классификации по ширине ЯПФ его макросложность будет равна <math>4</math>.

При нечётном <math>n</math> ветви нельзя выполнить синхронно, поэтому предпочтительнее выбирать чётные размеры задач.

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

'''Входные данные''': блочно-трёхдиагональная матрица <math>A</math> (блоки <math>A_{ij}</math>), вектор <math>B</math> (блоки <math>B_{i}</math>).

'''Выходные данные''': вектор <math>X</math> (блоки <math>X_i</math> ).

'''Объём выходных данных''': <math>n</math> '''блоков'''.

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

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

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

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

==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

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

=== Существующие реализации алгоритма ===

== Литература ==

<references />

[[Категория:Статьи в работе]]
[[Категория:Блочные алгоритмы]]

Встречная прогонка, блочный вариант - История изменений

ASA в 06:45, 18 июля 2022

ASA в 12:42, 14 марта 2018

Frolov: /* Свойства алгоритма */

Frolov: /* Макроструктура алгоритма */

Frolov: /* Вычислительное ядро алгоритма */

Frolov в 09:24, 23 декабря 2015

Frolov: /* Схема реализации последовательного алгоритма */

Frolov: /* Информационный граф */

Frolov: /* Схема реализации последовательного алгоритма */

Frolov: Новая страница: «{{algorithm | name = Встречная прогонка для трёхдиагональной матрицы, точечный вариан…»

Frolov: Новая страница: «{{algorithm | name = Встречная прогонка для трёхдиагональной матрицы,
точечный вариан…»