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

ASA в 07:26, 6 февраля 2017

2017-02-06T07:26:02Z

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

	Автор статьи: Хромов А. К.		Автор статьи: Хромов А. К.

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

2017-02-04T11:16:20Z

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

← Предыдущая версия		Версия от 11:16, 4 февраля 2017
Строка 162:		Строка 162:
	===Возможные способы и особенности параллельной реализации алгоритма===		===Возможные способы и особенности параллельной реализации алгоритма===
	===Масштабируемость алгоритма и его реализации===		===Масштабируемость алгоритма и его реализации===
	~~[[Файл:Chameleo.png\|300px]]~~

	~~На приведенном графике видна зависимость эффективности от объема данных и числа процессоров~~ для ~~реализации алгоритма~~, ~~описанной в~~ <ref name="real">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>		Реализации алгоритма Chameleon для систем с распределенной памятью найдено не было, но была найдена параллельная реализация для систем с общей памятью <ref name="real">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>. Для данной реализации авторы приводят информацию о производительности, но не приводят исходный код программы. По этой причине была исследована масштабируемость алгоритма в зависимости от количества точек для кластеризации для реализации в пределах одного узла для реализации <ref name="rel_code">http://www.codeforge.com/article/192925</ref>. Запуск программы осуществлялся на вычислительном комплексе IBM Blue Gene/P на одном узле. Характеристики узла приведены по ссылке <ref name="har">http://hpc.cmc.msu.ru/bgp</ref>.
			Далее приведены графики зависимости времени работы программы от размера входных данных. Графики для 4-х и 8 процессов оценочны.

	~~График построен для экспериментальной версии алгоритма для малого числа потоков.~~		[[Файл:718bad6be0fe40419c7ad15675f079f4.png\|600px]]
	Для тестирования использовался процессор Intel Pentium IV для одного потока, Intel Core i5 для 4-х потоков и Intel Core i7 для 8 потоков.

	~~Для набора из 8000 точек запуск на 8 потоках даёт ускорение 4,46x по сравнению~~ с ~~запуском на 1 потоке~~.		Эффективность алгоритма убывает с ростом числа процессов. Темпы убывания эффективности растут с ростом размера входных данных.
	~~Для набора из 10000 точек запуск на 8 процессорах даёт ускорение 4,8x по сравнению~~ с ~~запуском на 1 процессоре~~.
	~~Для набора из 20000 точек запуск на 8 процессорах даёт ускорение 5x по сравнению с запуском на 1 процессоре.~~

	Эффективность алгоритма падает при увеличении числа потоков (при увеличении числа потоков в 8 раз ускорение составляет ориентировочно 4-5x, то есть эффективность падает практически вдвое)

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

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

2017-02-03T15:06:55Z

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

← Предыдущая версия		Версия от 15:06, 3 февраля 2017
Строка 168:		Строка 168:
	График построен для экспериментальной версии алгоритма для малого числа потоков.		График построен для экспериментальной версии алгоритма для малого числа потоков.
	Для тестирования использовался процессор Intel Pentium IV для одного потока, Intel Core i5 для 4-х потоков и Intel Core i7 для 8 потоков.		Для тестирования использовался процессор Intel Pentium IV для одного потока, Intel Core i5 для 4-х потоков и Intel Core i7 для 8 потоков.

	К сожалению, в исследовании, на основе которого строится данный график, не приведены более подробные данные о том, как именно запускались тесты. Приводится только информация о процессорах, на которых выполнялись вычисления. Также в исследовании не приведён запускавшийся код. Вместе с тем, данное исследование является единственным, опирающимся на параллельный код и приводящее результаты запуска данного кода. Других параллельных реализаций найдено не было.

	Для набора из 8000 точек запуск на 8 потоках даёт ускорение 4,46x по сравнению с запуском на 1 потоке.		Для набора из 8000 точек запуск на 8 потоках даёт ускорение 4,46x по сравнению с запуском на 1 потоке.

Hromovalexander в 14:43, 3 февраля 2017

2017-02-03T14:43:16Z

← Предыдущая версия		Версия от 14:43, 3 февраля 2017
Строка 1:		Строка 1:
	{{assignment}		{{assignment}}
	Автор статьи: Хромов А. К.		Автор статьи: Хромов А. К.

Hromovalexander в 14:43, 3 февраля 2017

2017-02-03T14:43:10Z

← Предыдущая версия		Версия от 14:43, 3 февраля 2017
Строка 1:		Строка 1:
	{~~assigned~~}		{{assignment}
	Автор статьи: Хромов А. К.		Автор статьи: Хромов А. К.

Hromovalexander в 14:42, 3 февраля 2017

2017-02-03T14:42:02Z

← Предыдущая версия		Версия от 14:42, 3 февраля 2017
Строка 1:		Строка 1:
			{assigned}
	Автор статьи: Хромов А. К.		Автор статьи: Хромов А. К.

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

2017-02-03T14:41:20Z

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

← Предыдущая версия		Версия от 14:41, 3 февраля 2017
Строка 164:		Строка 164:

	На приведенном графике видна зависимость эффективности от объема данных и числа процессоров для реализации алгоритма, описанной в <ref name="real">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>		На приведенном графике видна зависимость эффективности от объема данных и числа процессоров для реализации алгоритма, описанной в <ref name="real">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>

			График построен для экспериментальной версии алгоритма для малого числа потоков.
	Для тестирования использовался процессор Intel Pentium IV для одного потока, Intel Core i5 для 4-х потоков и Intel Core i7 для 8 потоков.		Для тестирования использовался процессор Intel Pentium IV для одного потока, Intel Core i5 для 4-х потоков и Intel Core i7 для 8 потоков.

	К сожалению, в исследовании, на основе которого строится данный график, не приведены более подробные данные о том, как именно запускались тесты. Приводится только информация о процессорах, на которых выполнялись вычисления. Также в исследовании не приведён запускавшийся код. Вместе с тем, данное исследование является единственным, опирающимся на параллельный код и приводящее результаты запуска данного кода. Других параллельных реализаций найдено не было.		К сожалению, в исследовании, на основе которого строится данный график, не приведены более подробные данные о том, как именно запускались тесты. Приводится только информация о процессорах, на которых выполнялись вычисления. Также в исследовании не приведён запускавшийся код. Вместе с тем, данное исследование является единственным, опирающимся на параллельный код и приводящее результаты запуска данного кода. Других параллельных реализаций найдено не было.

	~~График построен для экспериментальной версии~~ алгоритма ~~для малого~~ числа потоков.		Для набора из 8000 точек запуск на 8 потоках даёт ускорение 4,46x по сравнению с запуском на 1 потоке.
			Для набора из 10000 точек запуск на 8 процессорах даёт ускорение 4,8x по сравнению с запуском на 1 процессоре.
			Для набора из 20000 точек запуск на 8 процессорах даёт ускорение 5x по сравнению с запуском на 1 процессоре.

			Эффективность алгоритма падает при увеличении числа потоков (при увеличении числа потоков в 8 раз ускорение составляет ориентировочно 4-5x, то есть эффективность падает практически вдвое)

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

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

2017-02-03T13:53:04Z

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

← Предыдущая версия		Версия от 13:53, 3 февраля 2017
Строка 164:		Строка 164:

	На приведенном графике видна зависимость эффективности от объема данных и числа процессоров для реализации алгоритма, описанной в <ref name="real">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>		На приведенном графике видна зависимость эффективности от объема данных и числа процессоров для реализации алгоритма, описанной в <ref name="real">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>
			Для тестирования использовался процессор Intel Pentium IV для одного потока, Intel Core i5 для 4-х потоков и Intel Core i7 для 8 потоков.

			К сожалению, в исследовании, на основе которого строится данный график, не приведены более подробные данные о том, как именно запускались тесты. Приводится только информация о процессорах, на которых выполнялись вычисления. Также в исследовании не приведён запускавшийся код. Вместе с тем, данное исследование является единственным, опирающимся на параллельный код и приводящее результаты запуска данного кода. Других параллельных реализаций найдено не было.

	График построен для экспериментальной версии алгоритма для малого числа потоков.		График построен для экспериментальной версии алгоритма для малого числа потоков.

Hromovalexander: /* Макроструктура алгоритма */

2017-02-03T13:40:36Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 13:40, 3 февраля 2017
Строка 71:		Строка 71:
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	1. Построение графа k-ближайших соседей по исходным данным		1. Построение графа k-ближайших соседей по исходным данным

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

	3. Итеративно осуществляется обхединение подграфов, на основе метрик взаимной связности и взаимного сходства. Процесс объединения завершается в момент достижения целевых показателей по данным метрикам.		3. Итеративно осуществляется обхединение подграфов, на основе метрик взаимной связности и взаимного сходства. Процесс объединения завершается в момент достижения целевых показателей по данным метрикам.

Hromovalexander: /* Макроструктура алгоритма */

2017-02-03T13:40:08Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 13:40, 3 февраля 2017
Строка 70:		Строка 70:

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	~~В рамках первого этапа макрооперацияй считается построение~~ графа k-ближайших соседей		1. Построение графа k-ближайших соседей по исходным данным
			2. Разбиения полученного на первом этапе графа на множество подграфов. На очередной итерации выбирается максимальный подграф, для него определяется оптимальное разбиение (подробнее описано в разделе 1.2), подграф разбивается в соответсвии с данным разбиением, начинается следующая итерация. В определенный момент, когда количество вершни в максимальном подграфе становится меньше, чем некоторая изначально заданная доля от количества вершин в первоначальном графе, разбиение прекращается.
	В ~~рамках второго этапа макрооперациями считаются операции разбиения подграфа~~.		3. Итеративно осуществляется обхединение подграфов, на основе метрик взаимной связности и взаимного сходства. Процесс объединения завершается в момент достижения целевых показателей по данным метрикам.

	~~В рамках третьего этапа макрооперациями считаются вычисления метрики~~, на ~~основании которой делается вывод о том, какие подграфы нужно объединять~~.

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===