Матричное умножение

Матричное умножение. Аналогично рассматриваются алгоритмы умножения матриц А и В. Пусть матрицы разбиты на блоки Пусть число процессоров р равно числу st блоков матрицы С. Тогда все блоки можно вычислять одновременно.

Рассмотрим специальные случаи разбиения s 1 матрица А разбита на группы столбцов t 1 матрица В разбита на группы строк s t 1 алгоритм блочного скалярного произведения r 1 алгоритм блочного внешнего произведения. Для блочного внешнего произведения распределение блоков по процессорам будет выглядеть следующим образом Для простоты будем считать, что матрицы А и В имеют размерность nn, nsm, где s число блоков, m число строк столбцов в блоке.

Далее, пусть умножение двух чисел происходит за время Tmul, а пересылка одного числа за время Tsend. Процесс вычисления состоит из трех этапов пересылка исходных данных на каждый процессор вычисление произведения блоков пересылка результата. Пусть t1n время умножения матриц на одном процессоре, tpn время умножения матриц в системе из p s2 процессоров.

В случае последовательного алгоритма произведение матриц требует n3 операций умножения, пересылки данных не требуются. В случае параллельного алгоритма пересылка исходных данных выполняется за время 2nmTsend, умножение блоков за время m2nTmul, пересылка результата за время n2Tsend. Тогда Построим график Spn при p4 и при различных значениях отношения TsendTmul. При достаточно больших значениях n Т.е. получаем линейный прирост производительности при n. Совсем другая картина получается, если строить строить график Spn как функции от р при некотором фиксированном значении n. В этом случае Spn сначала резко возрастает до некоторого экстремального значения S Sp n, а затем начинает плавно убывать.

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

Оно находится из уравнения p 1 Решая уравнение, получим. Следует отметить, что при pp максимум эффективности Ep скорее всего не будет достигнут. Результаты эксперимента nt1n, секtpn, p2, секSpn10001069,195571,6461,87011001081,1 61784,3251,37812001870,029987,8691,89313 002367,8531293,3551,83114002966,3111618, 9871,83215003647,5151999,7831,8241600501 1,0642812,0821,782 1.3.