В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 32
Текст из файла (страница 32)
6.12. 6.10. /'лабильные редуцированные (обьединеннме операции 119 6.10.2. Предопределенные редуцированные операции Следующие предопределенные операции поставлены для МР1НЕРРСЕ и зависимых функций ИР1 А1ЬНЕООСЕ, МР1 НЕООСЕ ЯСАТТЕН и МР1 ЯСАМ. Эти операции вызываются, размещая указанные имена вместо аргумента ор. Имена операций Значения операций Лве операции МР1 М1МЬОС и МР1 МАХЕОС описаны отдельно в п. 6.10.3.
Лля других предопределенных операций ниже перечислены позволяемые комбинации аргументов ор и басасуре. Сначала определим группы основных типов данных МР! следующим образом. С )псекег Гогсгап !пСеЕег МР1 1МТЕОЕН Г!оаИпЕ ро!пС (плавающая запятая) МР1 РЬОАТ, МР1 РООВЕЕ, МР1НЕА1, МР1 РООВ|Е РНЕС1Я1ОМ, МР1 1.ОМО РООВЕЕ Бой!са! Сепг р!ех Вуге МР1 ЬОО1СА1. МР1 СОМР!.ЕХ МР1 ВУТЕ Значение типа данных (г)асасурев) для каждой опции определено ниже.
Позволяемые типы Ор МР1 МАХ, МР1 М1М МР1 ЯОМ, МР1 РНОР МР11.АМО,МР1 1.0Н, МР1Л.ХОН МР1 ВАМР, МР1 ВОН, МР1 ВХОН Пример 0.15. Оператор, который вычисляет скалярное произведение двух векторов, распределенных по процессам группы, и возвращает ответ в нулевом процессе. РАН В1,АЯ1(и, а, Ь, с, соуп) !пС в; 1!вас аП, ЬП; 11оас с; ИР1 Сопли соуп; /ь локальный срез пассивов ь/ /* результат (в нулевои узле) */ МР1 МАХ МР1.М1М МР1 ЯОМ МР1РНОР МР1 1.АМР МР1 ВАНО МР1 !.ОН МР1 ВОН МР1.1.ХОН МР1 ВХОН МР1 МАХ|ОС МР1ЛТМ1ОС максимум минимум сумма произведение логическое "И" поразрядное "И" логическое "ИЛИ" поразрядное "ИЛИ" логический "ХОП" поразрядный вХОК" максимальное значение и локализация значение минимума и локализация МР1 1ИТ, МР1 !.ОНО, МР1.ЯНОНТ, МР1 ОМЯ1ОНЕР ЯНОНТ, МР1 УМЯ1ОМЕР, МР1 РМЯ1ОМЕР 1.0ИО С !псекег, ГогСгап )псейег, Г!оаС!пЕ ро1пс С )псеЕег, ГогСгап )псейег, Г!оас!пЕ ро)пС, Сопгр!ех С !псейег, 1,ок)са! С )псекег, Гогсгап )пгейег, Вусе 120 б.
Коааекигивнме взаимодепснгоия д дпс д; 11оас виш, /« Локальная виш «/ вив = О О, Хог(д = О, д < ш, д++) вив = вив + аЫ «ЬЫ; /« Глобальная виш «/ МР1 Веггисе(вив, с, 1, МР1 РЬОАТ, МР1 БОМ, О, совв), гесигп. ) Пример 6.16. Оператор, который вычисляет произведение вектора на массив, распреде. ленные по группе процессов, и возврашает ответ в нулевом процессе. Вектор а и матрица Ь иллюстрируется на рис. 6.11. РАВ ВЬАЯ2(в, и, а, Ь, с, совш) дпс в, и, 61оас аП, ЬП Ы, т1оаС с(п3 . МР1 Совв соти, ( ~1оас вив~п3; дпс д, /« Локальная вив «/ Хог() = О,) < и, О++) ( виш()] = О О, аког(д = О, д < в, д++) витЫ = вив()3 + аЫ «Ь(д,Я, /« Локальный срез пассивов «/ /« Результат «/ /« Глобальная вив «/ МР1 Веггисе(виш, с, ц, МР1 РЬОАТ, МР1 БОМ, О, сошв), /* Возврат результата в нулевой пропесс «/ гесигп, Рис. 6.11, Умножение вектора на матрицу.
Вектор а и матрица Ь распределены в одном измерении. Это иллюстрируется для четырех процессов. Срезы (слайсы) не обязаны быть все того же самого размера: каждый процесс может иметь различное значение для ш 6.10.3. ИППОС и МПХТОС Оператор МР1 М1МЬОС используется, чтобы вычислить глобальный минимум и индекс, присоединенный к минимальному значению. МР1 МА)(ЬОС аналогично вычисляет глобальный б.1д.
Глобальные реддцироеанные (обьединенные операции 121 максимум н индекс. Одно применение их должно вычислить глобальный минимум (максимум) и ранг процесса, содержащий это значение. Операция, которая определяет МР1 МАХЕОС: < 1, если и>и, ~ П ~ ) = ~ ), где и~ = пзах(и,и) и Й = ппп(г'.,1), если и = и, если и ( и. Операция, которая определяет МР1 М1ХЕОС: если и(и, Гз = ~ ~, где в = гпах(и,и) и Й = оп(1,1), если и = и, ) ~.1) ~,й~)' 1, если и>и. Описание Имя МР1 2ВЕАЕ пара КЕАЕ МР1 2000В1.ЕРВЕС1Я10М пара ВОВВ1.ЕРВЕС1Я10М переменных МР1 21МТЕОЕВ пара 1МТЕСЕК Имя Описание 11оас и зпс попЫе и зпс 1опи и тпс пара тпь вйогс и тпс 1опЕ попЫе и зпс МР1 ГЕОАТ 1МТ МР1 000ВЬЕ 1МТ МР1 1.0МО 1МТ МР1 21МТ МР1 БНОВТ 1МТ МР1 1.0МС 200ВЕЕ 1МТ Например, тип данных МР1 2ВЕАЕ определен так, как если бы он был определен следующей функцией (см.
п. 7.3): Обе операции ассоциативны н коммутативны. Заметьте, что если МР1 МАХ1,0С применяется, чтобы редуцировать последовательность пар (ио, 0), (им 1),..., (и„ы п-1), то возврашает значение (и, г), где и = гпах;, и, и г — индекс первого глобального максимума в последовательности. Таким образом, если каждый процесс поставляет значение и его ранг внутри группы, то приводяшееся действие с ор = МР1 МАХЕОС возвратит предельное значение и ранг первого процесса с тем же значением.
Точно так же МР1 М1МЕОС может использоваться, чтобы возвратить минимум и его индекс. В более общем смысле, МР1 М1МЕОС вычисляет лекснкографическнй минимум, где элементы упорядочены согласно первому компоненту каждой пары и связи решены согласно второму компоненту. Приведенная операция определена, чтобы оперировать на аргументах, которые состоят яз пары (величины и индекса). В порядке использования МР1 М1МЕОС и МР1МАХЕОС в пряводящейся операции, нужно обеспечить аргумент басасуре, который представляет пару (значение и индекс).
МР1 обеспечивает девять таких предопределенных басасурев. На С индекс тпс и значение может быть вйогс или 1опя тпс, Т1оас нли оопЫе. Потенциально природа смешиваемого типа таких аргументов — проблема в Рог1гап'е. Она разрешится при наличии МР1 обеспеченного типа, состоящего из пары того же самого типа (значение и принадлежность индекса также к этому типу). Операции МР1 МАХ1.0С и МР1 М1МЕОС могут использоваться с каждой следующей последовательностью типов (йасасурев).
Рог$гап: 122 б, Коллективные вэаимодейстпвия МР1 ТУРЕ СОМТ100ОЩ2,МР1.ЯЕАЬ,МР1 2ВЕАЬ) Аналогично определение и для МР1 21МТЕОЕВ, МР1 2ОООВЬЕРКЕС131ОМ, МР1 21МТ. Тип данных МР1 РЬОАТ 1МТ определен так, как если бы он был определен следующей последовательностью инструкций. Суре[0) = МР1 РЬОАТ суре[1) = МР1 1МТ йтвр[03 = 0 йзэр [13 = взвеот(г1оаС) 'о1осК[03 = 1 П1осК[13 = 1 ИР1 ТУРЕ БТКОСТ(2,о1осй,бтвр,суре,МР1 РЬОАТ 1МТ) Подобные утверждения верны и для других смешанных типов в С.
Пример 8.17. Каждый процесс имеет массив из 30 чисел бопо1е. Лля каждого из ЗО чисел вычисляется значение и ранг процесса, содержащего самое большое значение. /и Какдый процесс инеет пассив из 30 чисел бопо1е атп[303 */ Яопо1е атп[30), аоис[ЗО), гпС зпб[303 . зсгпсС ( бопо1е ча1, тпС гапК, ) тп [303, оцС[ЗОД, ~пС з, вугапК, гооС, чр1 Совв гапК(МР1 СОИМ МОМЬО, йвугапК), Рог(т = О, з < 30, ++з) ( тпЫ ча1 = азль , тпЫ гапК = вугэлК, ) 6Р1 Вебисе(тп,опС,ЗО,МР1 РООВЬЕ 1МТ, МР1 МАХЬОС,гоос,совв), ~и С этой точки работает только процесс гооС и результат в неви/ гй(вугапК == гооС) ( тог(гиО, т < ЗО, ++г) ( аопСЫ = опСЫ ча1, элбим = опСЫ гапК, Пример 8.18.
Каждый процесс имеет не пустой массив значений. Находится минимальное .лобапьное значение, ранг процесса и его индекс на этом процессе. йоетзпе ЬЕМ 1000 :1оап ча1[ЬЕМ3, /и накальный пассив величин э/ ~пС соппС, /э количество величин э/ ~пс вугапК, втпгапК, втпдпбех, .'1оас взпча1, ~СгпсС ( т1оаС ча1пе, зпс зпбех, ) тп, опС, 6.10. Глобальные редииироеанные объединенные операции 123 /» Локальный взп1ос »/ 1п ча1це = ча1(03, 1п зпбех = О, Хог(з = 1, з < соцпс, з++) зХ(зп ча1це > ча1Ы ) ( зп ча1це = ча1Ы ; 1п.зпбех = з, /» Глобальный шзп1ос »/ МР1 Сошв гапК(ИР1 СОИМ НОКЬР, йшугапй), 1п 1пбех = шугапк»ЬЕМ + зп зпбех, ИР1 Кебцсе(зп, оцп, 1, ИР1 РЬОАТ 1МТ, ИР1 И1МЬОС, гооС, савв); /» В этом пункте (точке), ответ постоянно находится на корневом процессе »/ 11(шугани == гоос) ( шзпча1 = оцс ча1це, в1пгапк = оцс зпбех / ЬЕМ, в1п1пбех = оцс зпбех % ЬЕМ, 6.10,4.
Редуцированная операция для всех МР1 включает вариант редуцированной операции, где результат возвращен всем процессам в группе. Все процессы, участвующие в этих операциях, получат идентичные результаты. ХР1 АЬЬВЕООСЕ(эепбЬцт, гесчЬцХ, соцпп, бапацуре, ор, савв) 1М вепбЬцй адрес передаваемого буфера 00Т гесчЬцй апрес буфера приема 1М соцпс количество передаваемых элементов 1М басасуре тип перелаваемых элементов 1М ар операция 1М сопка коммуникатор гап ИР1 А11гебцсе(чозб» вепбЬцХ, Чотб» гесчЬц1, зпц соцпС, ИР1 Оасасуре басасуре, ИР1 Ор ор, ИР1 Сошш сошв) МР1 АЬЬВЕООСЕ(БЕМРВОР, ВЕСЧВОР, СООМТ, ОАТАТУРЕ, ОР, СОИМ, 1ЕВКОВ) <суре> БЕМОВОР(»), НЕСЧВОР(») 1МТЕОЕК СООМТ, ОАТАТУРЕ, ОР, СОМИ, 1ЕКВОК Операция такая же, как ИР1 КЕРЧСЕ, исключая то, что результат появляется в буфере приема у всех процессов группы сошв.
Эта операция могла бы быть выполнена операцией ЬгоабсаэФ. Однако прямое выполнение может быть лучшим шагом. В этом случае нужно быть осторожным, чтобы удостовериться, что все процессы получают тот же самый результат. РАВ„ВЬАЯ2(в, и, а, Ь, с, сопцц) зпсв, и, 11оас аП, ЬП Ы, 11оас сЫ, МР1 сова сова, /» Локальные полосы массивов »/ /* Результат »/ Пример 6.19. Вычисление произведения вектора на матрицу, которые распределены по всем процессам группы и ответ возвращается во всех процессах группы (см, также пример 6.16).
124 б. Коввекшивмме взаимодействия ( Т1оас вцнЫ ; Тип 1, /х Локальная вца х/ Хог()' = 0; ) < п, )++) 1 вшп[)'3 = 0.0; тог(1 = 0; 1 < в, т++) ( вшп[)1 = вшп[)3 + аЫ х Ь[з.,)); ) /х Глобальная еца х/ МР1 А11гебцсе(вца, с, и, МР1 ГЬОАТ, МР1 БОМ, соав); /х Возврашение результата всем узлам х/ гесцги; МР1 ЕЕОУСЕ БСАТТЕК[веиббцг,гесчЬцТ,гесчсоцицв,басасуре,ор,соуп) 1М веибЬцг адрес перелаваемого буфера ОПТ гесчЬцг адрес буфера приема 1М гесчсоцисв целочисленный массив 1М басасуре тип принимаемых элементов ор операция 1М сони коммуникатор (совпшийсасог) йис МР1 Вебцсе всацсег[чогбх веибЬцг, чопбх гесчЬцТ, Тип хгесчсоцисв, МР1 Оасасуре басасуре, МРХ Ор ор, МР1 Сова сова) МР1 НЕООСЕ БСАТТЕВ(БЕМОВОР, КЕСЧВУР, ЕЕСЧСООМТБ, ОАТАТЧРЕ, ОР, СОИМ,1ЕКЕОЕ) <суре> БЕМОВОР(х), КЕСУВУГ(х) 1МТЕОЕК ВЕСЧСООМТБ(х), ОАТАТУРЕ, ОР, СОИМ, 1ЕВВОК МР1.ВЕООСЕ БСАТТЕК действует, как будто она сначала делает поэлементно редукцию па векторе из сеции = Е; гесчсоцисвЫ элементов в посылавшемся буфере, определенном зеибЬцг, сеции и басапуре.
Вектор результатов — это и непересекающихся сегментов, где и — число процессов в группе сопи. Сегмент 1 содержит гесчсоцисвЫ элементов. ьй сегмент посылается процессу 1 и записывается в буфере приема, определенном гесчЬц1, гесчсоцицв[13 и басацуре. Пример 6.20. Вычисление произведения вектора на матрицу, которые распределены по всем процессам группы и возвращение ответа в распределенной матрице. Это иллюстри- руется на рис.