Участник:Smirnov.maxim/BIRCH - История изменений

Coctic в 14:44, 13 декабря 2016

2016-12-13T14:44:21Z

← Предыдущая версия		Версия от 14:44, 13 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|{REVISIONUSER}}}}		{{Assignment\|{{REVISIONUSER}}}}
	Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].		Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].
	Вклад авторов:		Вклад авторов:

Coctic в 14:44, 13 декабря 2016

2016-12-13T14:44:05Z

← Предыдущая версия		Версия от 14:44, 13 декабря 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|{REVISIONUSER}}}}
	Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].		Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].
	Вклад авторов:		Вклад авторов:

Smirnov.maxim в 19:17, 12 декабря 2016

2016-12-12T19:17:12Z

← Предыдущая версия		Версия от 19:17, 12 декабря 2016
Строка 1:		Строка 1:
			{{Assignment}}
	Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].		Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].
	Вклад авторов:		Вклад авторов:

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

2016-12-12T19:16:40Z

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

← Предыдущая версия		Версия от 19:16, 12 декабря 2016
Строка 380:		Строка 380:

	Для исследования возможностей паралеллизма алгоритма BIRCH была написана [https://github.com/duran-duran/birch реализация на языке C++] с использованием технологии MPI. В данной реализации входные данные равномерно распределяются между всеми процессами, в каждом из которых выполняется построение собственного кластерного дерева. Листьевые элементы полученных деревьев затем подвергаются глобальной кластеризации с помощью распределенного алгоритма k-средних. В качестве входных данных использовались точки размерности <math>d=5</math>, координаты которых были равномерно распределены в диапазоне <math>[-10000;10000]</math>.		Для исследования возможностей паралеллизма алгоритма BIRCH была написана [https://github.com/duran-duran/birch реализация на языке C++] с использованием технологии MPI. В данной реализации входные данные равномерно распределяются между всеми процессами, в каждом из которых выполняется построение собственного кластерного дерева. Листьевые элементы полученных деревьев затем подвергаются глобальной кластеризации с помощью распределенного алгоритма k-средних. В качестве входных данных использовались точки размерности <math>d=5</math>, координаты которых были равномерно распределены в диапазоне <math>[-10000;10000]</math>.

			{\| class="wikitable mw-collapsible mw-collapsed"
			! Технические детали реализации
			\|-
			\|
			Компилятор: intel/15.0.090

			Версия реализации MPI: openmpi/1.10.2-icc

			Планировщик задач: slurm/2.5.6

			Очереди: test, regular4

			Команда компиляции: mpicxx -std=c++11 -Wall <source_files> -o <executable>

			Команда запуска: sbatch -n <num_of_processes> -p <queue> -o <log_file> ompi <executable> <args>

			\|}

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

Coctic в 09:57, 12 декабря 2016

2016-12-12T09:57:13Z

← Предыдущая версия		Версия от 09:57, 12 декабря 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~
	Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].		Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].
	Вклад авторов:		Вклад авторов:

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

2016-12-11T16:32:20Z

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

← Предыдущая версия		Версия от 16:32, 11 декабря 2016
Строка 377:		Строка 377:

	Оценка масштабируемости параллельной реализации:		Оценка масштабируемости параллельной реализации:
	* По числу процессов: при увеличении числа процессов эффективность распараллеливания снижается. При количестве процессов <math>n>30</math> темп снижения ~~становятся~~ несущественным.		* По числу процессов: при увеличении числа процессов эффективность распараллеливания снижается. При количестве процессов <math>n>30</math> темп снижения становится несущественным.
	* По размеру задачи: при увеличении размера входных данных эффективность растет неравномерно, что свидетельствует о сложной зависимости от входных данных.		* По размеру задачи: при увеличении размера входных данных эффективность растет неравномерно, что свидетельствует о сложной зависимости от входных данных.

Smirnov.maxim в 16:17, 11 декабря 2016

2016-12-11T16:17:47Z

← Предыдущая версия		Версия от 16:17, 11 декабря 2016
Строка 1:		Строка 1:
			{{Assignment}}
	Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].		Авторы: [[Участник:Светлана Морозова\|Морозова Светлана]], [[Участник:Smirnov.maxim\|Смирнов Максим]].
	Вклад авторов:		Вклад авторов:

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

2016-12-11T16:17:28Z

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

← Предыдущая версия		Версия от 16:17, 11 декабря 2016
Строка 358:		Строка 358:


	[[file:Масштабируемость параллельной реализации алгоритма BIRCH. Производительность.png\|thumb\|center\|700px\|Рисунок 1. ~~Масштабируемость~~ параллельной реализации алгоритма BIRCH~~. Максимальная производительность~~. ]]		[[file:Масштабируемость параллельной реализации алгоритма BIRCH. Производительность.png\|thumb\|center\|700px\|Рисунок 1. График времени работы параллельной реализации алгоритма BIRCH. ]]


	[[file:Масштабируемость параллельной реализации алгоритма BIRCH. Эффективность.png\|thumb\|center\|700px\|Рисунок 2. ~~Масштабируемость параллельной реализации~~ алгоритма BIRCH~~. Максимальная эффективность~~. ]]		[[file:Масштабируемость параллельной реализации алгоритма BIRCH. Эффективность.png\|thumb\|center\|700px\|Рисунок 2. График эффективности распараллеливания алгоритма BIRCH относительно последовательной реализации. ]]

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

2016-12-11T16:14:55Z

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

← Предыдущая версия		Версия от 16:14, 11 декабря 2016
Строка 376:		Строка 376:

	Оценка масштабируемости параллельной реализации:		Оценка масштабируемости параллельной реализации:
	* По числу процессов: при увеличении числа процессов эффективность распараллеливания снижается. ~~По мере увеличения числа~~ процессов ~~темпы~~ снижения становятся ~~несущественными~~.		* По числу процессов: при увеличении числа процессов эффективность распараллеливания снижается. При количестве процессов <math>n>30</math> темп снижения становятся несущественным.
	* По размеру задачи: при увеличении размера входных данных эффективность растет неравномерно, что свидетельствует о сложной зависимости от входных данных.		* По размеру задачи: при увеличении размера входных данных эффективность растет неравномерно, что свидетельствует о сложной зависимости от входных данных.

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

2016-12-11T16:12:11Z

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

← Предыдущая версия		Версия от 16:12, 11 декабря 2016
Строка 373:		Строка 373:
	* максимальная эффективность реализации 235,42% (8 процессоров, 800 000 точек)		* максимальная эффективность реализации 235,42% (8 процессоров, 800 000 точек)

			Полученные результаты могут быть объяснены недерминированностью алгоритма BIRCH и существенной зависимостью времени его работы от входных данных.

	Оценка масштабируемости		Оценка масштабируемости параллельной реализации:
	* По числу процессов		* По числу процессов: при увеличении числа процессов эффективность распараллеливания снижается. По мере увеличения числа процессов темпы снижения становятся несущественными.
			* По размеру задачи: при увеличении размера входных данных эффективность растет неравномерно, что свидетельствует о сложной зависимости от входных данных.

	Для исследования возможностей паралеллизма алгоритма BIRCH была написана [https://github.com/duran-duran/birch реализация на языке C++] с использованием технологии MPI. В данной реализации входные данные равномерно распределяются между всеми процессами, в каждом из которых выполняется построение собственного кластерного дерева. Листьевые элементы полученных деревьев затем подвергаются глобальной кластеризации с помощью распределенного алгоритма k-средних. В качестве входных данных использовались точки размерности <math>d=5</math>, координаты которых были равномерно распределены в диапазоне <math>[-10000;10000]</math>.		Для исследования возможностей паралеллизма алгоритма BIRCH была написана [https://github.com/duran-duran/birch реализация на языке C++] с использованием технологии MPI. В данной реализации входные данные равномерно распределяются между всеми процессами, в каждом из которых выполняется построение собственного кластерного дерева. Листьевые элементы полученных деревьев затем подвергаются глобальной кластеризации с помощью распределенного алгоритма k-средних. В качестве входных данных использовались точки размерности <math>d=5</math>, координаты которых были равномерно распределены в диапазоне <math>[-10000;10000]</math>.