Участник:Tereshinvs/MST Clusterization - История изменений

Tereshinvs в 09:55, 17 декабря 2016

2016-12-17T09:55:42Z

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

	[[File:boost_mst_time.png\|frame\|center\|alt=Время работы\|Время работы алгоритма построения MST на полном графе из 5000 вершин, синем показана полученное время работы в секундах, зелёным — ожидаемое относительно увеличения количества процессором]]		[[File:boost_mst_time.png\|frame\|center\|alt=Время работы\|Время работы алгоритма построения MST на полном графе из 5000 вершин, синем показана полученное время работы в секундах, зелёным — ожидаемое относительно увеличения количества процессором]]

			Более подробную информацию о производительности этого и других алгоритмов из Boost/graph/distributed можно получить на их странице: http://www.boost.org/doc/libs/1_55_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#performance.

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

Zhum в 12:29, 6 декабря 2016

2016-12-06T12:29:50Z

← Предыдущая версия		Версия от 12:29, 6 декабря 2016
Строка 1:		Строка 1:

	~~{{Assignment}}~~
	== Структура и свойства алгоритма ==		== Структура и свойства алгоритма ==

Tereshinvs: /* Структура и свойства алгоритма */

2016-12-04T11:14:38Z

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

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

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

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

2016-12-04T11:13:41Z

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

← Предыдущая версия		Версия от 11:13, 4 декабря 2016
Строка 168:		Строка 168:

	К сожалению, не удалось запустить программу, использующую данную библиотеку на суперкомпьютере IBM BlueGene/P, поэтому замеры производительности производились на компьютере с процессором Intel Core i5 4210U (два ядра и четыре потока, тактовая частота 1.7ГГц, до 2.7ГГц в режиме Turbo Boost), 6GB оперативной памяти DDR3, жёстким диском с частотой вращения шпинделя 5400 об/мин под управлением Windows 10 64-bit с использованием Windows Subsystem for Linux.		К сожалению, не удалось запустить программу, использующую данную библиотеку на суперкомпьютере IBM BlueGene/P, поэтому замеры производительности производились на компьютере с процессором Intel Core i5 4210U (два ядра и четыре потока, тактовая частота 1.7ГГц, до 2.7ГГц в режиме Turbo Boost), 6GB оперативной памяти DDR3, жёстким диском с частотой вращения шпинделя 5400 об/мин под управлением Windows 10 64-bit с использованием Windows Subsystem for Linux.

			На графике представлена зависимость времени работы программы на случайном полном графе из 5000 вершин (соответствует набору из 5000 точек для кластеризации) от количества доступных процессоров, а также ожидаемое время работы на этом же количестве процессоров.

	Замеры производились только для построения минимального остовного дерева для полного графа (вершины — объекты, рёбра с весами — отношения), так как это является вычислительным ядром алгоритма.		Замеры производились только для построения минимального остовного дерева для полного графа (вершины — объекты, рёбра с весами — отношения), так как это является вычислительным ядром алгоритма.

Zhum в 10:55, 23 ноября 2016

2016-11-23T10:55:51Z

← Предыдущая версия		Версия от 10:55, 23 ноября 2016
Строка 1:		Строка 1:

	~~{{Assignment}}~~

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

Tereshinvs: /* Структура и свойства алгоритма */

2016-11-20T09:25:57Z

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

← Предыдущая версия		Версия от 09:25, 20 ноября 2016
Строка 1:		Строка 1:

			{{Assignment}}

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

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

2016-11-20T09:22:31Z

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

← Предыдущая версия		Версия от 09:22, 20 ноября 2016
Строка 171:		Строка 171:
	Замеры производились только для построения минимального остовного дерева для полного графа (вершины — объекты, рёбра с весами — отношения), так как это является вычислительным ядром алгоритма.		Замеры производились только для построения минимального остовного дерева для полного графа (вершины — объекты, рёбра с весами — отношения), так как это является вычислительным ядром алгоритма.

	[[File:boost_mst_time.png\|frame\|center\|alt=Время работы\|Время работы алгоритма построения MST на полном графе из 5000 вершин, синем показана полученное время работы, зелёным — ожидаемое относительно увеличения количества процессором]]		[[File:boost_mst_time.png\|frame\|center\|alt=Время работы\|Время работы алгоритма построения MST на полном графе из 5000 вершин, синем показана полученное время работы в секундах, зелёным — ожидаемое относительно увеличения количества процессором]]

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

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

2016-11-20T09:19:59Z

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

← Предыдущая версия		Версия от 09:19, 20 ноября 2016
Строка 107:		Строка 107:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	В этом параграфе описывается масштабируемость параллельной реализации алгоритма из библиотеки Boost::graph::distributed.		В этом параграфе описывается масштабируемость параллельной реализации алгоритма из библиотеки Boost::graph::distributed.


	С использованием библиотеки Boost::graph::distributed программу можно реализовать следующим образом (указана только часть построения MST):		С использованием библиотеки Boost::graph::distributed программу можно реализовать следующим образом (указана только часть построения MST):

Tereshinvs: /* Программная реализация алгоритма */

2016-11-20T09:19:47Z

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

← Предыдущая версия		Версия от 09:19, 20 ноября 2016
Строка 102:		Строка 102:

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

			Интересной особенностью использования библиотеки Boost::graph::distributed является возможность задания изначального распределения вершин графа по процессам. К сложностям использования можно отнести нечитаемые сообщения об ошибках инстанцирования шаблонов С++ и отсутствие большого числа примеров использования библиотеки в интернете.

			=== Масштабируемость алгоритма и его реализации ===
			В этом параграфе описывается масштабируемость параллельной реализации алгоритма из библиотеки Boost::graph::distributed.


	С использованием библиотеки Boost::graph::distributed программу можно реализовать следующим образом (указана только часть построения MST):		С использованием библиотеки Boost::graph::distributed программу можно реализовать следующим образом (указана только часть построения MST):

Строка 160:		Строка 167:
	}		}
	</source>		</source>

	Интересной особенностью данной библиотеки является возможность задания изначального распределения вершин графа по процессам. К сложностям использования можно отнести нечитаемые сообщения об ошибках инстанцирования шаблонов С++ и отсутствие большого числа примеров использования библиотеки в интернете.

	~~=== Масштабируемость алгоритма и его реализации ===~~
	В этом параграфе описывается масштабируемость параллельной реализации алгоритма из библиотеки Boost::graph::distributed.

	К сожалению, не удалось запустить программу, использующую данную библиотеку на суперкомпьютере IBM BlueGene/P, поэтому замеры производительности производились на компьютере с процессором Intel Core i5 4210U (два ядра и четыре потока, тактовая частота 1.7ГГц, до 2.7ГГц в режиме Turbo Boost), 6GB оперативной памяти DDR3, жёстким диском с частотой вращения шпинделя 5400 об/мин под управлением Windows 10 64-bit с использованием Windows Subsystem for Linux.		К сожалению, не удалось запустить программу, использующую данную библиотеку на суперкомпьютере IBM BlueGene/P, поэтому замеры производительности производились на компьютере с процессором Intel Core i5 4210U (два ядра и четыре потока, тактовая частота 1.7ГГц, до 2.7ГГц в режиме Turbo Boost), 6GB оперативной памяти DDR3, жёстким диском с частотой вращения шпинделя 5400 об/мин под управлением Windows 10 64-bit с использованием Windows Subsystem for Linux.

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

2016-11-20T09:18:14Z

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

← Предыдущая версия		Версия от 09:18, 20 ноября 2016
Строка 170:		Строка 170:
	Замеры производились только для построения минимального остовного дерева для полного графа (вершины — объекты, рёбра с весами — отношения), так как это является вычислительным ядром алгоритма.		Замеры производились только для построения минимального остовного дерева для полного графа (вершины — объекты, рёбра с весами — отношения), так как это является вычислительным ядром алгоритма.

	[[File:boost_mst_time.png\|frame\|center\|alt=Время работы\|Время работы алгоритма построения MST на полном графе из 5000 вершин]]		[[File:boost_mst_time.png\|frame\|center\|alt=Время работы\|Время работы алгоритма построения MST на полном графе из 5000 вершин, синем показана полученное время работы, зелёным — ожидаемое относительно увеличения количества процессором]]

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