Основные характеристики Z4

Разработать блок-схему -алгоритма умножения матриц большого размера, обеспечивающего распределение в элементарных машинах ВС результирующей матрицы по горизонтальным полосам. Определить максимум коэффициента накладных расходов при реализации -алгоритма для ВС “Минск-222”.

Элементы матрицы С вычисляются по формуле –

к

c_ij = ∑ a_ih b_hj

h=1

Алгоритм умножения матриц должен быть построен так, что бы каждый вычислитель рассчитывал свой элемент матрицы С.

Для построения алгоритма требуется распределить по вычислителям элемент матриц А и В, требуется однородное распределение, так как оно обеспечивает однородную нагрузку на вычислители.

Для однородного распределения можно поступить так:

матрицу А нужно разделить на n одинаковых горизонтальных полос (где n – количество вычислителей в системе) и каждая полоса размещается в своем вычислителе. Матрицу В следует разделить на n вертикальных полос полос. В первом вычислителе можно разместить:

матрицы А размещены строки: 1,2,…,]N/n[

матрицы В помещены столбцы: 1,2,…,]M/n[

а следовательно, в l -ом вычислителе матрицы

А: (l-1)]N/n[+1,(l-1)]N/n[+2,…,l]N/n[ строки.

В: (l-1)]M/n[+1,(l-1)]M/n[+2,…,l]M/n[ столбцы.

При однородном распределении информации может быть построен алгоритм с идентичными ветвями.

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

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

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

Вычисление

Не нашли, что искали? Воспользуйтесь поиском: