В.Д. Корнеев - Параллельное программирование в MPI (1162616), страница 3
Текст из файла (страница 3)
Он может выполняться на сети рабочих станций, или на наборе процессоров на отдельной рабочей станции; 2) способностью параллельных программ выполняться на гетерогенных системах, т.е. на системах, состоящих из процессоров с различной архитектурой. МР1 обеспечивает вычислительную модель, которая скрывает много архитектурных различий в работе процессоров. МР1 автоматически делает любое необходимое преобразование данных и использует правильный протокол связи, посылается ли код сообщения между одинаковыми процессорами или между процессорами с различной архитектурой. МР1 может настраиваться как на работу на однородной, так и на работу на гетерогенной системах; 3) такими механизмами, как определение одного вычислительного компьютера в виде виртуального компьютера (см. п.
2,1) и возможностью задания произвольного количества таких виртуальных компьютеров в системе независимо от количества физических компьютеров (а только от объема оперативной памяти в системе); 4) заданием виртуальных топологий (см. и.
2.1). Отображение виртуальных топологий на физическую систему осуществляется системой МР1. Виртуальные топологии обеспечивают оптимальное приближение архитектуры системы к структурам задач при хорошей переносимости задач; 5) компиляторами для Рог1гап'а и С. Уровень языка параллельного программирования определяется языковыми конструкциями, с помощью которых создаются параллельные программы. Как было сказано выше, операторы задания топологий, обменов данными и т.
и. нужно задавать в программе явно и поэтому языковый уровень параллельной программы оказывается ниже уровня последовательной программы. Наличие в системе таких средств, как виртуальные топологии, коллективные взаимодействия, создаваемые пользователем типы данных и др., значительно повышают уровень параллельного программирования по сравнению с системами с передачей сообщений, у которых нет таких средств. 1.
Введение 1.4. Краткое содержание глав Вторая глава посвящена общим схемам конкретных параллельных алгоритмов решения прикладных задач. При этом рассматривается несколько вариантов решения одних и тех же задач, с демонстрацией различных подходов параллельных вычислений реальных задач на реальных вычислительных системах. В третьей главе рассмотрены средства МР1, позволяющие разбивать множества компьютеров на подмножества и выполнять операции над ними. Эти операции позволяют строить сложные коммуникационные области, способствующие параллельным процессам эффективно обмениваться данными.
В четвертой главе описываются средства задания виртуальных топологий МР1, обеспечивающие очень удобный механизм наименования процессов, связанных коммуникатором, и являющиеся мощным средством отображения процессов на оборудование системы. Виртуальные топологии являются одним из основных средств, обеспечивающих переносимость программ. И, кроме того, они позволяют оптимально отображать структуру параллельной задачи на архитектуру вычислительной системы.
В пятой главе подробно описан основной механизм в МР1, обеспечивающий связь между двумя взаимодействующими процессами. Эта связь называется точечной (вро1п1-1о-ро1пГ'). Почти все конструкции из МР1 построены на основе ро1пв-Фо-ро1п~ операций, и,таким образом, эта глава является основной. В шестой главе описаны операции коллективных взаимодействий. Коллективная связь обеспечивает обмен данными среди всех процессов в группе, указанной аргументом 1псгасоиипптсатог. Однако они сделаны более ограниченными чем ро1пФ-~о-ро1пг операпии.
Коллективная операция выполняется при наличии всех процессов в групповом вызове оператора связи, с соответствующими аргументами. Седьмая глава посвящена средствам конструирования пользователем собственных типов данных. Эти средства позволяют создавать нз элементов разных типов, к тому же расположенных в несмежных участках памяти, новые типы данных. И эти сконструированные данные можно передавать за один вызов коммуникационной функции, что значительно уменьшает время обмена данными, делает программу более компактной. В восьмой главе описываются операции для получения и установки соответствующих различных параметров, которые касаются выполнения программ, написанных с использовавием МР1.
В девятой главе приведены примеры параллельных программ, демонстрирующих, с одной стороны, методы распараллеливания некоторых классов задач, а с другой стороны, поясняющих применение средств параллельного программирования с использованием МР1. 2. Схемы параллельных алгоритмов задач В главе приводятся примеры параллельных алгоритмов решения следующих задач: умножения матрицы на матрицу, задача 1(ирихле, решение систем линейных уравнений методом Гаусса и методом простой итерации. Здесь рассматривается простой вариант сеточной задачи (задача Лирихле), когда шаг сетки в пространстве вычислений одинаков и не меняется в процессе вычислений.
При динамически изменяющемся шаге сетки, как было сказано во введении в п. 1.2, потребовалось бы решать такую задачу параллельного программирования, как перебалансировка вычислительного пространства между компьютерами, для выравнивания вычислительной нагрузки компьютеров, а эта задача здесь не рассматривается.
В этой главе приводятся только общие схемы решения указанных задач, а тексты программ приведены в гл. 9, т. к. для понимания общих схем решения знать МР1 не обязательно, а для понимании программ необходимо, что бы пользователь предварительно ознакомился с системой программирования МР1. Приведенные здесь параллельные алгоритмы решения задач являются иллюстрационными, демонстрирующими применение и возможности функций МР1, а не универсальными, предназначенными для библиотек алгоритмов.
Рассматриваемые задачи распараллеливаются крупнозернистыми методами. Лля представления алгоритмов используется ЯРМ1э-модель вычислений (распараллеливание по данным). Однородное распределение данных по компьютерам основа для хорошего баланса времени, затрачиваемого на вычисления, и времени, затрачиваемого на взаимодействия ветвей параллельной программы. При таком распределении преследуется цель — равенство объемов распределяемых частей данных и соответствие нумерации распределяемых частей данных нумерации компьютеров в системе. Исходными данными рассматриваемых здесь алгоритмов являются матрицы, векторы и 20 (двумерное) пространство вычислений.
В этих алгоритмах применяются следующие способы однородного распределения данных: горизонтальными полосами, вертикальными полосами и циклическими горизонтальными полосами. При распределении горизонтальными полосами матрица, вектор или 2П пространство "разрезается" на полосы по строкам (далее слово "разрезанная" будем писать без кавычек и матрицу, вектор или 20 пространство обозначать для краткости словом— данные). Пусть М количество строк матрицы, количество элементов вектора или количесг во строк узлов 20 пространства, Р количество виртуальных компьютеров в системе, С1 = М(Р целая часть от деления, Сз = М7ьР дробная часть. Ванные разрезаются на Р полос. Первые (Р— Сз) полос имеют по С1 строки, а остальные Сз полосы имеют по С~ + 1 строки.
Полосы данных распределяются по компьютерам следующим образом. Первая полоса помещается в компьютер с номером О, вторая полоса в компьютер 1 и т.д. Такое распределение полос по компьютерам учитывается в параллельном алгоритме. Распределение вертикальными полосами аналогично предыдущему, только в распределении участвуют столбцы матрицы или столбцы узлов 20 пространства. И, наконец, распределение циклическими горизонтальными полосами. При таком распределении данные разрезаются на количество полос значительно большее, чем количество компьютеров. И чаще всего полоса состоит из одной строки. Первая полоса загружается в компьютер О, вторая — в компьютер 1 и т. д., затем (Р— 1)-я полоса — снова в компьютер О, Р-я полоса — в компьютер 1 и т.д. Приведенные два алгоритма решения СЛАУ методом Гаусса показывают, что однородность распределения данных сама по себе еще недостаточна для эффективности алгоритма.
Эффективность алгоритмов зависит еще и от способа распределения данных. Разный способ представления данных влечет соответственно и разную организацию алгоритмов, обрабатывающих их. В книге эффективность рассматриваемых алгоритмов определяется упрощенными формулами, которые дают грубую оценку эффективности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
