В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 48
Текст из файла (страница 48)
Главный цикл приведем здесь, а в других примерах будем обозначать его, как "вычислительная часть". С целью удобства везде предполагается, что двумерные массивы данных располагаются в памяти компьютеров по столбцам, т.е. элементы столбца располагаются в памяти непрерывно. Поэтому вместо передачи или приема столбцов будут передаваться или приниматься строки. Хотя в гл. 2 на рис. 2,10 приведена схема обменов для столбцов, суть алгоритма это не меняет. /ь Главный цикл задачи Лирихле.
фрагмент программы. ь/ еьоцЫе А[в+23 [и+23, ВЫ [п1; нььд1е(ь сопчегбеб) д /ь Выполнение четырехточечного шаблона ь/ 1ог()' = 1; ) <= в, )++) аког(д = 1; д <= и; д++) В[3 1) [д-13 = 0.25а(А[)) [д 11 + А[)) [д+11 + А[)-13 [д| + А[)+13 [Д); /ь Копирование результата обратно в массив А */ аког() = 1, ) <= в; )++) Хог(д = 1, д <= и, д++) А[)3 [д3 = В[)3 [д-13; /* Каждая ветвь узнает количество ветвейь/ МР1 Соппп здхе(сопип, р); /ь и свой номер от 0 до (вдве-1) */ МР1 Соппп гапК(савв, вугапК); Этот фрагмент программы описывает главный цикл итерационного процесса решения, где на каждой итерации значение в окрестности точки заменяется средним значением сумм значений ее соседних точек на предыдущем шаге итерапии.
Граничные значения не изменяются. В массиве В вычисляются значения следующей итерации, а в массиве А находится значения предыдущей итерации. Здесь приведен внутренний цикл, где выполнено большинство вычислений. В первой и последней строке, а так же в первом и последнем столбце двумерного массива А записаны граничные значения. 9.Х Задана Пирихяе. Явная ревностная схема для уравнения Пуассона 193 9.3.1.
задача Дирихле. Реализация обменов функциями МР1 веинй, МРх веоч Для получения безопасной версии этой параллельной программы при использовании блокированных функций обмена данными нужно построить соответствующую модель связи между процессорами. Все процессоры разбиваются на два подмножества: с четными н нечетными номерами. Модель обмена состоит в следующем. Напомним, что топология связи между компьютерами — линейка. Обмен выполняется н два полушага. На первом полушаге нечетные процессоры передают данные четным процессорам с номером, на единицу меньшим (в сторону уменьшения номеров в линейке), а четные принимают от них, т.е.
от процессоров с большими номерами. На втором полушаге обмен выполняется наоборот. Напомним, что массив данных в этом случае располагается по столбцам. Далее будут приведены более простые способы обменов данными. /« Обмен ланными в задаче Пирихле. Первая версия параллельной программы. * Топология — "линейка". »/ /« Вычислительная часть »/ /» Обмен граничными столбцами мекду ветвями программы х/ 11(шугаиН/2 == 1) /« Работа нечетных ветвей «/ /х Передается 0-я строка массива В к ветви шугаиК-1 «/ МР1 Беиб(В, и, МР1 РВОАТ, шугаиК-1, сая, сошш); /» Принимается ш-1-я строка массива В от ветви шугаиК-1 и записывается » в 0-ю строку массива А, начиная с первого элемента. «/ МР1 Весч(ФА[0) [13, и, МР1 РВОАТ, шугаиК-1, сая, сопки, всаспв); 11(шугаиК < р-1) /х Здесь р = количеству ветвей «/ /х Передается ш-1-я строка массива В к ветви шугаиК+1.
х/ * У р-й ветви нет соседней ветви с рангом шугаиК+1 , поэтому она * исключена из этого обмена »/ МР1 Веиб(ЙВ[ш-13 [03, и, МР1 Г1.0АТ, шугаий+1, сап, сопки); /» Принимается 0-ая строка массива В от ветви шугаиК+1 и « записывается в ш+1-ю строку массива А, начиная с первого элемента«/ МР1 Весч(А[и+13 [13, и, МР1 Г1.0АТ, шугаий+1, Сап, сопки, вСаСив); ) /« Работа четных ветвей »/ е1ве пХ(шугаиК < р-1) ( /х Принимается 0-ая строка массива В от ветви шугалН+1 и * записывается в ш+1-ю строку массива А, начиная с первого элемента.
» У р-й ветви нет соседней ветви с рангом шугаиН+1 , поэтому она « исключена из этого обмена «/ МР1 Весч(А[и+13 [13, и, МР1 РКОАТ, шугаиК+1, Сая, соппп, зСаСпв); /» Передается ш-1-я строка массива В к ветви шугаиК+1 »/ ИР1 Беиб(В[ш-13[03, и, мр1 Р(.ОАт, шугаик+1, сая, сошш); ) е1ве 1й(шугаиК > 0) ( /« Принимается ш-1-я строка массива В от ветви шугаиК-1 и « записывается в 0-ю строку массива А. 194 9.
Примеры параллельных программ * У О-й ветви нет соседней ветви с рангом вугаиК-1 , поэтому она » исключена из этого обмена »/ ИР1 Весч(А[01 [13, п, ИР1 ГЬОАТ, вугаиК-1, сай, сова, виаиив), /» Передается 0-ой столбец массива В к ветви вугапК-1 »/ МР1 Яеиб(В, и, ИР1 РЬОАТ, вугаи1с-1, саВ, совв), 9.3.2. Задача Дирихле.
Реализации обменов фуннпней Ирх веве1хесч /* Обмен данными в задаче Пирихле Вторая версия параллельной » программы Топология — "линейка" »/ /» Вычислительная часть »/ /» Обмен граничными столбпами между ветвями программы »/ тХ(вугаиК > О) ( /» Передается 0-я строка массива В к ветви вугапК-1 » и принимается в-1-я строка массива В от ветви вугаиК-1 и » записывается в 0-ю строку массива А * У О-й ветви нет соседней ветви с рангом вугаиК-1, поэтому она » исключена из этого обмена »/ ИР1 Яеидгесч(В, п, МР1 ГЬОАТ, вугаиК-1, сай, АВТОЛ Е13, и, МР1 РЬОАТ, вугаиК-1, пай, сова„всасив), 11(вугаиК < р-1) /* Здесь р = количеству пропессоров »/ ( /» Передается в-1-я строка массива В к ветви вугаиК+1 » и принимается 0-я строка массива В от ветви вугаиК+1 и » записывается в в+1-ю строку массива А »/ » У р-й ветви нет соседней ветви с рангом вугаиК+1 , поэтому она » исключена из этого обмена МР1 Яепс1гесч(В(в-11(О), и, МР1 Р1.ОАТ, вугаиК+1, тая, А[в+11Г1Л, и, ИР1 ГЬОАТ, вугаиК+1, Сая, савв, виаииз), Можно заметить, что программа стала значительно короче по сравнению с первым вариантом.
9.3.3. Задача Дирихле. Реализация обменов с использованием МР1 РноС ноЫ, пропессов /» Обмен данными в задаче Пирихле Третья версия параллельной * программы с использованием МР1 РВОС ИПЬЬ продессов » Топология — "линейка" »/ /» Вычислительная часть »/ /» Каждая ветвь находит своих соседей »/ 11(вугэдК == 0) 195 Р.Ю. Задача Лнрихле. Явная раэностная схема для уравнения Луоссоно 1етс = МР1 РВОС МУ(.1.; е1ве 1еХс = иугапК-1; Н (юугапй == р-1) гХВЬс = МР1 РВОС МО(.1., е1не гХВЬС = ЮугапК+1; /« Обмен граничными столбцами между ветвями программы «/ /« Передается 0-я строка массива В к ветви иугапК-1 « и принимается и-1-я строка массива В от ветви юугапК-1 и « записывается в 0-ю строку массива А «/ МР1 Вепбгесч(В, и, МР1 Г(ОАТ, 1етс, сан, А(ОЛ (11, и, МР1 Р1ОАТ, 1еХс, сап, союи, нсасцн); /« Передается т-1-я строка массива В к ветви юугапК+1 * и принимается 0-я строка массива В от ветви юугапК+1 и « записывается в и+1-й строку массива А */ «/ МР1 Бепогесч(В(и-1) (03, п, МР1„Г(ОАТ, г1ВПС, Саб, А(в+1~ (13, и, МР1 Р1.ОАТ, гйбпс, тая, союю, зсасцв); Объем программы сильно не изменяется, но она становится проще для понимания.
9.3.4. Задача Дирихле. Реализация обменов неблокированными функциями МРХ Хяеаб и ИРХ Ххеач Здесь поясняется использование неблокированных операций. Чтобы достичь максимального перекрытия между вычислением и обменом данными, связь должна быть начата как можно скорее и закончена, когда возможно. То есть передача данных должна быть инициирована, как только данные, которые будут посланы, доступны.
Прием данных должен быть инициирован, как только буфер приема может повторно использоваться. Передача должна быть закончена непосредственно перед тем, как посылающийся буфер должен повторно использоваться. И прием должен быть закончен непосредственно перед тем, как данные в буфере приема должны использоваться. Иногда перекрытие может быть увеличено путем переупорядочивания вычислений. /« Обмен данными в запаче Пирихле. Четвертая версия параллельной « программы с использованием неблокированных функций « Топология — "линейка".
«/ /« Каждая ветвь находит своих сосепей «/ 11(юугапК "=- О) 1еХс = МР1 РВОС МП11„ е1не 1е1с = юугапК-1; Н(юугапК == р-1) гХВЬС = МР1 РВОС М01.10 е1ве г1ВЬС = юугапК+1; /* Вычисление граничных строк массива В */ Хог(1 = 1; 1 <= и; 1++) 196 9 Примеры парах»»льнах проерамм ( В[01 [ь-13 = О 25» (А[ОД Ы + А[21 Ы + А[11 [т+11 + А[13 [з-13), В[ш-1) Ет-11 = 0 25» (А[ш3 [т-11 + А[шЛ [з+13 + А[ш-13 Ы + А[ш+1|Ы), /» Старт неблокированных функций для обмена граничными стрекани нежду » параллельныни ветвями »/ /» Передается О-я строка массива В к ветви шугаиК-1 »/ МР1 1Беиб(В, и, МР1 Г(,ОАТ, 1етс, сая, сошш, тес([03), /» Передается ш-1-я строка массива В к ветви шугаиК+1 »/ МР1 1Беиб(В[ш-13 ЕОЗ, и, МР1 Р(.ОАТ, гзбЬС, Сая, сошш, гец[1] ), /» Принимается ш-1-я строка пассива В от ветви шугаиК-1 и » записывается в О-ш строку пассива А »/ МР1 1Весч(А[03 [13, п, МР1 РЮАТ, 1етс, тая, сошш, тес)[23), /» Принимается О-я строка массива В от процессора шугаиК+1 и » записывается в ш+1-ю строку массива А »/ МР1 1йесч(А[в+11[13, и, МР1 Р(.ОАТ, гтВЬс, саб, сопки, тес(ЕЗЗ), /» Выполнение четырехточечного шаблона пля внутренних строк » массива В »/ Хог(3 = 2, 3 <= и 1, 3++) 1ог(т = 1, т <= и, з++) ВЕ)-П [т-11 = О 25» (АЕ)3 [т-13 + А[)1[т+1з + АЫ Е)-13 + АЫ Е)+11), /» Копирование результата обратно в пассив А »/ Хог() = 1, ) <= ш, )++) аког(т = 1, з <= и, т++) АЕ)Л Ез) = ВЕ)-1) Ез-13, /» Завершение оперзлий обмена граничными строкани »/ тот(т = О,т <= З,т++) МР1 Матс(ге9Ы , есасие ЕОД Ы ), Эта программа стала несколько длиннее предыдугцих, но в ней передача соседям вычисленных границ перекрывается с вычислениями.
Вначале все процессы вычисляют крайний левый и крайний правый столбцы массива В и после этого сразу запускают процессы передачи их соседям. Пока выполняется передача процессы продолжают вычислять остальные, внутренние, столбцы массива В. Таким образом, передача и вычисления осушествляются с перекрытием. 9.3.5, Задача Дирихле. Реализация обменов неблокированными функциями ИРХ Хвеас1 и ИРХ Ххеоч и функцией завершения ИРХ Иаяса11 Эта задача аналогична предыдугцЕ, но здесь используется функция завергления обменов МР1 Матса11. /» Обнен данными в залаче Лирихле Пятая версия параллельной * програмны и использованиеи неблокированных функций и функции » завершения МР1 Натса11 Топология — "линейка" »/ /» Каждая ветвь каходит своих соседей »/ тт(шугаиК == О) 1етс = МР1 РВОС МО11, е1ве 1еус = шугаиК-1, 9.3. Задача Пирихяе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
