Теория и практика параллельных вычислений



         

Выделение информационных зависимостей - часть 2


Далее выполнение описанных действий повторяется до завершения всех итераций параллельного алгоритма.


Рис. 7.2.  Общая схема передачи даных для первого параллельного алгоритма матвичного умножения при ленточной схеме разделения данных

2. Второй алгоритм. Отличие второго алгоритма состоит в том, что в подзадачах располагаются не столбцы, а строки матрицы B. Как результат, перемножение данных каждой подзадачи сводится не к скалярному умножению имеющихся векторов, а к их поэлементному умножению. В результате подобного умножения в каждой подзадаче получается строка частичных результатов для матрицы C.

При рассмотренном способе разделения данных для выполнения операции матричного умножения нужно обеспечить последовательное получение в подзадачах всех строк матрицы B, поэлементное умножение данных и суммирование вновь получаемых значений с ранее вычисленными результатами. Организация необходимой последовательности передач строк матрицы B между подзадачами также может быть выполнена с использованием кольцевой структуры информационных связей (см. рис. 7.3).

На рис. 7.3 представлены итерации алгоритма матричного умножения для случая, когда матрицы состоят из четырех строк и четырех столбцов (n=4). В начале вычислений в каждой подзадаче i, 0i<n, располагаются i-е строки матрицы A и матрицы B. В результате их перемножения подзадача определяет i-ю строку частичных результатов искомой матрицы C. Далее подзадачи осуществляют обмен строками, в ходе которого каждая подзадача передает свою строку матрицы B следующей подзадаче в соответствии с кольцевой структурой информационных взаимодействий. Далее выполнение описанных действий повторяется до завершения всех итераций параллельного алгоритма.


Рис. 7.3.  Общая схема передачи данных для второго параллельного алгорится матричного умножения при ленточной схеме разделения данных




Содержание  Назад  Вперед