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

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

• 
  Минимальное значение: 0.000409 % достигается при n=20′000,p=480
  
• 
  Максимальное значение: 0.741119 % достигается при n=300′000,p=1
  

Оценки масштабируемости реализации алгоритма k-means:

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

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

2.4.2 Реализация 2

Исследование также проводилось на суперкомпьютере "Ломоносов".
Набор данных для тестирования состоял из 946000 векторов размерности 2 (координаты на сфере)
Набор и границы значений изменяемых параметров запуска реализации алгоритма:

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

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

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

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

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

Рис. 7. График зависимости эффективности параллельной реализации алгоритма от числа кластеров и числа процессов.
Исследовалась параллельная реализация алгоритма k-means на MPI.
Были получены следующие оценки масштабируемости реализации алгоритма k-means:

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