Новости
О Центре
Кластер
Обучение
Основной курс по параллельному программированию
Учебные курсы
Магистратура
Дополнительное образование
Работы студентов
Библиотека
Исследования
Конференции
Полезные ссылки
NVIDIA
Контакты
О сайте
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Перемножение матриц (Алгоритм Фокса)

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

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 факультета ВМК: Филиппенко Станислав Сергеевич

Новости

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012