K-means clustering, scalability1

Основные авторы описания: Д.Бротиковская, Д.Зобнин.

Ссылки

Использованная параллельная реализация алгоритма k-means.

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

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

Исследование масштабируемости параллельной реализации алгоритма k-means проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. Алгоритм реализован на языке C с использованием средств MPI. Для исследования масштабируемости проводилось множество запусков программы с разным значением параметра (количество векторов для кластеризации), а также с различным числом процессоров. Фиксировались результаты запусков – время работы [math]\displaystyle{ t }[/math] и количество произведенных итераций алгоритма [math]\displaystyle{ i }[/math].

Параметры запусков для экспериментальной оценки:

• Значения количества векторов [math]\displaystyle{ n }[/math]: 20'000, 30'000, 50'000, 100'000, 200'000, 300'000, 500'000, 700'000, 1'000'000, 1'500'000, 2'000'000.
• Значения количества процессоров [math]\displaystyle{ p }[/math]: 1, 8, 16, 32, 64, 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480, 512.
• Значение количества кластеров [math]\displaystyle{ k }[/math]: 100.
• Значение размерности векторов [math]\displaystyle{ d }[/math]: 10.

Для проведения экспериментов были сгенерированы нормально распределенные псевдослучайные данные (с использованием Python библиотеки scikit-learn):

from sklearn.datasets import make_classification
X1, Y1 = make_classification(n_features=10, n_redundant=2, n_informative=8,
                             n_clusters_per_class=1, n_classes=100,
                             n_samples=2000000)

Для заданной конфигурации эксперимента ([math]\displaystyle{ n, d, p, k }[/math]) и полученных результатов ([math]\displaystyle{ t, i }[/math]) производительность и эффективность реализации расчитывались по формулам:

• [math]\displaystyle{ {\rm Performance} = \frac{N_{\rm k-means}^{d, n}}{t}\ \ ({\rm FLOPS}), }[/math]

где [math]\displaystyle{ N_{\rm k-means}^{d, n} }[/math] – точное число операций с плавающей точкой (операции с памятью, а также целочисленные операции не учитывались), вычисленное в соответствие с разделом "Последовательная сложность алгоритма";

• [math]\displaystyle{ {\rm Efficiency} = \frac{100 \cdot {\rm Performance}}{{\rm Performance}_{\rm Peak}^{p}}\ \ (\%), }[/math]

где [math]\displaystyle{ {\rm Performance}_{\rm Peak}^{p} }[/math] – пиковая производительность суперкомпьютера при [math]\displaystyle{ p }[/math] процессорах, вычисленная согласно спецификациям Intel^® XEON^® X5670.

Графики зависимости производительности и эффективности параллельной реализации k-means от числа векторов для кластеризации ([math]\displaystyle{ n }[/math]) и числа процессоров ([math]\displaystyle{ p }[/math]) представлены на рисунках 1 и 2, соответственно.

Рис. 1. Параллельная реализация k-means. График зависимости производительности реализации алгоритма от числа векторов для кластеризации ([math]\displaystyle{ n }[/math]) и числа процессоров ([math]\displaystyle{ p }[/math]).

Рис. 2. Параллельная реализация k-means. График зависимости эффективности реализации алгоритма от числа векторов для кластеризации ([math]\displaystyle{ n }[/math]) и числа процессоров ([math]\displaystyle{ p }[/math]).

В результате экспериментальной оценки были получены следующие оценки эффективности реализации:

• Минимальное значение: 0.000409 % достигается при [math]\displaystyle{ n=20'000, p=480 }[/math]
• Максимальное значение: 0.741119 % достигается при [math]\displaystyle{ n=300'000, p=1 }[/math]

Оценки масштабируемости реализации алгоритма k-means:

• По числу процессоров: -0.002683 – эффективность убывает с ростом числа процессоров. Данный результат вызван ростом накладных расходов для обеспечения параллельного выполнения алгоритма.
• По размеру задачи: 0.002779 – эффективность растет с ростом числа векторов. Данный результат вызван тем, что при увеличении размера задачи, количество вычислений растет по сравнению с временем, затрачиваемым на пересылку данных.
• Общая оценка: -0.000058 – можно сделать вывод, что в целом эффективность реализации незначительно уменьшается с ростом размера задачи и числа процессоров.