Участник:Борис/Алгоритм Рунге-Кутты - История изменений

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

2016-12-19T20:51:01Z

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

← Предыдущая версия		Версия от 20:51, 19 декабря 2016
Строка 211:		Строка 211:
	График производительности:		График производительности:

	[[Файл:~~System_graph~~.png]]		[[Файл:Perf_b.png]]

	График эффективности:		График эффективности:

	[[Файл:~~System_graph~~.png]]		[[Файл:Effic.png]]

	Оценки:		Оценки:

	На основании полученных результатов были составлены графики [https://algowiki-project.org/ru/Глоссарий#.D0.9F.D1.80.D0.BE.D0.B8.D0.B7.D0.B2.D0.BE.D0.B4.D0.B8.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D1.8C\| производительности] и [https://algowiki-project.org/ru/Глоссарий#.D0.AD.D1.84.D1.84.D0.B5.D0.BA.D1.82.D0.B8.D0.B2.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D1.80.D0.B0.D1.81.D0.BF.D0.B0.D1.80.D0.B0.D0.BB.D0.BB.D0.B5.D0.BB.D0.B8.D0.B2.D0.B0.D0.BD.D0.B8.D1.8F\| эффективности] параллельной реализации, вычислены максимальная и минимальная [https://algowiki-project.org/ru/Глоссарий#.D0.AD.D1.84.D1.84.D0.B5.D0.BA.D1.82.D0.B8.D0.B2.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D1.80.D0.B5.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D0.B8\|эффективность реализации], 0.000256661928486 и 1.30949963513e-05 соответственно.		На основании полученных результатов были составлены графики [https://algowiki-project.org/ru/Глоссарий#.D0.9F.D1.80.D0.BE.D0.B8.D0.B7.D0.B2.D0.BE.D0.B4.D0.B8.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D1.8C\| производительности] и [https://algowiki-project.org/ru/Глоссарий#.D0.AD.D1.84.D1.84.D0.B5.D0.BA.D1.82.D0.B8.D0.B2.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D1.80.D0.B0.D1.81.D0.BF.D0.B0.D1.80.D0.B0.D0.BB.D0.BB.D0.B5.D0.BB.D0.B8.D0.B2.D0.B0.D0.BD.D0.B8.D1.8F\| эффективности] параллельной реализации, вычислены максимальная и минимальная [https://algowiki-project.org/ru/Глоссарий#.D0.AD.D1.84.D1.84.D0.B5.D0.BA.D1.82.D0.B8.D0.B2.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D1.80.D0.B5.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D0.B8\| эффективность реализации], 0.000256661928486 и 1.30949963513e-05 соответственно.

	~~Результаты исследования:~~

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

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

2016-12-19T19:38:57Z

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

← Предыдущая версия		Версия от 19:38, 19 декабря 2016
Строка 186:		Строка 186:
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==

			Для исследования масштабируемости алгоритма Рунге-Кутты 4-го порядка была написана своя [https://github.com/D86/superpc/blob/master/rk4.c\|параллельная реализация]. этого алгоритма на языке C.

			Свойства реализации:

			* Реализация написана под компилятор mpicxx.
			* Тестирование проводилось на [http://hpc.cmc.msu.ru/bgp\|IBM Blue Gene/P], расположенном на территории ВМК МГУ.

			Исследование проводилось по [https://algowiki-project.org/ru/Scalability_methodology\|рекомендованной методологии].

			Тестирование

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

			Список изменяющихся параметров:

			В качестве изменяемых параметров выбраны количество максимальное количество процессоров, выделяемое при запуске исследуемой реализации, и параметр m, так как из [[#Входные и выходные данные алгоритма\| раздела 1.9]] следует, что объём входных данных зависит от него.

			Границы изменяющихся параметров:

			* Число процессоров выделяется с 256 до 2048 с шагом 128;
			* Значение m находится в границах от 1000 до 10000 с шагом 1000.

			График производительности:

			[[Файл:System_graph.png]]

			График эффективности:

			[[Файл:System_graph.png]]

			Оценки:

			На основании полученных результатов были составлены графики [https://algowiki-project.org/ru/Глоссарий#.D0.9F.D1.80.D0.BE.D0.B8.D0.B7.D0.B2.D0.BE.D0.B4.D0.B8.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D1.8C\| производительности] и [https://algowiki-project.org/ru/Глоссарий#.D0.AD.D1.84.D1.84.D0.B5.D0.BA.D1.82.D0.B8.D0.B2.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D1.80.D0.B0.D1.81.D0.BF.D0.B0.D1.80.D0.B0.D0.BB.D0.BB.D0.B5.D0.BB.D0.B8.D0.B2.D0.B0.D0.BD.D0.B8.D1.8F\| эффективности] параллельной реализации, вычислены максимальная и минимальная [https://algowiki-project.org/ru/Глоссарий#.D0.AD.D1.84.D1.84.D0.B5.D0.BA.D1.82.D0.B8.D0.B2.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D1.80.D0.B5.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D0.B8\|эффективность реализации], 0.000256661928486 и 1.30949963513e-05 соответственно.

			Результаты исследования:

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

VadimVV в 10:29, 16 ноября 2016

2016-11-16T10:29:23Z

← Предыдущая версия		Версия от 10:29, 16 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|VadimVV}}~~

	{{algorithm		{{algorithm

VadimVV в 11:29, 7 ноября 2016

2016-11-07T11:29:58Z

← Предыдущая версия		Версия от 11:29, 7 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|VadimVV}}

	{{algorithm		{{algorithm

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

2016-11-01T07:45:21Z

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

← Предыдущая версия		Версия от 07:45, 1 ноября 2016
Строка 174:		Строка 174:
	* Устойчивость. Алгоритм устойчив на любом конечном отрезке.		* Устойчивость. Алгоритм устойчив на любом конечном отрезке.
	* Гибкость. На любом этапе вычисления можно легко изменить шаг интегрирования.		* Гибкость. На любом этапе вычисления можно легко изменить шаг интегрирования.
	* ~~Мощность~~ алгоритма стремится к константе. Сумма входных и выходных данных равна mn+m+3, а общее количество операций - 4nCm. Таким образом, при возрастании значений входных параметров, их отношение стремится к 4C.		* Вычислительная мощность алгоритма стремится к константе. Сумма входных и выходных данных равна mn+m+3, а общее количество операций - 4nCm. Таким образом, при возрастании значений входных параметров, их отношение стремится к 4C.

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

Борис в 16:52, 31 октября 2016

2016-10-31T16:52:12Z

← Предыдущая версия		Версия от 16:52, 31 октября 2016
Строка 1:		Строка 1:
			{{Assignment}}

	{{algorithm		{{algorithm

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

2016-10-31T16:51:27Z

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

← Предыдущая версия		Версия от 16:51, 31 октября 2016
Строка 173:		Строка 173:
	* Устойчивость. Алгоритм устойчив на любом конечном отрезке.		* Устойчивость. Алгоритм устойчив на любом конечном отрезке.
	* Гибкость. На любом этапе вычисления можно легко изменить шаг интегрирования.		* Гибкость. На любом этапе вычисления можно легко изменить шаг интегрирования.
			* Мощность алгоритма стремится к константе. Сумма входных и выходных данных равна mn+m+3, а общее количество операций - 4nCm. Таким образом, при возрастании значений входных параметров, их отношение стремится к 4C.

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

Jest в 09:55, 31 октября 2016

2016-10-31T09:55:53Z

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

	Основные авторы описания: [[Участник:Jest\|Е.П.Степанов]]([[#Общее описание алгоритма\|~~раздел~~ 1.1]], [[#Математическое описание алгоритма\|~~раздел~~ 1.2]], [[#Вычислительное ядро алгоритма\|~~раздел~~ 1.3]], [[#Макроструктура алгоритма\|~~раздел~~ 1.4]], [[#Входные и выходные данные алгоритма\|~~раздел~~ 1.9]]), [[Участник:Борис\|Б.Савков]] ( [[#Схема реализации последовательного алгоритма\|~~раздел~~ 1.5]], [[#Последовательная сложность алгоритма\|~~раздел~~ 1.6]], [[#Информационный граф\|~~раздел~~ 1.7]], [[#Ресурс параллелизма алгоритма\|~~раздел~~ 1.8]], [[#Свойства алгоритма\|~~раздел~~ 1.10]], [[#Существующие реализации алгоритма\|~~раздел~~ 2.7]])		Основные авторы описания: [[Участник:Jest\|Е.П.Степанов]](разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Входные и выходные данные алгоритма\|1.9]]), [[Участник:Борис\|Б.Савков]] (разделы [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Существующие реализации алгоритма\|2.7]])

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

Jest: /* Входные и выходные данные алгоритма */ без блоков

2016-10-31T09:53:37Z

Входные и выходные данные алгоритма: без блоков

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

	'''Входные данные''':		'''Входные данные''':
	<math> a, b </math> - интервал интегрирования,		:<math> a, b </math> - интервал интегрирования,
	n - количество точек в разбиении,		:n - количество точек в разбиении,
	<math> \bold y_0 </math> - вектор значений размерности m при <math> x = a </math>,		:<math> \bold y_0 </math> - вектор значений размерности m при <math> x = a </math>,
	функцию вычисления производной <math>\bold f </math> будем считать встроенной в алгоритм.		:функцию вычисления производной <math>\bold f </math> будем считать встроенной в алгоритм.

	'''Объём входных данных''':		'''Объём входных данных''':
	m + 3		:m + 3

	'''Выходные данные:'''		'''Выходные данные:'''
	<math> \bold y_i </math> - вектора размера m значений в n узлах сетки (т.е. при <math> x = a + i * \frac{b-a}{n}, i \in [1, n] </math>).		:<math> \bold y_i </math> - вектора размера m значений в n узлах сетки (т.е. при <math> x = a + i * \frac{b-a}{n}, i \in [1, n] </math>).

	'''Объем выходных данных'''		'''Объем выходных данных'''
	n * m		:n * m

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

Jest: /* Математическое описание алгоритма */ без блоков

2016-10-31T09:52:43Z

Математическое описание алгоритма: без блоков

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

	Исходные данные:		Исходные данные:
	<math> a, b </math> - интервал интегрирования,		:<math> a, b </math> - интервал интегрирования,
	<math> \bold y_0 </math> - вектор значений при <math> x = a </math>,		:<math> \bold y_0 </math> - вектор значений при <math> x = a </math>,
	n - количество точек в разбиении		:n - количество точек в разбиении
	<math>\bold f </math> - функция вычисления производной		:<math>\bold f </math> - функция вычисления производной

	Вычисляемые данные:		Вычисляемые данные:
	<math> \bold y_i </math> - вектора значений в узлах сетки, т.е. при <math> x = a + i * \frac{b-a}{n}, i \in [1, n] </math>		:<math> \bold y_i </math> - вектора значений в узлах сетки, т.е. при <math> x = a + i * \frac{b-a}{n}, i \in [1, n] </math>

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