В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 49
Текст из файла (страница 49)
Явная ревностною схема для уравнению Пуассона 197 1т(шугани == р-1) гйййс = МР1 РВОС МП11.; е1зе гйбйс = шугаи)с+1; /« Вычисление граничных строк пассива В «/ 1ог(1 = 1, 1 <= и; 1++) ~ В[0] [1-1] = 0.2Б «(А[0] [1] + А[2] [1] + А[1] [1+1] + А[1] [1-1]); В[ш-1] [1-1] = 0.2Б «(А[ш] [1-1] + А[ш] [1+1] + А[ш-1] [1] + А[и+1] [1]); /« Старт неблокированных функций для обмена граничными строками между « параллельными ветвями «/ /« Передается О-я строка массива В к ветви шугаи)с-1 «/ МР1 1Беио(В, и, МР1 ГВОАТ, 1еХс, Фай, сошш, геП[0]); /« Передается ш-1-я строка массива В к ветви шугаиц+1 «/ МР1 1Беиб(В[ш-1][0], и, МР1 Р(.ОАТ, гйбии, саб, сошш, гео[1]); /« Принимается ш-1-я строка массива В от ветви шугаий-1 и * записывается в 0-ю строку массива А «/ МР1 1Весч(А[О][1], и, МР1 Р(.ОАТ, 1етС, Саб, сошш, гас[2]).; /« Принимается 0-я строка массива В от процессора шугаик+1 и « записывается в ш+1-ю строку массива А «/ МР1 1Весу(А[и+1][1],и, МР1 Р1ОАТ, г~БАС, Саб, сошш, гео[З]); /« Выполнение четырехточечного шаблона для внутренних строк массива В «/ Хог()' = 2; ] <= ш-1; )++) Хог(1 = 1; 1 <= и; 1++) В[]-1] [1-1] = 0.25 * (АЦ] [1-1] + А[)] [1+1] + А[1] []-1] + А[1] [9+1]); /« Копирование результата обратно в массив А */ 1ог() = 1; ] <= ш; ]++) Хог(1 = 1; 1 <= и; 1++) А[]][1] = В[]-1][1-1]; /* Завершение операций обиена граничными строками «/ МР1 Иайса11(4, гео, зсасци); Эта программа та же самая, что и в предыдушем примере.
Здесь заменены четыре вызова функции МР1 на1т одним вызовом функции МР1 на1са11. 9.3.6. Задача Пирнхле. Реализации обменов функциями предварительной инициализации обменов Фач Пеа<й з аАЕ и МВХ Цеоч шайи Здесь используются функции предварительной инициализации обменов данными ИР1 Беиб 1ийс и МР1Лесч 1ийс, ускоряюшие обмен данными. /« Обмен данными в запаче Лирихле. Шестая версия параллельной « программы с использованием функций предварительной инициализапии « обменов МР1 Беиб 1ийс и МР1 Весу 1ийс. Топология — "линейка", «/ /« Каждая ветвь нахопит своих соседей «/ 11(шугаи)с == 0) 1еХс = МР1 РВОС Ий(.1; е1ве 198 р. Примеры параллельных программ 1еТс = шугаи)с-1, дт(шугаи)с == р-1) гдбпс = МР1 РЕ)С М~Е, е1зе гд8)гп = шугаи)с+1, /« Инициализация функций обмена данными«/ МР1 Яеиб дидс(В, и, МР1 Р(.ОАТ, 1е1с, саб, сова, тес)[О]), мР1 яеид дидс(В[ш-1)[О), и, мР1 РыАт, гдбьс, садсопап, гес1[1)), МР1 Кесп дидс(А[О)[1], и, МР1 Р|ОАТ, 1е1с, да8, соппп, гей[2)), мр1 Веси дидс(А[и+1][1], и, мР1 Р).ОАт, гдйьс, пай, сошш, гес)[з]), /« Вычисление граничных строк массива В «/ аког(д = 1, д <= и, д++) ( В[О] [ -1] = О 28«(А[О) [д]+А[2] [д]+А[1] [д+1)+А[1] [ -1]), В[ш-1) [д-1) = О 25«(А[ш) [д-1)+А[и] [д+1)+А[и-1) Ы+А[ш+1] Ы), /« Старт функций пля обмена граничными строками между параллельными ветвями «/ МР1 Япагпа11(4, геа), /« Выполнение четырехточечного шаблона для внутренних строк массива В «/ дог() = 2, ) <= ш-1, 1++) аког(д = 1, д <= и, д++) В[)-1] [д-1] = О 28«(А[)) [д-1]+А[)) [д+1]+АМ [)-1)+АЫ [)+1]), /« Копирование результата обратно в массив А «/ аког() = 1, ) <= ш, )++) тог(д = 1, д <= и, д++) А[1]Ы = В[)-1][д-1], /« Завершение оперэлий обмена граничными строками «/ МР1 надса11(4, гес), всадив), 9.4, Решение СЛАУ методом Гаусса Здесь рассматриваются два алгоритма решения СЛАУ методом Гаусса.
Они связаны с разными способами представления данных (матриц коэффициентов и правых частей) и распределенной памяти мультикомпьютера. Схемы распределения данных по компьютерам приведены в гл. 2 для обоих примеров. Хотя данные распределены в памяти мульти- компьютера в каждом алгоритме по-разному, но оба они реализуются на одной и той же топологии связи компьютеров — "полный граф". Топология "полный граф" обладает одной нехорошей особенностью, а именно, с ростом количества компьютеров в системе увеличивается и время выполнения коллективной операции обмена данными. Поэтому при решении этой задачи, нужно выбрать оптимальное соотношение между объемом данных н размером вычислительной системы.
И это соотношение зависит от скорости обменов между компьютерами. 9.4.1. Решение СЛАУ методом Гаусса. Первый алгоритм В алгоритме, представленном в данном пункте, исходная матрица коэффициентов А и вектор правых частей г' разрезаны горизонтальными полосами, как показано на рис. 2.9. Каждая полоса загружается в соответствующий компьютер: нулевая полоса — в нулевой компьютер, первая полоса — в первый компьютер и т. д., последняя полоса — в р1 компьютер. В примере предполагается, что матрица коэффициентов А и вектор правых частей г" разрезаны на части заранее и каждая ветвь считывает свои части с дисковой памяти. 199 9.».
Решение СЛАУ методом Гоуеео Здесь, в примере, каждая ветвь генерирует свои части матрицы. Схемы распределения данных по компьютерам приведены в п. 2.4.1. /» Первый алгоритм » Решение СЛАУ методом Гаусса Распрелеление данных — горизонтальными полосами » (Запуск задачи на 8-ми компьютерах) »/ №1пс1пбе<зпб1о и> №1пс1пбе<шрг 'и> №1пс1пбе<зуз/сгше Ь> /» Каилая ветвь задает размеры своих полос матрицы МА и вектора правой части (Предполагаем, что размеры данных делятся без остатка на количество » компьютеров ) »/ №бе11пе М 400 №беХгпе М 50 №бейгпе тея0 1 №бетгпе ЕЕ(х) (згхеоХ(х) / з1зеоХ(х[ОЛ)) /» Описываем массивы лля полос исходной матрицы — ИА и вектор Ч пля приема » ланных Пля простоты, вектор правой части уравнений присоединяем » дополнительным столбцом к матрице коэффициентов В этом дополнительном « столбце и получим результат »/ бопЫе МА[И1 [И+11, Ч[М+11, МА0, В, 1пс шагп(1лс агйз, сваг »»агйч) ( 1пс з1зе, МуР, 1, ), ч, к, б, р, тпс »гпбех, »ебиез, МР1 Сошш сошш пг, МР1 Бсаспз зсаспз, зсгпсс сгшеча1 сч1, сч2, гпс бс1, 1пс геогб = 1, /» Инициализация библиотеки »/ МР1 1пгс(йагяз, йагяч), /» Каилая ветвь узнает размер системы »/ МР1 Сошш з1хе(МР1 СОИМ НОВЫ, йз1хе), /» и свой номер (ранг) »/ МР1 Сошш гап)г(МР1 СОММ НСВТ.О, зМУР), /» Выделяем память поп массивы для описания вершин и ребер в топологии » полный граф »/ 1пбех = (1пс »)ша11ос(згзе » згхеог(гпФ)), ебяез = (1пс »)шаПос(згхе»(зтзе-1) » згхео1(1пс)), /» Заполняем массивы пля описания вершин и ребер ппя топологии * полный граф и залаем топологию "полный граф" «/ аког(1 = О, г < згзе, 1++) ( тпбех[г) = (згке — 1)»(1 + 1), ч=О, Хог(1 = О, ) с згге, 1++) ( ~10 '= )) ебпез[1» (з1хе — 1) + ч++3 = ), ) МР1 Огарй сгеапе(МР1 СОИМ НОВЫ, з1хе, гпбех, ебяез, геогб, йсошш яг), 200 9.
Примеры оороллельнаг программ /» Каждая ветвь генерирует свою полосу матрицы А и свой отрезок вектора « правой части, который присоединяется дополнительным столбцом к А « Нулевая ветвь генерирует нулевую полосу, первая ветвь — первую полосу * и т д (По диагонали исходной матрицы — числа = 2, остальные числа = 1) «/ аког(т = О, т < М, т++) С аког() = О, ) < М, )++) ( тХ((М«Мур+т) == )) МА[т3 [)3 = 2 О, е1яе МАЫ[)3 = 1 О, МАЫ [М3 = 1 О«(М)+1 О, /* Каждая ветвь засекает начало вычислений и производит вычисления «/ Еесствеохбау(мсч1, (ясгцсс ствезопе«)О), /« Прямой ход «/ /« Пикл р — цикл по компьютерам Все ветви, начиная с нулевой, последовательно « приводят к диагональному виду свои строки Ветвь, приводяшая свои строки « к диагональному вицу, назовем активной, строка, с которой производятся « вычисления, так же назовем активной »/ аког(р = О, р < ятзе, р++) с /« Пикл К вЂ” цикл по строкам (Все ветви "крутят" этот цикл) */ Хог(К = О, К < М, К++) ( тХ(Мур == р) ( /« Активная ветвь с номером Мур == р приводит свои строки к « диагональному виду » Активная строка К передается ветвям, с номером большим чем МуР«/ МА0 = 1 О/МА[К3 [И*р+К3 аког() = М, ) >= И«р+К ) — ) МА[К3 [)3 = МА[К3 [)3 * МАП, аког(о = р+1, 6 < ятяе, б++) МР1 Бепб(йМА[К3 [03, М+1, МР1 ПООВЕЕ, 6, сеЕП, совв Ег), Хог(~ = К+1, т < М, т++) ( аког() = М, ) >= М«р+К, ) †) МА Ы [)3 = МАЫ [)3 -МА Ы [М«р+К3 «МА[К3 [)3, /« Работа принимавших ветвей с номерами Мур > р «/ е1яе г1(Мур > р) ( МР1 Весч(Ч, ЕЬ(Ч), МР1 ПОПВЕЕ, р„ сеЕП, совв нг, йясатця), 1огй = О, я < М, т++) ( Хог() = М, ) >= И«р+К, ) †) МАЫ [)3 = МАЫ [)3-МАЫ [М«р+К]»Ч[)3, /* Хог К «/ /« бог р «/ /* Обратный ход «/ /* Пиклы по р и К аналогичны, как и при прямом ходе «/ Хог(р = ятке-1, р >= О, р †) ( ~ог(К = М-1, К >= О, К вЂ ) 9.4.
Решение СВАУ методом Гаусса 201 ( /е Работа активной ветви е/ Н(МуР == р) ( Хог(4 = р-1; б >= 0; 4 †) МР1 Яепб(ФМАВ) гМ1, 1, МР1 ООВВ1Е, б, сеп0, сошш яг); №ог(1 = К-1; 1 >= О; 1 — ) МАЫ (МЗ -= МАВЗ ЕМЗеМАЫ (Мер+К); /е Работа ветвей с номерами МуР < р е/ е1зе ( 11(МуР < р) ( МР1 Весч(кй, 1, МР1„00080Е, р, сея0, сошш яг, йзсевцз); аког(1 = М-1; 1 >= 0; 1 †) МА И (М) -= В*МА[1) Гйер+К1; /е йог К е/ /е аког р е/ /е Все ветви засекают время и печатают е/ яесс1шео1бау(йсч2, (зсгцсс сйшезопее)0); бс1 = (сч2.сч зес — сч1.сч„зес)е1000000 + сч2.сч цзес — сч1.сч пзес; РГ1ПСт'(еМур = %4 Т1ШЕ = %4Ы', Мур, бС1); /е Все ветви печатают, пля контроля, свои первые четыре значения корня е/ рг1пс~(еМур = %4 %1 %~ %1 %1~п-,МуР,МАГОЗ (М1,МА (1~ (М~,МА С23 СМЗ,МАЙЛЗ] СМ1); /е Все ветви завершают выполнение «/ МР1 Р1па11ке(); геспгп(0); ) 9.4.2.
Решение СЛАУ методом Гаусса. Второй алгоритм В алгоритме, представленном в данном пункте, исходная матрица коэффициентов А и вектор правых частей Р разрезаны циклическими горизонтальными полосами, как показано на рис. 2.11. Каждая полоса загружается в соответствуюший компьютер: нулевая полоса — в нулевой компьютер, первая полоса — в первый компьютер и т.д. В примере предполагается, что матрица А и вектор правых частей Р разрезаны на части заранее и каждая ветвь считывает свои части с дисковой памяти.
Здесь, в примере, каждая ветвь генерирует свои части матрицы. Схемы распределения данных по компьютерам приведены в и. 2.4.2. /е Второй алгоритм * Решение СЛАУ методом Гаусса. Распределение данных — циклическими * горизонтальными полосами. (Запуск запачи на 8-ми компьютерах). е/ №1пс1цбе<зсб1о.Ь> №йпс1цбе<шр1.Ь> №1пс1цбе<зуз/с1ше.Ь> /» Каждая ветвь залает размеры своих полос матрицы МА и вектора правой части. (Предполагаем, что размеры данных делятся без остатка на количество е компьютеров.) е/ №беХ(пе М 400 №бе11пе И 50 №ое11пе сея0 1 202 9 Примеры параллельиых программ /» Описываем массив для пиклических полос исходной матрипы - МА и вектор Ч для » приема данных Лля простоты, вектор правой части уравнений присоединяем » дополнительным столбдом к матрнпе коэффипиентов В этом дополнительном * столбпе и получим результат »/ бопЫе МАГМ1 ГМ+11, ЧГМ+1), МАО, К, хпс вахп(хпс агав, сваг »»агйч) 1 хпс вхге, МуР, т, ), ч, 1с, К1, р, 1пс »1пбех, »едяев, МР1 Сова сопел цг, зсгпсс схвеча1 сч!, сч2, тпс бс1, 1пс геогб = 1, /» Инипиализапия библиотеки »/ МР1 1пхС(йагйв, йагяч), /» Каждая ветвь узнает размер системы »/ МР1 Сопел втге(МР1 СОММ ИОК1.0, йв1ге), /» и свой номер (ранг) »/ МР1 Сопел гапк(МР1 СОММ 'лОК1.0, йМуР), /» Выделяем память под массивы для описания вершин и ребер в топологии » полный граф »/ 1пбех = »пп »)ша11ос(з1ге » з1геоХ »пС)), ее(йев = (хпС »)ва11ос(в1ге»(зхге-1)»в1геот(тпС)), /» Заполняем массивы для описания вершин и ребер для топологии » полный граф и задаем топологию "полный граф" »/ 1ог» = О, 1 < з1ге, 1++) ( 1пбехЫ = (в1ге — 1)»» + 1), ч= О, 1ог() = О, ) с вхге, )++) ( 1» =)) ебкевЬ * (з1ге — 1) + ч»+3 = ), ) МР1 Огарп сгеасе(МР1 СОММ ИОКИ, в1ге, 1пбех, едяев, геогб, йсовш яг), /» Каждая ветвь генерирует свои пиклические полосы матрицы А и свой отрезок » вектора правой части, который присоепиняется дополнительным столбпом к А » Нулевая ветвь генерирует слепуюшие строки исходной матрипы О, в1ге, » 2»з1ге, З»вхге, и т д Первая ветвь — строки 1, 1+зхге, 1+2»в1ге, 1+З»вгге » и т д Вторая ветвь — строки 2, 2+в1ге, 2+2»в1ге, 2+З»в1ге и т д » (По диагонали исходной матрипы — числа = 2, остальные числа = 1) */ Хог(а = О, х < М, х++) ( 1ог() = О, ) < М, )++) ( 11((МуР+зхге»1) == )) МАЫ[)3 = 2 О, е1ве МАЫ()1 = ! О, МАЫ СМ1 = 1 0»(М)+1 О, /* Каждая ветвь засекает начало вычислений и производит вычисления »/ ВеССппео1бау(йСч1, (зпгцсС Схвегопе»)0), /» Прямой ход */ /» Пикл )е — цикл по строкам Все ветви, начиная с нулевой, последовательно 203 94.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
