Dense matrix multiplication, scalability

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

1 Ссылки

Реализация алгоритма на языке C.

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

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

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

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

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

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

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

• Минимальная эффективность 4,71%
• Максимальная эффективность 31,72%

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

• По числу процессов: -0.0436 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы связано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
• По размеру задачи: -0.0255 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
• По двум направлениям: -0.000968 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 25% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.