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

ASA в 08:56, 14 июля 2022

2022-07-14T08:56:53Z

ASA: /* Масштабируемость алгоритма и его реализации */

2022-04-28T13:37:26Z

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

← Предыдущая версия		Версия от 13:37, 28 апреля 2022
Строка 318:		Строка 318:
	Мизерная эффективность, по-видимому, связана с избыточной локальностью, описанной в разделе о [[#Локальность данных и вычислений\|локальности данных и вычислений]].		Мизерная эффективность, по-видимому, связана с избыточной локальностью, описанной в разделе о [[#Локальность данных и вычислений\|локальности данных и вычислений]].

	Исследованная [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Teplov~~/Scalability/blob/master/tridiagonal_other/tridiagonal_other.h реализация алгоритма]		Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/tridiagonal_other/tridiagonal_other.h реализация алгоритма]

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

ASA: /* Количественная оценка локальности */

2022-04-28T13:36:38Z

Количественная оценка локальности

← Предыдущая версия		Версия от 13:36, 28 апреля 2022
Строка 277:		Строка 277:
	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====

	Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [~~http~~://~~git~~.~~parallel~~.ru/shvets.pavel.srcc/locality/blob/master/benchmarks/tridiagonal_other/tridiagonal_other.h здесь] (функция Kernel). Условия запуска описаны [~~http~~://~~git~~.~~parallel~~.ru/shvets.pavel.srcc/locality/blob/master/README.md здесь].		Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/blob/master/benchmarks/tridiagonal_other/tridiagonal_other.h здесь] (функция Kernel). Условия запуска описаны [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/blob/master/README.md здесь].

	Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.		Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

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

2016-11-11T09:59:42Z

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

@@ Строка 202: / Строка 202: @@
        do 20 i=m+1,N
          x(i)=a(1,i)*x(i-1)+x(i) ! y i
-         x(N-i)=a(3,N-i)*x(N-i+1)+x(i) ! y N-i
+         x(N-i)=a(3,N-i)*x(N-i+1)+x(N-i) ! y N-i
   continue
        return

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

2016-10-31T10:12:14Z

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

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

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

	<source lang="fortran">		<source lang="fortran">

Frolov: /* Математическое описание алгоритма */

2016-10-31T10:11:02Z

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

← Предыдущая версия		Версия от 10:11, 31 октября 2016
Строка 66:		Строка 66:
	Поэтому в более поздних источниках<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref> приводятся формулы, которые более оптимальны для нечётного количества неизвестных. В них старт обратного хода заменяется на формулу (в наших обозначениях)		Поэтому в более поздних источниках<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref> приводятся формулы, которые более оптимальны для нечётного количества неизвестных. В них старт обратного хода заменяется на формулу (в наших обозначениях)

	<math>y_{m} = (f_{m}+b_{m}\eta_{m+1}+a_{m}\beta_{m})/(c_{m}-\a_{m}\alpha_{m}-b_{m}\xi_{m+1})</math>		<math>y_{m} = (f_{m}+b_{m}\eta_{m+1}+a_{m}\beta_{m})/(c_{m}-a_{m}\alpha_{m}-b_{m}\xi_{m+1})</math>

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

Frolov: /* Математическое описание алгоритма */

2016-10-31T10:10:33Z

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

← Предыдущая версия		Версия от 10:10, 31 октября 2016
Строка 62:		Строка 62:


	В обычно ~~приводимых~~<ref name="SETKI" /> формулах встречной прогонки нет формулы для компоненты <math>y_{m-1}</math>, которая вычисляется позже в обратном ходе. Однако это удлиняет критический путь графа как в случае с чётным числом переменных, откладывая вычисление <math>y_{m-1}</math> на момент, когда уже будет вычислена <math>y_{m}</math>, хотя обе компоненты могут быть вычислены одновременно почти независимо друг от друга, так и в случае с нечётным числом переменных, когда для вычисления на "месте встречи" нужно подождать дополнительно одно вычисление коэффициентов либо "сверху" от него, либо "снизу".		В приводимых обычно<ref name="SETKI" /> формулах встречной прогонки нет формулы для компоненты <math>y_{m-1}</math>, которая вычисляется позже в обратном ходе. Однако это удлиняет критический путь графа как в случае с чётным числом переменных, откладывая вычисление <math>y_{m-1}</math> на момент, когда уже будет вычислена <math>y_{m}</math>, хотя обе компоненты могут быть вычислены одновременно почти независимо друг от друга, так и в случае с нечётным числом переменных, когда для вычисления на "месте встречи" нужно подождать дополнительно одно вычисление коэффициентов либо "сверху" от него, либо "снизу".

			Поэтому в более поздних источниках<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref> приводятся формулы, которые более оптимальны для нечётного количества неизвестных. В них старт обратного хода заменяется на формулу (в наших обозначениях)

			<math>y_{m} = (f_{m}+b_{m}\eta_{m+1}+a_{m}\beta_{m})/(c_{m}-\a_{m}\alpha_{m}-b_{m}\xi_{m+1})</math>

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

Frolov: /* Математическое описание алгоритма */

2016-10-31T09:48:43Z

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

← Предыдущая версия		Версия от 09:48, 31 октября 2016
Строка 62:		Строка 62:


	В обычно приводимых<ref name="SETKI" /> формулах встречной прогонки нет формулы для компоненты <math>y_{m-1}</math>, которая вычисляется позже в обратном ходе. Однако это удлиняет критический путь графа, откладывая вычисление <math>y_{m-1}</math> на момент, когда уже будет вычислена <math>y_{m}</math>, хотя обе компоненты могут быть вычислены одновременно почти независимо друг от друга.		В обычно приводимых<ref name="SETKI" /> формулах встречной прогонки нет формулы для компоненты <math>y_{m-1}</math>, которая вычисляется позже в обратном ходе. Однако это удлиняет критический путь графа как в случае с чётным числом переменных, откладывая вычисление <math>y_{m-1}</math> на момент, когда уже будет вычислена <math>y_{m}</math>, хотя обе компоненты могут быть вычислены одновременно почти независимо друг от друга, так и в случае с нечётным числом переменных, когда для вычисления на "месте встречи" нужно подождать дополнительно одно вычисление коэффициентов либо "сверху" от него, либо "снизу".

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

Frolov: /* Общее описание алгоритма */

2016-10-31T09:26:02Z

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

← Предыдущая версия		Версия от 09:26, 31 октября 2016
Строка 17:		Строка 17:

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

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

ASA в 08:28, 10 августа 2016

2016-08-10T08:28:45Z

← Предыдущая версия		Версия от 08:28, 10 августа 2016
Строка 319:		Строка 319:
	[[Категория:Алгоритмы с небольшим уровнем параллелизма]]		[[Категория:Алгоритмы с небольшим уровнем параллелизма]]

	[[En:Two-sided ~~elimination method~~, pointwise version]]		[[En:Two-sided Thomas algorithm, pointwise version]]