K-means clustering, scalability4

Основные авторы описания: И.Егоров, Е.Богомазов.

Ссылки

Параллельная реализация была написана самостоятельно на языке C, ссылка на реализацию. Так как на каждой итерации число действий на единицу данных не велико и данные должны быть собраны вместе при перерасчете центроидов, было решено для ускорения вычислений воспользоваться только OpenMP без использовании MPI.

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

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

Исследование масштабируемости данной параллельной реализации алгоритма k-средних также проводилось на суперкомпьютере "Ломоносов".

Код собирался под gcc с опцией -fopenmp. Код считался на одном процессоре, технология hyperthreading не использовалась.

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

• число процессоров [1 : 16] с увеличением в 2 раза;
• размер данных [100000 : 1600000] с увеличением в 2 раза.

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

• Максимальная эффективность в точке достигается при переходе от 1 потока на 4 при минимальном размере данных, она равна [math]\displaystyle{ 87,5% }[/math].
• Усредненная максимальная эффективность достигается при переходе с одного потока на два. Среднее время вычислений на всех рассмотренных потока снижается с 16,33 до 11.87 секунд, поэтому формально эффективность [math]\displaystyle{ = 16.33 / 11.87 / 2 \approx 68,4\% }[/math]
• Минимальная эффективность в точке достигается при переходе от 1 потока на 16 при размере данных 800000, она равна [math]\displaystyle{ 11,1\% }[/math].
• Усредненная минимальная эффективность наблюдается при переходе с одного на максимальное рассматриваемое в эксперименте число потоков, равное 16. Время вычисления изменяется с 16,33 до 7,6 секунд, поэтому формально эффективность [math]\displaystyle{ = 16.33 / 7.6 / 16 \approx 14,9\% }[/math]

Ниже приведены графики зависимости вычислительного времени алгоритма и его эффективности от изменяемых параметров запуска — размера данных и числа процессоров:

Рис. 1. Параллельная реализация алгоритма k-средних. Изменение вычислительного времени алгоритма в зависимости от числа процессоров и размера исходных данных.

Здесь видно, что время выполнения операций алгоритма плавно убывает по каждому из параметров, причем скорость убывания по параметру числа процессоров выше, чем в зависимости от размерности задачи.

Рис. 2. Параллельная реализация алгоритма k-средних. Изменение эффективности алгоритма в зависимости от числа процессоров и размера исходных данных.

Здесь построена эффективность перехода от последовательной реализации к параллельной. Рассчитывается она по формуле Время вычисления на 1 потоке / Время вычисления на [math]\displaystyle{ T }[/math] потоках / [math]\displaystyle{ T }[/math], где [math]\displaystyle{ T }[/math] — это число потоков. При вычислении на 1 процессоре она равна 100 \% в силу используемой формулы, что и отражено на графике.

Проведем оценки масштабируемости:

По числу процессов — при увеличении числа процессов эффективность уменьшается на всей области рассматриваемых значений, причем темп убывания замедляется с ростом числа процессов.

По размеру задачи — при увеличении размера задачи эффективность вычислений вначале кратковременно возрастает, но затем начинает относительно равномерно убывать на всей рассматриваемой области.

По размеру задачи — при увеличении размера задачи эффективность вычислений в общем случае постепенно убывает. На малых данных она выходит на пик мощности, являющийся максимумом эффективности в исследуемых условиях, но затем возвращается к процессу убывания.