1 Свойства и структура алгоритма

2.4.3 Реализация 3

Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара^[12]. Исследование происходило на суперкомпьютере Jaguar - Cray XT5^[13]. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.
Реализация алгоритма была выполнена на языке программирования C с использованием MPI.
Объем данных составлял 84 ГБ, количество объектов (d-мерных векторов) n равнялось 1,024,767,667, размерность векторов d равнялась 22, количество кластеров k равнялось 1000.
На рис. 8 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.

Рис. 8. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (из работы: Kumar etc. 2011).
Также было произведено самостоятельное исследование масштабируемости алгоритма k-means. Исследование производилось на суперкомпьютере "Blue Gene/P"^[14].
Набор и границы значений изменяемых параметров запуска реализации алгоритма:

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

Был использован набор данных Dataset for Sensorless Drive Diagnosis Data Set^[15] из репозитория Machine learning repository^[16].
Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.
Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI^[17]. Код можно найти здесь: https://github.com/serban/kmeans. Данная реализация предоставляет возможность распараллеливать решение задачи с помощью технологий MPI, OpenMP И CUDA. Для запуска MPI-версии программы использовалась цель "mpi_main" Makefile.
На рис. 9 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.

Рис. 9. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.
На рис. 10 показана эта же зависимость, только в трехмерном пространстве. По аналогии с рис. 9, были использованы логарифмические оси. Как и в случае двумерного рисунка, можно видеть близкое к линейному увеличение времени работы программы.

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