Постановка задачи
1) Реализовать последовательный алгоритм перемножения матриц.
2) Реализовать программу блочного умножения матриц Фокса.
3) Реализовать программу ленточного умножения матриц.
4) Рассчитать теоретическое ускорение и эффективность.
5) Провести набор тестов. Сравнить и сопоставить производительность трех алгоритмов.
Описание алгоритма и метод решения
1. Ленточный алгоритм
Алгоритм представляет собой итерационную процедуру, количество итераций которой совпадает с числом подзадач.
- На каждой итерации алгоритма каждая подзадача содержит по одинаковому количеству строк матрицы А и матрицы В
- При выполнении итерации проводится скалярное умножение содержащихся в подзадачах строк, что приводит к получению соответствующих элементов результирующей матрицы С
- По завершении вычислений в конце каждой итерации столбцы матрицы В должны быть переданы между подзадачами с тем, чтобы в каждой подзадаче оказались новые столбцы матрицы В и могли быть вычислены новые элементы матрицы C
- По завершении итераций строки собираются в единую матрицу C
При этом данная передача столбцов между подзадачами должна быть организована таким образом, чтобы после завершения итераций алгоритма в каждой подзадаче последовательно оказались все столбцы матрицы В.
2. Алгоритм Фокса
Пусть перемножаемые матрицы A и B имеют порядок n. Количество процессов является полноым квадратом, квадратный корень которого кратен n. В алгоритме Фокса матрицы разделяются среди процессов в виде клеток шахматной доски. При этом процессы рассматриваются как виртуальная двухмерная сетка, и каждому процессу назначена подматрица каждого множителя.
В конце работы полученные блоки собираются в единую матрицу.
Алгоритм состоит в следующем:
for(step = 0; step < q; step++)
{
* Выбрать подматрицу A в каждой строке
для всех процессов
* В каждой строке для всех процессов разослать
сетку подматриц, выбранную в этой строке для
других процессов в этой строки
* В каждом процессе, перемножить полученную подматрицу
A на подматрицу B, находящуюся в процессе
* В каждом процессе, отослать подматрицу B процессу,
расположенному выше. (Для процессов первой строки
отослать подматрицу в последнюю строку.)
}
Анализ эффективности
Примем за Ts - время работы последовательного алгоритма, за Tp - время работы параллельного алгоритма, за S - ускорение, за E - эффективность, за p – количество процессоров.
При применении последовательного алгоритма перемножения матриц число шагов имеет порядок O(n3).
Для параллельного алгоритма на каждой итерации каждый процессор выполняет умножение имеющихся на процессоре полос исходных матриц А и В (размерность каждой полосы составляет n/p, следовательно, общее количество выполняемых при этом умножении операций равно n3/p2). Поскольку число итераций алгоритма совпадает с количеством процессоров, сложность параллельного алгоритма без учета затрат на передачу данных может быть определена при помощи выражения:
Tp = (n3/p2) * p = n3/p.
Показатели ускорения и эффективности данного параллельного алгоритма можно записать как:
S = Ts/Tp = n3 / ( n3 / p) = p
E = n3 / [ ( n3 / p) * p] = 1
Полученные показатели являются идеальными. На практике же мы обычно получаем относительные показатели, которые с идеальными не совпадают из-за затрат на выполнение операций передачи данных между процессорами, служебных затарт и пр.
Оценим реальные показатели с учётом затрат на выполнение операций передачи данных между процессорами. С учетом числа и длительности выполняемых операций время выполнения вычислений параллельного алгоритма может быть оценено следующим образом:
Tp(calc) = [ n2 / p ] * [ 2 n - 1 ] * t,
где t - время выполнения одной элементарной скалярной операции.
Для оценки коммуникационной сложности параллельных вычислений будем предполагать, что все операции передачи данных между процессорами в ходе одной итерации алгоритма могут быть выполнены параллельно. Объем передаваемых данных между процессорами определяется размером полос и составляет n/p строк или столбцов длины n. Общее количество параллельных операций передачи сообщений на единицу меньше числа итераций алгоритма (на последней итерации передача данных не является обязательной). Тем самым, оценка трудоемкости выполняемых операций передачи данных может быть определена как:
Tp ( comm ) = ( p - 1 ) * ( a + w * n * ( n / p ) / b ),
где a - латентность, b - пропускная способность сети передачи данных, а w - размер элемента матрицы в байтах. Тогда
Tp = ( n2 / p ) * ( 2 n - 1 ) * t + ( p - 1 ) * ( a + w * n * ( n / p ) / b ).
Демонстрация
Ленточный алгоритм.
Алгоритм Фокса.
Результаты вычислительных экспериментов
Эксперименты
проводились на двухпроцессорном вычислительном узле на базе двухядерных
процессоров Intel Core
2 Duo E6550, 2.33 ГГц,
4 Гб RAM, под управлением операционной системы Microsoft Windows 7 Enterprise
2010. Разработка программ проводилась в среде Microsoft Visual Studio
2008, для компиляции использовался стандартный компилятор, предоставляемый
средой, с включенной полной оптимизацией.
Параметры
теоретических зависимостей в данной вычислительной системе имеют значения:
латентность a – 44 мкс; пропускная способность
b – 39,73 Мбайт/с и величина w равна 8 байт.
Умножение матрицы на матрицу при ленточном алгоритме
Порядок матрицы, элементы |
Последовательный алгоритм, секунды |
Ленточный алгоритм (проводился на oднoм процессe), секунды |
Ленточный алгоритм |
Теоретические результаты (проводился на 4х процессах) |
Практические результаты (проводился на 4х процессах) |
Tp, секунды |
Sp |
Tp, секунды |
Sp |
100 |
0,002701 |
0,002855 |
0,003494 |
1,919756 |
0,00162 |
1,000702 |
200 |
0,022318 |
0,023033 |
0,027516 |
1,963886 |
0,007307 |
1,732726 |
400 |
0,295446 |
0,301225 |
0,218806 |
1,982404 |
0,048931 |
3,888782 |
800 |
3,312004 |
3,862941 |
1,745563 |
1,991245 |
0,306079 |
7,186375 |
1600 |
35,241822 |
35,456047 |
13,945395 |
1,995624 |
5,080979 |
5,403332 |
2000 |
71,548384 |
71,587075 |
27,229668 |
1,996498 |
10,112401 |
5,50228 |
Умножение матрицы на матрицу методом Фокса
Порядок матрицы, элементы |
Последовательный алгоритм, секунды |
Алгоритм Фокса (проводился на oднoм процессe), секунды |
Алгоритм Фокса |
Теоретические результаты (проводился на 4х процессах) |
Практические результаты (проводился на 4х процессах) |
Tp, секунды |
Sp |
Tp, секунды |
Sp |
100 |
0,002701 |
0,003079 |
0,003524 |
1,936492 |
0,002011 |
0,806251 |
200 |
0,022318 |
0,019891 |
0,027631 |
1,972067 |
0,009824 |
1,288783 |
400 |
0,295446 |
0,302998 |
0,219257 |
1,986493 |
5,051228 |
0,03767 |
800 |
3,312004 |
3,424989 |
1,747361 |
1,993296 |
0,915809 |
2,401807 |
1600 |
35,241822 |
35,503525 |
13,952579 |
1,996652 |
14,02866 |
1,957009 |
2000 |
71,548384 |
71,971157 |
27,240892 |
1,997321 |
27,180319 |
2,047116 |
Об автораx
Лабораторную работу выполнили студенты группы 8409 факультета ВМК: Неумоина Татьяна и Васяев Александр
