ASA: Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:Бротиковская_ДанутаД.Брот...»

2022-07-19T13:08:59Z

Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:Бротиковская_ДанутаД.Брот...»

Новая страница
{{level-i}}

Основные авторы описания: [https://algowiki-project.org/ru/Участник:Бротиковская_ДанутаД.Бротиковская], [https://algowiki-project.org/ru/Участник:DennZo1993Д.Зобнин].

= Ссылки =

[https://github.com/serban/kmeans Использованная параллельная реализация алгоритма k-means].

= Локальность данных и вычислений =
== Локальность реализации алгоритма ==
=== Структура обращений в память и качественная оценка локальности ===
=== Количественная оценка локальности ===
= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==

Исследование масштабируемости параллельной реализации алгоритма k-means проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Алгоритм реализован на языке C с использованием средств MPI.
Для исследования масштабируемости проводилось множество запусков программы с разным значением параметра (количество векторов для кластеризации), а также с различным числом процессоров. Фиксировались результаты запусков – время работы <math>t</math> и количество произведенных итераций алгоритма <math>i</math>.

Параметры запусков для экспериментальной оценки:
<ul>
<li>Значения количества векторов <math>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.</li>
<li>Значения количества процессоров <math>p</math>: 1, 8, 16, 32, 64, 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480, 512.</li>
<li>Значение количества кластеров <math>k</math>: 100.</li>
<li>Значение размерности векторов <math>d</math>: 10.</li>
</ul>

Для проведения экспериментов были сгенерированы нормально распределенные псевдослучайные данные (с использованием Python библиотеки [http://scikit-learn.org/ scikit-learn]):
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

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

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


<ul><li><math>{\rm Efficiency} = \frac{100 \cdot {\rm Performance}}{{\rm Performance}_{\rm Peak}^{p}}\ \ (\%),</math></li></ul>
где <math>{\rm Performance}_{\rm Peak}^{p}</math> – пиковая производительность суперкомпьютера при <math>p</math> процессорах, вычисленная согласно спецификациям Intel® XEON® X5670<ref>"http://ark.intel.com/ru/products/47920/Intel-Xeon-Processor-X5670-12M-Cache-2_93-GHz-6_40-GTs-Intel-QPI"</ref>.


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

[[file:Flops.png|thumb|center|800px|Рис. 1. Параллельная реализация k-means. График зависимости производительности реализации алгоритма от числа векторов для кластеризации (<math>n</math>) и числа процессоров (<math>p</math>).]]
[[file:Efficiency.png|thumb|center|800px|Рис. 2. Параллельная реализация k-means. График зависимости эффективности реализации алгоритма от числа векторов для кластеризации (<math>n</math>) и числа процессоров (<math>p</math>).]]


В результате экспериментальной оценки были получены следующие оценки эффективности реализации:
<ul>
<li>Минимальное значение: 0.000409 % достигается при <math>n=20'000, p=480</math></li>
<li>Максимальное значение: 0.741119 % достигается при <math>n=300'000, p=1</math></li>
</ul>



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


= Динамические характеристики и эффективность реализации алгоритма =
= Результаты прогонов =

= Литература =

<references />

[[Категория:Статьи в работе]]

[[En:K-means clustering, scalability1]]

K-means clustering, scalability1 - История изменений

ASA: Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:Бротиковская_ДанутаД.Брот...»