ASA в 13:23, 19 июля 2022

2022-07-19T13:23:58Z

← Предыдущая версия		Версия от 13:23, 19 июля 2022
Строка 1:		Строка 1:
	{{level-i}}		{{level-i}}

	Основные авторы описания: [[Участник:~~Elijah\|~~И.В.~~Афанасьев]~~]		Основные авторы описания: [https://algowiki-project.org/ru/Участник:Parkhomenko<b>П.А.Пархоменко</b>], [https://algowiki-project.org/ru/Участник:Ivan.mashonskiy<b>И.Д.Машонский</b>].

	= Ссылки =		= Ссылки =

ASA: Новая страница: «{{level-i}} Основные авторы описания: И.В.Афанасьев = Ссылки = Исследование ма...»

2022-07-19T13:20:19Z

Новая страница: «{{level-i}} Основные авторы описания: И.В.Афанасьев = Ссылки = Исследование ма...»

Новая страница

{{level-i}}

Основные авторы описания: [[Участник:Elijah|И.В.Афанасьев]]

= Ссылки =

Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара<ref>Kumar, J., Mills, R. T., Hoffman, F. M., & Hargrove, W. W. (2011). Parallel k-means clustering for quantitative ecoregion delineation using large data sets. Procedia Computer Science, 4, 1602-1611.</ref>. Реализация алгоритма была выполнена на языке программирования C с использованием MPI. Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI<ref>http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html</ref>. Код можно найти здесь: https://github.com/serban/kmeans. Данная реализация предоставляет возможность распараллеливать решение задачи с помощью технологий MPI, OpenMP И CUDA. Для запуска MPI-версии программы использовалась цель "mpi_main" Makefile.

= Локальность данных и вычислений =
== Локальность реализации алгоритма ==
=== Структура обращений в память и качественная оценка локальности ===
=== Количественная оценка локальности ===
= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==

Исследование происходило на суперкомпьютере Jaguar - Cray XT5<ref>https://www.top500.org/system/176029</ref>. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Объем данных составлял 84 ГБ, количество объектов (d-мерных векторов) n равнялось 1,024,767,667, размерность векторов <math>d</math> равнялась 22, количество кластеров <math>k</math> равнялось 1000.

На рис. 1 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.

[[Файл:k-means-proc-scalability.png|thumb|center|700px|Рис. 1. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (из работы: Kumar etc. 2011).]]

Также было произведено самостоятельное исследование масштабируемости алгоритма k-means. Исследование производилось на суперкомпьютере "Blue Gene/P"<ref>http://hpc.cmc.msu.ru/bgp</ref>.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

* число процессоров [1, 2, 4, 8, 16, 32, 64, 128, 256, 512];
* количество объектов [5000, 10000, 25000, 50000].

Был использован набор данных ''Dataset for Sensorless Drive Diagnosis Data Set''<ref>PASCHKE, Fabian ; BAYER, Christian ; BATOR, Martyna ; MÃ–NKS, Uwe ; DICKS, Alexander ; ENGE-ROSENBLATT, Olaf ; LOHWEG, Volker: Sensorlose ZustandsÃ¼berwachung an Synchronmotoren, Bd. 46. In: HOFFMANN, Frank; HÃœLLERMEIER, Eyke (Hrsg.): Proceedings 23. Workshop Computational Intelligence. Karlsruhe : KIT Scientific Publishing, 2013 (Schriftenreihe des Instituts fÃ¼r Angewandte Informatik - Automatisierungstechnik am Karlsruher Institut fÃ¼r Technologie, 46), S. 211-225</ref> из репозитория ''Machine learning repository''<ref>https://archive.ics.uci.edu/ml/datasets/Dataset+for+Sensorless+Drive+Diagnosis</ref>.

Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.

На рис. 2 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.
[[Файл:Plot_1.png|thumb|center|900px|Рис. 2. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

На рис. 3 показана эта же зависимость, только в трехмерном пространстве. По аналогии с рис. 2, были использованы логарифмические оси. Как и в случае двумерного рисунка, можно видеть близкое к линейному увеличение времени работы программы.
[[Файл:Kmeans-3d.png|thumb|center|900px|Рис. 3. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

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

= Литература =

<references />

[[Категория:Статьи в работе]]

[[En:K-means clustering, scalability3]]

K-means clustering, scalability3 - История изменений

ASA в 13:23, 19 июля 2022

ASA: Новая страница: «{{level-i}} Основные авторы описания: И.В.Афанасьев = Ссылки = Исследование ма...»