Описание алгоритма:

Первый вычислитель рассылает всем остальным вычислителям первую строку из своей полосы матрицы A. После этого каждый из вычислителей рассчитывает ]M/n[ элементов первой троки своей полосы для результирующей матрицы C. Затем первый вычислитель рассылает во все остальные вычислители вторую строку своей полосы матрицы A и производятся вычисления элементов второй строки матрицы C и так до тех пор, пока первый вычислитель не перешлёт все строки своей части матрицы А. После этого пересылками будут заниматься последовательно второй вычислитель, третий и далее до n-го вычислителя. Матрицы С получается распределённой по вычислителям, причём в каждом будет своя вертикальная полоса. При этом стоит учитывать, что в результирующую матрицу C не должны включаться n]N/n[-N последний строк из полученных вертикальных полос любого вычислителя, а так же n]M/n[-M последних столбцов из полосы n-го вычислителя. Далее идёт взаимодействие вычислителей.

Схема l-й ветви P-алгоритма, реализуемая на вычислителе с номером l, 1≤ l ≤ n :

Нахождение максимума коэффициента накладных расходов при реализации р-алгаритма на вс Минск-222.

Известно

время пересылки элементов матрицы t_п= 50 мкс.

время выполнения операции умножения t_у= 360 мкс.

время выполнения операции сложения t_с= 220 мкс.

Коэффициент накладных расходов рассчитывается по формуле:

=t/T

где t - время, расходуемое на обмен информацией;

T - время, расходуемое на вычисление логических операций;

В соответствии с алгоритмом при пересылки строки матрицы В, состоящей из K – элементов, в каждом вычислители производится K*]M/n[ - операций умножения и (K-1)*]M/n[ - операций сложения.

Так как используется матрицы с большой размерностью, т.е. K>>n,

cледовательно можно считать, что после пересылки одного элемента из любого вычислителя во все остальные вычислители производится ρ=]M/n[ - операций сложения и умножения.

Получаем:

=t_п/(ρ*(t_с+t_у))

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

Итак, максимум коэффициента накладных расходов достигается при ρ=1.

Подставим, известные численные значения в формулу:

Ответ: Максимум коэффициента накладных расходов равен мкс.