Complete cyclic reduction, scalability

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

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

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

Проведём исследование масштабируемости параллельной реализации циклической редукции согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2" Суперкомпьютерного комплекса Московского университета.

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

• число процессоров [2 : 256] с шагом степени двойки;
• размер матрицы [64 : 33554432] с шагом степени двойки.

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

• минимальная эффективность реализации 3.89e-09%;
• максимальная эффективность реализации 0.00163%.

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

Рисунок 1. Параллельная реализация циклической редукции. Изменение производительности в зависимости от числа процессоров и размера матрицы.

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