K-means clustering, scalability2
Основные авторы описания: Я.А.Валуйская, Е.С.Глотов.
Ссылки
Исследовалась параллельная реализация алгоритма k-means на MPI.
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Исследование проводилось на суперкомпьютере "Ломоносов"[1] Суперкомпьютерного комплекса Московского университета.
Набор данных для тестирования состоял из 946000 векторов размерности 2 (координаты на сфере)
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессов (виртуальных ядер) [8 : 512];
- число кластеров [128 : 384].
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
- минимальная эффективность реализации [math]\displaystyle{ 2,47% }[/math] достигается при делении исходных данных на 128 кластеров с использованием 512 процессов;
- максимальная эффективность реализации [math]\displaystyle{ 7,13% }[/math] достигается при делении исходных данных на 352 кластера с использованием 8 процессов.
На рисунках 1 и 2, соответственно, представлены графики зависимости производительности и эффективности параллельной реализации k-means от числа кластеров и числа процессов.
По рис. 1 можно отметить практически полное отсутствие роста производительности с увеличением числа процессов от 256 до 512 при минимальном размере задачи. Это связано с быстрым ростом накладных расходов по отношению к крайне низкому объёму вычислений. При росте размерности задачи данный эффект пропадает, и при одновременном пропорциональном увеличении числа кластеров и числа процессов рост производительности становится близким к линейному.
Были получены следующие оценки масштабируемости реализации алгоритма k-means:
- По числу процессов: [math]\displaystyle{ -0.02209 }[/math]. Следовательно, с ростом числа процессов эффективность уменьшается. На рис. 7 можно наблюдать плавное и равномерное снижение производительности по мере увеличения числа процессов при неизменном числе кластеров, что свидетельствует об относительно невысоком росте накладных расходов на передачу данных между процессами и преобладании объёма вычислений над объёмом пересылок данных по сети.
- По размеру задачи: [math]\displaystyle{ 0.01252 }[/math]. Следовательно, с ростом размера задачи (числа кластеров) эффективность увеличивается. При этом объём пересылок данных по сети пропорционален [math]\displaystyle{ (n + k) \cdot p }[/math] (где [math]\displaystyle{ k }[/math] - число кластеров, [math]\displaystyle{ n }[/math] - число входных векторов, [math]\displaystyle{ p }[/math] - число процессов) таким образом, поскольку [math]\displaystyle{ k \lt \lt n }[/math], рост накладных расходов с ростом числа кластеров при неизменном числе процессов и входных векторов представляет собой незначительную величину.
- Общая оценка: [math]\displaystyle{ -0.00081 }[/math]. Таким образом, с ростом и размера задачи, и числа процессов эффективность уменьшается. Это связано с тем, что отношение объёма вычислений к объёму передаваемых данных изменяется пропорционально [math]\displaystyle{ {kn \over (n + k) \cdot p} \thicksim {k \over p} }[/math], что представляет собой невысокий коэффициент, но при этом позволяет параллельной реализации не деградировать до нулевой эффективности при значительном увеличении числа процессов.
Динамические характеристики и эффективность реализации алгоритма
Результаты прогонов
Литература
- ↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.
[[En:K-means clustering, scalability2