Участник:Full/Поиск автоморфизмов графов - История изменений

Full: /* Ресурс параллелизма алгоритма */

2017-12-12T18:10:36Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 18:10, 12 декабря 2017
Строка 198:		Строка 198:
	* <math>n</math> ярусов сравнений (количество сравнений <math> k = 1 \ldots n: \frac{1}{e^{k}} \frac{n^{n+1/2}}{(n-k-2)^{(n-k-3/2)}~2^{(k)^2}} \times (n - k)(2k + 1) </math>)		* <math>n</math> ярусов сравнений (количество сравнений <math> k = 1 \ldots n: \frac{1}{e^{k}} \frac{n^{n+1/2}}{(n-k-2)^{(n-k-3/2)}~2^{(k)^2}} \times (n - k)(2k + 1) </math>)

	При классификации по высоте ЯПФ, таким образом, ~~алогоритм~~ имеет ~~сложностью~~ <math> O(n) </math>.		При классификации по высоте ЯПФ, таким образом, алгоритм имеет сложность <math> O(n) </math>.

	При классификации по ширине ЯПФ его сложность <math> O(n(\frac{e}{2})^{\ln(n)^2} \ln(n))) </math>.		При классификации по ширине ЯПФ его сложность <math> O(n(\frac{e}{2})^{\ln(n)^2} \ln(n))) </math>.

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

2017-12-10T20:54:17Z

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

← Предыдущая версия		Версия от 20:54, 10 декабря 2017
Строка 239:		Строка 239:

	Оценки масштабируемости выбранной реализации:		Оценки масштабируемости выбранной реализации:
	* По числу процессов: -0,~~000593~~.		* По числу процессов: -0,00837.
	* По размеру задачи: 0,~~06017~~.		* По размеру задачи: 0,04612.
	* По двум направлениям: 0,~~000403~~.		* По двум направлениям: 0,00253.

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

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

2017-12-10T20:39:33Z

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

← Предыдущая версия		Версия от 20:39, 10 декабря 2017
Строка 223:		Строка 223:
	Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Набор и границы значений изменяемых ~~[[Глоссарий#Параметры запуска\|~~параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых параметров запуска реализации алгоритма:

	* число процессоров [4 : 128] с шагом <math> 2^n</math> (точки отображены с шагом 4, усреднив результаты);		* число процессоров [4 : 128] с шагом <math> 2^n</math> (точки отображены с шагом 4, усреднив результаты);

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

2017-12-10T20:32:37Z

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

← Предыдущая версия		Версия от 20:32, 10 декабря 2017
Строка 236:		Строка 236:

	[[file:График_производительности_поиска_автоморфизмов.jpg\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма поиска автоморфизмов. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:График_производительности_поиска_автоморфизмов.jpg\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма поиска автоморфизмов. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:~~График эффективности~~\|thumb\|center\|700px\|Рисунок 3. Параллельная реализация алгоритма поиска автоморфизмов. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:График_эффективности.jpg\|thumb\|center\|700px\|Рисунок 3. Параллельная реализация алгоритма поиска автоморфизмов. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

	Оценки масштабируемости выбранной реализации:		Оценки масштабируемости выбранной реализации:

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

2017-12-10T20:31:16Z

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

← Предыдущая версия		Версия от 20:31, 10 декабря 2017
Строка 230:		Строка 230:
	В результате проведённых экспериментов был получен следующий диапазон алгоритма:		В результате проведённых экспериментов был получен следующий диапазон алгоритма:

	* минимальная эффективность реализации ~~???~~%;		* минимальная эффективность реализации 17,44%;
	* максимальная эффективность реализации ~~???~~%.		* максимальная эффективность реализации 88,73%.

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

	[[file:График_производительности_поиска_автоморфизмов.jpg\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма поиска автоморфизмов. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:График_производительности_поиска_автоморфизмов.jpg\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма поиска автоморфизмов. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:~~.png~~\|thumb\|center\|700px\|Рисунок 3. Параллельная реализация алгоритма поиска автоморфизмов. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:График эффективности\|thumb\|center\|700px\|Рисунок 3. Параллельная реализация алгоритма поиска автоморфизмов. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

	Оценки масштабируемости выбранной реализации:		Оценки масштабируемости выбранной реализации:

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

2017-12-10T16:13:26Z

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

← Предыдущая версия		Версия от 16:13, 10 декабря 2017
Строка 230:		Строка 230:
	В результате проведённых экспериментов был получен следующий диапазон алгоритма:		В результате проведённых экспериментов был получен следующий диапазон алгоритма:

	* минимальная эффективность реализации ~~0,11~~%;		* минимальная эффективность реализации ???%;
	* максимальная эффективность реализации ~~2,65~~%.		* максимальная эффективность реализации ???%.

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

	[[file:.~~png~~\|thumb\|center\|700px\|Рисунок 1. Параллельная реализация алгоритма поиска автоморфизмов. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:График_производительности_поиска_автоморфизмов.jpg\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма поиска автоморфизмов. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма поиска автоморфизмов. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:.png\|thumb\|center\|700px\|Рисунок 3. Параллельная реализация алгоритма поиска автоморфизмов. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

	Оценки масштабируемости выбранной реализации:		Оценки масштабируемости выбранной реализации:
	* По числу процессов: -0,000593. При увеличении числа процессов эффективность на рассмотренной области изменений параметров запуска уменьшается, однако в целом уменьшение не очень быстрое. Малая интенсивность изменения объясняется крайне низкой общей эффективностью работы приложения с максимумом в 2,65%, и значение эффективности на рассмотренной области значений быстро доходит до десятых долей процента. Это свидетельствует о том, что на большей части области значений нет интенсивного снижения эффективности. Это объясняется также тем, что с ростом [[Глоссарий#Вычислительная сложность\|вычислительной сложности]] падение эффективности становится не таким быстрым. Уменьшение эффективности на рассмотренной области работы параллельной программы объясняется быстрым ростом накладных расходов на организацию параллельного выполнения. С ростом вычислительной сложности задачи эффективность снижается так же быстро, но при больших значениях числа процессов. Это подтверждает предположение о том, что накладные расходы начинают сильно превалировать над вычислениями.		* По числу процессов: -0,000593.
	* По размеру задачи: 0,06017. При увеличении размера задачи эффективность возрастает. Эффективность возрастает тем быстрее, чем большее число процессов используется для выполнения. Это подтверждает предположение о том, что размер задачи сильно влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска сильно увеличивается. Также, учитывая разницу максимальной и минимальной эффективности в 2,5%, можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений.		* По размеру задачи: 0,06017.
	* По двум направлениям: 0,000403. При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров небольшая, эффективность с увеличением масштабов возрастает, но медленно и с небольшими перепадами.		* По двум направлениям: 0,000403.

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

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

2017-12-10T16:06:45Z

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

← Предыдущая версия		Версия от 16:06, 10 декабря 2017
Строка 183:		Строка 183:
	== Информационный граф ==		== Информационный граф ==
	[[глоссарий#Граф алгоритма\|Граф алгоритма]]<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> для <math>n = 4</math> (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны:		[[глоссарий#Граф алгоритма\|Граф алгоритма]]<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> для <math>n = 4</math> (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны:



	[[file:Граф_автоморфизмов.png\|thumb\|center\|1100px\|Рисунок 1. Граф алгоритма. CHECK - проверка по критерию.]]		[[file:Граф_автоморфизмов.png\|thumb\|center\|1100px\|Рисунок 1. Граф алгоритма. CHECK - проверка по критерию.]]


	При больших <math>n</math> ширина ярусов будет расти до яруса под номером <math>\lceil\frac{5}{7}\log_2(n)\rceil</math>, после начнет убывать.
			При больших <math>n</math> ширина ярусов будет расти до яруса под номером <math>\lceil\frac{5}{7}\log_2(n) - 1\rceil</math>, после начнет убывать.

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

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

2017-12-10T16:05:48Z

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

← Предыдущая версия		Версия от 16:05, 10 декабря 2017
Строка 183:		Строка 183:
	== Информационный граф ==		== Информационный граф ==
	[[глоссарий#Граф алгоритма\|Граф алгоритма]]<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> для <math>n = 4</math> (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны:		[[глоссарий#Граф алгоритма\|Граф алгоритма]]<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> для <math>n = 4</math> (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны:

			[[file:Граф_автоморфизмов.png\|thumb\|center\|1100px\|Рисунок 1. Граф алгоритма. CHECK - проверка по критерию.]]


			При больших <math>n</math> ширина ярусов будет расти до яруса под номером <math>\lceil\frac{5}{7}\log_2(n)\rceil</math>, после начнет убывать.

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

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

2017-12-10T15:32:39Z

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

← Предыдущая версия		Версия от 15:32, 10 декабря 2017
Строка 182:		Строка 182:

	== Информационный граф ==		== Информационный граф ==
	[[глоссарий#Граф алгоритма\|Граф алгоритма]]<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> ~~при~~ <math>n</math> ~~= 4~~ (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны:		[[глоссарий#Граф алгоритма\|Граф алгоритма]]<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> для <math>n = 4</math> (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны:

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

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

2017-12-10T15:31:59Z

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

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

	== Информационный граф ==		== Информационный граф ==
	[[глоссарий#Граф алгоритма\|Граф алгоритма]]<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> при <math> n = 4 (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны~~</math>~~:		[[глоссарий#Граф алгоритма\|Граф алгоритма]]<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> при <math>n</math> = 4 (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны:

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