K-means clustering, scalability2

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

1 Ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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