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