Теория и практика параллельных вычислений
Матричное умножение
Задача умножения матрицы на матрицу определяется соотношениями:
(для простоты изложения материала будем предполагать, что перемножаемые матрицы A и B являются квадратными и имеют порядок n?n). Как следует из приведенных соотношений, вычислительная сложность задачи является достаточно высокой (оценка количества выполняемых операций имеет порядок n3).
Основу возможности параллельных вычислений для матричного умножения составляет независимость расчетов для получения элементов сij результирующей матрицы C. Тем самым, все элементы матрицы C могут быть вычислены параллельно при наличии n2
процессоров, при этом на каждом процессоре будет располагаться по одной строке матрицы A и одному столбцу матрицы B. При меньшем количестве процессоров подобный подход приводит к ленточной схеме разбиения данных, когда на процессорах располагаются по несколько строк и столбцов (полос) исходных матриц.
Другой широко используемый подход для построения параллельных способов выполнения матричного умножения состоит в применении блочного представления матриц, при котором исходные матрицы A, B и результирующая матрица C рассматриваются в виде наборов блоков (как правило, квадратного вида некоторого размера m?m). Тогда операцию матричного умножения матриц A и B в блочном виде можно представить следующим образом:
где каждый блок Cij матрицы C определяется в соответствии с выражением:
Полученные блоки Cij также являются независимыми, и, как результат, возможный подход для параллельного выполнения вычислений может состоять в расчетах, связанных с получением отдельных блоков Cij, на разных процессорах. Применение подобного подхода позволяет получить многие эффективные параллельные методы умножения блочно-представленных матриц.
В системе ПараЛаб реализованы параллельный алгоритм умножения матриц при ленточной схеме разделения данных и два метода (алгоритмы Фокса и Кэннона) для блочно представленных матриц. Более полная информация об алгоритмах умножения матриц, реализованных в системе ПараЛаб, содержится в лекции 7.
