Постановка задачи
1. Реализовать последовательный алгоритм перемножения матриц.
2. Реализовать программу ленточного умножения матриц.
3. Провести набор тестов. Сравнить и сопоставить производительность двух алгоритмов.
Ленточный алгоритм
Алгоритм представляет собой итерационную процедуру, количество итераций которой совпадает с числом подзадач.
• На каждой итерации алгоритма каждая подзадача содержит по одинаковому количеству строк матрицы А и матрицы В.
• При выполнении итерации проводится скалярное умножение содержащихся в подзадачах строк, что приводит к получению соответствующих элементов результирующей матрицы С.
• По завершении вычислений в конце каждой итерации столбцы матрицы В должны быть переданы между подзадачами с тем, чтобы в каждой подзадаче оказались новые столбцы матрицы В и могли быть вычислены новые элементы матрицы C.
• По завершении итераций строки собираются в единую матрицу C.
При этом данная передача столбцов между подзадачами должна быть организована таким образом, чтобы после завершения итераций алгоритма в каждой подзадаче последовательно оказались все столбцы матрицы В.
Анализ эффективности
Для анализа будем использовать следующие показатели:
T1 - оценка трудоемкости решения задачи на одном процессоре.
Tp(calc) - оценка трудоемкости решения задачи на p процессорах.
Tp(comm) - оценка трудоемкости выполняемых операций передачи данных.
S - ускорение. Ускорение определяется из отношения: S=T1/(Tp(calc)+Tp(comm))
Оценка трудоемкости последовательного алгоритма: T1=n^3
Оценка трудоемкости параллельного алгоритма: Tp(calc)=(n^3)/p
Оценка трудоемкости выполняемых операций передачи данных: Tp(comm)=(p−1)*(a+w*n*(n/p)/b), где a – латентность, b – пропускная способность сети передачи данных, а w есть размер элемента матрицы в байтах.
Ускорение: s=(n^3)/((n^3)/p+(p-1)*(a+w*n*(n/p)/b))
Результаты
Эксперимент проводился на следующем ПК:
Intel Core 2 Duo E8500, Up to 3.16 MHz
Microsoft Windows Vista Ultimate x64
Компилятор MS Visual Studio 2005
Пропускная способность: 267506473 байт/сек
Латентность: 0.000024 сек
Время, затрачиваемое на одну операцию: ~31 нс
Размер матрицы |
Последовательный алгоритм |
Последовательный алгоритм(теоретическое время) |
Параллельный алгоритм(4 потока) |
Параллельный алгоритм(4 потока)(теоретическое время) |
Ускорение |
Ускорение(теоретическое) |
100 |
0.012691 |
0,006766 |
0.007269 |
0,003494 |
1.745876 |
1,919756 |
200 |
0.060255 |
0,054264 |
0.035815 |
0,027516 |
1.682375 |
1,963886 |
300 |
0.204928 |
0,183294 |
0.135160 |
0,092487 |
1.516183 |
1,97639 |
400 |
0.480475 |
0,434656 |
0.301263 |
0,218806 |
1.594870 |
1,982404 |
500 |
0.949451 |
0,84915 |
0.628690 |
0,426873 |
1.510204 |
1,98596 |
600 |
1.631549 |
1,467576 |
0.940577 |
0,737088 |
1.734625 |
1,988315 |
700 |
2.596448 |
2,330734 |
1.732621 |
1,169852 |
1.4985675 |
1,98999 |
800 |
3.873000 |
3,479424 |
2.355052 |
1,745563 |
1.644550 |
1,991245 |
900 |
5.717707 |
4,954446 |
3.400358 |
2,484624 |
1.681501 |
1,992219 |
1000 |
7.902827 |
6,7966 |
4.835743 |
3,407432 |
1.634253 |
1,992998 |
Размер матрицы |
Последовательный алгоритм |
Параллельный алгоритм(2 потока) |
Ускорение |
100 |
0.007497 |
0.004711 |
1.591361 |
200 |
0.060409 |
0.049961 |
1.209127 |
300 |
0.201906 |
0.137908 |
1.464065 |
400 |
0.480734 |
0.309894 |
1.551284 |
500 |
0.943268 |
0.599591 |
1.573185 |
600 |
1.631433 |
1.037070 |
1.573118 |
700 |
2.593723 |
1.627808 |
1.593384 |
800 |
3.868340 |
2.453623 |
1.576583 |
900 |
5.610638 |
3.527647 |
1.590476 |
1000 |
7.603838 |
4.847480 |
1.568617 |
Размер матрицы |
Последовательный алгоритм |
Параллельный алгоритм(1 поток) |
100 |
0.011897 |
0.014926 |
200 |
0.060766 |
0.093259 |
300 |
0.201848 |
0.252131 |
400 |
0.479810 |
0.609116 |
500 |
0.936974 |
1.165074 |
600 |
1.618121 |
2.007215 |
700 |
2.567468 |
3.196951 |
800 |
3.842222 |
4.781128 |
900 |
5.536666 |
6.877959 |
1000 |
7.638913 |
9.476469 |
Автор: Удалова Татьяна 8409
