В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 6
Текст из файла (страница 6)
Поскольку время обменов равно нулю, а время загрузки и выгрузки здесь не учитывается, то общее время вычислений будет равно 2" = (С + В)((р * р ). И отношение времени "вычислений без обменов" к общему времени вычислений есть величина К = (У+ Я)/(Г+ Я) = 1. Здесь значения Т, К, У и Я вЂ” см. в п. 2.2.1. 2.2.3. Алгоритм 3 Лля больших матриц время вычисления произведения может быть уменьшено применением алгоритма, который осуществляет вычисление на трехмерной (пространственной) сетке компьютеров. В приведенном ниже алгоритме осуществляется отображение основных данных объемом п1 х пз+пз х пз+п1 х пз на объемную сетку компьютеров размером р1 хрз хрз. Матрицы разрезаны, как показано на рис.
2,5: матрица А — на р1 х рз субматрипы, матрица  — на рз х рз субматрицы и матрица С разрезана на р1 х рз субматрицы. Компьютер (г, 1', Й) вычисляет произведение субматрицы (г, 1) матрицы А и субматрицы (~, й) матрицы В. Субматрица (1, и) матрицы С получается суммированием промежуточных результатов, вычисленных в компьютерах (1,у, й), у = О,..., рз — 1.
рз рз х Рг = Р1 В С Рис. 2.5. Разрезание данных для параллельного алгоритма произведения двух матриц при вычислении в 30 решетке компьютеров Последовательные стадии вычисления иллюстрируются на рис. 2.6. 1. Субмэтрицы А распределяются в (з, у, О) плоскости. 2. Субматрицы В распределяются в (О, у, з) плоскости. 3. Субматрицы А распространяются в измерении г. 4.
Субматрицы В распространяются в измерении х. 5. Каждый процесс вычисляет одну субматрнцу. б. Промежуточные результаты редуцируется в измерении у. 7. Матрица С собирается из (х,О,г) плоскости. Этот алгоритм похож на предыдущий, но дополнительно разрезаются еше полосы матриц, и эти разрезанные полосы распределяются в третьем измерении у. В данном случае в каждом компьютере будут перемножаться только части векторов строк матрицы А и части столбцов матрицы В и в результате будет только частичная сумма для каждого В Схемы параллельных алеорввзлгое задач 18 1. Ясвмег А воордмна ты 3.
Вговдсезс подмвтриц из А 2. Ясвмег В 5. Вычисление произведений (подматриц из С) 4. Вговбсезз подматриц из В 7. Саспег С (сбор результатов) 6. Ведшее произведений (суммирование произведений) Рис. 2.6. Стадии вычислений в ЗР параллельном алгоритме произведения мвтрип Т = (~У+ ~)/(рз з рз *рз). А отношение времени "вычислений без обменов" к общему времени вычислений есть величина К = (У+ Я)ДУ+ Я) = 1, Значения Т, К, У и 5 — см.
ранее. элемента результирующей матрицы С. Операция суммирования вдоль координаты у этих полученных частичных сумм для результирующих элементов и завершает вычисления матрицы С. Этот алгоритм для больших матриц является еще более эффективным, чем предыдущий. Соотношения для общего времени вычислений в этом алгоритме будет равно х.З.
Задача Лиихле. Явная раэнастная схема для уравнсния Пуассона 19 2,3. Задача Дирихле. Явная разностная схема для уравнения Пуассона В прямоугольной области О < х < а, О < у требуется найти решение уравнения: дзи дзи — + — =Их у) дхз дуя прн заданных значениях функции и на границе. Явная разностная схема решения этого уравнения имеет вид: и О 25э (и' 1 + ц+1 т+ и~ ~и — 1 + ивт+1 ~ вин)~ где и; и д; — значения функций и в точке разностной сетки. Ниже представлен главный фрагмент программы итерационного решения задачи.
цоцЫе АЬ+23 1т+21, ВЕп3 Ьй; /в Главный цикл в/ ип11е(! сопчегцеб) /в выполнение схемы "крест" в/ 1ог() = 1; ) <= а; )++) 1ог(1 = 1; 1 <= п; 1++) В(1-11 С)-13 = О. 25*(А(1-11 С))+А(1+13 Е))+А Ы Ц-1)+АЫ 3+1) ); /* копирование результата обратно в массив А в/ 1ог() = 1; ) <= а; )++) Хог(1 = 1; 1 <= и; 1++) АЫ()) = ВИ-Й Гд-П; Этот фрагмент программы описывает главный цикл итерационного процесса решения, где на каждой итерации значение в окрестности точки заменяется средним значением сумм значений ее четырех соседних точек на предыдущем временном шаге итерации (рис.
2.7). н+1 — слай по времени и — слой ло времени 1, /с1 Рис. 2.7. Вычисление точки через значения точек на предыдушем шаге итерации Граничные значения не изменяются. В массиве В вычисляются значения следуюшей итерации, а в массиве А находятся значения предыдушей итерации.
Здесь приведен внутренний цикл, где выполнено большинство вычислений. В первой и последней строке, а также в первом и последнем столбце двумерного массива А записаны граничные значения. Алгоритм этой задачи имеет простую структуру, идентичную для всех точек пространства вычисления, поэтому здесь при построении параллельной программы целесообразно использовать метод распараллеливания по данным. Массивы "разрезаются" на части, затем в каждый процессор загружается программа, аналогичная последовательной программе, но с модифицированными значениями индексов циклов и соответствующая часть массива данных, т.е.
каждый процессор обрабатывает только часть данных. Части данных соответственно упорядочены. 20 й. Схемы параллельных алгоритмов задач Способы разрезания данных могут быть разные, и в зависимости от способа разрезания данных будут и разные схемы взаимодействий между параллельными процессами. Распределение данных по процессорам должно быть сбалансировано. Связь между процессорами должна быть минимизирована. двумерный массив может быть разрезан на части как в одном измерении, так и в двух измерениях. Рис. 2.8 поясняет эти способы разрезания данных: 11) разрезание— матрица разрезана в одном измерении полосами и 20 разрезание — матрица разрезана в двух измерениях.
1Р разрезание 2Р разрезание Рис, 2.8. Лва разных способа разрезания двумерного массива на блоки На рисунке матрица разрезана на четыре блока; каждый блок обрабатывается в отдельном процессоре. Так как связь между процессорами осуществляется границами блоков, то объем связи минимизирован в 20 разрезании, которое имеет меньший периметр области связи. В этом разбиении каждый процессор взаимодействует, в общем случае, с четырьмя соседями быстрее, чем два соседа в 1Р разрезании. Когда отношение п(Р 1Р— число процессоров) маленькое, время связи будет зависеть от внешних коммуникаций, и первое разбиение будет лучше по взаимодействиям. Когда это отношение большое, второе разбиение лучше по взаимодействиям.
Здесь используется первое разбиение. Значение каждой точки в массиве В вычисляется через значения четырех ее соседей в массиве А. Связь между процессорами необходима границами блоков, чтобы вычислять граничные точки блоков через свои соседние точки, которые принадлежат другому процессору. Так как точки вычисляются через только свои соседние точки, вычисленные на предыдущей итерации, то для вычисления граничных точек блока необходимо присутствие копии соответствующего столбца предыдущей итерации соседнего блока, находящегося в соседнем компьютере.
Следовательно, при Ю разрезании необходимо распределение блоков массива А по компьютерам с перекрытием в один столбец. Таких перекрытий столбцами для массива В не нужно — это следует из алгоритма. На рис. 2.9 иллюстрируется перекрытие соседних полос в один столбец: римскими цифрами обозначены крайние столбцы соседних полос, пунктирной линией — граница разреза массива данных. ! ! ! ! ! ! ! ! ! П 1 П ! 1 П ! иачольиый разрез массива данных перекрытие полое в один столбец Рис. 2.9.
Перекрытие двух полос в один столбец х.Ж Задача барахле. Явнав ревностная схема для уравнения Пуассона 21 Процесс О О т+1 О Процесс 1 О т+1 Процесс 3 О т+1 и+1 Рвс. 2.10. Перекрытие 1Р блоков в массиве А и пересылка столбцов в конце каждой итерации Алгоритм и схема обменов данными аналогичны и при 21) разрезании массивов. В этом случае обмен данными будет осуществляться с четырьмя соседними компьютерами.
Подобно этой задаче аналогичным методом распараллеливания по данным решаются итерационные задачи размерности больше трех. На рис. 2.10 показаны дополнительные столбцы массива А и то, как данные пересылаются после каждой итерации. Перекрытие одним столбцом обычно используется для разпостной схемы, представляемой пятиточечным шаблоном сетки. Лля разностной схемы, использующей девятиточечный шаблон сетки, необходимо делать двух столбцовое перекрытие полос массивов, находящихся в смежных компьютерах. В общем случае, если рассматривается окрестность с диаметром в Й точек от вычисляемой точки на предыдущем шаге вычислений, то перекрытие массивов нужно делать в Й столбцов. Фрагменты программ рассмотренного здесь параллельного алгоритма приведены в гл.
9. Выше приведена общая схема параллельного алгоритма решения задачи. При реализации этой схемы могут использоваться разные языковые средства МР1, приспосабливающие программу к вычислительной системе. В гл. 9 приведено несколько разных фрагментов программ решения рассмотренной задачи, демонстрирующих возможности конструкций МР1, в частности, возможность совмещении пересылок данных с вычислениями, При этом способе в каждом процессоре вначале вычисляются граничные точки массивов, после чего запускается процесс передачи этих граничных точек соседним компьютерам и затем продолжается вычисление внутренних точек массивов. При этом передача данных и вычисления будут частично перекрываться во времени. Эффективность этого алгоритма зависит от соотношения количества обрабатываемых точек в каждом компьютере к количеству передаваемых компьютером граничных точек соседним компьютерам.
Эффективность, конечно же, зависит и от самого алгоритма, например, вычисления организуются с перекрытием обменов данными или без перекрытия. Практика показывает, что подобные задачи решаются параллельными методами очень эффективно, т.е. временные затраты на обмен данными в процентном соотношении ко всему времени решения очень незначительны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
