LU decomposition via Gaussian elimination, scalability

Основные авторы описания: А.М.Теплов (раздел 3).

1 Ссылки

Исследованная параллельная реализация на языке C.

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

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

Рисунок 1. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная производительность.

Рисунок 2. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная эффективность.

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

• число процессоров [4 : 256]
• размер матрицы [1024 : 5120]

Эффективность выполнения реализации алгоритма

• Минимальная эффективность 0,11 %
• Максимальная эффективность 6.65%

Оценка масштабируемости

• По числу процессов: -0.000101 – при увеличении числа процессов эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении размера задачи. Учитывая разницу между максимальным и минимальным значением эффективности в 6,5% можно сделать вывод, что на рассмотренной области снижение эффективности, скорее всего, достаточно равномерное. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Могут присутствовать области возрастания эффективности, на всех рассмотренных размерах матрицы. Это может объясняться увеличением вычислительной сложности задачи, что при постоянных накладных расходах на организацию параллельного взаимодействия приводит к общему увеличению эффективности работы.
• По размеру задачи:-0.00674– при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области. Это может свидетельствовать о том, что при увеличении размера задачи возрастают и накладные расходы на организацию параллельного взаимодействия. Так как интенсивность снижения эффективности по этому направлению выше, чем по направлению числа процессов, скорее всего падение интенсивности значительно при малом числе процессов более интенсивное, чем в присутствующих областях возрастания эффективности при большом числе процессов.
• По двум направлениям: -6.621e-05 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности очень мала. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 6,5 % говорит о том, что если на поверхности присутствуют области с очень интенсивным изменением эффективности, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.