В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 5
Текст из файла (страница 5)
Мы видим, что распределение виртуальных компьютеров по физическим в этом случае уже другое, чем в первом случае. Таким образом, с помощью составления списка компьютеров пользователь может частично влиять на отображение виртуальных компьютеров на физические. 3. Пользователь может запускать параллельную программу, ветви которой реализуются разными программами и имеют разные имена. допустим, четыре ветви параллельной программы имеют имена: ргоягав. ехе, ргойгав1. ехе, ргойгав2.
ехе, ргобгавЗ ехе. И эти программы записаны в разные компьютеры н в разноименные директории !директории могут быть и одноименными). ргоцгэл. ехе в К1азс, в файл 111е, ргобгав1. ехе в 1нбс-а, в файл 111е1, ргобгав2.ехе в язе!, в файл 111е2, ргокгавЗ.ехе в ззд2, в файл ШеЗ. Список компьютеров может быть таким: К1аян.язсс.гп О Коше/паве/т11е/ тсе!с-а.ззсс.гп 1 Коше/паве/111е1/ ззд.язсс.гп 1 Коше/паве/111е2/ язе!2.ззсс гп 1 Коше/паве/111еЗ/ В этом случае в командной строке запуска программ из компьютера Пояс должно стоять имя ветви, стоящей в этом же компьютере. Например, если программа в приведенном примере запускается с компьютера К1азс, то имя программы в команде вр1гпп должно быть ргобгэл. ехе.
Я.я. Умножение матрмчм на лаврику 2.2, Умножение матрицы на матрицу Умножение матрицы на вектор и матрицы на матрицу являются базовыми макрооперациями для многих задач линейной алгебры, например итерационных методов решения систем линейных уравнений и т.п. Поэтому приведенные алгоритмы можно рассматривать как фрагменты в алгоритмах этих методов. В этом пункте приведено три алгоритма умножения матрицы на матрицу. Разнообразие вариантов алгоритмов проистекает от разнообразия вычислительных систем и размеров задач. Рассматриваются и разные варианты загрузки данных в систему: загрузка данных через один компьютер; и загрузка данных непосредственно каждым компьютером с дисковой памяти. Если загрузка данных осуществляется через один компьютер, то данные считываются этим компьютером с дисковой памяти, разрезаются и части рассылаются по остальным компьютерам.
Но данные могут быть подготовлены и заранее, т. е. заранее разрезаны по частям и каждая часть записана на диск в виде отдельного файла со своим именем; затем каждый компьютер непосредственно считывает с диска, предназначенный для него файл. 2,2.1, Алгоритм 1 Заданы две исходные матрицы А и В, Вычисляется произведение С = А х В, где А— матрица пг х пз, и  — матрица пз Х пз. Матрица результатов С имеет размер пз х пз. Исходные матрицы предварительно разрезаны на полосы, полосы записаны на дисковую память отдельными файлами со своими именами и доступны всем компьютерам. Матрица результатов возвращается в нулевой процесс.
Реализация алгоритма выполняется на кольце из р~ компьютеров. Матрицы разрезаны как показано на рис. 2.1: матрица А разрезана на рз горизонтальных полос, матрица  — на р~ вертикальных полос и матрица результата С разрезана на, рз полосы. Здесь предполагается, что в память каждого компьютера загружается и может находиться только одна полоса матрицы А и одна полоса матрицы В. А В С Рис.
2.1. Разрезание данных для параллельного алгоритма произведения двух матриц при вычислении иа кольце компьютеров. Выделенные полосы расположены в одном компьютере Поскольку по условию в компьютерах находится по одной полосе матриц, то полосы матрицы В (либо полосы матрицы А) необходимо "прокрутить" по кольцу компьютеров мимо полос матрицы А (матрицы В). Каждый сдвиг полос вдоль кольца и соответствующее умножение представлено на рис. 2.2 в виде отдельного шага. На каждом таком шаге вычисляется только часть полосы. Процесс ~ вычисляет на у-м шаге произведение г-й горизонтальной полосы матрицы А н у-й вертикальной полосы матрицы В, произведение получено в подматрице (~,у) матрицы С.
Текст программы, реализующий алгоритм, приведен в гл. 9. Последовательные стадии вычислений иллюстрируются на рис, 2.2. 1. Каждый компьютер считывает с диска соответствующую ему полосу матрицы А. Нулевая полоса должна считываться нулевым компьютером, первая полоса — первым компьютером и т.д., последняя полоса считывается последним компьютером. На рис. 2.2 полосы матрицы А и В пронумерованы. 2. Каждый компьютер считывает с диска соответствующую ему полосу матрицы В. В данном случае нулевая полоса должна считываться нулевым компьютером, первая полоса — первым компьютером и т.д., последняя полоса считывается последним компьютером.
1. Бсаььег А 2. Ясаыег В 7. Сбор результатов в С Рнс. л.2. Стадии вычислений произведения матриц в кольце компьютеров 3, Вычисли тельный Шаг 1 5. Вычисли тельный Шаг р1-1 х. Схемы параллельных алгоритмов задач 4. Вычисли тельный Шаг 2 6. Вычисли тельный Шаг р1 й.й. Умножение матрицы ни матрицу 15 3. Вычислительный шаг 1. Каждый процесс вычисляет одну подматрицу произведения. Вертикальные полосы матрицы В сдвигаются вдоль кольца компьютеров. 4. Вычислительный шаг 2.
Каждый процесс вычисляет одну подматрицу произведения. Вертикальные полосы матрицы В сдвигаются вдоль кольца компьютеров и т.д. 5. Вычислительный шаг рз — 1. Каждый процесс вычисляет одну подматрицу произве- дения. Вертикальные полосы матрицы В сдвигаются вдоль кольца компьютеров. б. Вычислительный шаг ры Каждый процесс вычисляет одну подматрицу произведения. Вертикальные полосы матрицы В сдвигаются вдоль кольца компьютеров. 7.
Матрица С собирается в нулевом компьютере. Если "прокручивать" вертикальные полосы матрицы В, то матрица С будет распределена горизонтальными полосами, а если "прокручивать" горизонтальные полосы матрицы А, то матрица С будет распределена вертикальными полосами. Алгоритм характерен тем, что после каждого шага вычислений осуществляется обмен данными. Пусть 1„, 1, и 1р — время операций соответственно умножения, сложения и пересылки одного числа в соседний компьютер. Согласна приведенным в начале пункта обозначениям суммарное время операций умножений равно й = (п1 е пз и пз) *1и, суммарное время операций сложений равно 5 Цп1 1)эпявпз)Фе суммарное время операций пересылок данных по всем компьютерам равно Р= (пзепз) и (р1 1)и1р ° Тогда общее время вычислений будет равно Т = (17+ Я+ Р)7*ры И отношение времени "вычислений без обменовн к общему времени вычислений есть величина К = (У+Я)/(П+5+ Р).
Если время передачи данныя велико по сравнению с временем вычислений, либо каналы передачи данных медленные, то эффективность алгоритма будет не высока. Здесь не учитывается время начальной загрузки и выгрузки данныи в память системы. В полосах матриц может быть разное количество строк (различие в одну строку). При больших матрицах этим можно пренебречь, При достаточных ресурсах памяти в системе, конечно же, лучше использовать алгоритм, в котором минимизированы обмены между компьютерами в процессе вычислений. Это достигается за счет дублирования некоторых данных в памяти компьютеров. В следующих двух алгоритмах используется этот подход.
2.2.2. Алгоритм 2 Вычисляется произведение С = А х В, где А — матрица п1 х пз и  — матрица пз х пз. Матрица результатов С имеет размер п1 х пз. Исходные матрицы первоначально доступны на нулевом процессе, и матрица результатов возвращена в нулевой процесс. Параллельное выполнение алгоритма осуществляется на двумерной (21Э) решетке компьютеров размером р1 х рз. Матрицы разрезаны, как показано на рис. 2.3: матрица А — на рз горизонтальных полос, матрица  — на рз вертикальных полос и матрица результата С вЂ” на р1 х рз подматрицы (или субматрицы).
Й Схемы параллельных алгоришмое задач Рг А В С Рис. 2.3. Разрезание данных для параллельного алгоритма произведения двух матриц при вычислении в 2П решетке компьютеров. Выделенные данные расположены в одном компьютере Каждый компьютер (г, у) вычисляет произведение зтй горизонтальной полосы матрицы А и 3'-й вертикальной полосы матрицы В, произведение получено в подматрице (з,Я матрицы С.
Последовательные стадии вычисления иллюстрируются на рис. 2.4: 1. Матрица А распределяется по горизонтальным полосам вдоль координаты (х, 0). 2. Матрица В распределяется по вертикальным полосам вдоль координаты (О, у). 3. Полосы А распространяются в измерении у. 4. Полосы В распространяются в измерении х. л. Бсамег В координаты У 1. Ясаыег А 3. Вгоайсает подматриц А 4. Вгоадсазя подматрнц В 5. Вычисление произведений (подматриц в С) б.
Сбор результатов в С Рис. 2.4. Стадии вычисления произведения матриц в 20 параллельном алгоритме й.я. Умножение матрицы на матрицу 17 5. Каждый процесс вычисляет одну подматрицу произведения. б. Матрица С собирается из (х, у) плоскости. Осуществлять пересылки между компьютерами во время вычислений не нужно, т.к. все полосы матрицы А пересекаются со всеми полосами матрицы В в памяти компьютеров системы. Этот алгоритм эффективней предыдущего, т. к. непроизводительное время пересылок данных осуществляется только при загрузке исходных данных в память компьютеров и их выгрузке и нет обменов данными в процессе вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
