3. Задания и упражнения:

3.1. Напишите и отладьте программу умножения матрицы на вектор.

3.2. Элементы матрицы и векторадолжны определяться по формулам

,

, ,

где - номер варианта,- размерность матрицы.

3.3. Заполните таблицу:

Размер	Последовательный алгоритм	Параллельный алгоритм
		2 процесса		4 процесса
		Время	Ускорение	Время	Ускорение
10
100
1000
2000
5000
10000

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

Лабораторная работа 6.

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

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

1. Постановка задачи.

Умножение матрицы A размера n×m и матрицы B размера m×l приводит к получению матрицы С размера n×l, каждый элемент которой определяется в соответствии с выражением

, ,.

Этот алгоритм предполагает выполнение m×n×l операций умножения и столько же операций сложения элементов исходных матриц. При умножении квадратных матриц размера n количество выполненных операций имеет порядок .

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

double MatrixA[Size][Size];

double MatrixB[Size][Size];

double MatrixC[Size][Size];

int i,j,k;

...

for (i=0; i<Size; i++){

for (j=0; j<Size; j++){

MatrixC[i][j] = 0;

for (k=0; k<Size; k++){

MatrixC[i][j] = MatrixC[i][j] + MatrixA[i][k]*MatrixB[k][j];

}

}

}

Рисунок 6.1 – Последовательный алгоритм умножения матриц.

2. Умножение матриц при ленточной схеме разделения данных.

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

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

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

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

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

Возможная простая схема организации необходимой последовательности передач столбцов матрицы В между подзадачами состоит в представлении топологии информационных связей подзадач в виде кольцевой структуры. В этом случае, на каждой итерации подзадача i, 0 ≤ i < n, будет передавать свой столбец матрицы В подзадаче с номером i+1 (в соответствии с кольцевой структурой подзадача n-1 передает свои данные подзадаче с номером 0) – см. рис. 6.2. После выполнения всех итераций алгоритма необходимое условие будет обеспечено – в каждой подзадаче поочередно окажутся все столбцы матрицы В.

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