Умножение матрицы на вектор

Задача умножения матрицы на вектор определяется соотношениями

.

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

.

Как следует из выполняемых действий при умножении матрицы и вектора, параллельные способы решения задачи могут быть получены на основе параллельных алгоритмов суммирования (см. параграф 4.1). В данном разделе анализ способов распараллеливания будет дополнен рассмотрением вопросов организации параллельных вычислений в зависимости от количества доступных для использования процессоров. Кроме того, на примере задачи умножения матрицы на вектор будут обращено внимание на необходимость выбора наиболее подходящей топологии вычислительной системы (существующих коммуникацион­ных каналов между процессорами) для снижения затрат для организации межпроцессорного взаимодействия.

Достижение максимально возможного быстродействия ()

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

-       выполняемые при проведении вычислений операции умножения отдельных строк матрицы на вектор являются независимыми и могут быть выполнены параллельно;

-       умножение каждой строки на вектор включает независимые операции поэлементного умножения и тоже могут быть выполнены параллельно;

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

Таким образом, максимально необходимое количество процессоров определяется величиной

.

Использование такого количества процессоров может быть представлено следующим образом. Множество процессоров  разбивается на  групп

,

каждая из которых представляет набор процессоров для выполнения операции умножения отдельной строки матрицы на вектор. В начале вычислений на каждый процессор группы пересылаются элемент строки матрицы и соответствующий элемент вектора . Далее каждый процессор выполняет операцию умножения. Последующие затем вычисления выполняются по каскадной схеме суммирования. Для иллюстрации на рис. 4.5 приведена вычислительная схема для процессоров группы  при размерности матрицы .

Рис. 4.5. Вычислительная схема операции умножения строки матрицы на вектор

Оценка показателей эффективности алгоритма. Время выполнения параллельного алгоритма при использовании  процессоров определяется временем выполнения параллельной операции умножения и временем выполнения каскадной схемы

.

Как результат, показатели эффективности алгоритма определяются следующими соотношениями:

, ,

.

Выбор топологии вычислительной системы. Для рассматриваемой задачи умножения матрицы на вектор наиболее подходящими топологиями являются структуры, в которых обеспечивается быстрая передача данных (пути единичной длины) в каскадной схеме суммирования (см. рис. 4.5). Таковыми топологиями являются структура с полной системой связей (полный граф) и гиперкуб. Другие топологии приводят к возрастанию коммуникационного времени из-за удлинения маршрутов передачи данных. Так, при линейном упорядочивании процессоров с системой связей только с ближайшими соседями слева и справа (линейка или кольцо) для каскадной схемы длина пути передачи каждой получаемой частичной суммы на итерации , , является равной . Если принять, что передача данных по маршруту длины  в топологиях с линейной структурой требует выполнения  операций передачи данных, общее количество параллельных операций (суммарной длительности путей) передачи данных определяется величиной

(без учета передач данных для начальной загрузки процессоров).

Применение вычислительной системы с топологией в виде прямоугольной двумерной решетки размера   приводит к простой и наглядной интерпретации выполняемых вычислений (структура сети соответствует структуре обрабатываемых данных). Для такой топологии строки матрицы   наиболее целесообразно разместить по горизонталям решетки; в этом случае элементы вектора   должны быть разосланы по вертикалям вычислительной системы. Выполнение вычислений при таком размещении данных может осуществляться параллельно по строкам решетки; как результат, общее количество передач данных совпадает с результатами для линейки ().

Коммуникационные действия, выполняемые при решении поставленной задачи, состоят в передаче данных между парами процессоров МВС. Подробный анализ длительности реализации таких операций проведен в п. 3.3.

Рекомендации по реализации параллельного алгоритма. При реализации параллельного алгоритма целесообразно выделить начальный этап по загрузке используемых процессоров исходными данными. Наиболее просто такая инициализация обеспечивается при топологии вычислительной системы с топологией в виде полного графа (загрузка обеспечивается при помощи одной параллельной операции пересылки данных). При организации множества процессоров в виде гиперкуба может оказаться полезной двухуровневое управление процессом начальной загрузки, при которой центральный управляющий процессор обеспечивает рассылку строк матрицы и вектора к управляющим процессорам процессорных групп , , которые, в свою очередь, рассылают элементы строк матрицы и вектора по исполнительным процессорам. Для топологий в виде линейки или кольца требуется  последовательных операций передачи данных с последовательно убывающим объемом пересылаемых данных от   до   элементов.

Использование параллелизма среднего уровня ()

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

.

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

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

-       множество процессоров  разбивается на непересекающиеся процессорные группы

 ,

при этом группа , , состоит из  процессоров и используется для выполнения  итерации каскадного алгоритма (группа   применяется для реализации поэлементного умножения); общее количество процессоров ;

-       инициализация вычислений состоит в поэлементной загрузке процессоров группы  значениями 1 строки матрицы и вектора ; после начальной загрузки выполняется параллельная операция поэлементного умножения и последующей реализации обычной каскадной схемы суммирования;

-       при выполнении вычислений каждый раз после завершения операции поэлементного умножения осуществляется загрузка процессоров группы  элементами очередной строки матрицы и инициируется процесс вычислений для вновь загруженных данных.

В результате применения описанного алгоритма множество процессоров  реализует конвейер для выполнения операции умножения строки матрицы на вектор. На подобном конвейере одновременно могут находиться несколько отдельных строк матрицы на разных стадиях обработки. Так, например, после поэлементного умножения элементов первой строки и вектора  процессоры группы  будут выполнять первую итерацию каскадного алгоритма для первой строки матрицы, а процессоры группы  будут исполнять поэлементное умножение значений второй строки матрицы и т.д. Для иллюстрации на рис. 4.6 приведена ситуация процесса вычислений после 2 итераций конвейера при .

Рис. 4.6. Состояние конвейера для операции умножения строки матрицы на вектор после выполнения 2 итераций

Оценка показателей эффективности алгоритма. Умножение первой строки на вектор в соответствии с каскадной схемой будет завершено, как и обычно, после выполнения () параллельных операций. Для других же строк – в соответствии с конвейерной схемой организации вычислений - появление результатов умножения каждой очередной строки будет происходить после завершения каждой последующей итерации конвейера. Как результат, общее время выполнения операции умножения матрицы на вектор может быть выражено величиной

.

Данная оценка является несколько большей, чем время выполнения параллельного алгоритма, описанного в предыдущем пункте (), однако вновь предлагаемый способ требует меньшего количества передаваемых данных (вектор  пересылается только однократно). Кроме того, использование конвейерной схемы приводит к более раннему появлению части результатов вычислений (что может быть полезным в ряде ситуаций обработки данных).

Как результат, показатели эффективности алгоритма определяются соотношениями следующего вида:

, ,

.

Выбор топологии вычислительной системы. Целесообразная топология вычислительной системы полностью определяется вычислительной схемой – это полное бинарное дерево высотой . Количество передач данных при такой топологии сети определяется общим количеством итераций, выполняемых конвейером, т.е.

.

Инициализация вычислений начинается с листьев дерева, результаты суммирования накапливаются в корневом процессоре.

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

Организация параллельных вычислений при

Выбор параллельного способа вычислений. При использовании  процессоров для умножения матрицы   на вектор   может быть использован ранее уже рассмотренный в пособии параллельный алгоритм построчного умножения, при котором строки матрицы распределяются по процессорам построчно и каждый процессор реализует операцию умножения какой-либо отдельной строки матрицы  на вектор. Другой возможный способ организации параллельных вычислений может состоять в построении конвейерной схемы для операции умножения строки матрицы на вектор (скалярного произведения векторов) путем расположения всех имеющихся процессоров в виде линейной последовательности (линейки).

Подобная схема вычислений может быть определена следующим образом. Представим множество процессоров в виде линейной последовательности (см. рис. 4.7):

;

каждый процессор , , используется для умножения элементов  столбца матрицы и  элемента вектора . Выполнение вычислений на каждом процессоре , , состоит в следующем:

-       запрашивается очередной элемент  столбца матрицы;

-       выполняется умножение элементов  и ;

-       запрашивается результат вычислений   предшествующего процессора;

-       выполняется сложение значений ;

-       полученный результат  пересылается следующему процессору.

Рис. 4.7. Состояние линейного конвейера для операции умножения строки матрицы на вектор после выполнения двух итераций

При инициализации описанной схемы необходимо выполнить ряд дополнительных действий:

-       при выполнении первой итерации каждый процессор дополнительно запрашивает элемент вектора ;

-       для синхронизации вычислений (при выполнении очередной итерации схемы запрашивается результат вычисления предшествую­щего процессора) на этапе инициализации процессор , , выполняет () цикл ожидания.

Кроме того, для однородности описанной схемы для первого процессора , у которого нет предшествующего процессора, целесообразно ввести пустую операцию сложения ().

Для иллюстрации на рис. 4.7 показано состояние процесса вычислений после второй итерации конвейера при .

Оценка показателей эффективности алгоритма. Умножение первой строки на вектор в соответствии с описанной конвейерной схемой будет завершено после выполнения () параллельных операций. Результат умножения следующих строк будет происходить после завершения каждой очередной итерации конвейера (напомним, итерация каждого процессора включает выполнение операций умножения и сложения). Как результат, общее время выполнения операции умножения матрицы на вектор может быть выражено соотношением:

.

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

Показатели эффективности данной вычислительной схемы определяются соотношениями:

, ,

.

Выбор топологии вычислительной системы. Необходимая топология вычислительной системы для выполнения описанного алгоритма однозначно определяется предлагаемой вычислительной схемой – это линейно упорядоченное множество процессоров (линейка).

Использование ограниченного набора процессоров ()

Выбор параллельного способа вычислений. При уменьшении количества процессоров до величины  параллельная вычислительная схема умножения матрицы на вектор может быть получена в результате адаптации алгоритма построчного умножения. В этом случае каскадная схема суммирования результатов поэлементного умножения вырождается и операция умножения строки матрицы на вектор полностью выполняется на единственном процессоре. Получаемая при таком подходе вычислительная схема может быть конкретизирована следующим образом:

-       на каждый из имеющихся процессоров пересылается вектор  и  строк матрицы;

-       выполнение операции умножения строк матрица на вектор выполняется при помощи обычного последовательного алгоритма.

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

Оценка показателей эффективности алгоритма. Время выполнения параллельного алгоритма определяется оценкой

,

где величина  есть наибольшее количество строк, загружаемых на один процессор. С учетом данной оценки показатели эффективности предлагаемой вычислительной схемы имеют вид:

, .

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

,

и принимают, тем самым, максимально возможные значения.

Выбор топологии вычислительной системы. В соответствии с характером выполняемых межпроцессорных взаимодействий в предложенной вычислительной схеме в качестве возможной топологии МВС может служить организация процессоров в виде звезды (см. рис. 1.1). Управляющий процессор подобной топологии может использоваться для загрузки вычислительных процессоров исходными данными и для приема результатов выполненных вычислений.

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

Задача умножения матрицы на матрицу определяется соотношениями

.

(для простоты изложения материала будем предполагать, что перемножаемые матрицы  и  являются квадратными и имеют порядок ).

Анализ возможных способов параллельного выполнения данной задачи может быть проведен по аналогии с рассмотрением задачи умножения матрицы на вектор. Оставив подобный анализ для самостоятельного изучения, покажем на примере задачи матричного умножения использование нескольких общих подходов, позволяющих формировать параллельные способы решения сложных задач.

Макрооперационный анализ алгоритмов решения задач

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

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

Рис. 4.8. Вычислительная схема матричного умножения при использовании макроопераций умножения матрицы A на столбец матрицы B

Важно отметить, что процесс введения макроопераций может осуществляться поэтапно с последовательно возрастающим уровнем детализации используемых операций. Так, для задачи матричного умножения после построения графа вычислений на основе макроопераций умножения матрицы на вектор может быть выполнено рассмотрение каждой макрооперации как последовательности независимых операций скалярного произведения векторов и т.п. Подобная иерархическая декомпозиционная методика построения параллельных методов решения сложных задач является одной из основных в параллельном программировании и широко используется в практике.

Организация параллелизма на основе разделения данных

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

Пусть количество процессоров составляет , а количество строк и столбцов матрицы является кратным величине , т.е. . Представим исходные матрицы ,  и результирующую матрицу  в виде наборов прямоугольных блоков размера . Тогда операцию матричного умножения матриц  и  в блочном виде можно представить следующим образом:

,

где каждый блок  матрицы  определяется в соответствии с выражением

.

Информационный граф алгоритма умножения при подобном представлении матриц показан на рис. 4.9 (на рисунке представлен фрагмент графа для вычисления только одного блока матрицы ). При анализе этого графа можно обратить внимание на взаимную независимость вычислений блоков  матрицы . Как результат, возможный подход для параллельного выполнения вычислений может состоять в выделении для расчетов, связанных с получением отдельных блоков , разных процессоров. Применение подобного подхода позволяет получить многие эффективные параллельные методы умножения блочно-представленных матриц; один из алгоритмов данного класса рассматривается ниже.

Рис. 4.9. Информационный граф матричного умножения при блочном представлении матриц

Для организации параллельных вычислений предположим, что процессоры образуют логическую прямоугольную решетку размером  (обозначим через   процессор, располагаемый на пересечении  строки и  столбца решетки). Основные положения параллельного метода, известного как алгоритм Фокса (Fox) [15], состоят в следующем:

• каждый из процессоров решетки отвечает за вычисление одного блока матрицы ;

• в ходе вычислений на каждом из процессоров  располагается четыре матричных блока:

  • блок  матрицы , вычисляемый процессором;
  • блок  матрицы , размещенный в процессоре перед началом вычислений;
  • блоки ,  матриц  и , получаемые процессором в ходе выполнения вычислений;

Выполнение параллельного метода включает:

• этап инициализации, на котором на каждый процессор  передаются блоки ,  и обнуляются блоки   на всех процессорах;

• этап вычислений, на каждой итерации , которого выполняется:

  • для каждой строки , процессорной решетки блок  процессора  пересылается на все процессоры той же строки ; индекс , определяющий положение процессора  в строке, вычисляется по соотношению

    ,

    ( есть операция получения остатка от целого деления);

  • полученные в результаты пересылок блоки ,   каждого процессора   перемножаются и прибавляются к блоку

    ;

  • блоки  каждого процессора  пересылаются процессорам , являющимися соседями сверху в столбцах процессорной решетки (блоки процессоров из первой строки решетки пересылаются процессорам последней строки решетки).

Для пояснения приведенных правил параллельного метода на рис. 4.10 приведено состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений (для процессорной решетки ).

Приведенный параллельный метод матричного умножения приводит к равномерному распределению вычислительной нагрузки между процессорами

, .

Вместе с тем, блочное представление матриц приводит к некоторому повышению объема пересылаемых между процессорами данных - на этапе инициализации и на каждой итерации этапа вычислений на каждый процессор передается 2 блока данных общим объемом . Учитывая выполняемое количество итераций метода, объем пересылаемых данных для каждого процессора составляет величину

Рис. 4.10. Состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений

Объем пересылаемых данных может быть снижен, например, при использовании строкового (для ) и столбцового (для ) разбиения матриц, при котором справедлива оценка

.

Данные оценки показывают, что различие объемов пересылаемых данных

является не столь существенным и данное различие уменьшается при увеличении числа используемых процессоров.

С другой стороны, использование блочного представления матриц приводит к ряду положительных моментов. Так, при данном способе организации вычислений пересылка данных оказывается распределенной по времени и это может позволить совместить процессы передачи и обработки данных; блочная структура может быть использована для создания высокоэффективных методов слабо заполненных (разреженных) матриц. И главное – данный метод является примером широко распространенного способа организации параллельных вычислений, состоящего в распределении между процессорами обрабатываемых данных с учетом близости их расположения в содержательных постановках решаемых задач. Подобная идея, часто называемая в литературе геометрическим принципом распараллеливания, широко используется при разработке параллельных методов решения сложных задач, поскольку во многих случаях может приводить к значительному снижению потоков пересылаемых данных за счет локализации на процессорах существенно информационно-зависимых частей алгоритмов (в частности, подобный эффект может быть достигнут при численном решении дифференциальных уравнений в частных производных).