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

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

Последовательный алгоритм

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

void LinearMatrixMultiplication( const double* A, const double* B, double* C, int size)

{

    for (int i=0; i < size; i++)

    {
       for (int j=0; j

       {
          C[i*size+j]=0;
          for (int k=0; k

          {
             C[i*size+j] += A[i*size+k]*B[j*size+k];
          }
    }
}

Этот алгоритм является итеративным и ориентирован на последовательное вычисление строк матрицы С. Предполагается выполнение n·n·n операций умножения и столько же операций сложения элементов исходных матриц. Количество выполненных операций имеет порядок O(n^3). 

Поскольку каждый элемент результирующей матрицы есть скалярное произведение строки и столбца исходных матриц, то для вычисления всех элементов матрицы С размером n*n необходимо выполнить (n^2)*(2n-1) скалярных операций и затратить время T1 = (n^2)*(2n-1)*t, где t есть время выполнения одной элементарной скалярной операции.

Из определения операции матричного умножения следует, что вычисление всех элементов матрицы С может быть выполнено независимо друг от друга. Как результат, возможный подход для организации параллельных вычислений состоит в использовании в качестве базовой подзадачи процедуры определения одного элемента результирующей матрицы С. Для проведения всех необходимых вычислений каждая подзадача должна содержать по одной строке матрицы А и одному столбцу матрицы В. Общее количество получаемых при таком подходе подзадач оказывается равным n² (по числу элементов матрицы С).

Алгоритм представляет собой итерационную процедуру, количество итераций которой совпадает с числом подзадач. На каждой итерации алгоритма каждая подзадача содержит по одной строке матрицы А и одному столбцу матрицы В. При выполнении итерации проводится скалярное умножение содержащихся в подзадачах строк и столбцов, что приводит к получению соответствующих элементов результирующей матрицы С. По завершении вычислений в конце каждой итерации столбцы матрицы В должны быть переданы между подзадачами с тем, чтобы в каждой подзадаче оказались новые столбцы матрицы В и могли быть вычислены новые элементы матрицы C. При этом данная передача столбцов между подзадачами должна быть организована таким образом, чтобы после завершения итераций алгоритма в каждой подзадаче последовательно оказались все столбцы матрицы В.
Выделенные базовые подзадачи характеризуются одинаковой вычислительной трудоемкостью и равным объемом передаваемых данных. Когда размер матриц n оказывается больше, чем число процессоров p, базовые подзадачи можно укрупнить, объединив в рамках одной подзадачи несколько соседних строк и столбцов перемножаемых матриц. В этом случае исходная матрица A разбивается на ряд горизонтальных полос, а матрица B представляется в виде набора вертикальных полос. Размер полос при этом следует выбрать равным k=n/p (в предположении, что n кратно p), что позволит по-прежнему обеспечить равномерность распределения вычислительной нагрузки по процессорам, составляющим многопроцессорную вычислительную систему.

Пусть Ts - время работы последовательного алгоитма, Tp - время работы параллельного алгоитма, A - ускорение, E - эффективность. Общая трудоемкость последовательного алгоритма пропорциональна n^3. Для параллельного алгоритма на каждой итерации каждый процессор выполняет умножение имеющихся на процессоре полос матриц А и В (размер полос равен n/p, следовательно, общее количество выполняемых при этом умножении операций равно n^3/p^2). Поскольку число итераций алгоритма совпадает с количеством процессоров, сложность параллельного алгоритма без учета затрат на передачу данных может быть определена при помощи выражения Tp=(n^3/p^2)*p=n^3/p Так как A=Ts/Tp, то: A=(n^3)/((n^3)/p)=p E=(n^3)/[((n^3)/p)*p]=1 Мы получили идеальные показатели эффективности, но на практике это не всегда выполняется. Для уточнения полученных соотношений оценим более точно количество вычислительных операций алгоритма и учтем затраты на выполнение операций передачи данных между процессорами. С учетом числа и длительности выполняемых операций время выполнения вычислений параллельного алгоритма может быть оценено следующим образом: Tp(calc)=[(n^2)/p]*[2n-1]*t t - время выполнения одной элементарной скалярной операции Для оценки коммуникационной сложности параллельных вычислений будем предполагать, что все операции передачи данных между процессорами в ходе одной итерации алгоритма могут быть выполнены параллельно. Объем передаваемых данных между процессорами определяется размером полос и составляет n/p строк или столбцов длины n. Общее количество параллельных операций передачи сообщений на единицу меньше числа итераций алгоритма (на последней итерации передача данных не является обязательной). Тем самым, оценка трудоемкости выполняемых операций передачи данных может быть определена как Tp(comm)=(p-1)*(a+w*n*(n/p)/b) a - латентность, b - пропускная способность сети передачи данных, а w - размер элемента матрицы в байтах. Тогда Tp=(n^2/p)(2n-1)*t+(p-1)*(a+w*n*(n/p)/b)