Участник:Павел/Алгоритм кластеризации категорийных данных CLOPE - История изменений

ASA в 13:07, 15 февраля 2017

2017-02-15T13:07:23Z

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

	Автор описания: [[Участник:Павел\|П.М.Бронников]]		Автор описания: [[Участник:Павел\|П.М.Бронников]]

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

2017-02-15T08:39:31Z

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

← Предыдущая версия		Версия от 08:39, 15 февраля 2017
Строка 400:		Строка 400:
	return 0;		return 0;
	}		}

			Результаты проверки на графике ниже.

			[[file:Clope lom.PNG\|thumb\|center\|1000px]]

			В данной реализации алгоритм показал плохую масштабируемость. Оптимальное число нитей - 8.

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

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

2017-02-15T08:01:17Z

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

← Предыдущая версия		Версия от 08:01, 15 февраля 2017
Строка 400:		Строка 400:
	return 0;		return 0;
	}		}


	~~Результаты проверки на графике ниже.~~

	~~//[[file:Graf_lom.png\|\|700px]]~~

	~~//Таким образом, можно сделать вывод о том, что алгоритм кластеризации CLOPE является масштабируемым.~~

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

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

2017-02-15T08:00:15Z

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

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

Павел в 21:00, 6 февраля 2017

2017-02-06T21:00:48Z

← Предыдущая версия		Версия от 21:00, 6 февраля 2017
Строка 137:		Строка 137:

	Этап итераций отличается только тем, что на нем дополнительно считается функция '''DeltaRemove''' вычисления стоимости удаления транзакции с кластера. На этапе итерации функции DeltaAdd/DeltaRemove могут считать параллельно для каждой транзакции.		Этап итераций отличается только тем, что на нем дополнительно считается функция '''DeltaRemove''' вычисления стоимости удаления транзакции с кластера. На этапе итерации функции DeltaAdd/DeltaRemove могут считать параллельно для каждой транзакции.

			Синие точки сетки - вычисление функций DeltaAdd. На этапе инициализации количество кластеров может как увеличиться, так и не измениться, это показано пунктирными линиями.
			[[File:init1.PNG\|thumb\|center\|300px\|Этап Инициализации]]

			Зеленые точки сетки - вычисление функций DeltaAdd и DeltaRemove. На этапе итераций функции могут считаться параллельно для каждой транзакции.
			[[File:iter1.PNG\|thumb\|center\|300px\|Этап Итераций]]

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

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

2017-01-19T15:33:31Z

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

← Предыдущая версия		Версия от 15:33, 19 января 2017
Строка 172:		Строка 172:

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Проверка масштабируемости проводилась на суперкомпьютере "Ломоносов" с числом процессоров 1, 8, 16, 32 и 64 на десяти различных сетках - от 1000×1000 до 10000×10000. Для компиляции использовался компилятор Intel(13.1.0) с OpenMPI(1.8.4). Результаты проверки на графике ниже.		Проверка масштабируемости проводилась на суперкомпьютере "Ломоносов" с числом процессоров 1, 8, 16, 32 и 64 на десяти различных сетках - от 1000×1000 до 10000×10000. Для компиляции программы использовался компилятор Intel(13.1.0) с OpenMPI(1.8.4). Результаты проверки на графике ниже.

	[[file:Graf_lom.png\|\|700px]]		[[file:Graf_lom.png\|\|700px]]

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

2017-01-19T15:32:00Z

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

← Предыдущая версия		Версия от 15:32, 19 января 2017
Строка 172:		Строка 172:

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Проверка масштабируемости проводилась на суперкомпьютере "Ломоносов" с числом процессоров 1, 8, 16, 32 и 64 на десяти различных сетках - от 1000×1000 до 10000×10000. Результаты проверки на графике ниже.		Проверка масштабируемости проводилась на суперкомпьютере "Ломоносов" с числом процессоров 1, 8, 16, 32 и 64 на десяти различных сетках - от 1000×1000 до 10000×10000. Для компиляции использовался компилятор Intel(13.1.0) с OpenMPI(1.8.4). Результаты проверки на графике ниже.

	[[file:Graf_lom.png\|\|700px]]		[[file:Graf_lom.png\|\|700px]]

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

2017-01-19T15:12:57Z

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

← Предыдущая версия		Версия от 15:12, 19 января 2017
Строка 173:		Строка 173:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Проверка масштабируемости проводилась на суперкомпьютере "Ломоносов" с числом процессоров 1, 8, 16, 32 и 64 на десяти различных сетках - от 1000×1000 до 10000×10000. Результаты проверки на графике ниже.		Проверка масштабируемости проводилась на суперкомпьютере "Ломоносов" с числом процессоров 1, 8, 16, 32 и 64 на десяти различных сетках - от 1000×1000 до 10000×10000. Результаты проверки на графике ниже.

	[[file:Graf_lom.png\|\|700px]]		[[file:Graf_lom.png\|\|700px]]

			Таким образом, можно сделать вывод о том, что алгоритм кластеризации CLOPE является масштабируемым.

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

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

2017-01-19T14:35:18Z

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

← Предыдущая версия		Версия от 14:35, 19 января 2017
Строка 172:		Строка 172:

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Проверка масштабируемости проводилась на суперкомпьютере "Ломоносов" с числом процессоров 1, 8, 16, 32 и 64. Результаты проверки на графике ниже.		Проверка масштабируемости проводилась на суперкомпьютере "Ломоносов" с числом процессоров 1, 8, 16, 32 и 64 на десяти различных сетках - от 1000×1000 до 10000×10000. Результаты проверки на графике ниже.
	[[file:Graf_lom.png\|\|700px]]		[[file:Graf_lom.png\|\|700px]]

Павел: /* Последовательная сложность алгоритма */

2017-01-19T14:26:07Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 14:26, 19 января 2017
Строка 122:		Строка 122:
	Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.		Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более <math>m</math> сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого <math>m + 8</math> операций.

	Операции выполняются для всех ~~транзаций~~ (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>nk(m+8)</math> операций.		Операции выполняются для всех транзакций (<math>n</math> штук) и для всех кластеров (<math>k</math> штук). Итого выполняется <math>nk(m+8)</math> операций.

	В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.		В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: <math>m+2</math> операции.