Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Когда мы сталкиваемся с новой компьютерной системой параллельного действия, возникает три вопроса:
1. Каков тип, размер и количество процессорных элементов?
2. Каков тип, размер и количество модулей памяти?
3. Как взаимодействуют элементы памяти и процессорные элементы?
В любой системе параллельной обработки процессоры, выполняющие разные части одной задачи, должны как-то взаимодействовать друг с другом, чтобы обмениваться информацией. Как именно должен происходить этот обмен? Было предложено и реализовано две разработки: мультипроцессоры и мультикомпьютеры
Есть ряд причин, по которым практически невозможно достичь идеального повышения скорости: все программы содержат последовательную часть, они часто имеют фазу инициализации, они обычно должны считывать данные и собирать результаты. Большое количество процессоров здесь не поможет. Предположим, что на однопроцессорном компьютере программа работает Т секунд, причем доля (f) от этого времени является последовательным кодом, а доля (1-f) потенциально параллелизуется, как показано на рис. 9, а. Если второй код можно запустить на процессорах без издержек, то время выполнения программы в лучшем случае сократится с (l-f)T до (l-f)T/n, как показано на рис. 9, б. В результате общее время выполнения программы (и последовательной и параллельной частей) будет f T+(l-f )T/n. Коэффициент ускорения — это время выполнения изначальной программы (Т), разделенное на это новое время выполнения:
Speedup= n /d+(n-l)f)
Для f=0 мы можем получить линейное повышение скорости, но для f>0 идеальное повышение скорости невозможно, поскольку в программе имеется последовательная часть. Это явление носит название закона Амдала.
«В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента».[1] Согласно этому закону, ускорение выполнения программы за счётраспараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.
Закон Амдала показывает, что прирост эффективности вычислений зависит от алгоритма задачи и ограничен сверху для любой задачи с . Не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной системе.
Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь максимум. Это накладывает ограничение на масштабируемость вычислительной системы, то есть означает, что с определенного момента добавление новых узлов в систему будет увеличивать время расчёта задачи.
Для программирования мультикомпьютера требуется специальное программное обеспечение (обычно это библиотеки), чтобы обеспечить связь между процессами и синхронизацию. В этом разделе мы расскажем о таком программном обеспечении. Отметим, что большинство этих программных пакетов работают в системах МРР и COW.
В системах с передачей сообщений два и более процессов работают независимо друг от друга. Например, один из процессов может производить какие-либо данные, а другой или несколько других процессов могут потреблять их. Если у отправителя есть еще данные, нет никакой гарантии, что получатель (получатели) готов принять эти данные, поскольку каждый процесс запускает свою программу.
В большинстве систем с передачей сообщений имеется два примитива send и recei ve, но возможны и другие типы семантики. Ниже даны три основных варианта:
1. Синхронная передача сообщений.
2. Буферная передача сообщений.
3. Неблокируемая передача сообщений.
Синхронная передача сообщений. Если отправитель выполняет операцию send, а получатель еще не выполнил операцию recei ve, то отправитель блокируется до тех пор, пока получатель не выполнит операцию receive, а в это время сообщение копируется. Когда к отправителю возвращается управление, он уже знает, что сообщение было отправлено и получено. Этот метод имеет простую семантику и не требует буферизации. Но у него есть большой недостаток: отправитель блокируется до тех пор, пока получатель не примет и не подтвердит прием сообщения.
Буферная передача сообщений. Если сообщение отправляется до того, как получатель готов его принять, это сообщение временно сохраняется где-либо, например в почтовом ящике, и хранится там, пока получатель не возьмет его оттуда. При таком подходе отправитель может продолжать работу после операции send, даже если получатель в этот момент занят. Поскольку сообщение уже отправлено, отправитель может снова использовать буфер сообщений сразу же. Такая схема сокращает время ожидания. Вообще говоря, как только система отправила сообщение, отправитель может продолжать работу. Однако нет никаких гарантий, что сообщение было получено. Даже при надежной системе коммуникаций получатель мог сломаться еще до получения сообщения.
Неблокируемая передача сообщений. Отправитель может продолжать работу сразу после вызова. Библиотека только сообщает операционной системе, что она сделает вызов позднее, когда у нее будет время. В результате отправитель вообще не блокируется. Недостаток этого метода состоит в том, что когда отправитель продолжает работу после совершения операции send, он не может снова использовать буфер сообщений, так как есть вероятность, что сообщение еще не отправлено. Отправитель каким-то образом должен определять, когда он может снова использовать буфер. Например, можно опрашивать систему или совершать прерывание, когда буфер имеется в наличии. В обоих случаях программное обеспечение очень сложное.
В следующих двух разделах мы рассмотрим две популярные системы с передачей сообщений, которые применяются во многих мультикомпьютерах: PVM и MPI. Существуют и другие системы, но эти две наиболее распространенные.
PVM — виртуальная машина параллельного действия
12.1 РVM — виртуальная машина параллельного действия)
12.1.1. РVM (Parallel Virtual Machine — виртуальная машина параллельного действия) — это система с передачей сообщений, изначально разработанная для машин COW с операционной системой UNIX [45, 142]. Позднее она стала применяться в других машинах, в том числе в системах МРР. Это самодостаточная система с управлением процессами и системой ввода-вывода.
PVM состоит из двух частей: библиотеки, вызываемой пользователем, и «сторожевого» процесса, который работает постоянно на каждой машине в мульти-компьютере. Когда PVM начинает работу, она определяет, какие машины должны быть частью ее виртуального мультикомпьютера. Для этого она читает конфигурационный файл. «Сторожевой» процесс запускается на каждой из этих машин. Машины можно добавлять и убирать, вводя команды на консоли PVM.
Можно запустить п параллельных процессов с помощью команды
spawn -count n prog
Каждый процесс запустит prog. PVM решает, куда поместить процессы, но пользователь может сам подменять их с помощью аргументов команды spawn. Процессы могут запускаться из работающего процесса — для этого нужно вызвать процедуру Pvmjspawn. Процессы могут быть организованы в группы, причем состав групп может меняться во время выполнения программы.
Взаимодействие в машине PVM осуществляется с помощью примитивов для передачи сообщений таким образом, чтобы взаимодействовать могли машины с разными системами счисления. Каждый процесс PVM в каждый момент времени имеет один активный пересылочный буфер и один активный приемный буфер. Отправляя сообщение, процесс вызывает библиотечные процедуры, запаковывающие значения с самоописанием в активный пересылочный буфер, чтобы получатель мог узнать их и преобразовать в исходный формат.
Когда сообщение скомпоновано, отправитель вызывает библиотечную процедуру pvm_jend, которая представляет собой блокирующий сигнал send. Получатель может поступить по-разному. Во-первых, он может вызвать процедуру pvm__recv, которая блокирует получателя до тех пор, пока не придет подходящее сообщение. Когда вызов возвратится, сообщение будет в активном приемном буфере. Оно может быть распаковано и преобразовано в подходящий для данной машины формат с помощью набора распаковывающих процедур. Во-вторых, получатель может вызвать процедуру pvm_trecv, которая блокирует получателя наопределенный промежуток времени, и если подходящего сообщения за это время не пришло, он разблокируется. Процедура нужна для того, чтобы не заблокировать процесс навсегда. Третий вариант — процедура pvm_nrecv, которая сразу же возвращает значение — это может быть либо сообщение, либо указание на отсутствие сообщений. Вызов можно повторять, чтобы опрашивать входящие сообщения.
Помимо всех этих примитивов PVM поддерживает широковещание (процеду-papvmbcast) и мультивещание (процедура pvm_mcast). Первая процедура отправляет сообщение всем процессам в группе, вторая посылает сообщение только некоторым процессам, входящим в определенный список.
Синхронизация между процессами осуществляется с помощью процедуры pvm_barrier. Когда процесс вызывает эту процедуру, он блокируется до тех пор, пока определенное число других процессов не достигнет барьера и они не вызовут эту же процедуру. Существуют другие процедуры для управления главной вычислительной машиной, группами, буферами, для передачи сигналов, проверки состояния и т. д. PVM — это простой, легкий в применении пакет, имеющийся в наличии в большинстве компьютеров параллельного действия, что и объясняет его популярность.
12.1.2 MPI — интерфейс с передачей сообщений
Следующий пакет для программирования мультикомпьютеров — MPI (Message-Passing Interface — интерфейс с передачей сообщений). MPI гораздо сложнее, чем PVM. Он содержит намного больше библиотечных вызовов и намного больше параметров на каждый вызов. Первая версия MPI, которая сейчас называется MPI-1, была дополнена второй версией, MPI-2, в 1997 году. Ниже мы в двух словах расскажем о MPI-1, а затем посмотрим, что нового появилось в MPI-2. MPI-1, в отличие от PVM, никак не связана с созданием процессов и управлением процессами. Создавать процессы должен сам пользователь с помощью локальных системных вызовов. После создания процессы организуются в группы, которые уже не изменяются. Именно с этими группами и работает MPI.
В основе MPI лежат 4 понятия: коммуникаторы, типы передаваемых данных, операции коммуникации и виртуальные топологии. Коммуникатор — это группа процессов плюс контекст. Контекст — это метка, которая идентифицирует что-либо (например, фазу выполнения). В процессе отправки и получения сообщений контекст может использоваться для того, чтобы несвязанные сообщения не мешали друг другу.
Сообщения могут быть разных типов: символьные, целочисленные (short, regular и long integers), с обычной и удвоенной точностью, с плавающей точкой и т. д. Можно образовать новые типы сообщений из уже существующих.
MPI поддерживает множество операций коммуникации. Ниже приведена операция, которая используется для отправки сообщений:
MPI_Send(buffer. count. data_type. destination, tag. communicator)
Этот вызов отправляет содержимое буфера {buffer) с элементами определенного типа (datajtype) в пункт назначения. Count — это число элементов буфера. Поле tag помечает сообщение; получатель может сказать, что он будет приниматьсообщение только с данным тегом. Последнее поле показывает, к какой группе процессов относится целевой процесс (поле destination — это просто индекс списка процессов из определенной группы). Соответствующий вызов для получения сообщения таков:
MPI_Recv(&buffer, count, data_type. source, tag. cormiunicator. Sstatus)
В нем сообщается, что получатель ищет сообщение определенного типа из определенного источника с определенным тегом.
MPI поддерживает 4 основных типа коммуникации. Первый тип синхронный. В нем отправитель не может начать передачу данных, пока получатель не вызовет процедуру MPI_Recv. Второй тип — коммуникация с использованием буфера. Ограничение для первого типа здесь недействительно. Третий тип стандартный. Он зависит от реализации и может быть либо синхронным, либо с буфером. Четвертый тип сходен с первым. Здесь отправитель требует, чтобы получатель был доступен, но без проверки. Каждый из этих примитивов бывает двух видов: блокирующим и неблокирующим, что в сумме дает 8 примитивов. Получение может быть только в двух вариантах: блокирующим и неблокирующим.
MPI поддерживает коллективную коммуникацию — широковещание, распределение и сбор данных, обмен данными, агрегацию и барьер. При любых формах коллективной коммуникации все процессы в группе должны делать вызов, причем с совместимыми параметрами. Если этого сделать не удается, возникает ошибка. Например, процессы могут быть организованы в виде дерева, в котором значения передаются от листьев к корню, подчиняясь определенной обработке на каждом шаге (это может быть сложение значений или взятие максимума). Это типичная форма коллективной коммуникации.
Четвертое основное понятие в MPI — виртуальная топология, когда процессы могут быть организованы в дерево, кольцо, решетку, тор и т. д. Такая организация процессов обеспечивает способ наименования каналов связи и облегчает коммуникацию.
В MPI-2 были добавлены динамические процессы, доступ к удаленной памяти, неблокирующая коллективная коммуникация, расширяемая поддержка процессов ввода-вывода, обработка в режиме реального времени и многие другие особенности. В научном сообществе идет война между лагерями MPI и PVM. Те, кто поддерживают PVM, утверждают, что эту систему проще изучать и легче использовать. Те, кто на стороне MPI, утверждают, что эта система выполняет больше функций и, кроме того, она стандартизована, что подтверждается официальным документом.