Алгоритм продольно-поперечной прогонки - История изменений

Ateina в 22:19, 12 июня 2017

2017-06-12T22:19:43Z

← Предыдущая версия		Версия от 22:19, 12 июня 2017
Строка 83:		Строка 83:
	===Схема реализации последовательного алгоритма===		===Схема реализации последовательного алгоритма===
	Последовательность исполнения метода следующая:		Последовательность исполнения метода следующая:
	Осуществляется прогонка вдоль строк, как это изображено на рисунке ~~1.1 [4]~~:		Осуществляется прогонка вдоль строк, как это изображено на рисунке:

	~~Рисунок~~ 1.1– Прогонка вдоль строк		[[Файл:Adi method 1.png\|300px\|thumb\|center\|Прогонка вдоль строк]]

	Затем осуществляется прогонка вдоль столбцов, как это представлено на рисунке ~~1.2 [4]~~:		Затем осуществляется прогонка вдоль столбцов, как это представлено на рисунке:

	~~Рисунок 1~~.2- Прогонка вдоль столбцов		[[Файл:Adi_method_2.png\|300px\|thumb\|center\|Прогонка вдоль столбцов]]

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

Ateina в 22:02, 12 июня 2017

2017-06-12T22:02:52Z

← Предыдущая версия		Версия от 22:02, 12 июня 2017
Строка 1:		Строка 1:
			{{algorithm
			\| name = Алгоритм продольно-поперечной прогонки<br />
			\| input_data = <math>(N_{x} + 1)(N_{y} + 1)</math>
			\| output_data = <math>(N_{x} + 1)(N_{y} + 1)</math>
			}}

	Основные авторы описания: [[Участник:Ateina\|Дружкина А.И.]], [[Участник:Likhoded\|Лиходед Н.А.]]		Основные авторы описания: [[Участник:Ateina\|Дружкина А.И.]], [[Участник:Likhoded\|Лиходед Н.А.]]

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	===Общее описание алгоритма===		===Общее описание алгоритма===

Ateina в 21:59, 12 июня 2017

2017-06-12T21:59:57Z

Внесённые изменения

Ateina в 22:53, 11 июня 2017

2017-06-11T22:53:36Z

← Предыдущая версия		Версия от 22:53, 11 июня 2017
Строка 120:		Строка 120:
	====Вычислительный алгоритм продольно-поперечной прогонки====		====Вычислительный алгоритм продольно-поперечной прогонки====
	Основную вычислительную часть алгоритма, реализующего двухшаговую разностную схему продольно–поперечной прогонки, т.е. метода переменных направлений, можно представить в виде следующего псевдокода (циклы, итерации которых заведомо можно выполнять независимо, запишем как dopar):		Основную вычислительную часть алгоритма, реализующего двухшаговую разностную схему продольно–поперечной прогонки, т.е. метода переменных направлений, можно представить в виде следующего псевдокода (циклы, итерации которых заведомо можно выполнять независимо, запишем как dopar):
			<source>
	do j =1, j0		do j =1, j0
	dopar i2= 1, N2 –1		dopar i2= 1, N2 –1
Строка 141:		Строка 141:
	enddopar		enddopar
	enddo(j)		enddo(j)
			</source>
	Здесь (i) и (i) – коэффициенты прогонки, возникающие при решении промежуточных систем линейных алгебраических уравнений. Конечные значения являются приближенным решением задачи.		Здесь (i) и (i) – коэффициенты прогонки, возникающие при решении промежуточных систем линейных алгебраических уравнений. Конечные значения являются приближенным решением задачи.
	Алгоритм метода переменных направлений обладает естественным параллелизмом: можно организовать независимые вычислительные процессы на каждом временном слое. Так как число вычислительных ядер обычно гораздо меньше N1 и N2, то при реализации на параллельных компьютерах с распределенной памятью итерации циклов, отмеченных как dopar, следует сгруппировать и получить макрооперации, называемые зернами вычислений или тайлами. Процесс получения макроопераций–тайлов называется тайлингом.		Алгоритм метода переменных направлений обладает естественным параллелизмом: можно организовать независимые вычислительные процессы на каждом временном слое. Так как число вычислительных ядер обычно гораздо меньше N1 и N2, то при реализации на параллельных компьютерах с распределенной памятью итерации циклов, отмеченных как dopar, следует сгруппировать и получить макрооперации, называемые зернами вычислений или тайлами. Процесс получения макроопераций–тайлов называется тайлингом.

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

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

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

			===Существующие реализации алгоритма===
			В языке Matlab существует реализация алгоритма продольно-поперечной прогонки.
			Также метод продольно–поперечной прогонки реализован в библиотеке для решения дифференциальных уравнений языка Python.

Ateina в 22:49, 11 июня 2017

2017-06-11T22:49:47Z

← Предыдущая версия		Версия от 22:49, 11 июня 2017
Строка 107:		Строка 107:
	Продольно–поперечная схема равномерно и безусловно устойчива по начальным данным, так как при переходе с одного целого слоя на следующий целый слой ошибки начальных данных не нарастают.		Продольно–поперечная схема равномерно и безусловно устойчива по начальным данным, так как при переходе с одного целого слоя на следующий целый слой ошибки начальных данных не нарастают.
	При переходе с целого слоя на целый погрешность локальной аппроксимации на равномерных сетках есть <math>O(\tau^{2} + h_{x}^{2} + h_{y}^{2})</math> т.е. продольно–поперечная схема имеет второй порядок аппроксимации по всем переменным.		При переходе с целого слоя на целый погрешность локальной аппроксимации на равномерных сетках есть <math>O(\tau^{2} + h_{x}^{2} + h_{y}^{2})</math> т.е. продольно–поперечная схема имеет второй порядок аппроксимации по всем переменным.

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

			===Локальность данных и вычислений===

			===Возможные способы и особенности параллельной реализации алгоритма===
			Вычислительные процессы реализаций, основанных на естественном па-раллелизме, на каждом временном слое могут выполняться независимо, но при переходе к новому слою требуют групповых коммуникаций “каждый с каждым”. С ростом числа используемых процессов это приводит к большим накладным расходам.
			Локальность алгоритма – это вычислительное свойство, отражающее степень использования при реализации алгоритма памяти с быстрым доступом. При многопроцессорной обработке памятью с быстрым доступом считается локальная память процессора. В этой работе вместо части естественного параллелизма предлагается использовать конвейерный параллелизм. Такой параллелизм приводит к разгону и торможению вычислительного конвейера на каждом временном слое, но позволяет построить параллельный алгоритм с улучшенной локальностью (с существенно меньшим объемом коммуникационных операций).

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

			do j =1, j0
			dopar i2= 1, N2 –1
			do i1= 1, N1 –1
			S1:
			S2:
			enddo
			do i1= 1, N1 –1
			S3:
			enddo
			enddopar
			dopar i1= 1, N1 –1
			do i2= 1, N2 –1
			S4:
			S5:
			enddo
			do i2= 1, N2 –1
			S6:
			enddo
			enddopar
			enddo(j)

			Здесь (i) и (i) – коэффициенты прогонки, возникающие при решении промежуточных систем линейных алгебраических уравнений. Конечные значения являются приближенным решением задачи.
			Алгоритм метода переменных направлений обладает естественным параллелизмом: можно организовать независимые вычислительные процессы на каждом временном слое. Так как число вычислительных ядер обычно гораздо меньше N1 и N2, то при реализации на параллельных компьютерах с распределенной памятью итерации циклов, отмеченных как dopar, следует сгруппировать и получить макрооперации, называемые зернами вычислений или тайлами. Процесс получения макроопераций–тайлов называется тайлингом.

Ateina в 22:44, 11 июня 2017

2017-06-11T22:44:50Z

← Предыдущая версия		Версия от 22:44, 11 июня 2017
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Ateina\|А.И.~~Дружкина~~]], Лиходед Н.А. ~~(Профессор кафедры вычислительной математики ФПМИ, доктор физико-математических наук)~~		Основные авторы описания: [[Участник:Ateina\|Дружкина А.И.]], [[Участник:Likhoded\|Лиходед Н.А.]]
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	===Общее описание алгоритма===		===Общее описание алгоритма===

Ateina в 22:40, 11 июня 2017

2017-06-11T22:40:56Z

← Предыдущая версия		Версия от 22:40, 11 июня 2017
Строка 1:		Строка 1:
			Основные авторы описания: [[Участник:Ateina\|А.И.Дружкина]], Лиходед Н.А. (Профессор кафедры вычислительной математики ФПМИ, доктор физико-математических наук)
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	===Общее описание алгоритма===		===Общее описание алгоритма===

Ateina в 22:33, 11 июня 2017

2017-06-11T22:33:59Z

@@ Строка 19: / Строка 19: @@
 и граничными условиями
 === Вычислительное ядро алгоритма ===
 Вычислительное ядро алгоритма можно считать состоящим из двух частей – продольной прогонки и поперечной прогонки. В свою очередь, каждая из этих прогонок состоит из прямого и обратного хода. В прямом ходе вычислительное ядро составляют последовательности операций деления, умножения и сложения/вычитания. В обратном ходе в вычислительном ядре остаются только последовательности умножения и сложения.
 ===Макроструктура алгоритма===

Ateina в 22:02, 11 июня 2017

2017-06-11T22:02:49Z

← Предыдущая версия		Версия от 22:02, 11 июня 2017
Строка 5:		Строка 5:
	Рассмотрим в области		Рассмотрим в области

	<math>D_{T}=G\times [0\leq t\leq T],		<math>\begin{align} D_{T}=G\times [0\leq t\leq T], \\
	G=[0\leq x\leq l_{x}]\times[0\leq y\leq l_{y}]</math>		G=[0\leq x\leq l_{x}]\times[0\leq y\leq l_{y}]\end{align}</math>

	двумерное нелинейное уравнение теплопроводности		двумерное нелинейное уравнение теплопроводности
Строка 14:		Строка 14:

	с начальными		с начальными

	<math>T(x,y,0) = T_{0}(x,y), (x,y)\in G,</math>		<math>T(x,y,0) = T_{0}(x,y), (x,y)\in G,</math>

	и граничными условиями		и граничными условиями


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


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

Ateina в 21:40, 11 июня 2017

2017-06-11T21:40:46Z

@@ Строка 3: / Строка 3: @@
 Продольно–поперечная схема, которая также носит название метода переменных направлений (ADI – alternate directions implicit method), получила широкое применение для решения многомерных задач, приводящих к уравнениям в частных производных параболического типа (уравнение диффузии, уравнение теплопроводности). Эта схема была предложена в 1955 году Писменом и Рэкфордом.
 === Математическое описание алгоритма ===
 === Вычислительное ядро алгоритма ===