В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 46
Текст из файла (страница 46)
< И, д++) ( аког() = О, ) < М, )++) ( А[д][)] = 3 141528 В[)3[д) = 2 812, С[дз [)1 = О О, ) /х Засекаем начало умножения матриц х/ Ееспдшео1е)ъу(йсч1, (зсгцсс сдшекопех)О), /х Каждая ветвь производит умножение своих полос матриц х/ /х Самый внешний цикл Хог(К) — цикл по компьютераи х/ аког(К = О, К < здхе, К++) /х Каждая ветвь вычисляет координаты (вдоль строки) для результируюших » злементов матрицы С, которые зависят от нонера цикла К и х ранга компьютера х/ б = ((гапК + К)увдке)»М, /х Каждая ветвь производит умножение своей полосы матрицы А на х текушую полосу натрипы В х/ Хог() = О, ) с М, )++) ( аког(дд = О, )1 = б, )1 С й+М, )1++, дд++) ( аког(д = О, д < М, д++) С[)3 [) 11 +и А[)3 Ы х ВЫ [д13, /х Унножение полосы строк матрицы А на полосу столбцов матрицы В в каждой х ветви завершено х/ /* Каждая ветвь передает своим соседним ветвям с меньшим рангом * вертикальные полосы матрицы В Т е полосы матрицы В сдвигаются вдоль х кольца компьютеров х/ МР1 Беппгесч гер1асе(В, Е1(В), МР1 ПООВЕЕ, бевс, 12, нопг, 12, сопле сагс, йвс), 180 9.
Примеры параллельных программ /» Умножение завершено Каждая ветвь умножила свою полосу строк матрицы А на » все полосы столбцов матрицы В » Засекаем время и результат печатаем »/ Вессдшеотбау(йсч2, (всгпсс Фдшекопе»)О), бтд = (та2 Сч вес — Счд Сч вес) » 1000000 + Сч2 Сч овес — тчд тч пвес, ргдптт(ьгапк = Уб Тдше = /б'дп", гапй, бт1), /» Пля контроля печатаем первые четыре элемента первой строки результата »/ дХ(гапй == О) ( Хог(д = О, д < 1, д++) бог() = О, д < 4, б++) ргдптТ(»СЫ()3 = /Йп", СЫ [)1), /» Все ветви завершают системные процессы, связанные с топологией сошш сагс » и завершаю выполнение программы »/ ИР1 Сошш аггее(йсошш сагс), МР1 Едпа1дхе(), геспгп(0), 9.2.2.
Произведение двух матриц в топологии "двумерная решпета" В этом примере исходные н результируюшая матрицы разрезаются в нулевой ветви и затем части матриц рассылаются во все другяе ветви. Схемы распределения данных по компьютерам приведены в и. 2.2.2. /» Произведение двух матриц в топологии "двумерная решетка" компьютеров »/ /» В примере предполагается, что количество строк матрицы А и количество » столбцов матрицы В делятся без остатка на кокичество компьютеров в системе » В данном примере задачу запускаем на 4-х компьютерах и на решетке 2х2 »/ №дпс1ибе<втбдо Ь> №дпс1ибе<втб1дЬ Ь> №дпс1ибе<шрд Ь> №дпс1ибе<сдше Ь> №дпс1пбе<вув/сдше Ь> /» ИПМ 01МБ — размер декартовой топологии "двумерная решетка" РОхР1 */ №бетдпе МОИ 01ИЯ 2 №бетдпе РО 2 №бе1дпе Р1 2 /» Задаем размеры матриц А = Ихй, В = ИхК и С = МхК (Эти размеры значимы в » ветви О) »/ №беХдпе М 8 №беддпе И 8 №бетдпе К 8 №бед'дпе А(д,)) Аьй»д+)3 №беддпе В(д,1) ВЕК»д+13 №бейдпе С(д,1) СЕК»д+~] /» Подпрограмма, осушествпяюшая перемножение матриц »/ РМАТМАТ 2(п, А, В, С, р, сошш) /» Аргументы А, В, С, и„ р значимы в данном случае только в ветви 0 »/ р.е.
Произведение двух матриц 181 /» Размеры исходных матрип х/ /« Исхолные катрины: А[и[0]][и[1]], В[и [1]] [и[2]], С[и[0]] [п[2]]; х/ 1пт »и; е)опЫе *А; хВ, хС; /х Лалее все описываемые перененные значимы во всех ветвях, в том числе * и ветви 0 х/ бопЫе »АА, »ВВ, »СС; /» Локальные полматрипы (доносы) х/ 1пп пп[2]; /х Размеры полос в А и В и подматрип СС в С «/ 1пс соогбя[2]; /» Лекартовы координаты ветвей »/ 1пс гапк; /х Ранг ветвей х/ /» Смешения и размер полматрил СС лля сборки в корневом пропессе (ветви) х/ 1пъ »соппсс, хбйзрс, »соппСЬ, хбйярЬ; /х Типы ланных и массивы лля создаваемых типов »/ МР1 Оаъасуре пуреЬ, сурес, сурен[2]; 1пп Ыеп [2]; 1пп1,],к; 1пс регйобз[2], гешайпз[2]; 1пс з1хеоте)опЫе, б1зр[2], /х Комнуникаторы лля 2Р решетки, для полрешеток 1Р, и копии х/ /» коммуникатора сопел х/ МР1 Сопел сошш 20, сопел 10[2], рсошш; /х Создаем новый коммуникатор »/ МРХ Сошш бпр(сопвп, ерсошш); /» Нулевая ветвь передает всем ветвям массивы и[] и РП х/ МР1 Всазт(п, 3, МР1 1МТ, О, рсошш); МР1 Всаят(р, 2, МР1 1МТ, О, рсошш); /» Создаен 20 решетку компьютеров размером р[О] хр[1] */ рег1обз[0] = 0; рег1обя[1] = О; МР1 Сагс сгеасе(рсоппп, 2, р, рег1ое(з, О, асошш 2Р); /х Находим ранги и лекартовы координаты ветвей в этой решетке х/ МР1 Сошш гап)е(сошш 2Р, агап)е); МР1 Сагс соогбз(соппп 20, гапк, 2„ соогбя); /х Нахожление коммуникаторов лля полрешеток 1Р для рассылки полос « матрип А и В »/ Хог(1 = 0; т < 2; 1++) ( аког() = 0; ] < 2; ]++) /х Ванные х/ тпФ »р; /х размеров решетки компьютеров.
Р[0] соответствует п[О], р[1] » соответствует п[2] и произвеление р[0] »р[1] бупет эквивалентно » размеру группы сошш х/ /* Коммуникатор лля пропессов, участвующих в умножении матрипы на матрипу »/ МР1 Сошщ сошш, 182 9, Примеры параллельных программ гешатпв[)] = (т == )) ИР1 Саги зиЬ(сошш 20, геша1пя, мсоюш 10[т]) /х Во всех ветвях задаем подматрииы (полосы) */ /* Здесь предполагается, что пеление без остатка ь/ пп[О] = п[О]/р[О], пп[1] = п[2]/р[1], №бе1тпе АА(т,)) АА[п[1]*а+)] №йет1пе ВВ(1,]) ВВ[пп[1]ах+)] №беХтпе СС(т,)) СС[пп[1]ьт+)] АА = (боиЫе *)ша11ос(пп[О] ь п[1] ь з1нео1(боиЫе)), ВВ = (поиЫе ь)ша11ос(п[1] ь пп[1] ь втяеоХ(йоиЫе)), СС ~ (боиЫе ь)ша11ос(пи[О] х пи[1] м вднео1(боиЫе)), /ь Работа нулевой ветви м/ т1(гяпК == О) ( /* Задание типа данных для вертикальной полосы в В х Этот тип создать необходимо, т к в языке С массив в памяти Ф располагается по строкаи Лля массива А такой тип создавать * нет необходимости, т к там передаются горизонтальные полосы, а они в памяти расположены непрерывно ь/ ИР1 Туре чессог(п[1], пи[1], п[2], ИР1 000ВЬЕ, йеурез[О]), /* и корректируем пиапазон размера полосы ь/ МР1 Туре ехсепс(МР1 000В|Е, яятлео1боиЫе), Ыеп[О] = 1, Ыеп[1] = 1, а яр[О] = О, 61вр[1] = втнео1боиЫе ь пп[1], сурен[1] = МРТ ОВ, ИР1 Туре ясгисс(2, Ыеп, д1вр, сурен, 8ьсуреЬ), ИР1 Туре сошштп(йпуреЬ), /ь Вычисление размера подматриды ВВ и смешений каждой * подматриды в матриде В Подматрипы ВВ упорядочены в В м в соответствии с порядком номеров компьютеров в решетке, * т к ма~сизы расположены в памяти по строкам, то подматриды э ВВ в памяти (в В) должны располагаться в следуюшей * последовательности ВВО, ВВ1,' ь/ бтзрЬ = (тпс э)ша11ос(р[1] * зтнео1(тпп)), соипсЬ = (тпс *)ша11ос(р[1] ь втиеот(тпс)), Хог() = О, 1 < р[1], 1++) ( бтврЬ[)] соипъЬ[)] = 1, /* Задание типа данных для подматриды СС в С ь/ МР1 туре чессог(пп[О], пп[1], п[2], мР1 000В|е, ясурев[О]), /* и корректируем размер диапазона */ МР1 Туре всгисс(2, Ыеп, бтяр, сурен, йсурес), У.в.
Лроизведеиие даув матриц 1ВЗ МР1 Туре сопап1С(впурес); /» Вычисление размера подматрипы СС и смешений каждой » подматрипы в катрине С. Попматрипы СС упорядочены в С » в соответствии с порядком номеров компьютеров в решетке, » т.к. массивы распопожены в памяти по строкам, то подматрипы * СС в памяти (в С) должны располагаться в следуюшей » последовательности ССО, СС1, СС2, ССЗ, СС4, СС5, ССб, СС7.
»/ бйврс = (1пс»)ша11ос(р[0]» р[1]» в1веоХ(1пс)); соппсс = (1пс »)ша11ос(р[О] » р[1] » в1зео1(1пс)); бог(1 = 0; 1 < р[0]; 1++) ( Хог() = О; ] < р[1]; )++) ( б1врс[1»р[1]+)] = (1»р[1]»пп[0] + )): соппсс[1»р[1]+)] = 1; ) /» Нупевая ветвь завершает подготовительную работу */ /* Вычиспения (этапы указаны на рнс.2.4 в гп. 2) »/ /* 1.
Нулевая ветвь передает (всагтег) горизонтальные полосы матрипы А » по х координате »/ 11(соогбв[1] == О) ( МР1 Всапсег(А, па[О]»п[1], МР1 ОООВЬЕ, АА, по[О]»п[1], МР1 0ОВВЕЕ, О, соппп 10[0]); МР1 Ваггйег(МР1 СОНМ НОЕВО); /» 2. Нулевая ветвь передает (всассег) горизонтальные полосы матрипы В по у координате »/ 11(соогбв[0] == 0) ( МР1 Ясастеги(В, соппсЬ, бйврЬ, СуреЬ, ВВ, п[1]»по[1], МР1 0ОУВЕЕ, О, сошш 10[1]); ) /» Э. Передача подматрип АА в измерении у */ МР1 Всавт(АА, оп[0]»п[1], МР1 0ООВЕЕ, О, сошш 10[1]); /* 4. Передача подматрип ВВ в измерении х »/ МР1 Всавс(ВВ, п[1] »оп[1], МР1 ПСОВОЕ, О, соппп 10[0] ); /* 5 Вычисление подматрип СС в каждой ветви »/ аког(1 = 0; 1 < оп[О]; 1++) ( аког() = О; ] < пп[1]; ]++) С СС(1,]) = О.О; Хог(й = О; К < п[1]; К++) ( СС(1,)) = СС(1,)) + АА(1,к) » ВВ(К,)); ) /» б.
Сбор всех подматрип СС в ветви 0 »/ 184 9. Примеры параллельных проерамм МР1 ОасЬегч(СС, пи[03«ппМ , МР1 ООчВсЕ, С, соипъс, б1врс, пурес, О, соппп 20); /х Освобождение памяти всеми ветвяни и завершение подпрогранны х/ атее(АА); атее(ВВ); атее(СС); МР1 Сошш атее(жрсошш); МР1 Сошш 1гее(жсошш 20); 1ог(1 - "О; 1 < 2; г++) ( МР1 Соппп атее(еесошш 1ЭЫ); Н(тапи -"= 0) ( тгее(сапиенс); 1гее(бйврс); МР1 Туре 1гее(жпуреЪ); МР1 Туре атее(йсурес); МР1 Туре гтее(асурев[ОЛ); теъитп 0; /х Главная программа х/ тпъ ша1п(гпп атис, сваг х*агбч) с 1пп в1ке, Мур, и[33, р[2л, 1, ), К; 1пс бйшв [МОМ Р1МЯ , регйобв[МОМ 01МЯ]; боибйе «А, «В, «С; 1пс геогбет = 0; впгисп Сйшеча1 пч1, сч2; /х Лля засечения времени х/ 1пп бъ1; МР1 Соппп сошш; /х Инипиализапия библиотеки МР1 х/ МР1 1п1п(лагос, Магич); /х Каждая ветвь узнает количество задач в стартовавшен приложении х/ МР1 Сошш вбяе(МР1 СОММ ИОВЫ, йвбхе), /х и свой собственный номер (ранг) «/ МР1 Сошш тапи(МР1 СОММ ИОВЫ, жМуР); /х Обнуляен массив ббшв и заполняеи пассив регйобв для топологии х "двунерная решетка" х/ Тот(1 = 0; 1 < МУМ 01МЯ; 1++) ( б1швЫ = О„рег1обвЫ = 0; /х Заполняен массив бтшв, где указываются разиеры двумерной решетки х/ МР1 01шв сгеасе(в1ке, ИУМ 01МЯ, бгшв), /х Создаен топологию "двунерная решетка" с сошшипбсасог(он) соппп х/ МР1 Сагл сгеасе(МР1 СОММ МОВЮ, МОМ 01МЯ, ббшв, регбобв, теогбег, йсопып) /х В первой ветви выпеляен в памяти кесто для исходных натрии х/ 11(МуР == 0) ( /х Задаен размеры натрии и размеры двуиерной решетки конпьютеров х/ и[ОД = М; 9 Я Произведение дене .наенрич пШ =и, пС23 = К, р(0) = РО, р(1~ = Р1, А = (боцЫе х)ва11ос(М * М х егхеотйоцЫе)), В = (боцЫе х)ва11ос(И» К х егхео1(боцЫе)), С = (боцЫе х)ва11ос(М х К х зтвеоТИоцЫе)), /х Генерируем в первой ветви исхопные матрицы А и В, матрицу С обнуляем х/ аког(т = О, т с М, з++) аког() = О, ) < М, д++) А(э.,)) = т+1, Хог(д = О, д < М, д++) аког(к = О, )е < К, К++) в(),н) = 21+), тог(т = О, т < М, т++) Хог(К = О, )» < К, К++) С(з.,н) = О О, ) /х Попготовка матриц ветвью 0 завершена х/ /х Засекаем начало умножения матриц во всех ветвях х/ кесствео1бау(йсч1, (зсгцсс ствехопех)О), /* Все ветви вызывают функцию перемножения матриц х/ РМАТМАТ 2(п, А, В, С, р, сопеп), /х Умножение завершено Кажлая ветвь умножина свою полосу строк матрицы А на х поносу стопбпов матрицы В Резуиьтат нахопится в нупевой ветви * Засекаем время и результат печатаем х/ Весствеотоау(асч2, (зсгцсс ствекопех)0), ос1 = (сч2 тч зес — гч1 гч зес) х 1000000 + сч2 сч цзес — сч1 тч цзес, ргтпсХ(нМуР = %6 Ттве = %б~п", МуР, бс1), /х Лля контроля 0-я ветвь печатает результат х/ т1(МуР == 0) ( аког(т = О, з < М, т++) ( аког() = О, ) с К, )++) ргтпс1(и %3 11»,с(т,))), ргтпс1(»1пн), /х Все ветви завершают системные процессы, связанные с топологией совв х и завершают выполнение програмны »/ дт(Мур == 0) ( аггее(А), тгее(В), аггее(С), МР1 Савв аггее(асовв), МР1 Ртпа1тхе(), гесцгп(0), 9.
Примеры параААельмых программ 9.2,3, Произведение двух матриц в топологии "трехмерная решетка" В этом примере исходные и резупьтируюшая матрицы разрезаются в нулевой ветви н затем части матриц рассыпаются во все другие ветви. Схемы распределения данных по компьютерам приведены в и. 2.2.3. /» Произведение двух матриц в топологии "трехмерная решетка" компьютеров »/ /» В примере предполагается, что копичество строк и столбцов иатрицы А » и количество строк и стопбцов иатрицы В делятся без остатка на количество » компьютеров в системе * В данном примере зэлачу запускаем на 8-х компьютерах и на решетке 2х2х2 »/ №тпс1пбе<всбзо Ь> №зпс1пде<зсб1зЬ Ь> №тпс1пбе<шрп Ь> №зпс1пбе<сзше Ь> №ппс1пбе<зуз/Сппе Ь> /» МРИ Р1ИЯ вЂ” размер декартовой топологии "трехмерная решетка" РОхр1хр2 »/ №беттпе МОМ Р1И3 3 №беХзпе РО 2 №бе1зпе Р1 2 №беХзпе Р2 2 /* Залаем размеры матриц А = Ихй, В = МхК и С = ИхК (Эти размеры значимы в ветви 0) »/ №6е1зпе М 8 №беттпе М 8 №беХтпе К 8 №бе1зпе А(т, ) ) А сМ»~+)3 №бегзпе В(т,)) ВГК»з+)3 №бейзпе С1з,)) СГК»з+)) №беХгпе С1(з,)) С1~К»з+)Я /» Подпрограмма, осушествпяюшая перемножение матриц »/ РМАТИАТ 3(п, А, В„ С, р, соппп) /» Аргументы А, В, С, и, р значимы только в ветви 0 */ зпс »и, /» Размеры исходных матриц »/ бопбйе »А, »В, »С, /* Исходные матрицы А~п~031 ~пШ1, ВСп[133 СпС2П .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
