1 Свойства и структура алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

В настоящем разделе проведено исследование масштабируемости различных параллельных реализации алгоритма k средних согласно методике AlgoWiki.

2.4.1 Реализация 1

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

• 
  Значения количества векторов n: 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.
  
• 
  Значения количества процессоров p: 1, 8, 16, 32, 64, 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480, 512.
  
• 
  Значение количества кластеров k: 100.
  
• 
  Значение размерности векторов d: 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)
Для заданной конфигурации эксперимента (n,d,p,k) и полученных результатов (t,i) производительность и эффективность реализации расчитывались по формулам:

• 
  Performance=Nd,nk−meanst (FLOPS),
  

где Nd,nk−means – точное число операций с плавающей точкой (операции с памятью, а также целочисленные операции не учитывались), вычисленное в соответствие с разделом "Последовательная сложность алгоритма";

• 
  Efficiency=100⋅PerformancePerformancepPeak (%),
  

где PerformancepPeak – пиковая производительность суперкомпьютера при p процессорах, вычисленная согласно спецификациям Intel^® XEON^® X5670^[11].
Графики зависимости производительности и эффективности параллельной реализации k-means от числа векторов для кластеризации (n) и числа процессоров (p) представлены на рисунках 4 и 5, соответственно.

Рис. 4. Параллельная реализация k-means. График зависимости производительности реализации алгоритма от числа векторов для кластеризации (n) и числа процессоров (p).

Рис. 5. Параллельная реализация k-means. График зависимости эффективности реализации алгоритма от числа векторов для кластеризации (n) и числа процессоров (p).