В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 50
Текст из файла (страница 50)
Решение С//АУ методом Гаусса х приводят к диагонапьному виду свои строки. Ветвь, приводяшая свои строки * к диагональному виду, назовем активной, строка, с которой производятся х вычисления, так же назовеи активной. х/ аког(К = О; К < М; К++) /» Викл р — дики по компьютеран. (Все ветви "крутят" этот дикл). »/ аког(р = О; р < вйзе; р++) ( 1г(Мур == р) с /» Активная ветвь с номером Мур == р приводит свою строку с х нонером К к диагональному виду х Активная строка — К передается воен ветвям, »/ МАО = 1 О/МА(К1(з1зе»К+р3; аког(1' = М; ) >= з1ге»К+р; ) †) МАМ(дЗ = МА(КЛ()1 х МА0; аког() = О; ) <= М; )»») Чи = мА(К1(11; МР1 Всазг(У, М+1, МР1 РООВ1Е, р, сошш цг); тог(1 = К+1; 1 < И; 1++) 1 аког() = М; ) >= з1ке»К+р; ) †) МАЫ СЗ1 = МА(11()Л-МА(11(з1ке»К+РЛ»МА(К) С)3; /» Работа принимаюших ветвей с номерами Мур < р х/ е1яе Н(МуР < р) ( МР1 Всавг(Ч, М+1, МР1 0ООВЕЕ, Р, сова Ег); Хог(1 ~ К+1; 1 < Н; 1++) ( Хог(1 = М; ) >= з1хе»К+р; ) †) МАЫ ()1 = МАЫ ()3 — МАЫ Св1зе»К»р1»ЧС)3; /» Работа принимаюших ветвей с номерами МуР > р х/ е1зе 1г(МуР > р) ( МР1 Всаяс(Ч, М+1, МР1 000ВЕЕ, р, союш Ег); 1ог(1 = К; 1 < М; 1++) ( Хог() = М; ) >= вйгехК+р; ) †) МА[г1()3 = МА(П Сд1 - МАЫ1 з1зе»К+р1»ЧЦ3; /»Хог р »/ /»гог К »/ /х Обратный ход »/ /» Биклы по К и р аналогичны, как и при прямом ходе.
«/ аког(К1 = М-г, К = М-1; К >» О; К вЂ”,К1 — ) ( гог(р = вйие-1; р >= О; р — ) ( 1г(Мур == р) ( /» Работа активной ветви х/ В = МАГИ (М); МР1„Всазс(яй, 1, МР1 000ВЕЕ, р, союш Ег); аког(1 = К-1, 1 >= О; 1 †) МА Ы (М] -= МА (Ц 1МЗ»МА Ы (в1ие»К+рЛ; 204 9. Примеры параллельных программ /х Работа ветвей с номерами МуР < р л/ е1ве Н(Мур < р) ( МР1 Всаеп(ап, 1, МР1 ЭООВЕЕ, р, савв Ег); аког(1 = )с; 1 >= 0; 1 †) МА[Я [М3 -= ВхМА[г1 [ ване»)г+р3; /х Работа ветвей с номерамн Мур > р а/ е1ве 11(Мур > р) ( МР1 Всавг(ФВ, 1, МР1 ОООВЕЕ, р, савв яг); тот(1 = 'к1; 1 >= 0; 1 †) МА[з1[МЛ -= ВьМАЫ [в№хехх+рл; э /х гог р ь/ /л ~от Н */ /ь Все ветви засекают время и печатают ь/ ЕессйвеоЫау(йсч2, (есгисс сйвенопе*)0); би1 = (Сч2.тч вес — Сч1.Сч зес) х 1000000 + Сч2.гч инес — Сч1.Сч инес; ргйпСХ(ьМур = Я 11ве = '/Юп", Мур, бп1); /ь Все ветви печатают, для контроля, свои первые четыре значения корня х/ ргйпс1(ьМур = /б '/1 И /1 '/Х~п", МуР, МА[0)[Мз,МА[11 [МЛ,МА[23[ИЛ,МА[33 [МЛ); /х Все ветви завершают выполнение */ МР1 Рйпа11хе(); гесигп(0); 9.5.
Решение СЛАУ методом простой итерации В алгоритме, представленном в данном пункте, исходная матрица коэффициентов А я вектор правых частей Г разрезаны горизонтальными полосами, как показано на рис. 2.9. Каждая полоса загружается в соответствуюший компьютер: нулевая полоса — в нулевой компьютер, первая полоса — в первый компьютер, и т.д., последняя полоса — в р1 компьютер. В примере предполагается, что матрица. коэффициентов А и вектор правых частей г разрезаны на части заранее и каждая ветвь считывает свои части с дисковой памяти.
Здесь, в примере, каждая ветвь генерирует свои части матрицы. Схемы распределения данных по компьютерам приведены в и. 2.4.1. Вид уравнения н обшая схема решения представлены в и. 2.5. /а х Решение СВАУ методом простой итерации. Распрепеленне данных— « горизонтальными доносами. (Запуск задачи на 8-ми компьютерах), х/ №Апс1ибе<всбйо . *и> №Апс1ибе<врй.б> №1пс1ибе<сйве.й> №йпс1иде<вуе/сйве.п> /а Каждая ветвь залает размеры своих полос матрицы МА и вектора правой части. * (Предполагаем, что размеры данных делятся без остатка на количество * компьютеров.) */ №бегйпе М 64 №бе11пе М 8 №бегйпе Е1(х) (вйзео1(х) / вйяео1(к[01)) №с1еХ1пе АВЯ(Х) ((Х) < 0 ? -(Х) : (Х)) 205 9.о.
Решение СЛАУ методом простой итерации /» Задаем необходиную точность приближенных корней »/ вс1е11пе Е 0.0001 /» Задаем шаг итерации »/ йбе11пе Т 0.1 /» Описываем массивы для полос исходной матрицы — МА, вектора правой части — Р, » значения приближений на предьшушей итерации — У и текушей — У1, результата « умножения матрицы коэффициентов на вектор — Я, и всего вектора значения » приближений на прельшушей итерации — Ч «/ вСаС1с с)оное МА[В] [М], у[И], У[И], У1[Н], Я[В], Ч[М]; ьпс вайп(1пс агяс, сваг »«агяч) ( 1пс ), г, Н, МуР, зйге, ч; 1пс »1пйех, «ебВез; МР1 Сова савв яг; всгцсс сйвеча1 сч1, сч2; /* Лля засечения вренени »/ 1пс бс1; 1пс геогб = 1; /» Инициализапия библиотеки »/ МР1 1птС(йагяс, йагнч); /» Каждая ветвь узнает размер системы »/ МР1 Савв вйге(МР1 СОИМ ЫОВ(.Р, йвйге); /» и свой номер (ранг) »/ МР1 Савв гал)с(МР1 СОММ 'йОВ(.Р, йМуР); /» Выделяем память под массивы для описания вершин и ребер в топологии « полный граф */ ьпс)ех = (1пс «)ваПос(зйге « в1гео1(ьпс)); е6яев = (1пс »)ваПос(в1ге»(в1ге-1)«в1гео1(1пс)); /» Заполняем массивы для описания вершин и ребер для топологии » полный граф и залаем топологию "полный граф".
»/ аког(1 = О; 1 < зйге; 1++) ( 1пбех[1] = (зйге — 1)«(1 + 1); ч= О; 1ог() = 0; ] < в1ге; ]++) ( 11(1 != ]) ес)пел[1 «(вйге — 1) + ч++] ) МР1 Огарй сгеасе(МР1 СОНМ ИОВЫ, в1ге, 1пбех, ес)йев, геогс), йсовв яг); /» Каждая ветвь генерирует свои полосы матрицы А и свой отрезок вектора » правой части. (По диагонали исходной матрицы - числа = 2, остальные числа = 1). »/ аког(1 = 0; т < М; 1++) ( йог() = О; ] < М; ]++) ( 11((М»МуР + 1) == )) МА[ь][]] = 2.0; е1ве МА[1] []] = 1.0,' Р[1] =М+1; ) /* Каждая ветвь засекает начало вычислений и производит вычисления «/ Весс1веоЫау(йсч1, (зсгисС сьвеголе»)0); /» Каждая ветвь задает начальное приближение корней.
»/ 206 9. Примеры параллельных проерамм Тот(д = О, з. < Н, д++) У1Ы =08, /* Начало вычислений »/ з1о С аког(д = О, д < Н, д++) СНЫ =ОО, УЫ = У1Ы, /» В кажной ветви формируем весь вектор предыпушей итерации и умножаем * матрицу коэффициентов на этот вектор »/ МР1„А11яасЬег(У, Е1(У), МР1 ОООВЬЕ, У, ЕЬ(У), МР1 ООУВЬЕ, сошш цг), дог() = О, ) < Н, )++) тот(д = О, д < М, д++) ВГ)3 += МАГ)> [д3» УЫ, выо, /* Флаг завершения вычислений всеми ветвями »/ Тот(д = О, д < Н, д++) С У1Ы = УЫ вЂ” т*(БЫ вЂ” ГЫ), дт(АВБ(АВЗ(У1Ы) — АВЯ(УЫ)) > е) и=1, /» Суммируем все флаги (по всем ветвям) и результат записываем в Н в » каждой ветви »/ МР1 А11гебпсе(вя, вН, 1, МР1 1НТ, МР1 БОМ, сошш цг), нЬд1е(Н > 0), /» Все ветви засекают вреня и печатают »/ ВессдшеоТз1ау(йсч2, (всгцсс сзшехопе*)0), нс1 = (сч2 сч„вес — сч1 сч вес) » 1000000 + сч2 сч цвес — сч1 сч цвес, ргдпс1(иМур = %д Тзлае = %ез'дп", МУР, е)с1), /* Все ветви печатают, для контроля, свои первые четыре значения корня »/ ргдпСд("Нех Мур = %е1 УО=%1 У1=%д У2=%т УЗи%д'дп", МуР,У(01,У(13,УЫ .У(33), /* Все ветви завершают выполнение »/ МР1 Гдпа1две(), гесцгп(0).
9,6. Упорядочивание множеств Алгоритм, представленный в данном пункте, упорядочивает заданные множества чисел по возрастанию (убыванию). Части исходного множества, расположенные в каждой ветви, должны быть неизменными как н процессе упорядочивания, так и в конечном итоге, /» » Упорядочивание множеств чисел (Запуск залачи на 8-мн компьютерах) »/ Фдпс1цйе<всНдо Ь> №длс1цйе<шрд Ь> №дпс1цде<сдше Ь> №дпс1це1е<вув/сдше Ь> /* Каждая ветвь залает размеры своих частей множества (Предполагаем, что размеры данных делятся без остатка на У.б.
Упорядочивание миожеете 207 * количество компьютеров.) »/ №пег1пе М 80 /» Задави размерность декартовой топологии. * Задачу решаен на топологии "линейка", »/ №оет1пе МОМ 01МЯ 1 /» Каждая ветвь задает массив для своей части нножества. »/ всасйс 1пс ММО)(М3; /» Подпрогранна генералки пелых чисел и их упорядочивания по возрастанию. »/ Оепегас(йпс гп) (1пс1, К, Й; згап6(( гп + 1 )»(ппз18пеб)С1ше(О)); аког(1 = О, 1 < М; 1++) ММО5[11 = 1 + гапп()У10000; Оо (К=О; Хог(1 = 0; 1 < М-1; 1++) С 11(мма,)В+1] < мма)Ы) ( М = ММОЗ(1Л; ММО)Ы = ММОЛЬ+13; ММО55+13 = й; К=1; ыЬ11е(К > 0); /» Подпрограмма вставки пелых чисел в ММО), начиная с большего при рг == 1, * и их упорядочивания по возрастанию, и вставки, начиная с неньшего при » рг == О, и их упорядочивания по возрастанию.
»/ Чвлач(йпт рг, 1пп сЬ) ( 1пс 1, К; К= 0; 11(рг == 1) ( Хог(1 = 1; 1 < М; 1++) ( 1~(ММО)СМ-1-1~ <-" сЬ) ( ММО)ЕМ-Л = сЬ; К=1; Ьгеаь; е1ве Имаев(М-П = ММОЛГМ-1-13; 1Х( К =и 0 ) ММОП01 = сЬ е1ве 1 Хог(1 = 1; 1 < М; 1++) ( 11(ИМОЕ(13 >= сЬ) ( ММО.)Б-11 = сЬ; К=1; ЬгеаК; е1зе 208 9 Примеры параллельных программ ММО)[т-13 = ММО)Ы , 11( К == 0 ) МЙО)[М-11 = сЬ, йка" ь/ х/ бо ) ) /л Главная програмна л/ тпс вата(тпп агяс, спаг ееагяч) ( тпт т, з, Н, ВВ, ВМ, МАХ, М1И, тпс Мур, зтзе, беяпв, вопгв, беясЬ, зопгЬ, тпп бтшя[КОМ 01МЯ, регтобв[ЖОМ 01МЯ, пен соогбя [БОМ 01МЯ3, тпп геогбег = О, МР1 Соппп савв сага, МР1 Япаппз вс, впгцсп ттшеча1 Пч1, Пи2, /ь ))пя засечения времени */ тпй бп1, /ь Инипиализапия библиотеки ь/ МР1 1пгт( йагйс, 3аагяп ), /ь Кажная ветвь узнает размер системы л/ МР1 Соппп втяе(МР1 СОИМ ЫОВ10, ввгве), /* и свой номер (ранг) */ МР1 Савв гапК(МР1 СОММ НОВЕГО, йМур), /ь Обнупяем массив б1шз и запопняем массив регтобз пля топологии "лине 1ог(1 = О, т < МОМ 01МЯ, 1++) ( б1ввЫ = О, регтобя[11 = О, /л Заполняем массив бтвв, гпе указываются размеры (опномерной) решетки МР1 0твз сгеате(ягве, ИОМ 01МЯ, б1вз), /* Сознаем топологию "линейка" с сошвпптсасог(ом) совш сага */ МР1 Сага агенте(МР1 СОИМ ЫОВ10, ИУМ 01МЯ, бпвв, регтобв, геогбег, мсошв сага), /ь Отображаем ранги на коорпинаты компьютеров, с пенью оптимизапии е отображения запанной виртуапьнай топологии на физическую топологию ь системы л/ МР1 Сага соогбя(совш сага, Мур, НОМ 01МЯ, пеи соогбв), /* Кажная ветвь нахопит своих сосепей вновь линейки Ф/ 11(пеи соогбв[03 == О) ( бевпш = вопгв = МР1 РВОС ИОЫ., беятЬ = зопгЬ = 1, е1зе т1(пеы соогбв[03 == я1зе-1) ( бевтв = воцгв = втзе-2, безсЬ = яопгЬ = МР1 РВОС М01.1., ) е1зе ( безпв = зопгв - "пен соогбв[03-1, беяСЬ = заагЬ = пен соогбв[03+1, /* Кажная ветвь генерирует в МИО) свою часть множества целых чисел и э упоряпочивает их по возрастанию е/ Оепегас(муР), /л Засекаем начальный момент времени ь/ дЕССПВЕО1бау(пти1, (ВСГПСП ПтшЕЗОПЕл)0), 9.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
