K-means clustering, scalability2

Основные авторы описания: Я.А.Валуйская, Е.С.Глотов.

1 Ссылки

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

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

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

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета.

Набор данных для тестирования состоял из 946000 векторов размерности 2 (координаты на сфере)

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

• число процессов (виртуальных ядер) [8 : 512];
• число кластеров [128 : 384].

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

• минимальная эффективность реализации [math]2,47%[/math] достигается при делении исходных данных на 128 кластеров с использованием 512 процессов;
• максимальная эффективность реализации [math]7,13%[/math] достигается при делении исходных данных на 352 кластера с использованием 8 процессов.

На рисунках 1 и 2, соответственно, представлены графики зависимости производительности и эффективности параллельной реализации k-means от числа кластеров и числа процессов.

Рис. 1. График зависимости производительности параллельной реализации алгоритма от числа кластеров и числа процессов.

По рис. 1 можно отметить практически полное отсутствие роста производительности с увеличением числа процессов от 256 до 512 при минимальном размере задачи. Это связано с быстрым ростом накладных расходов по отношению к крайне низкому объёму вычислений. При росте размерности задачи данный эффект пропадает, и при одновременном пропорциональном увеличении числа кластеров и числа процессов рост производительности становится близким к линейному.

Рис. 2. График зависимости эффективности параллельной реализации алгоритма от числа кластеров и числа процессов.

Были получены следующие оценки масштабируемости реализации алгоритма k-means:

• По числу процессов: [math]-0.02209[/math]. Следовательно, с ростом числа процессов эффективность уменьшается. На рис. 7 можно наблюдать плавное и равномерное снижение производительности по мере увеличения числа процессов при неизменном числе кластеров, что свидетельствует об относительно невысоком росте накладных расходов на передачу данных между процессами и преобладании объёма вычислений над объёмом пересылок данных по сети.
• По размеру задачи: [math]0.01252[/math]. Следовательно, с ростом размера задачи (числа кластеров) эффективность увеличивается. При этом объём пересылок данных по сети пропорционален [math](n + k) \cdot p[/math] (где [math]k[/math] - число кластеров, [math]n[/math] - число входных векторов, [math]p[/math] - число процессов) таким образом, поскольку [math]k \lt \lt n[/math], рост накладных расходов с ростом числа кластеров при неизменном числе процессов и входных векторов представляет собой незначительную величину.
• Общая оценка: [math]-0.00081[/math]. Таким образом, с ростом и размера задачи, и числа процессов эффективность уменьшается. Это связано с тем, что отношение объёма вычислений к объёму передаваемых данных изменяется пропорционально [math]{kn \over (n + k) \cdot p} \thicksim {k \over p}[/math], что представляет собой невысокий коэффициент, но при этом позволяет параллельной реализации не деградировать до нулевой эффективности при значительном увеличении числа процессов.