В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 44
Текст из файла (страница 44)
Общие схемы распараллеливания этих задач приведены в гл. 2. Лля каждой вз них приводится несколько вариантов программ. Например, приведено три алгоритма умножения матрицы на матрицу. Разнообразие вариантов алгоритмов проистекает от разнообразия вычислительных систем и размеров задач. Здесь рассматриваются и разные варианты загрузки данных в систему: загрузка данных через один компьютер (например, нулевой) и загрузка данных непосредственно каждым компьютером с дисковой памяти, Если загрузка данных осуществляется через олин компьютер, то в этом случае данные считываются этим компьютером с дисковой памяти, разрезаются и части рассылаются по компьютерам. Но данные могут быть подготовлены и заранее, т.е. заранее разрезаны по частям и каждая часть записана на диск в виде отдельного файла со своим именем; затем каждый компьютер непосредственно считывает с диска предназначенный для этого компьютера файл.
Приводится два варианта алгоритмов решения СЛАУ методом Гаусса. Эти злгоритмы показывают, что равномерного распределения данных по компьютерам еше не достаточно для сбалансированной и эффективной работы, а важен еше и способ распределения данных. В начале рассматривается несколько простых задач, поясняющих программирование разных ветвей параллельной программы и их взаимодействие. 9.1.
Простые примеры В данном пункте приведены простые примеры параллельных программ, демонстрирующих программирование ветвей параллельной программы в простых случаях. Первый пример— это обмен данными между двумя ветвями параллельной программы без задания топологий. Рассматривается пример приема данных неизвестной длины. Приводятся примеры с ваданием виртуальных топологий и работы ветвей в этих топологиях, например, обмен цаиными между ветвями параллельной программы на кольце, в двумерной решетке. 9.1.1. Обмен данными между двумя ветвями параллельной программы Программируется работа двух ветвей параллельной программы. Одна ветвь передает какие-то данные другой ветви.
/» * Простая передача-приен: МР1 Яепй, МР1 алеся * Завершение по ошибке: МР1 АЬогс »/ Фйпс1пое <ар1.Ь> $1пс1пое <всо1о.п> /» Идентификаторы сообшений «/ Фйекйпе ЬаЕР1оасбага 1 йбе11пе саяПопЬ1еПаса 2 /» Этот макрос введен для удобства, «/ /» он позволяет указывать ллину массива в количестве ячеек «/ Ябе11пе ЕЕЕМБ(х) ( вйхео1(х) / вкхеок(х(Оц) ) 1вс аа1п(йпс агпс, спаг ««агбч) 170 9. Примеры параллельных программ /х Все ветви в области связи МР1 СОММ ИОВЫ бупут стоять, х пока ветвь 0 не вывелет сообшение.
х/ МРХ Ваггйег(МРХ СОИМ ИОВЫ); /х Без точки синхронизации может оказаться, что одна из ветвей » вызовет МР1 АЬогс раньше, чем успеет отработать рг1пс1() х в ветви О, МР1 АЬогс немедленно принудительно завершит х все ветви и сообшение выведено не будет »/ /х все задачи аварийно завершают работу х/ МР1 АЬогс( МР1 СОММ йОВХ.0, /х Описатель области связи, на которую »/ /х распространяется действие ошибки х/ МР1 ЕВВ„ОТМЕН); /» Оелочисленный код ошибки х/ гесцгп -1; ) 11(гапк == 0) ( /» Ветвь 0 что-то передает ветви 1 х/ МР1 Зепи( 11оас0аса, /х 1) 5, /» 2) адрес передаваемого массива х/ сколько.
5 элементов, т.е. 11оас0аса~03 11оасОасаМ х/ тип элементов х/ кону: ветви 1 х/ идентификатор сообшения х/ описатель области связи, через которую происходит передача х/ МРХ РЬОАТ, /х 3) 1, /» 4) саяРХоас0аса, /х 5) МР1 СОММ ИОВЫ); /» б) /» и еше одна передача: данные другого типа х/ МР1 Бепб(боцЫе0аса, б, МР1 000ВХЕ, 1, СаЕОоцЫе0аса, МР1 СОММ нОВЮ); 1пс в1ке, гапк, соцпс; 11оаС 11оаС0аСа~103; боцЫе е(оцЫе0асаГ203; МР1 Ясасцв всасцв; /х Инициализация библиотеки МР1х/ МР1 Хп1с(йагяс, йагяч); /» Каждая ветвь узнает количество задач в стартовавшем приложении »/ МР1 Сопел вйле(МР1 СОНМ нОКХ.0, йвгие); /х и свой собственный номер; от 0 до (вйле-1) х/ МР1 Сопел гап)е(МРХ СОИМ КОНЬО, йгапк); /х Пользователь должен запустить ровно две задачи, иначе ошибка »/ 11(в1ле != 2) /х Задача с номером 0 сообшает пользователю об ошибке х/ 11(гапк == О) рг1пс1("Еггог: сио ргосеввев гее)ц1гее1 1пвсеае) о1 '/б, аЬогс~п", в1яе); 9.А Простые преверы 171 е1ве ( /» Ветвь 1 что-то такое /* дожидается сообщения МР1 Весч( Х1оапОаса, приникает от ветви О */ и понещает пришедшие данные в буфер »/ /» 1) адрес нассива, куда скпадывать принятое »/ /» 2) фактическая длина приемного массива в числе эпеиентов »/ /» 3) сообщаен МР1, что пришедшее сообщение состоит из чисел типа '11оас' »/ /» 4) от кого: от ветви О »/ /» 5) ожидаем сообщение с таким идентификатором */ /* б) описатель обпасти связи, через которую ожидается приход сообщения »/ /» 7) сюпа будет записан статус завершения приена »/ ЕРЕМЕ(11оасОаса), МР1 Р(,ОАТ, О, саяГ1оасОаса, МР1 СОИМ ЧОВЕО, йвсасив); /» Вычисляем фактически принятое копичество данных »/ МР1 Оес соипс( йвпапив, /» статус завершения »/ МР1 РЕОАТ, /» сообщаем МР1, что и ишедшее со Р общение состоит из чисел типа '11оас' »/ /» сюда будет записан результат »/ йсоипс); /» Выводим фактическую дпину принятого на экран »/ ргйпп1(егапк = '/б Весейчеб '/с) е1ешв~п", гапк, соипс); /» Аналогично принижаем сообщение с данными типа с)оиЫе МР1 Весч(боиЫе0апа, ЕЬЕИЯИоиЫе0апа), МР1 ООПВОЕ, О, саяПоиЫеПаса, МР1 СОММ иОВ10, йвсасив ); ИР1 пес соипс(йвсасив, мР1 ПООВее, йсоипс); ) /» Обе ветвя завершают выполнение »/ МР1 Рйиа11хе(); гесигп О; /» * Приен сообщений неизвестной янины: » МР1 РгоЬе »/ й1пс1ибе <шр1.Ь> ййпс1ибе <втбйо.Ь> ййпс1иде <всб11Ь, Ь> 9.1.2.
Прием сообщений неизвестной длины Прием сообщений от разных отправителей с разными идентификаторами (с содержимым разных типов) в произвольном порядке: МР1 АИУ ЯОПВСЕ, МР1 АМ1' ТАО-(джокеры). 172 9. Призеры параллельных прогрпмм №йпс1пбе <С1ше Ь> /* Ипентификаторы (теги) сообшений */ №бе11пе саиР1оасПаса 1 №беХгпе сан1опЕПаса 2 /« Блина передаваемых сообшений может быть случайной от 1 до « шахМеззацеЕ1ешз «/ №йеТАпе шахМеввапеЕ1ешв 100 гпс ша1п(1пс атис, сьаг ««аген) ( 1пС з1ге, гапК, соцпС, г, и, оК; №1оаС «11оаСРСг, гпС «1опирсг, сЬаг «Суреиаше, МР1 БСаСпв всасцв, /« Инициализация библиотеки и сообшение об ошибке целиком перенесены « из предыдушего примера «/ МР1 1пгС(йагйс, йагйн), МР1 Сошш вазе(МР1 СОИМ ИОНОВ, йвйзе); МР1 Сошш гапК(МР1 СОИМ КОНЕВ, жгапК), /« Пользователь должен запустить ровно ТРИ ветви (процесса), иначе « ошибка «/ гХ(в1хе != 3) ( 11(гапК == О) рггпс1("Еггог.
3 ргосеввев геопггеб гпзсеаб о1 /б~п",вйзе), МР1 Ваггтег(МР1 СПИМ ИОВ10), МР1 АЬогС(МР1 СОММ ИОВХ.П, МР1 ЕНН ОТНЕИ), гесцтп -1; /« Иажпая ветвь инициализирует генератор случайных чисел «/ вгапб( ( гапК + 1 ) « (ппзгнпеб )Сгше(О) ), ви1СсЬ(гапК) с саве О /« Создаем сообшение случайной длины */ соцпс = 1 + гапд() / шахМезванеЕ1ешв; 11оасрсг = ша11ос(соцпс « згзеот(т1оас)); гог(г = О, г < соппс, 1++) г1оаСРСгЫ = И1оаС)г; /* Посылаем сообшение в ветвь 2 «/ МР1 Зепб(11оасРСг, соипс, МР1 ГПОАТ, 2, саяГ1оаСПаСа, МР1 СОИМ ЧОН1.0), рг1пС1("/б Яепб '/б Т1оаС гсешз Со ргос 2~п", гапК, соипС), ЬгеаК; 9.1. Простые примеры 173 саве 1: /» Создаем саобшение случайной длины «/ сацпс = 1 + гапб() '/ шахМеввайеЕ1ешв; 1опЕРПг = ша11ос(соцпп » в1кеоХ(1апи)); тог(1 = О, 1 < соцпс; 1+») 1опЕРсгЫ = 1; /» Посыпаем сообшение в ветвь 2 »/ ИР1 Яепб(1опЕРсг, сацпс, ИР1 ЬОМС, 2, саЕ(.апЕ0аса, ИР1 СОММ МОК(.0); рг1псХ(»/б.
Яепб уб 1опЕ 1пешв со ргос.2~п", гапй, соцпс); ЬгеаК; саве 2: /» Ветвь 2 принимает сообшения неизвестной длины, » испопьзуя ИР1 РгоЬе »/ Хог(п=О; п<2; и++) /» Всего ожидаются два сообшения »/ ( МР1 РгоЬе( МР1 АМУ ЯСОНЕ, /» Лискер ждем от пюбой задачи »/ ИР1 АМУ ТАС, /» Лжокер: ждем с любым идентификатором»/ МР1 СОМИ МОЕГО, йвсасцз); /» МР1„ргоЬе вернет управление, когда сообшение будет » уже на приемной стороне в служебном буфере »/ /» Проверяем идентификатор и размер пришедшего сообшения »/ 1Х(зпасцз.МР1 ТАС == саЕР1оас0аса) ИР1 Сеп соцпс(йзсасцэ, МР1 ГЕОАТ, йсоцпс); /» Принятое будет размешено в динамической памяти: * заказываем в ней буфер соответствующей длины »/ 11оасрсг = ша11ос(соцпс » з1кео1Н1оас)); МР1 Весч(т1оасРсг, соцпс, ИР1 РЬОАТ, МР1 АМУ ЯООВСЕ, МР1 АМУ ТАС, МР1 СОММ МОЕЮ, йвпапцв); /» МР1 Кесч просто скопирует уже принятые данные » из системнога буфера в пользаватепьский »/ /» Проверяем принятое »/ тот(ои = 1, х»О; 1 < соцпс; 1++) 11(11оасРсгЫ != (11оас)1) ой = О; суреМаше = »г1оас"; е1ве 11(всасцв,ИР1 ТАС == саЕ(.опЕОаса) с /» Пействия, аналогичные выше описанным »/ МР1 Сеп соцпп(йзпапцв, МР1 АЛОИС, йсацпп); 1опбрсг = ша11ос(соцпс » в1зео1(1опЕ)); ИР1 Кесч(1опЕРСг, соцпп, ИР1 ЮМС, МР1 АМУ ЯООКСЕ, ИР1 АМУ ТАС, ИР1 СОИИ МОК(.0, йвсасцв ); 174 9.
Примеры параллельных программ уог(ой = 1, т = О, т < соцпс, т++) т1(1опйрсгЫ '= т) о)е=О, Сурейаше = «1опп", /« Сообшаем о завершении приема */ ргтпс1( и/б '/6 '/з тсешз аге гесетчеб 1гош '/б '/з'тп", гапй, соцпс, суреиаше, зсасцз МР1 БОРБОЕВ, ой т "ОК" оРА1(.БРа ), ) /» аког(п) Ьгеа)е, /« знтссЬ(гапк) «/ /» Завершение работы »/ МР1 Ртпа1тхе(), гесцгп О, ) 9.1.3. Обмен данными на системе компьютеров с топологией свизи "кольцо" В этом пункте приведено два примера, демонстрирующих операцию сдвига данных вдоль кольца компьютеров. Эта операция очень часто встречается при решении задач на мультикомпьютерах.
Хотя приведенные здесь примеры очень простые, они могут послужить неким шаблоном, который можно применять для решения сложных задач. В первом примере выполняется сдвиг данных соседним ветвям вдоль кольца компьютеров на один шаг, т.е. все ветви параллельной программы передают данные соседним ветвям, например, в сто.
рону увеличения рангов (номеров) компьютеров. Во втором примере реализуется конвейер, Нулевая ветвь инициирует запуск данных вдоль кольца компьютеров, посланные данные последовательно "проходят" по всем компьютерам ^ возвращаются в нулевой компьютер, реализуюший нулевую ветвь. /» Пример 1 « Сдвиг данных на кольце компьютеров «/ лтпс1пбе <шрт Ь> лтпс1цбе <зсбто Ь> Ие1тпе МОМ Р1МБ 1 тпс шатп( тпс атис, сЬаг«« агич ) ( тпс гапк, зтле, т„А, В, бтшзЮМ Р1МБЗ, тпс регтодз'ьМУМ Р1МБ), золгсе, безс, тпс геогс)ег = О, МР1 Сопел сошш сагт,, МР1 Бсасцз зсасцз, МР1 1птс(йагбс, йагбч), /» Кажная ветвь узнает обшее количество ветвей */ МР1 Сошш гапк(МР1 СОММ МОВЫ, агапК), /« и свой номер от О до (зтне-1) «/ МР1 Сошш зтхе(МР1 СОММ ИОВЫ, азтне), А = гапк, В = -1, 175 9.1.
Простые примеры /« Обнуляем массив бааз и заполняем массив регйобв лля топологии "кольпо" «/ Хог(т = О; 1 с ИОМ 01МЯ; 1++) 1 61шзИ = О; рег1обзШ = 1; ) /« Заполняем массив 61шв, в котором указываются размеры решетки «/ МР1 01шв сгеасе(з1хе, ИУМ 01МЯ, б1шз); /« Сознаем топологию "кольпо" с сопппппйсасог(ом) сошш саге «/ МР1 Сагп сгеапе(МР1 СОММ НОВЫ, ИУМ 01МЯ, б1шв, регпобв, геогбег, йсошш сагс); /« Каждая ветвь находит своих соседей вдоль кольна, в направлении « больших значений рангов «/ МР1 Сагс зЬ11с(сошш саго, О, 1, йвопгсе, йбезп); /« Кажлая ветвь перелает свои ланные (значение переменной А) соседней « ветви с большим рангом и принимает данные в В от соседней ветви с « меньшим рангом.
Ветвь с рангом зйхе-1 передает свои данные ветви с « рангом О, а ветвь О прининает данные от ветви зйхе-1. «/ МР1„Яепбгесч(йА, 1, МР1 1ИТ, бевс, 12, йВ, 1, МР1 1ИТ, зопгсе, 12, сопла сагп, йвсаспз); /« Каждая ветвь печатает свой ранг (он ие и был послан соседней ветви « с большим рангом) и значение переменной В (ранг соседней ветви с « меньшим рангом).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
