Уровень реализации

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 в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.

Рис. 1. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (из работы: Kumar etc. 2011).

Также было произведено самостоятельное исследование масштабируемости алгоритма 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 в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.

Рис. 2. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.

На рис. 3 показана эта же зависимость, только в трехмерном пространстве. По аналогии с рис. 2, были использованы логарифмические оси. Как и в случае двумерного рисунка, можно видеть близкое к линейному увеличение времени работы программы.

Рис. 3. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.

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

5 Результаты прогонов

6 Литература

  1. 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.
  2. http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html
  3. https://www.top500.org/system/176029
  4. http://hpc.cmc.msu.ru/bgp
  5. 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
  6. https://archive.ics.uci.edu/ml/datasets/Dataset+for+Sensorless+Drive+Diagnosis