task4 (практическая работа (4))

Асирян Александр, 428 группаПостановка задачиРазработать параллельный алгоритм и исследовать его эффективность для задачиумножения матрицы на матрицу. Тип данных – double. Размер матриц – mxm.Описание алгоритмаИспользуется алгоритм Фокса: матрицы распределяются блоками, при инициализации (Cij= 0) и при основной работе алгоритма процесс (i, j) пересылает свой блок матрицы Aij всемпроцессам той же строки решетки (MPI_Bcast()), а блок матрицы Bij – всем процессам тогоже столбца решетки (MPI_Sendrecv_replace()), т.е.

диагональные блоки Aii пересылаютсявсем процессам i-той строки, а блоки Bij просто циклически пересылаются в каждомстолбце решетки процессов. После инициализации каждый процесс (i, j) вычисляет Cij += Aij* Bij, Эти умножения/пересылки осуществляются sqrt(p) раз, где p – количество процессовв решетке. Размер блока – l = m / sqrt(p), 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 штук.

Каждый процесс в решетке в зависимости от своих координатустанавливает курсор в нужную позицию и читает данные. По завершении вычислений всепроцессы пишут свои блоки в результирующий файл построчно, т.е. в первой строке – блокнулевого процесса, во второй – первого, и т.д. Барьерная синхронизация на каждом шагезаписи не позволяет получить монопольный доступ по записи более чем одному процессув один момент времени.Запуск на выполнение:<…> ./task4 <m> <file_out> <file_int> <file_ext>, либо<…> ./task4 <m> <file_out> <file_int>в зависимости от установленного флага (save) в программе.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Строка компиляции: mpicc -fomit-frame-pointer -fno-zero-initialized-in-bss -funsafe-loop-optimizations -ffastmath -O3 -funroll-all-loops -o task4 task4.cВремя, сВремя выполнения450,0400,0350,0300,0250,0200,0150,0100,050,00,0304608121624321 узел0,8139056,15413847,763568381,3161824 узла0,0916131,64623012,35445195,71211016 узлов0,0475340,1868713,31340124,71652264 узла0,3492510,3951761,0798056,903593256 узлов0,5680760,8849040,9689730,886240Коэффициент ускорения1 узел4 узла16 узлов64 узла256 узловУскорение500,0450,0400,0350,0300,0250,0200,0150,0100,050,00,01 узел4 узла16 узлов64 узла256 узлов3041,0000008,8841656081,0000003,73832217,1225862,3304301,43274032,93254715,5731576,95458312161,00000024321,0000003,86610214,41526944,23351349,2929813,98399115,42758255,234453430,26288830460812162432Коэффициент эффективностиЭффективность2,382,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,2210411,0701620,0364130,0055976081,0000000,9345812,0582840,2433310,02716612161,0000000,9665260,9009540,6911490,19255124321,0000000,9959980,9642240,8630381,68071430460812162432ВыводыT(n, p) ~ T(k2n, k2p)Blue Gene/PT(304, 1) = 0,813905 ~ 12,354451 = T(1216, 4)T(608, 1) = 6,154138 ~ 95,712110 = T(2432, 4)T(304, 4) = 0,091613 ~ 3,313401 = T(1216, 16)T(608, 4) = 1,646230 ~ 24,716522 = T(2432, 16)T(304, 16) = 0,047534 ~ 1,079805 = T(1216, 64)T(608, 16) = 0,186871 ~ 6,903593 = T(2432, 64)T(304, 64) = 0,349251 ~ 0,968973 = T(1216, 256)T(608, 64) = 0,395176 ~ 0,886240 = T(2432, 256)Алгоритм является масштабируемым только при достаточно больших размерах матриц, т.к.на меньших размерах накладные расходы, связанные с пересылкой данных, значительнопревышают полезное время.

Время выполнения программы при пропорциональномувеличении размера матрицы и количества процессоров изменяется все меньше и меньше.(6,903593 / 0,186871 ~ 37 раз; 0,886240 / 0,395176 ~ 2,2 раз). Ускорение и эффективностьсхожи с результатами, полученными при реализации алгоритма Кэннона..