Участник:Viktorrulev/Алгоритм устойчивой кластеризации с иcпользованием связей - История изменений

ASA в 13:06, 3 февраля 2017

2017-02-03T13:06:25Z

← Предыдущая версия		Версия от 13:06, 3 февраля 2017
Строка 1:		Строка 1:
	{{Assignment\|Teplov}}		{{Assignment\|Teplov}}

	~~{{Assignment}}~~

	{{algorithm		{{algorithm

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

2016-12-16T09:40:56Z

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

← Предыдущая версия		Версия от 09:40, 16 декабря 2016
Строка 219:		Строка 219:
	[[file:ROCK results 2.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.]]		[[file:ROCK results 2.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.]]

	~~Таблица с временем~~ выполнения кластеризации:		Время выполнения кластеризации:

	{\|border="1"		{\|border="1"

Viktorrulev в 09:40, 16 декабря 2016

2016-12-16T09:40:20Z

@@ Строка 1: / Строка 1: @@
 {{Assignment|Teplov}}
 {{algorithm
@@ Строка 216: / Строка 218: @@
 [[file:ROCK results 2.png|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.]]
 Реализация алгоритма была выполнена автором статьи.<ref>https://gitlab.com/viktorrulev/superprak-1/tree/master</ref>

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

2016-12-16T09:22:01Z

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

← Предыдущая версия		Версия от 09:22, 16 декабря 2016
Строка 172:		Строка 172:
	'''Шаг 3:''' имеет небольшую асимптотическую сложность, может быть выполнен последовательно.		'''Шаг 3:''' имеет небольшую асимптотическую сложность, может быть выполнен последовательно.

	'''Шаг 4:''' ~~аналогично шагу 3~~.		'''Шаг 4:''' имеет небольшую асимптотическую сложность, может быть выполнен последовательно.

	'''Шаг 5:''' каждая итерация цикла может быть выполнена только после полного завершения предыдущей, а внутри каждой отдельной итерации все вставки могут быть выполнены независимо друг от друга. Следовательно ширина ЯПФ в этом случае равна <math>O(M)</math>, а высота ЯПФ равна <math>O(MlogM)</math>.		'''Шаг 5:''' каждая итерация цикла может быть выполнена только после полного завершения предыдущей, а внутри каждой отдельной итерации все вставки могут быть выполнены независимо друг от друга. Следовательно ширина ЯПФ в этом случае равна <math>O(M)</math>, а высота ЯПФ равна <math>O(MlogM)</math>.

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

2016-12-16T09:19:16Z

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

← Предыдущая версия		Версия от 09:19, 16 декабря 2016
Строка 168:		Строка 168:
	'''Шаг 1:''' каждая итерация цикла может быть выполнена независимо от всех остальных. Таким образом, в этом случае ширина ЯПФ равна <math>O(M^2)</math>, а высота - <math>O(1)</math>.		'''Шаг 1:''' каждая итерация цикла может быть выполнена независимо от всех остальных. Таким образом, в этом случае ширина ЯПФ равна <math>O(M^2)</math>, а высота - <math>O(1)</math>.

	'''Шаг 2:''' высота ЯПФ равна <math>O(M)</math>, а ширина - <math>O(M^2)</math> (''см. [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)\|перемножение плотных матриц]]'')		'''Шаг 2:''' при использовании алгоритма наивного перемножения плотных матриц высота ЯПФ равна <math>O(M)</math>, а ширина - <math>O(M^2)</math> (''см. [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)\|перемножение плотных матриц]]'')

	'''Шаг 3:''' имеет небольшую асимптотическую сложность, может быть выполнен последовательно.		'''Шаг 3:''' имеет небольшую асимптотическую сложность, может быть выполнен последовательно.

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

2016-12-16T09:16:51Z

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

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

	Реализация алгоритма была выполнена автором статьи.<ref>https://gitlab.com/viktorrulev/superprak-1/tree/master</ref>		Реализация алгоритма была выполнена автором статьи.<ref>https://gitlab.com/viktorrulev/superprak-1/tree/master</ref>


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

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

2016-12-16T09:16:34Z

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

← Предыдущая версия		Версия от 09:16, 16 декабря 2016
Строка 213:		Строка 213:
	* количество точек [500 : 1500] с шагом 100.		* количество точек [500 : 1500] с шагом 100.

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

			[[file:ROCK results 2.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.]]

			Реализация алгоритма была выполнена автором статьи.<ref>https://gitlab.com/viktorrulev/superprak-1/tree/master</ref>

	[[file:ROCK results 2.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.]]

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

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

2016-12-16T08:58:36Z

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

← Предыдущая версия		Версия от 08:58, 16 декабря 2016
Строка 215:		Строка 215:
	На следующих рисунках приведены графики времени выполнения выбранной реализации разложения Холецкого в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики времени выполнения выбранной реализации разложения Холецкого в зависимости от изменяемых параметров запуска.

	[[file:ROCK results.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.]]		[[file:ROCK results 2.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма устойчивой кластеризации с использованием связей. Изменение времени выполнения кластеризации в зависимости от количества точек и от количества параллельных нитей.]]

	'' '''Для проверяющего''': я сделал OpenMP и MPI реализации этого алгоритма, но при запуске на Ломоносове они не дают никакого ускорения в зависимости от количества нитей/процессов. Я могу предоставить графики, показывающие это. Также я готов предоставить исходники обеих программ, но не могу выложить их на git.algowiki-project.org, потому что мне не приходит письмо с подтверждением регистрации.''

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

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

2016-12-16T08:56:37Z

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

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

Teplov в 12:49, 7 декабря 2016

2016-12-07T12:49:21Z

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

	{{algorithm		{{algorithm