Эта задача является базовой макрооперацией для многих задач линейной алгебры.
В связи с тем, что число элементов матриц ещё долго будет значительно больше числа ЭМ в транспьютерной системе, необходимо осуществить распараллеливание процессов.
Рассмотрим основные принципы создания ветвей параллельных алгоритмов.
Принцип 1. Режим параллельной обработки должен применяться для тех задач, которые не могут быть реализованы достаточно эффективно ресурсами одной ЭМ.
Принцип 2. Параллельный алгоритм в первую очередь должен быть носителем «внутреннего» параллелизма решаемой задачи, а не архитектуры используемой вычислительной системы или известного для этой задачи последовательного алгоритма.
Принцип 3. Крупноблочный иерархический подход. При этом параллельный алгоритм строится из возможности более крупных и редко взаимодействующих блоков. Данный подход является важнейшим способом достижения требуемой эффективности параллельных алгоритмов, предназначенных для реализации на многомодульных системах.
При таком подходе схема последовательного метода (если она используется для распараллеливания) рассматривается как иерархическая структура, высший уровень которой – крупные блоки (сегменты), следующий уровень – подблоки крупных блоков и т.д., самый низкий уровень – операторы машинных команд.
Процесс распараллеливания начинается с самого высокого уровня; переход на следующий уровень происходит всегда, если не удалось достичь нужной степени распараллеливания (эффективности) на данном. В качестве блоков одного уровня иерархии удобно использовать циклические структуры одинаковой вложенности. Аналогично используется иерархия в структуре данных, когда построение параллельного алгоритма происходит в первую очередь на основе распределения по ветвям обрабатываемой информации, а не операторов последовательного алгоритма.
Принцип 4. Однородное распределение массивов и других структур данных по ветвям параллельного алгоритма – это основа для уменьшения времени, затрачиваемого на взаимодействие ветвей. При таком распределении имеют место:
- равенство объемов распределяемых частей массивов;
- соответствие нумерации распределяемых частей массивов нумерации ветвей;
- распределение массивов на части параллельными линиями (многомерных массивов – параллельными поверхностями);
- дублирование массивов или частей одинаковым образом.
С учетом перечисленных принципов распараллеливания, построение параллельного алгоритма начинаем с построения ветвей, выполняющих достаточно большое число операций между двумя межпроцессорными взаимодействия.
Пусть A[1:N, 1:M], B[1:M, 1:J] – матрицы больших размеров, произведение которых необходимо вычислить на системе, и пусть элементы результирующей матрицы C = A × B определяются по формуле .
Для распределения матриц по ветвям могут быть использованы горизонтальные, вертикальные, циклические горизонтальные, скошенные полосы, горизонтальные полосы с частичным дублированием, а также обычные блоки (клетки).
Рассмотрим следующие распределения: матрицу A распределим по ветвям горизонтальными полосами, а матрицу B – вертикальными полосами; кроме того в каждой ветви вводится рабочий массив W = max{N, M, J}, который может содержать любую строку или столбец.
Суть параллельных вычислений состоит в следующем: сначала первая ветвь передает первую строку матрицы A для других ветвей. После этого все ветви параллельно вычисляют элементы первой строки матрицы C. Затем то же повторяется со следующими строками первой ветви. Когда первая ветвь перешлет все свои строки, пересылками начинает заниматься вторая ветвь и т.д. до l. Результирующая матрица C получается распределенной вертикальными полосами. Если не строки матрицы A, а столбцы матрицы B, то C получается распределенной горизонтальными полосами.
Однако такая трактовка параллельного алгоритма поднимает вопрос об операции трансляционного обмена (который рассматривается как операция глобального взаимодействия). В данном случае эта операция представляет собой последовательность локальных взаимодействий, а основная сущность состоит в посылке данных в канал и получение данных из канала. Такая реализация канала и взаимодействий через него может быть различной, в частности, передающая ветвь сдвигает данные соседним ветвям и сразу переходит к вычислениям; ветви, получившие данные, ретранслируют их своим соседям (ещё не имеющим эти данные) и также сразу переходят к вычислениям, таким образом, данные доходят до самых дальних ветвей.
Рассмотрим простейшую схему умножения матриц.
Данные продвигаются таким образом, что aik встречает bik в машине (i,j). Эта схема даёт непосредственное представление об информационных потоках данных между «точками» (i,j) двумерного пространства.
Вычисление начинается в точке (1,1), которая передает значение a11 и b11 активизирует точки (1,2) и (2,1) соответственно. Указанные точки далее активизирует своих соседей снизу и справа и т.д. до точки (N,J). Каждая точка накапливает у себя значение cij.
Рассмотренную двумерную систему вычислений можно интерпретировать и на линейной подсистеме. И здесь возможны два варианта. Первый, соответствуют крупноблочному распараллеливанию, который мы рассматривали вначале. Второй – мелкоблочному распараллеливанию. В этом случае элементарные машины подсистемы образуют цепочку из J элементов, каждая i-ая машина (i = 1, …, J) содержит столбец i матрицы B. Значение матрицы A поэлементно и построчно поступают в машину слева, а затем ретранслируются в машину справа.
Этот вариант позволяет уменьшить число обращений к памяти, реализовать основные операции на быстрых регистрах и осуществлять обмен между ЭМ в рамках этих же регистров.
.
Данные продвигаются таким образом, что aik встречает bik в машине (i,j). Эта схема даёт непосредственное представление об информационных потоках данных между «точками» (i,j) двумерного пространства.