Постановка задачи
1) Реализовать последовательный алгоритм перемножения матриц.
2) Реализовать программу блочного умножения матриц (Алгоритм Фокса), используя технологию MPI.
3) Провести расчет теоретического ускорения и эффективности.
4) Провести ряд тестов. Сравнить ускорение параллельного и не параллельного алгоритма.
Последовательный алгоритм.
Последовательный алгоритм умножения матриц представляется тремя вложенными циклами:
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×n, количество блоков по горизонтали и вертикали одинаково и равно q (т.е. размер всех блоков равен k×k, k=n/q). При таком представлении данных операция матричного умножения матриц А и B в блочном виде может быть представлена так:
,где каждый блок результирующей матрицы С определяется по формуле
За основу параллельных вычислений для матричного умножения при блочном разделении данных принят подход, при котором базовые подзадачи отвечают за вычисления отдельных блоков матрицы C и при этом в подзадачах на каждой итерации расчетов располагается только по одному блоку исходных матриц A и B. Для нумерации подзадач будем использовать индексы размещаемых в подзадачах блоков матрицы C, т.е. подзадача (i,j) отвечает за вычисление блока Cij – тем самым, набор подзадач образует квадратную решетку, соответствующую структуре блочного представления матрицы C.
В соответствии с алгоритмом Фокса в ходе вычислений на каждой базовой подзадаче (i,j) располагается четыре матричных блока:
1. Блок Cij матрицы C, вычисляемый подзадачей;
2. Блок Aij матрицы A, размещаемый в подзадаче перед началом вычислений;
3. Блоки A'ij , B'ij матриц A и B, получаемые подзадачей в ходе выполнения вычислений.
Выполнение параллельного метода включает:
1. Этап инициализации, на котором каждой подзадаче (i,j) передаются блоки Aij, Bij и обнуляются блоки Cij на всех подзадачах;
2. Этап вычислений, в рамках которого на каждой итерации l, l от нуля (включительно) до q, осуществляются следующие операции:
a. Для каждой строки i (i от нуля включительно и строго до q) блок Aij подзадачи (i,j) пересылается на все подзадачи той же строки i решетки; индекс j, определяющий положение подзадачи в строке, вычисляется в соответствии с выражением j=(i+l)mod q, где mod есть операция получения остатка от целочисленного деления;
b. Полученные в результаты пересылок блоки A'ij, B'ij каждой подзадачи (i,j) перемножаются и прибавляются к блоку Cij
c. Блоки B'ij каждой подзадачи (i,j) пересылаются подзадачам, являющимся соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).
Анализ эффективности
Все матрицы являются квадратными размера n×n, количество блоков по горизонтали и вертикали являются одинаковым и равным q (т.е. размер всех блоков равен k×k, k=n/q), процессоры образуют квадратную решетку и их количество равно p=q2.
Алгоритм Фокса требует для своего выполнения q итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц А и В и прибавляет результаты умножения к текущему значению блока матрицы C. С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок n3/p. Как результат, показатели ускорения и эффективности алгоритма имеют вид:
Общий анализ сложности дает идеальные показатели эффективности параллельных вычислений. Уточним полученные соотношения — для этого укажем более точно количество вычислительных операций алгоритма и учтем затраты на выполнение операций передачи данных между процессорами.
Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы A на столбец блока матрицы В можно оценить как 2(n/q)-1. Количество строк и столбцов в блоках равно n/q и, как результат, трудоемкость операции блочного умножения оказывается равной (n2/p)(2n/q-1). Для сложения блоков требуется n2/p операций. С учетом всех перечисленных выражений время выполнения вычислительных операций алгоритма Фокса может быть оценено следующим образом:
Примечание: τ есть время выполнения одной элементарной скалярной операции.
Общее время выполнения алгоритма Фокса может быть определено при помощи следующих соотношений:
Примечание: Параметр q определяет размер процессорной решетки и q=sqrt(p)
Результаты вычислительных экспериментов
Эксперименты
проводились на четырехядерном процессоре Intel Core 2 Quad Q6600, 2.4 Ghz,
4 Гб RAM, под управлением операционной системы Microsoft Windows 7 Enterprise
2010. Разработка программ проводилась в среде Microsoft Visual Studio
2008, для компиляции использовался стандартный компилятор, предоставляемый
средой, с включенной полной оптимизацией.
Параметры
теоретических зависимостей в данной вычислительной системе имеют значения:
латентность a – 44 мкс; пропускная способность
b – 39,73 Мбайт/с и величина w равна 8 байт.
Порядок матрицы, n x n |
Последовательный алгоритм, с |
Параллельный алгоритм (практические результаты, 4 процесса), с |
Параллельный алгоритм (теоретические результаты, 4 процесса), с |
Ускорение |
100 |
0,015113 |
0,014062 |
0,018540 |
1,014253 |
200 |
0,081213 |
0,037576 |
0.028956 |
2,198204 |
400 |
0,816583 |
0,212274 |
0.194320 |
3,837934 |
1000 |
19,594463 |
4,774127 |
3,957080 |
4,073012 |
2000 |
161,333884 |
56,22347 |
47,00741 |
2,888426 |
4000 |
1234,596841 |
347,830344 |
301.3056 |
3,559235 |
Об автораx
Лабораторную работу выполнил студент группы 8303 факультета ВМК: Филиппенко Станислав Сергеевич
|