task3 (практическая работа (3))

Асирян Александр, 428 группаПостановка задачиРазработать параллельный алгоритм и исследовать его эффективность для задачи умноженияматрицы на матрицу. Тип данных – double. Размер матриц – mxm.Описание алгоритмаИспользуется алгоритм Кэннона: матрицы распределяются блоками, при инициализации (Cij = 0)и при основной работе алгоритма процесс (i, j) сдвигает свой блок матрицы A на (i – 1) позицийвлево, а блок матрицы B – на (j - 1) позиций вверх по решетке процессов (без явного участияпромежуточных узлов в передаче – MPI_Sendrecv_replace()). После инициализации каждыйпроцесс (i, j) вычисляет Cij += Aij * Bij, Эти умножения/пересылки осуществляются sqrt(p) раз, гдеp – количество процессов в решетке.

Размер блока – l = m / sqrt(p). Матрицы генерируютсяслучайным образом. Формат файла следующий:A[0][0]A[0][1]A[0][2]A[0][3]…A[0][l-1]B[0][0]B[1][0]B[2][0]B[3][0]…B[l-1][0]A[1][0]A[1][1]A[1][2]A[1][3]…A[1][l-1]B[0][1]B[1][1]B[2][1]B[3][1]…B[l-1][1]…A[l-1][0]A[l-1][1]A[l-1][2]A[l-1][3]…A[l-1][l-1]B[0][l-1]B[1][l-1]B[2][l-1]B[3][l-1]…B[l-1][l-1], и таких блоков p штук. Каждый процесс в решетке в зависимости от своих координатустанавливает курсор в нужную позицию и читает данные.

По завершении вычислений всепроцессы пишут свои блоки в результирующий файл построчно, т.е. в первой строке – блокнулевого процесса, во второй – первого, и т.д. Барьерная синхронизация на каждом шаге записине позволяет получить монопольный доступ по записи более чем одному процессу в одинмомент времени.Запуск на выполнение:<…> ./task3 <m> <file_out> <file_int> <file_ext>, либо<…> ./task3 <m> <file_out> <file_int>в зависимости от установленного флага (SAVERESULT) в программе.1.

save = 0 – не сохранять результат работы в файл, будет выведена только информация овремени выполнения вычислений.2. save = 1 – сохранение результата работы в файл <file_out>.3. gen = 0 – не генерировать файлы входных данных. Предполагается, что существует файл<file_int> в соответствующем формате, откуда процесс считает данные.4. gen = 1 – генерация файлов с бинарными данными (случайным образом).

Приактивированном флаге save помимо файла с бинарными данными будет создан файл,удобный для просмотра, а сам файл с бинарными данными будет удален послезавершения программы.В программе – gen = 1, save = 1. По умолчанию, в стандартный поток вывода печатается времясчета каждого процесса, а также время генерации и сохранения в файл данных.m – размер матриц;file_out – имя выходного файла с результатом умножения;file_int – имя файла с бинарными данными (будет создан при выполнении программы);file_ext – имя файла с преобразованными в понятное представление бинарными данными.РезультатыBlue Gene/PЗапуск на выполнение:mpisubmit.bg -n <…> -mode=SMP -env OMP_NUM_THREADS=4 ./task3 …Время, сВремя выполнения450,0400,0350,0300,0250,0200,0150,0100,050,00,0304608121624321 узел0,7861866,15348847,761434381,2998314 узла0,0928571,64805612,37161095,76297216 узлов0,0276780,1808613,17764324,71847064 узла0,2319990,1938050,4227326,567628256 узлов0,5779290,4902791,3686351,177164Коэффициент ускорения1 узел4 узла16 узлов64 узла256 узловУскорение350,0300,0250,0200,0150,0100,050,00,01 узел4 узла16 узлов3041,0000008,46663128,4047263,3887471,3603506081,0000003,73378634,02330031,75092512,55099212161,0000003,86056715,030459112,98277434,89713024321,0000003,98170415,42570558,057465323,913941304608121664 узла2432256 узловКоэффициент эффективностиЭффективность2,252,132,001,881,751,631,501,381,251,131,000,880,750,630,500,380,250,130,001 узел4 узла16 узлов64 узла256 узлов3041,0000002,1166581,7752950,0529490,0053146081,0000000,9334472,1264560,4961080,04902712161,0000000,9651420,9394041,7653560,13631724321,0000000,9954260,9641070,9071481,26528930460812162432ВыводыT(n, p) ~ T(k2n, k2p)Blue Gene/PT(304, 1) = 0,786186 ~ 12,371610 = T(1216, 4)T(608, 1) = 6,153488 ~ 95,762972 = T(2432, 4)T(304, 4) = 0,092857 ~ 3,177643 = T(1216, 16)T(608, 4) = 1,648056 ~ 24,718470 = T(2432, 16)T(304, 16) = 0,027678 ~ 0,422732 = T(1216, 64)T(608, 16) = 0,180861 ~ 6,567628 = T(2432, 64)T(304, 64) = 0,231999 ~ 1,368635 = T(1216, 256)T(608, 64) = 0,193805 ~ 1,177164 = T(2432, 256)Алгоритм является масштабируемым только при достаточно больших размерах матриц, т.к.

наменьших размерах накладные расходы, связанные с пересылкой данных, значительнопревышают полезное время. Время выполнения программы при пропорциональномувеличении размера матрицы и количества процессоров изменяется все меньше и меньше(6,567628 / 0,180861 ~ 36,3 раз; 1,177164 / 0,193805 ~ 6,1 раз). Также ускорение растет приповышении размера матриц и почти не меняется при увеличении количества узлов..