Методичка по параллельному программированию. Методические указания к выполнению лабораторных работ по дисциплине "параллельное программирование"
 Скачать 214.06 Kb.
|
|
Министерство образования Российской Федерации Пензенский государственный университет МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ ПО ДИСЦИПЛИНЕ “ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ” Методические указания к выполнению лабораторных работ Пенза 2010 УДК 681.3 (новый УДК -???) М ?? Приведены задания на лабораторные работы, каждое из которых сопровождается теоретическим материалом. Большинство заданий предназначены для выполнения в среде UNIX/Linux на языке C/C++, для выполнения лабораторных работ №3 и №4 потребуется также установка пакета MPI. Задания лабораторной работы №5 ориентированы на выполнение на языке OCCAM, также в среде UNIX/Linux. Работа подготовлена на кафедре “Математическое обеспечение и применение ЭВМ” и предназначена для студентов специальности 230105 и 230202. Рис 4, табл. 3, библиогр. 5 назв. С о с т а в и т е л ь: к.т.н., доцент каф. “МО и ПЭВМ” . Кольчугина Е.А.. Р е ц е н з е н т: к.т.н., доцент кафедры “Информационные системы и моделирование” ПГПУ им. В.Г. Белинского Артюхин В.А. 2 СОДЕРЖАНИЕ ЛАБОРАТОРНАЯ РАБОТА №1 СРЕДСТВА МЕЖПРОЦЕССНОГО ВЗАИМОДЕЙСТВИЯ ОС UNIX/LINUX: СЕМАФОРЫ И РАЗДЕЛЯЕМАЯ ПАМЯТЬ. МОДЕЛЬ “ПРОИЗВОДИТЕЛЬ- ПОТРЕБИТЕЛИ”..............................................................................................4 ЛАБОРАТОРНАЯ РАБОТА №2 СРЕДСТВА МЕЖПРОЦЕССНОГО ВЗАИМОДЕЙСТВИЯ ОС UNIX/LINUX: СООБЩЕНИЯ. БАРЬЕРНАЯ СИНХРОНИЗАЦИЯ.......................................................................................10 ЛАБОРАТОРНАЯ РАБОТА №3 РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ С ПОМОЩЬЮ MPI. ВЗАИМОДЕЙСТВИЯ POINT-TO- POINT И КОЛЛЕКТИВНЫЕ ВЗАИМОДЕЙСТВИЯ. БАРЬЕРНАЯ СИНХРОНИЗАЦИЯ В MPI...........................................................................13 ЛАБОРАТОРНАЯ РАБОТА №4 РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ С ПОМОЩЬЮ MPI: ВИРТУАЛЬНЫЕ ТОПОЛОГИИ 21 ЛАБОРАТОРНАЯ РАБОТА №5 РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НА ЯЗЫКЕ OCCAM..............................................................25 СПИСОК ЛИТЕРАТУРЫ.............................................................................32 3 Лабораторная работа №1 Средства межпроцессного взаимодействия ОС UNIX/Linux: семафоры и разделяемая память. Модель “производитель-потребители”. Теоретическая часть Понятие процесса является основополагающим для операционных систем семейства UNIX. Процесс - это совокупность набора инструкций программы, запущенной на выполнение, а также среды или окружения, в которой осуществляется выполнение программы. Среду выполнения образуют ресурсы памяти, доступные системные ресурсы и устройства ввода/вывода. Процесс также можно определить, как совокупность данных ядра системы, необходимых для описания образов программ в памяти и управления их выполнением. Структуры данных, описывающих различные процессы, а также образы программ в памяти, соответствующих разным процессам, никогда не пересекаются. Процесс может считывать и записывать информацию в выделенные ему раздел данных и стек, но ему не доступны данные и стеки других процессов. Образ текущего состояния процесса называется его контекстом. Наличие контекста позволяет реализовать переключение выполнения с одного процесса на другой, и тем самым обеспечивать режим многозадачности даже для однопроцессорных ЭВМ. Для идентификации процессов каждому из них присваивается уникальный идентификатор, или номер: pid. С каждым из процессов связывается набор атрибутов, позволяющих провести дополнительную идентификацию или определить свойства процесса. Такими атрибутами являются: идентификатор процесса-родителя (ppid), идентификатор сеанса, идентификатор ассоциированного псевдотерминала (tty), реальные и эффективные идентификаторы пользователей и групп.(ruid, rgid, euid, egid), приоритет процесса (nice number) и т.д. Обеспечение взаимодействия процессов осуществляет модуль, входящий в состав подсистемы управления процессами. В UNIX-системах поддерживаются следующие средства межпроцессных коммуникаций, или IPC (от Inter-Process Communications).: -сигналы; -неименованные каналы; -именованные каналы, или FIFO (происходят из системы System III); 4 -файлы; -группа средств, пришедших из архитектуры UNIX System V (семафоры, разделяемая память, очереди сообщений); -средства, унаследованные от UNIX BSD (сокеты). Сигналы, неименованные каналы, FIFO и обычные файлы относят к простейшим средствам межпроцессного взаимодействия. Сигналы - это сообщения, генерируемые операционной системой в ответ на происходящие события. Неименованные каналы реализуются в виде пары файловых дескрипторов, один из которых используется для чтения информации из канала, другой - для записи в канал. Неименованные каналы позволяют обмениваться информацией только родственным процессам, поэтому определение неименованного канала как правило предшествует вызову функции порождения процессов fork. В классическом варианте передача информации через неименованный канал возможна только в одном направлении. Именованные каналы реализуются как файлы особого типа: FIFO. Эти средства позволяют организовать обмен информацией между любыми, даже и не родственными процессами, выполняющимися в одной файловой системе. Отличительным свойством FIFO является нулевая длина файлов этого типа, поэтому в них нельзя хранить информацию. Обычные файлы являются наиболее очевидным средством для обмена информацией между процессами. Однако с использованием файлов одновременно несколькими процессами связана проблема гонок. Для разрешения этой проблемы можно использовать функцию flock, которая задает дисциплину доступа к открытому файлу, однако данное средство следует отнести к ненадежным. В UNIX System V впервые появились такие средства межпроцессного взаимодействия, как семафоры, очереди сообщений и разделяемая память. Созданию этих объектов предшествует генерация уникального системного идентификатора (ключа), который регистрируется IPC и позволяет обращаться к данным объектам из различных (в том числе и не родственных) процессов. В целом, функции для работы с данными средствами межпроцессных взаимодействий, подразделяются на три группы: -функция генерации ключа ftok; -управляющие функции семейств *get и *ctl (создание и уничтожение объекта, задание и изменение его базовых характеристик); -все прочие функции, изменяющие состояния объекта (например, добавление сообщения в очередь, освобождение или захват семафора, и т.д.). Сообщения помещаются в очередь сообщений и являются 5 разделяемыми системными ресурсами. Процесс может работать с несколькими очередями, каждая из которых имеет свой собственный идентификатор. Сообщения реализуются как структуры, включающие в себя: тип сообщения; длину сообщения; собственно данные. Сообщения можно мультиплексировать, т.е. в одну и ту же очередь помещать сообщения для разных процессов. Разделяемая память - это область оперативной памяти произвольной структуры, доступная для чтения-записи одновременно нескольким процессам по уникальному идентификатору (ключу), как правило, используется совместно с семафорами. Семафор в UNIX реализуется как группа из нескольких счетчиков, объединенных общими признаками, например дескриптором объекта, правами доступа, и т.п. Каждый из этих счётчиков может принимать любое неотрицательное значение в пределах определённой системы. Операционная система не накладывает семантических ограничений на использование различных состояний семафоров. В частности, процессы могут решать, какое значение семафора считать разрешающим, на какую величину изменять значение семафора и так далее. Одним из простейших вариантов использования семафоров UNIX является бинарный семафор Дейкстра, но возможны и более сложные схемы. Сокеты – средства межпроцессорного взаимодействия, появившиеся в BSD UNIX. Назначение сокетов состоит в обеспечении унифицированного интерфейса обмена информацией между процессами, вне зависимости от того, выполняются ли они в одной файловой системе или в разной. Сокеты, в зависимости от основных характеристик, могут принадлежать к одному из двух доменов: UNIX или Internet. Сокеты UNIX реализуются как файлы особого типа и являются дальнейшим развитием концепции FIFO. Сокеты Internet описывают сетевое соединение и идентифицируются парой, состоящей из IP-адреcа и номера порта В данной работе требуется реализовать взаимодействие между параллельными процессами по модели “производитель-потребители”. В этом случае имеется процесс-производитель, который формирует данные, помещаемые в разделяемую область памяти (общий ресурс). Остальные процессы выполняют роль потребителей, захватывая общий ресурс и извлекая данные из разделяемой области памяти, при этом извлеченные данные уничтожаются. Очевидно, что работа с разделяемым ресурсом должна быть организована в соответствии с моделью семафора Дейкстра, который позволяет управлять доступом к разделяемому ресурсу, избегая ситуаций блокировок и отталкивания. 6 Механизм семафора Дейкстра включает в себя переменные особого типа - семафоры, и две операции - P и V , единственным аргументом которых может быть только переменная типа семафор. Состояние семафора представляется целым неотрицательным числом. Если диапазон значений ограничен нулем и единицей, то семафор называют бинарным. В соответствии с механизмом семафора Дейкстра, операция P выполняется процессом перед входом в критическую секцию, а операция V - перед выходом из критической секции. Операция P реализуется по следующему алгоритму: - если значение семафора отлично от нуля, оно уменьшается на единицу; - если значение семафора равно нулю, то операция P не завершается до тех пор, пока другой процесс не увеличит значение семафора с помощью операции V , после чего P продолжит выполнение и уменьшит значение семафора на единицу. Операция V всегда увеличивает значение семафора на единицу. Операции P и V являются неделимыми в том смысле, что их выполенение не может быть прервано на какой-либо промежуточной фазе. Тем самым гарантируется целостность состояния переменной-семафора и отсутствие конфликтных ситуаций. На рисунке 1 показан пример взаимодействия двух процессов, организованного с помощью семафора Дейкстра. Переходы, помеченные p p 1 2 , соответствуют выполнению операций P , переходы, помеченные v v 1 2 , - выполнению операций V . Выполнению операций критической секции соответствуют переходы c c 1 2 , , а остатки циклов моделируются переходами r r 1 2 , Экспериментальная часть. 1. Разработать программу на языке С/C++ для ОС UNIX/Linux, которая моделирует обслуживание клиентов бензозаправочной станции. На бензозаправочной станции имеется пять колонок с бензином АИ-76 (2 колонки), АИ-92 (2 колонки) и АИ-95 (1 колонка). Прибывающие на заправку машины ожидают обслуживания в общей очереди, которая программно моделируется областью разделяемой памяти. При поступлении новой заявки на обслуживание (новой машины) в область разделяемой памяти добавляется запись, содержащая: -уникальный порядковый номер машины (клиента); -требуемая марка бензина (одна из перечисленных). 7 Рисунок 1 - Синхронизация двух процессов с помощью семафора Дейкстра. Состояние области разделяемой памяти отображается в протоколе, который может быть реализован как текстовый файл. Протокол содержит данные о всех поступавших заявках в формате, аналогичном записям, помещаемым в область разделяемой памяти. Как только какая-либо бензоколонка освобождается, очередь покидает машина, для которой требуется бензин соответствующей марки и которая ближе остальных находится к началу очереди. Эта машина занимает соответствующую бензоколонку. При этом информация о клиенте удаляется из области разделяемой памяти, моделирующей общую очередь. После обработки заявки информация о клиенте переносится в файл протокола (текстовый файл), хранящий информацию о клиентах, обслуженных на данной бензоколонке. Таким образом, в приложении используется шесть файлов протокола (соответствуют очереди и бензоколонкам) и шесть потоков (см. рисунок 2): -поток заявок, поступающих в очередь; -потоки, моделирующие обслуживание заявок. 2. Формат записи информации выбирается разработчиком. Информация из файла протокола не удаляется, обслуженные заявки каким-либо образом 8 помечаются. Эксперимент проводить для не менее чем 150 заявок. 3. Математические ожидания и среднеквадратичные отклонения для времени генерации очередной заявки и обслуживания по каждой бензоколонке должны быть настраиваемыми, также как и предельное количество заявок в очереди. Емкость очереди должна быть подобрана так, чтобы не происходило потерь заявок. Рисунок 2.- Модель задачи из лабораторной работы №1. 4. Исходную задачу необходимо решить с использованием семафоров и разделяемой памяти (с использованием функций ftok, semget, semop, semctl, shmget, shmat, shmdt, shmctl). Описания необходимых функций приведены во встроенной справочной системе UNIX/Linux и в [1]. 9 Лабораторная работа №2 Средства межпроцессного взаимодействия ОС UNIX/Linux: сообщения. Барьерная синхронизация. Теоретическая часть Основной полезный эффект, получаемый в результате параллельного программирования, связан с асинхронной обработкой информации множеством независимых, параллельно выполняющихся процессов. Однако в ряде случаев бывает необходимо, чтобы параллельные процессы обменивались информацией между собой, передавая друг другу данные и сообщения о событиях. Кроме того, поскольку не исключены ситуации, когда несколько процессов обращаются к одному и тому же ресурсу (аппаратному, программному, информационному), необходимо установить порядок получения доступа к ресурсам. Так возникает задача синхронизации, которая состоит в обеспечении взаимодействия параллельных процессов. Введем ряд терминов и определений. Разделяемым ресурсом называется ресурс, равно доступный всем взаимодействующим процессам. В качестве разделяемого ресурса могут выступать данные, организованные в виде файлов баз данных или разделяемой памяти в UNIX-системах, аппаратное обеспечение (принтеры, каналы связи, дисковые накопители), программные единицы (модули, библиотеки, задачи). “Гонки” - это ситуация, при которой несколько процессов одновременно получают доступ к общему ресурсу. Результат в этом случае непредсказуем и определяется соотношением скоростей процессов. Особенно драматичны ситуации, когда асинхронные процессы могут изменять состояние общего ресурса. Участок программы, в котором реализуется доступ к ресурсу, общему для нескольких процессов, называется критической секцией. С понятием критической секции связано понятие взаимной блокировки. Различают два вида взаимных блокировок. Первая разновидность, которую собственно и называют блокировкой (deadlock, clinch), соответствует ситуации, когда группа процессов не может продолжить выполнение, ожидая сообщения об освобождении критической секции. При этом такое сообщение никогда не поступит, поскольку критическая секция пуста. Классический пример возникновения блокировки 10 приведен на рисунках 3 и 4. Другой разновидностью взаимных блокировок является отталкивание (livelock), при котором асинхронные процессы заняты только тем, что пересылают друг другу сообщение об освобождении критической секции. Рисунок 3 – Исходное состояние перед возникновением блокировки. Рисунок 4 – Блокировка, возникшая после срабатывания переходов 1 t и 4 t . Как правило, при работе с разделяемым ресурсом устанавливается дисциплина доступа, при которой в каждый момент времени в критической секции может находиться не более одного процесса. Такая дисциплина носит название взаимного исключения (mutual exclusion, mutex). Она позволяет исключить ситуацию “гонок”. Надежная реализация дисциплины взаимного исключения обеспечивается в модели семафора Дейкстра (рисунок 1). Барьером называется способ координации выполнения нескольких процессов, при котором все они должны достигнуть некоторой общей программной точки, прежде чем каждому из них будет позволено продолжить выполнение. В данной лабораторной работе требуется вручную реализовать способ барьерной синхронизации параллельных процессов. В некоторых языках и средах программирования барьерная синхронизация поддерживается с 11 помощью встроенных средств, как например в пакете MPI. Также в данной работе потребуется реализовать одновременную передачу всем процессам общего и равнодоступного сигнала о наступлении события. При этом, хотя сигнал и представляет собой разделяемый ресурс, доступ к нему разрешен всем процессам одновременно. Экспериментальная часть. 1. Разработать программу на языке С/C++ для ОС UNIX/Linux, имитирующую соревнования гоночных автомобилей. Гоночный заезд включает в себя три этапа, очередной этап начинается после того, как все автомобили завершат предыдущий этап. Победитель определяется по итогам всех трех этапов. После того, как последний автомобиль достигнет финиша, производится подсчет баллов и распределение мест. В гонках принимают участие пять автомобилей. Система начисления баллов определяется разработчиком. Необходимо также разработать интерфейс, позволяющий следить за ходом гонок в наглядной форме. В конце соревнования, а также в конце каждого этапа, вывести итоги, включающие в себя: - расстановку машин по местам в итоге этапа или соревнования; - набранные каждым участником баллы. 2. Гоночный автомобиль моделируется отдельным процессом. Процессы выполняются параллельно. Необходим также одни управляющий процесс, который запускает остальные процессы и отслеживает момент их завершения, а затем подсчитывает и выводит на экран итоги (арбитр). 3. Сигнал к началу каждого заезда подается арбитром однократно, в единственном экземпляре для всех участников. Способ реализации подачи сигнала к началу заезда – на усмотрение разработчика. 4. Для решения задачи необходимо использовать барьерную синхронизацию. Способ реализации барьерной синхронизации – на усмотрение разработчика, можно воспользоваться массивом, каждый элемент которого соответствует состоянию одного процессов, моделирующих гоночные автомобили. 5. Программа должна обладать интерфейсом, позволяющим в удобной форме наблюдать за ходом каждого заезда, то есть за движением машин к финишу. 5. Рекомендуемые функции: ftok, msgget, msgsnd, msgrcv msgctl. Описания функций приведены во встроенной справочной системе UNIX/Linux и в [1]. 12 Лабораторная работа №3 Разработка параллельных программ с помощью MPI. Взаимодействия Point- to-Point и коллективные взаимодействия. Барьерная синхронизация в MPI. Теоретическая часть MPI фактически представляет собой технологию программирования, поскольку пользователю предоставляется набор функций для разработки параллельных программ. В состав пакета MPI минимально входят: - библиотека программирования (реализации для языков C/C++ и Fortran); - загрузчик приложений. В соответствии с технологией MPI, параллельное приложение состоит из независимых ветвей, или процессов. Каждый процесс идентифицируется целым неотрицательным числом и принадлежит к некоторой группе процессов. Группы также идентифицируются целыми неотрицательными числами. Они создаются для объединения процессов при проведении вычислений. Каждой группе соответствует своя область связи (communication domain). Для получения доступа к области связи процессу предоставляется описатель этой области, или коммуникатор. Для любого приложения MPI автоматически создается группа MPI_COMM_WORLD, и одноименная область связи, которая позволяет объединить все процессы, входящие в данное приложение. В процессе выполнения процессы обмениваются между собой сообщениями. Каждое сообщение идентифицируется целым неотрицательным числом из интервала от 0 до 32767. Сообщение имеет атрибуты, для хранения которых создается структура MPI_Status, содержащая три основных поля: - MPI_Source - код процесса-отправителя; - MPI_Tag - номер сообщения; - MPI_Error - код ошибки. Все идентификаторы, объявленные в пакете MPI, начинаются с префикса “MPI_”, поэтому данный префикс не рекомендуется включать в пользовательские идентификаторы. При выборе и использовании идентификаторов в случае программирования на MPI для языка С/C++ регистр букв является существенным. Об успешности выполнения той или иной функции MPI можно судить по возвращаемому целочисленному значению. В случае успеха оно 13 соответствует MPI_SUCCESS, во всех остальных случаях возвращается код ошибки. Первой функцией MPI, с которой начинается работа параллельной программы и которая позволяет выполнить инициализацию параллельной части приложения, является MPI_Init: int MPI_Init (int argc, char **argv); Аргументами функции являются входные параметры основной программы. Инициализация MPI производится только один раз в течении выполнения программы, попытка повторной инициализации вызовет ошибку. Обращение к функциями MPI возможно только после выполнения инициализации. Обратное действие, завершающее выполнение параллельной части приложения, выполняется функцией MPI_Finalize: int MPI_Finalize (void); После вызова MPI_Finalize обращаться к функциям MPI уже нельзя. Узнать номер данного процесса в группе можно с помощью вызова функции MPI_Comm_rank: int MPI_Comm_rank (MPI_Comm comm, int *rank); где comm - идентификатор группы, rank - номер процесса в группе comm. Задача определения общего числа параллельных процессов в группе решается с помощью вызова функции MPI_Comm_size: int MPI_Comm_size (MPI_Comm comm, int *size); где comm - идентификатор группы, size - количество процессов в группе comm. Основным механизмом синхронизации, предлагаемым MPI, является прием и передача сообщений. Передача сообщений с блокировкой осуществляется функцией MPI_Send. Как отмечалось выше, блокировка гарантирует, что выполнение программы будет продолжено только после того, как функция будет либо полностью выполнена, либо система перейдет в устойчивое и целостное состояние, гарантирующее корректность повторного использования всех параметров функции. Описание MPI_Send: int MPI_Send (void *buf, int count, MPI_Datatype datatype, 14 int dest, int msgtag, MPI_Comm comm ); где buf -адрес начала буфера посылки сообщения; count -число передаваемых элементов сообщения; datatype -тип элементов сообщения (таблица 1); dest -номер процесса-получателя; msgtag -идентификатор принимаемого сообщения; comm -идентификатор группы. В дополнение к вышесказанному следует отметить, что для процесса разрешается передача сообщений самому себе, сообщение может иметь нулевую длину, все элементы сообщения располагаются друг за другом, подряд. Возврат из MPI_Send не осзначает, что сообщение покинуло процессорный элемент, но повторное использование всех параметров вызова MPI_Send будет гарантированно корректным. Парной к MPI_Send является функция MPI_Recv: int MPI_Recv (void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Status *status); где buf -адрес начала буфера приема сообщения; count -максимальное число элементов сообщения; datatype -тип элементов сообщения (таблица 1); source -номер процесса-отправителя; msgtag -идентификатор принимаемого сообщения; comm -идентификатор группы; status -параметры принятого сообщения. Блокировка гарантирует, что после возврата из функции все элементы сообщения приняты и расположены друг за другом в буфере buf. Число принимаемых элементов сообщения не может быть больше, чем значение count. Точное значение числа принятых элементов сообщения определяется с помощью вызова функции MPI_Probe. В качестве номера процесса-отправителя и номера принимаемого сообщения можно указывать константы-джокеры, тем самым говоря, что ожидается сообщение с любым идентификатором от любого процесса. Имеются две таких константы-джокера: - MPI_ANY_SOURCE - используется как признак ожидания сообщения от любого процесса; - MPI_ANY_TAG - используется как признак ожидания сообщения с любым идентификатором. 15 Таблица 1 Наименование константы MPI Тип данных MPI_CHAR Символьный тип MPI_SHORT Короткое знаковое целое MPI_INT Знаковое целое MPI_LONG Длинное знаковое целое MPI_UNSIGNED_CHAR Символьный беззнаковый тип MPI_UNSIGNED_SHORT Короткое беззнаковое целое MPI_UNSIGNED Беззнаковое целое MPI_UNSIGNED_LONG Длинное беззнаковое целое MPI_FLOAT Число с плавающей точкой MPI_DOUBLE Число с плавающей точкой двойной точности MPI_LONG_DOUBLE Число с плавающей точкой двойной точности и повышенной длины Проанализировать структуру ожидаемого сообщения позволяет функция MPI_Probe: int MPI_Probe (int source, int msgtag,MPI_Comm comm MPI_Status *status); где source - идентификатор процесса-отправителя или MPI_ANY_SOURCE; msgtag -идентификатор ожидаемого сообщения или MPI_ANY_TAG; comm -идентификатор группы; status -параметры принятого сообщения. Данная функция позволяет только определить сам факт поступления сообщения и проанализировать его структуру, но приме как таковой не осуществляется. Для синхронизации процессов служит коллективная функция MPI_Barrier, реализующая механизм барьера: int MPI_Barrier (MPI_Comm comm); где comm - идентификатор группы. В состав пакета MPI входят также функции, позволяющие осуществлять коллективные взаимодействия процессов. К таким функциям относят MPI_Bcast - функцию, осуществляющую рассылку данных всем 16 процессам данной группы в широковещательном режиме: int MPI_Bcast (void *buf, int count, MPI_Datatype datatype, int source, MPI_Comm comm ); где buf -адрес начала буфера посылки сообщения; count -число передаваемых элементов сообщения; datatype -тип элементов сообщения (таблица 1); source -номер передающего процесса; comm -идентификатор группы. Возврат из данной функции означает, что рассылка сообщения всем процессам группы, включая передающий, уже произведена. Получили ли процессы это сообщение или нет - не известно, но параметры, переданные данной функции, уже можно использовать и это не будет некорректным. Значения параметров count, datatype, source должны быть одинаковыми у всех процессов. Функция MPI_Gather позволяет решить противоположную задачу: осуществить сборку данных со всех процессов, входящих в заданную группу: int MPI_Gather(void *sbuf, int scount, MPI_Datatype sdatatype, void *rbuf, int rcount, MPI_Datatype rdatatype, int dest, MPI_Comm comm ); где sbuf -адрес начала буфера посылки сообщения; scount -число передаваемых элементов сообщения; sdatatype -тип элементов сообщения (таблица 1); rbuf -адрес начала буфера сборки; rcount -число принимаемых элементов сообщения; rdatatype -тип элементов сообщения (таблица 1); dest -номер собирающего процесса; comm -идентификатор группы. Каждый процесс, включая dest, посылает содержимое своего буфера sbuf процессу dest. Сборка данных осуществляется в буфере rbuf собирающим процессом dest, данные располагаются в порядке возрастания номеров процессов. Параметр rbuf имеет значение только для собирающего процесса и у остальных игнорируется, но значения параметров scount, rcount, sdatatype, rdatatype, а также параметра dest должны быть идентичными у всех процессов группы. Функция MPI_Scatter является парной к MPI_Gather: int MPI_Scatter (void *sbuf, int scount, MPI_Datatype sdatatype, 17 void *rbuf, int rcount, MPI_Datatype rdatatype, int source, MPI_Comm comm ); где sbuf -адрес начала буфера посылки сообщения; scount -число передаваемых элементов сообщения; sdatatype -тип элементов сообщения (таблица 1); rbuf -адрес начала буфера сборки; rcount -число принимаемых элементов сообщения; rdatatype -тип элементов сообщения (таблица 1); source -номер рассылающего процесса; comm -идентификатор группы. Массив sbuf делится на n равных частей, состоящих из порций элементов типа rdatatype, в каждую входит scount элементов. Каждая i-ая порция посылается i-ому процессу. Для процесса source должны быть определены все параметры, а для всех остальных процессов достаточно параметров rbuf, rcount, rdatatype, source, comm. Параметры source, comm должны быть одинаковы для всех участвующих процессов. MPI_Reduce - функция глобальной редукции. Редукция означает выполнение какой-либо операции над группой данных, в результате которой образуется единственный результат. Пример: вычисление максимума и минимума, суммы, произведения. Операция редуцирования задается пользователем. Возможно два варианта выполнения редукций: редукция выполняется в одном узле либо редукция выполняется во всех узлах с последующим просмотром. int MPI_Reduce (void * sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm ), где sendbuf - адрес буфера-источника данных; recvbuf - адрес буфера-получателя данных; count, - количество передаваемых элементов; datatype -тип передаваемых элементов; op -операция редукции; root -ранг корневого процесса; comm -коммуникатор. MPI_Reduce объединяет элементы, находящиеся в буфере-источнике данных каждого процесса, используя операцию op, и возвращает 18 объединенное значение в буфере приема в процессе с рангом root. Параметры sendbuf, recvbuf, count, datatype, op, root, comm должны быть идентичны для всех процессов-участников. Таблица2 Имена операций Семантика операций MPI_MAX Вычисление максимума MPI_MIN Вычисление минимума MPI_SUM Вычисление суммы MPI_PROD Вычисление произведения MPI_LAND логическое И MPI_BAND поразрядное И MPI_LOR логическое ИЛИ MPI_BOR поразрядное ИЛИ MPI_LXOR логическое XOR MPI_BXOR поразрядное XOR MPI_MAXLOC максимальное значение с локализацией MPI_MINLOC минимальное значение с локализацией Функция MPI_Comm_Split позволяет разбить процессы группы comm на непересекающиеся подгруппы. В каждую подгруппу входят процессы одного “цвета” (от наименования параметра color - цвет), “цвет” задается целым неотрицательным числом. Если “цвет” не задан, и в качестве значения color указано MPI_UNDEFINED, то в выходном параметре newcomm будет возвращено MPI_COMM_NULL. Прототип функции MPI_Comm_Split: MPI_Comm_Split (MPI_Comm comm, int color, int key, MPI_Comm *newcomm) где comm -идентификатор исходной группы; color - “цвет”, признак разделения на подгруппы; key - параметр, определяющий нумерацию в новых группах; newcomm -идентификатор группы. Уничтожение группы производится с помощью функции MPI_Comm_Free, уничтожаемая группа указывается в параметре comm, который после возвращения из функции принимает значение MPI_COMM_NULL: MPI_Comm_Free (MPI_Comm comm) где comm -идентификатор исходной группы. 19 Характерными особенностями программ с использованием MPI являются: - небольшой объем по сравнению с реализациями аналогичных задач на языке C/C++; - зависимость поведения функций MPI от номера ветви программы, в которой располагается их вызов. Последнее означает, что абсолютно идентичные вызовы функций MPI выполняются в разных ветвях программы по-разному. Например, в одной ветви вызов функции означает рассылку данных, в других – прием данных. Эта особенность подчеркивает необходимость начинать разработку программ с использованием MPI с проектирования виртуальной параллельной структуры и описания распределения данных по узлам кластера, схемы обмена данными между узлами, определение ролей виртуальных узлов в составе структуры. Экспериментальная часть. 1. Набрать, откомпилировать и выполнить программу-пример: #include “mpi.h” main (argc, argv) int argc; char **argv; { char message [20]; int myrank; MPI_Status status; MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &myrank); if (myrank==0) { strncpy(message,”Hello, there!\0”,15); MPI_Send (message, strlen(message)+1, MPI_CHAR, 1,99, MPI_COMM_WORLD); } else { MPI_Recv (message, 20, MPI_CHAR, 0,99, MPI_COMM_WORLD, &status); printf (“received: %s \n”, message); 20 } MPI_Finalize (); } 2. Решить задачу из лабораторной работы №2 средствами MPI. Использовать функции MPI_Barrier, MPI_Bcast, MPI_Gather. 3. Вычислить произведение матрицы 4 × 5 и матрицы 5 × 6 средствами MPI. Для распределения элементов массивов использовать функцию MPI_Scatter, MPI_Bcast. Для сборки результирующего массива использовать MPI_Gather и MPI_Reduce. Задачу решить в двух вариантах: - каждому процессорному элементу назначается строка матрицы 4 × 5 и столбец матрицы 5 × 6 (использовать 4 процессора); - каждому процессорному элементу назначается один элемент матрицы 4 × 5 и одни элемент матрицы 5 × 6 (использовать 20 процессоров). Для двух вариантов решения сравнить время выполнения программ. Решение каждого варианта задачи из пункта 3 следует начать с разработки графической схемы, на которой показаны взаимодействующие процессы (вычислительные узлы), распределение данных по узлам, последовательность передачи данных от узла к узлу. При сдаче лабораторной работы обязательно представить данные схемы преподавателю. Лабораторная работа №4 Разработка параллельных программ с помощью MPI: виртуальные топологии Теоретическая часть Виртуальные топологии позволяют выделить и упорядочить связи между процессорными элементами (узлами) виртуального кластера. В MPI поддерживается два вида топологий: - графовые топологии; - декартовы топологии. Топологии первой группы предоставляют большие возможности в плане создания разнообразных виртуальных вычислительных структур, однако они сложнее для описания. Декартовы топологии проще в использовании, но ограничены в своих возможностях. Фактически, они позволяют описывать только регулярные структуры, представляющие собой решетки различных размерностей. При 21 создании декартовых топологий обычно указываются: количество узлов в решетке; количество размерностей; распределение узлов по размерностям; замкнутость или открытость по каждому измерению. С помощью декартовых топологий можно создавать такие структуры, как “кольцо”, “линейка”, двумерная решетка, тор, кубы произвольной размерности и т.д. Для создания декартовой топологии произвольной структуры применяется функция-построитель: int MPI_Cart_create (MPI_Comm comm_old, int ndims, int *dims, int *periods, int reorder, MPI_Comm *comm_cart ); где comm_old -исходный коммуникатор; ndims - число размерностей в топологии; dims - целочисленный массив размером ndims, определяющий количество процессов (узлов) в каждом измерении; periods - целочисленный массив размером ndims, определяющий периодичность (если задано значение true) или непериодичность (если задано значение false) по каждому измерению; reorder - логическое значение, определяющее, будут ли ранги процессов перенумерованы (если true) или нет (если false); comm_cart – новый коммуникатор с декартовой топологией. Функция MPI_Dims_create позволяет получить сбалансированное распределение процессов по размерностям топологии, в зависимости от числа процессов в группе и необязательного параметра, заданного пользователем. Таким параметром является dims – описание декартовой топологии с размерностями ndims и числом узлов nnodes. Если в элементе массива dims[i] уже записано значение, большее нуля, то функция MPI_Dims_create не будет изменять количество узлов в i-ом измерении. Размерности устанавливаются так, чтобы быть как можно ближе друг к другу. Функция MPI_Dims_create локальная и используется перед вызовом MPI_Cart_create. Прототип функции: int MPI_Dims_create (int nnodes, int ndims, int *dims ); где nnodes –количество узлов в решетке; ndims - число размерностей в топологии; dims - целочисленный массив размером ndims, определяющий количество процессов (узлов) в каждом измерении. Примеры работы функции приведены в таблице 3. 22 Таблица 3 Массив dims перед вызовом функции Вызов функции MPI_Dims_create Массив dims после вызова функции (0,0) MPI_Dims_create (6,2,dims) (3,2) (0,0) MPI_Dims_create (7,2,dims) (7,1) (0,3,0) MPI_Dims_create (6,3,dims) (2,3,1) (0,3,0) MPI_Dims_create (7,3,dims) ошибка Ситуации, когда пользователем задано отрицательное значение dims[i] или nnodes не кратно произведению всех dims[i], рассматриваются как ошибочные. Получить информацию о декартовой топологии можно с помощью локальной функции MPI_Cart_get: int MPI_Cart_get (MPI_Comm comm, int maxdims, int *dims, int *periods, int *coords ); где comm – коммуникатор с декартовой топологией; maxdims - максимальный размер массивов dims, periods и coords; dims - целочисленный массив размером ndims, содержащий количество процессов (узлов) в каждом измерении; periods - целочисленный массив размером ndims, содержащий сведения о периодичности (если задано значение true) или непериодичности (если задано значение false) по каждому измерению; coords - массив координат вызвавшего процесса в декартовой топологии. Имеются функции, которые позволяют получить координату процесса по его рангу или выполнить обратное преобразование. Локальная функция MPI_Cart_rank позволяет определить ранг процесса по его координате: int MPI_Cart_rank (MPI_Comm comm, int *cords, int rank); где comm – коммуникатор с декартовой топологией; coords - массив координат вызвавшего процесса в декартовой топологии; rank – соответствующий ранг процесса. Обратное преобразование, то есть вычисление координаты по рангу, выполняется функцией MPI_Cart_coords: int MPI_Cart_coords (MPI_Comm comm, int rank, 23 int maxdims, int *coords ); где comm – коммуникатор с декартовой топологией; rank - ранг процесса в группе comm; maxdims - максимальный размер массива coords; coords - массив координат вызвавшего процесса в декартовой топологии. Функция MPI_Cart_shift, или функция декартова смещения, позволяет определить ранг процесса, смежного заданному в указанной декартовой топологии. Функция является локальной. Прототип функции: int MPI_Cart_shift (MPI_Comm comm, int directions, int disp, int *rank_source, int *rank_dest ); где comm – коммуникатор с заданной декартовой топологией; directions - номер измерения в топологии, по которому определяется смещение; disp - направление смещения: при положительном значении смещение отсчитывается в сторону увеличения координаты по измерению directions, при отрицательном – в сторону уменьшения координаты; rank_source –ранг процесса, относительно координаты которого отсчитывается смещение; rank_dest - искомый ранг процесса. Функция MPI_Cart_sub позволяет выделять в составе исходной декартовой топологии наборы подрешеток с меньшим числом размерностей: int MPI_Cart_sub (MPI_Comm comm, int *remain_dims, MPI_Comm *newcomm ); где comm – исходный коммуникатор с декартовой топологией; remain_dims - массив логических значений, каждый элемент которого указывает, включена ли соответствующая размерность в подрешетку (если значение true) или не включена (если false); newcomm - коммуникатор созданных подрешеток. Экспериментальная часть. 1. Для задачи упорядочивания одномерного массива по неубыванию разработать граф зависимости (ГЗ) и граф потока сигналов (ГПС). 24 Смоделировать процесс вычислений в ГЗ и ГПС с помощью программы на MPI, реализующей построение виртуальных топологий. 2. Разработать MPI-программу, выполняющую умножение матрицы 5 × 5 и вектора из 5 элементов на топологиях “кольцо” и “линейка”. Каждому процессорному элементу назначается строка матрицы 5 × 5, элементы вектора поочередно передаются (прокачиваются) вдоль линейки или по кольцу. Лабораторная работа №5 Разработка параллельных программ на языке OCCAM Теоретическая часть Основными единицами, из которых строится программа на языке Оккам, являются простейшие действия, или операции, из которых с помощью управляющих примитивов организуются различного рода процессы: последовательные, параллельные, альтернативные, условные, циклические. Операторных скобок в языке Оккам нет, поэтому принадлежность действия или подпроцесса какому-либо процессу определяется благодаря величине отступа от левого края, который был сделан при написании команды. Простейшие действия в Оккам принадлежат к одному из следующих видов: -присваивание; -ввод; -вывод; -дейстие SKIP (пустое действие); -действие STOP (блокировка выполнения процесса). Синтаксис операции присваивания: переменная:=выражение Синтаксис операции ввода данных: канал ? переменная Можно с помощью одной команды описать последовательность ввода нескольких переменных из одного канала. В этом случае имена переменных разделяются символом “точка с запятой”. 25 канал ? переменная1;переменная2; ... ;переменнаяN Синтаксис операции вывода данных: канал ! выражение Ввод и вывод данных соответствуют операциям чтения информации из канала и записи информации в канал. Каналами называются средства, позволяющие передавать данные между процессами. Обмен данными происходит тогда, когда оба процесса, и передающий данные, и ожидающий их поступления, готовы взаимодействовать по одноименному каналу, то есть взаимодействия синхронизируются. Каналы, наряду с константами и переменными, являются основными объектами, с которыми оперирует программа на языке Оккам. Все эти объекты являются именованными и подлежат предварительному описанию. Имена объектов могут включать в себя буквы, цифры и символ “точка”. Описания завершаются символом “двоеточие”. Возможно описать сразу несколько объектов, одной директивой, в этом случае имена описываемых объектов разделяются запятыми. Константы - это именованные объекты, которым соответствуют постоянные, неизменные значения. Синтаксис описания констант: DEF константа1=значение1, ..., константаN=значениеN: Переменные в Оккам представляют собой обозначения битовых комбинаций фиксированного размера. Переменные должны быть описаны раньше того процесса, в котором они используются. Изначально значения переменных не определены, но в последствии, в результате выполнения операций ввода или присваивания, они получают значения. Синтаксис описания переменных: VAR переменная1, ... ,переменнаяN: Каналы описываются аналогичным образом: CHAN канал1, ... , каналN: Поскольку канал - это средство взаимодействия между процессами, в области описания канала должно находиться два параллельных процесса. Поэтому удобнее всего расположить описание канала перед управляющим 26 примитивом PAR. В Оккам поддерживается только один структурированный тип данных: массивы переменных или каналов. Индексация элементов массивов начинается с нуля. Массивы переменных или констант описываются следующим образом: {VAR|CHAN} имя.массива [количество.элементов]: Здесь и далее фигурные скобки используются для перечисления вариантов, отделенных друг от друга вертикальной чертой. Имена могут быть присвоены и целым процессам. Описание именованного процесса предваряется ключевым словом PROC, за которым следуют имя процесса, формальные параметры (их пристуствие не обязательно), его тело (основной текст), и завершающий символ “двоеточие”: PROC имя (формальные.параметры) = текст.процесса : Управляющие примитивы SEQ, PAR, ALT служат для организации последовательных, параллельных, альтернативных процессов на базе простейших действий или других процессов, используя их в качестве подпроцессов. В случае SEQ-процесса входящие в его состав действия или процессы выполняются последовательно, один за другим. Пример: SEQ chan1 ? a chan2 ? b z:=a+b Действия и процессы, входящие в состав PAR-процесса, могут выполняться в любом порядке, возможно, они будут выполнены параллельно. PAR SEQ PAR chan1 ? a chan2 ? b z:=a+b chan3 ! z 27 SEQ PAR chan1 ! 5 chan2 ! 10 chan3 ? z Поскольку последовательность действий в случае PAR-процесса неопределена, то недопустимо наличие в одном PAR-процессе действий, изменяющих значение переменных, которые являются операндами в других действиях: PAR a:=a-b z:=a+b ALT-процесс включает в себя группу компонентов, из которых выполняется только один, тот, который считается “готовым”. Компонентом ALT-процесса является либо другой ALT-процесс, либо комбинация, состоящая из “сторожа” и охраняемого процесса. Охраняемый процесс - это собственно те действия, которые являются одной из альтернатив выполнения ALT-процесса. “Сторож” определяет готовность компонента, влияет на выбор альтернативы. В состав “сторожа” входят охраняющий процесс и логическое выражение. Логическое выражение не является обязательным, но если оно задано, то оно предшествует охраняющему процессу и отделяется от него знаком “&”. Охраняющий процесс SKIP готов всегда. В целом, “сторож”, считается готовым, если истинно логическое выражение и готов охраняющий процесс. Пример ALT-процесса: ALT (x>y) & chan1 ? a res ! a (x res ! zero.code Условный процесс, или IF-процесс, имеет следующий синтаксис: IF 28 логическое.выражение1 процесс1 . . . . логическое.выражениеN процессN В целом, IF-процесс больше напоминает оператор case языка Паскаль или оператор switch С/C++. В результате выполнения IF-процесса будет выполнен только тот процесс, которому соотвествует логическое выражение, имеющее значение “истина”. Пример: IF aa>b chan1 ! (-1) a=b chan1 ! 0 Для организации циклов используются WHILE-процессы. Фактически это последовательные циклы с неограниченным количеством повторений. Синтаксис описания WHILE-процесса: WHILE логическое.выражение повторяемый.процесс Пример использования WHILE-процесса: b:=TRUE WHILE b SEQ chan1 ? a chan2 ! a IF a>10 b:=FALSE Помимо традиционных последовательных циклов, Оккам позволяет задавать такую разновидность циклов, как массивы процессов. При этом указывается, сколько процессов надо повторить и каковы эти процессы. 29 Синтаксис описания массивов процессов: {ALT|PAR|SEQ|IF} имя.счетчика = [база FOR количество] повторяемый.процесс В общем случае циклы FOR есть не что иное, как способ организации циклов с заданным количеством повторений. Однако циклы PAR-FOR позволяют задавать массивы процессов, которые выполняются параллельно. В следующем примере производится параллельное заполнение 100 ячеек массива: VAR array [100]: CHAN buffer [100]: PAR i=[0 FOR 100] buffer[i] ? array[i] Пример последовательной прокачки данных через массив n параллельных процессов: CHAN b[n+1]: PAR j=[0 FOR n] WHILE TRUE VAR y: SEQ b[j]? y b[j+1]! y Экспериментальная часть. 1. Решить задачу из лабораторной работы №4 пункт 1 (вариант с ГЗ) на языке OCCAM. 2. Решить задачу об обедающих философах. Пять философов гуляют по саду и размышляют. Когда философ чувствует, что проголодался, он заходит в столовую. В столовой находится круглый стол, вокруг которого расположены пять стульев. Напротив каждого стула на столе стоит тарелка. Возле каждой тарелки, справа и слева от нее, находится по одной палочке (всего палочек пять) В центре стола находится миска лапши. Философов садится за стол, берет палочки и начинает есть лапшу. При этом философу, чтобы начать есть, необходимы две палочки – правая и левая. Утолив голод, философ снова выходит в сад и продолжает размышлять. 30 Требуется смоделировать поведение философов так, чтобы избегнуть блокировок. Блокировки возникают тогда, когда все философы сидят за столом, каждый взял по одной палочке, но никто не может начать есть лапшу. Решить задачу на языке OCCAM. 31 Список литературы 1. Робачевский А.М. Операционная система UNIX . - СПб.: БХВ- Петербург, 2000. - 528 с.: ил. 2. Котов В.Е. Сети Петри. - М.:Наука, Гл. ред. физ-мат. лит., 1984.- 160 с. 2. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. - СПб. : БХВ-Питербург, 2002.- 608 с. : ил. 4. Корнеев В.Д. Параллельное программирование в MPI. - Москва- ИжевскЖ Институт компьютерных исследований, 2003, 304 с. 5. Джоунс Г. Программирование на языке OCCAM. - М.:Мир, 1989. 32 |