K-means clustering, scalability3
Основные авторы описания: П.А.Пархоменко, И.Д.Машонский.
Содержание
1 Ссылки
Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара[1]. Реализация алгоритма была выполнена на языке программирования C с использованием MPI. Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI[2]. Код можно найти здесь: https://github.com/serban/kmeans. Данная реализация предоставляет возможность распараллеливать решение задачи с помощью технологий MPI, OpenMP И CUDA. Для запуска MPI-версии программы использовалась цель "mpi_main" Makefile.
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
3.2 Масштабируемость реализации алгоритма
Исследование происходило на суперкомпьютере Jaguar - Cray XT5[3]. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 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. Исследование производилось на суперкомпьютере "Blue Gene/P"[4].
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [1, 2, 4, 8, 16, 32, 64, 128, 256, 512];
- количество объектов [5000, 10000, 25000, 50000].
Был использован набор данных Dataset for Sensorless Drive Diagnosis Data Set[5] из репозитория Machine learning repository[6].
Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.
На рис. 2 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.
На рис. 3 показана эта же зависимость, только в трехмерном пространстве. По аналогии с рис. 2, были использованы логарифмические оси. Как и в случае двумерного рисунка, можно видеть близкое к линейному увеличение времени работы программы.
4 Динамические характеристики и эффективность реализации алгоритма
5 Результаты прогонов
6 Литература
- ↑ 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.
- ↑ http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html
- ↑ https://www.top500.org/system/176029
- ↑ http://hpc.cmc.msu.ru/bgp
- ↑ 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
- ↑ https://archive.ics.uci.edu/ml/datasets/Dataset+for+Sensorless+Drive+Diagnosis
