task2 (практическая работа (2))

Асирян Александр, 428 группаПостановка задачиРазработать параллельный алгоритм и исследовать его эффективность для задачиумножения матрицы на вектор. Тип данных – double. Размер матрицы – mxm.Описание алгоритмаМатрица и вектор генерируются случайным образом (~1 минута для m = 16384) при запускепрограммы и записываются в один файл для удобства будущего чтения root-процессом.Формат файла следующий:A[0][0]A[1][0]A[2][0]A[3][0]…A[m – 1][0]X[0]A[0][1]A[1][1]A[2][1]A[3][1]…A[m – 1][1]X[1]…A[0][m – 1]A[1][m – 1]A[2][m – 1]A[3][m – 1]…A[m – 1][m – 1]X[m – 1], т.е.

столбцы матрицы расположены в строках. При этом, в зависимости от размеракоммуникатора, в первую очередь идут строки со столбцами матрицы с индексами 0, 0 + i, 0+ 2i, 0 + 3i, …, затем 1, 1 + i, 1 + 2i, 1 + 3i, …, и т.д., т.е. шагом является отношение порядка m кразмеру коммуникатора size. Таким образом, всем вычислительным процессам достанетсяодна порция вычислений одного размера. Затем root-процесс собирает от всех процессовчастичные суммы каждой строки и суммирует со своими данными.Запуск на выполнение:<…> ./task2 <m> <file_out> <file_int> <file_ext>, либо<…> ./task2 <m> <file_out> <file_int>в зависимости от установленных флагов (debug, save) в программе.

Возможны 4 случая:1. debug = 0, save = 0 – запуск осуществляется вторым способом, при этом файл ссгенерированными бинарными данными будет сохранен.2. debug = 0, save = 1 – запуск осуществляется первым способом, при этом длясгенерированного файла с бинарными данными будет создана копия, удобная дляпросмотра, а сам файл с бинарными данными будет удален после завершенияпрограммы.3. debug = 1, save = 0 – запуск осуществляется вторым способом, при этом, помимо пункта1, в стандартный поток вывода будет выведена информация о пересылке данныхмежду процессами.4. debug = 1, save = 1 – запуск осуществляется первым способом, при этом все файлыбудут сохранены и в стандартный поток вывода будет выведена информация опересылке данных между процессами.В программе – debug = 0, save = 1. По умолчанию, в стандартный поток вывода печатаетсявремя счета каждого процесса, а также время генерации и сохранения в файл данных.m – размер матрицы/вектора;file_out – имя выходного файла с результатом умножения;file_int – имя файла с бинарными данными (будет создан при выполнении программы);file_ext – имя файла с преобразованными в понятное представление бинарными данными.РезультатыРезультаты замерялись по 5 раз для каждой ячейки таблиц и усреднялись.РегаттаВремя, сВремя выполнения3,002,752,502,252,001,751,501,251,000,750,500,250,00102440968192163841 узел0,0170830,1898410,7302392,7040454 узла0,0067140,0665950,2376090,9057718 узлов0,0034250,0337690,1182880,44942912 узлов0,0028320,0219740,0824350,29451016 узлов0,0022370,0174490,0651770,2309591 узел4 узла8 узлов12 узлов16 узловКоэффициент ускоренияУскорение15,014,013,012,011,010,09,08,07,06,05,04,03,02,01,01 узел4 узла8 узлов12 узлов10241,0000002,5443854,9877376,0321337,63656740961,0000002,8506795,6217548,63934710,87976481921,0000003,0732806,1733998,85836111,203937163841,0000002,9853526,0166239,18150511,707901Коэффициент эффективности10244096819216 узлов16384Эффективность1,00,90,80,70,60,50,40,30,20,10,01 узел4 узла8 узлов12 узлов16 узлов10241,0000000,6360960,6234670,5026780,47728540961,0000000,7126700,7027190,7199460,67998581921,0000000,7683200,7716750,7381970,700246163841,0000000,7463380,7520780,7651250,73174410244096819216384ВыводыT(n, p) ~ T(k2n, k2p)РегаттаT(1024, 1) = 0,017083 ~ 0,066595 = T(4096, 4)T(1024, 1) = 0,017083 ~ 0,230959 = T(16384, 16)T(4096, 1) = 0,189841 ~ 0,905771 = T(16384, 4)T(1024, 4) = 0,006714 ~ 0,017449 = T(4096, 16)T(4096, 4) = 0,066595 ~ 0,230959 = T(16384, 16)Алгоритм является масштабируемым, т.к.

время выполнения программы припропорциональном увеличении размера матрицы и количества процессоров изменяется неболее чем на один порядок (0,522667 / 0,033468 ~ 15,6 раз)..