Теория вычислительных процессов |
Лекция 14 |
Лекция 14
3.5. Программирование параллельных вычислений
3.5.1. Основные понятия
Исполнение процессов типичной параллельной программы прерывается значительно чаще, чем процессов, работающих в последовательной среде, так как процессы параллельной программы выполняют еще действия, связанные с обменом данными между процессорами. Манипулирование полновесными процессами в мультипрограммной среде является дорогостоящим действием, поскольку это тесно связанно с управлением и защитой памяти. Вследствие этого большинство парaллельных компьютеров использует легковесные процессы, называемые нитями или потоками управления, а не полновесные процессы. Легковесные процессы не имеют собственных защищенных областей памяти (хотя могут обладать собственными локальными данными), а в результате очень сильно упрощается манипулирование ими. Более того, их использование более безопасно.
В соответствии с возможностями параллельного компьютера процессы взаимодействуют между собой обычно одним из следующих способов.
Обмен сообщениями. Посылающий процесс формирует сообщение с заголовком, в котором указывает, какой процессор должен принять сообщение, и передает сообщение в сеть, соединяющую процессоры. Если, как только сообщение было передано в сеть, посылающий процесс продолжает работу, то такой вид отправки сообщения, называется не блокирующим. Если же посылающий процесс ждет, пока принимающий процесс не примет сообщение, то такой вид отправки сообщения, называется блокирующим. Принимающий процесс должен знать, что ему необходимы данные, и должен указать, что готов получить сообщение, выполнив соответствующую команду приема сообщения. Если ожидаемое сообщение еще не поступило, то принимающий процесс приостанавливается до тех пор, пока сообщение не поступит.
Обмен через общую память. В архитектурах с общедоступной памятью процессы связываются между собой через общую память - посылающий процесс помещает данные в известные ячейки памяти, из которых принимающий процесс может считывать их. При таком обмене сложность представляет процесс обнаружения того, когда безопасно помещать данные, а когда удалять их. Чаще всего для этого используются стандартные методы операционной системы, такие как семафоры или блокировки процессов. Однако это дорого и сильно усложняет программирование. Некоторые архитектуры предоставляют биты занято/свободно, связанные с каждым словом общей памяти, что обеспечивает легкий и высокоэффективный способ синхронизации отправителей и приемников.
Прямой доступ к удаленной памяти. В первых архитектурах с распределенной памятью работа процессоров прерывалась каждый раз, когда поступал какой-нибудь запрос от сети, соединяющей процессоры. В результате процессор плохо использовался. Затем в таких архитектурах в каждом процессорном элементе стали использовать пары процессоров - один процессор (вычислительный), исполняет программу, а другой (процессор обработки сообщений) обслуживает сообщения, поступающие из сети или в сеть. Такая организация обмена сообщениями позволяет рассматривать обмен сообщениями как прямой доступ к удаленной памяти, к памяти других процессоров. Эта гибридная форма связи, применяется в архитектурах с распределенной памятью, обладает многими свойствами архитектурах с общей памятью.
Рассмотренные механизмы связи не обязательно используются только непосредственно на соответствующих архитектурах. Так легко промоделировать обмен сообщениями, используя общую память, с другой стороны можно смоделировать общую память, используя обмен сообщениями. Последний подход известен как виртуальная общая память.
Наиболее желательными (даже скорее обязательными) признаками параллельных алгоритмов и программ являются:
. параллелизм,
. масштабируемость,
. локальность,
. модульность.
Параллелизм указывает на способность выполнения множества действий одновременно, что существенно для программ выполняющихся на нескольких процессорах.
Масштабируемость - другой важнейший признак параллельной программы, который требует гибкости программы по отношению к изменению числа процессоров, поскольку наиболее вероятно, что их число будет постоянно увеличиваться в большинстве параллельных сред и систем.
Локальность характеризует необходимость того, чтобы доступ к локальным данным был более частым, чем доступ к удаленным данным. Важность этого свойства определяется отношением стоимостей удаленного и локального обращений к памяти. Оно является ключом к повышению эффективности программ на архитектурах с распределенной памятью.
Модульность отражает степень разложения сложных объектов на более простые компоненты. В параллельных вычислениях это такой же важный аспект разработки программ, как и в последовательных вычислениях.
Код, исполняющийся в одиночном процессоре параллельного компьютера, находится в некоторой программной среде такой же, что и среда однопроцессорного компьютера с мультипрограммной операционной системой, поэтому и в контексте параллельного компьютера так же говорят о процессах, ссылаясь на код, выполняющийся внутри защищенного региона памяти операционной системы. Многие из действий параллельной программы включают обращения к удаленным процессорам или ячейкам общей памяти. Выполнение этих действий может потребовать времени, существенного, особенно, по отношению к времени исполнения обычных команд процессора. Поэтому большинство процессоров исполняет более одного процесса одновременно, и, следовательно, в программной среде отдельно взятого процессора параллельного компьютера применимы обычные методы мультипрограммирования.
3.5.2. Многопоточная обработка
Если L - метка некоторого места в программе, то команда: fork L
передает управление на метку L, а также и на следующую команду в тексте программы. В результате создается эффект, что с этого момента два процессора одновременно исполняют одну и ту же программу. Каждый из них независимо обрабатывает свою последовательность команд. Поскольку каждая такая последовательность обработки может снова разветвиться, эта техника получила название многопоточной обработки.
Введя способ разбиения одного процесса на два, мы нуждаемся и в способе слияния двух процессов в один. Проще всего ввести команду join, которая может выполниться только при одновременном исполнении ее двумя процессами. Первый достигший этой команды процесс должен ждать, когда ее достигнет другой. После этого уже только один процесс продолжает исполнение последующих команд.
Разновидность команды ветвления до сих пор используется в операционной системе UNIXTM. При этом ветвление не подразумевает переход по метке. Его эффект заключается во взятии совершенно новой копии всей памяти программы и передачи этой копии новому процессу. Как исходный, так и новый процессы продолжают исполнение с команды, следующей за командой ветвления. У каждого процесса есть средство определить, является ли он порождающим (отец) или порождаемым (сын). Выделение процессам непересекающихся участков памяти снимает основные трудности и опасности многопоточной обработки, но может быть неэффективным как по времени, так и по объему памяти. Это означает, что параллелизм допустим только на самом внешнем (самом глобальном) уровне задания, а использование его в мелком масштабе затруднительно.
3.5.3. Условные критические участки
Предположим, например, что один процесс изменяет некоторую переменную с целью, чтобы другой процесс считывал ее новое значение. Второй процесс не должен считывать значения переменной до тех пор, пока оно не будет изменено. Аналогично, первый процесс не должен изменять значение переменной до тех пор, пока все остальные процессы не считают ее предыдущие значения.
Для решения этой проблемы предложено удобное средство, называемое условным критическим участком. Он имеет вид
witb общеперем wben условие do критический участок
При входе в критический участок проверяется значение условия. Если оно истинно, критический участок исполняется как обычно, но если условие ложно, данный вход в критический участок задерживается, чтобы позволить другим процессам войти в свои критические участки и изменить общую переменную. По завершении каждого такого изменения происходит перепроверка условия. Если оно стало истинным, отложенному процессу позволяют продолжать исполнение своего критического участка; в противном случае процесс вновь откладывается. Если можно запустить более чем один из приостановленных процессов, выбор между ними произвольный.
Своим возникновением и развитием мониторы обязаны понятию класса. Основной идеей является то, что все осмысленные операции над данными (включая их инициализацию) должны быть собраны вместе с описанием структуры и типа самих данных. Активизация этих операций должна происходить при вызове процедуры всякий раз, когда этого требуют процессы, совместно использующие данные. Важной характеристикой монитора является то, что одновременно может быть активным только одно из его процедурных тел; даже когда два процесса одновременно делают вызов процедуры (одной и той же или двух различных), один из вызовов (<<ждет”) откладывается до завершения другого. Таким образом, тела процедур ведут себя как критические участки, защищенные одним и тем же семафором.
Приведем пример очень простого монитора, ведущего себя как счетчиковая переменная. В обозначениях языка РASCAL он имеет вид
Пример 3.31.
1 monitor счет;
2 var n: iпteger
3 procedure* вверх; begin n := n + 1 end;
4 procedure* "вниз; when > 0 do begin n := п - 1 end;
5 function* приземл. Вооlеап; begin приземл := (n = 0) end;
6 begin n := 0;
7 ...;
8 if n <> 1 then priпt(n)
9 end
Строка
1 описывает монитор с именем счет.
2 описывает локальную для монитора общую переменную n. Она доступна только внутри самого монитора.
3 - 5 описывают три процедуры и их тела. Звездочки обеспечивают вызов этих процедур из программы, использующей монитор.
6 здесь начинается исполнение монитора.
7 три жирные точки обозначают внутреннее предложение, соответствующее блоку, который будет использовать монитор.
8 при выходе из использующего блока печатается конечное значение n (если оно ненулевое).
Новый экземпляр этого монитора может быть описан локальным для блока Р:
instance ракета: счет; Р
Внутри блока Р можно вызывать помеченные звездочками процедуры, используя команды
ракета. вверх;... ракета. вниз;. ..;, if ракета.приземл then...
Непомеченная же процедура или такая переменная, как n, недостижимы из Р. Свойственное мониторам взаимное исключение позволяет вызывать процедуру монитора любому числу процессов внутри Р без взаимного влияния при изменении n. Заметим, что попытка вызвать ракета. вниз при n. = 0 будет отложена до тех пор, пока некоторый другой процесс внутри Р не вызовет ракета. вверх. Это гарантирует, что значение n никогда не станет отрицательным.
Неэффективность повторяющейся проверки входных условий привела к появлению мониторов с более сложной схемой явного ожидания и явной подачей сигнала о возобновлении ожидающего процесса. Эти схемы даже позволяют приостанавливаться процедурному вызову в процессе его исполнения подвоздействием автоматически возникающего исключения до того момента, когда некоторый последующий вызов процедуры другим процессом подаст сигнал о возобновлении приостановленного процесса. Таким путем можно эффективно реализовать множество оригинальных способов планирования, которые реализуются программой-планировщиком.
Так как в мониторе ожидающих процессов может быть несколько, простой порядок обслуживания очереди состоящий в том, что освобождается процесс, ожидающий дольше всех, гарантирует, что ни один из обратившихся процессов не будет задержан на неопределенное время.
3.6. Модели параллельных вычислений
Параллельное программирование представляет дополнительные источники сложности - необходимо явно управлять работой тысяч процессоров, координировать миллионы межпроцессорных взаимодействий. Для того, чтобы решить задачу на параллельном компьютере, необходимо распределить вычисления между процессорами системы так, чтобы каждый процессор был занят решением части задачи. Кроме того, желательно, чтобы как можно меньший объем данных пересылался между процессорами, поскольку коммуникации значительно больше медленные операции, чем вычисления. Часто, возникают конфликты между степенью распараллеливания и объемом коммуникаций, то есть, чем между большим числом процессоров распределена задача, тем больший объем данных необходимо пересылать между ними. Среда параллельного программирования должна обеспечивать адекватное управление распределением и коммуникацией данных.
Из-за сложности параллельных компьютеров и их существенного отличия от традиционных однопроцессорных компьютеров нельзя просто воспользоваться традиционными языками программирования и ожидать получения хорошей производительности. Рассмотрим основные модели параллельного программирования.
В этой модели программы состоят из одного или более процессов, распределенных по процессорам. Процессы выполняются одновременно. Их число может измениться в течение времени выполнения программы. Процессы обмениваются данными через каналы, которые представляют собой однонаправленные коммуникационные линии, соединяющие только два процесса. Каналы можно создавать и удалять. Модель характеризуется следующими свойствами.
1) Параллельное вычисление состоит из одного или более одновременно исполняющихся процессов, число которых может изменяться в течение времени выполнения программы.
2) Процесс - это последовательная программа с локальными данными. Процесс имеет входные и выходные порты, которые служат интерфейсом к среде процесса.
3) В дополнение к обычным операциям процесс может выполнять следующие действия: послать сообщение через выходной порт, получить сообщение из входного порта,создать новый процесс и завершить процесс.
4) Посылающаяся операция асинхронная - она завершается сразу, не ожидая того, когда данные будут получены. Получающаяся операция синхронная: она блокирует процесс до момента поступления сообщения.
5) Пары из входного и выходного портов соединяются очередями сообщений, называемыми каналами. Каналы можно создавать и удалять. Ссылки на каналы (порты) можно включать в сообщения, так что связность может измениться динамически.
6) Процессы можно распределять по физическим процессорам (или одиночному процессору) произвольным способами, причем используемое отображение (распределение) не воздействует на семантику программы.
Понятие процесс а позволяет говорить о местоположении данных; данные, содержащихся в локальной памяти процесса - расположены “близко”, другие данные “удалены”. Понятие канала обеспечивает механизм для указания того, что для того, чтобы продолжить вычисление одному процессу требуются данные другого процесса (зависимость по данным).
В этой модели программы, возможно различные, написанные на традиционном последовательном языке исполняются процессорами компьютера. Каждая программа имеют доступ к памяти исполняющего ее процессора. Программы обмениваются между собой данными, используя подпрограммы приема/передачи данных некоторой коммуникационной системы.
На сегодняшний день модель обмен сообщениями является наиболее широко используемой моделью параллельного программирования. Программы этой модели, подобно программам модели процесс/канал, создают множество процессов, с каждым из которых ассоциированы локальные данные. Каждый процесс идентифицируется уникальным именем. Процессы взаимодействуют, посылая и получая сообщения. В этом отношении модель обмен сообщениями является разновидностью модели процесс/канал и отличается только механизмом, используемым при передаче данных.
Модель не накладывает ограничений ни на динамическое создание процессов, ни на выполнение нескольких процессов одним процессором, ни на использование разных программ для разных процессов. Просто формальные описания систем обмена сообщениями не рассматривают вопросы, связанные с манипулированием процессами. Однако при реализации таких систем приходится принимать какое-либо решение в этом отношении. На практике сложилось так, что большинство систем обмена сообщениями при запуске параллельной программы создает фиксированное число идентичных процессов и не позволяет создавать и разрушать процессы в течение работы программы.
В таких системах каждый процесс выполняет одну и ту же программу, но работает с разными данными.
В этой модели единственная программа задает распределение данных между всеми процессорами компьютера и операции над ними. Распределяемыми данными обычно являются массивы. Как правило, язык программирования, поддерживающие данную модель, допускают операции над массивами, позволяют использовать в выражениях целыe массивы, вырезки из массивов. Распараллеливание операций над массивами, циклов обработки массивов позволяет увеличить производительность программы. Компилятор отвечает за генерацию кода, осуществляющего распределение элементов массивов и вычислений между процессорами. Каждый процессор отвечает за то подмножество элементов массива, которое расположено в его локальной памяти. Программы с параллелизмом данных могут быть оттранслированы и исполнены как на МIМD, так и на SIМD компьютерах.
Модель также является часто используемой моделью параллельного программирования. Название модели происходит оттого, что она эксплуатирует параллелизм, который заключается в применении одной и той же операции к множеству элементов структур данных. Например, “умножить все элементы массива М на значение х”. Программа с параллелизмом данных состоит из последовательностей подобных операций. Поскольку операции над каждым элементом данных можно рассматривать как независимые процессы, то степень детализации таких вычислений очень велика, а понятие <<локальности” (распределения по процессам) данных отсутствует. Следовательно, компиляторы языков с параллелизмом данных требуют, чтобы программист предоставил информацию относительно того, как данные должны быть распределены между процессорами, другими словами, как программа должны быть разбита на процессы.
В этой модели все процессы совместно используют общее адресное пространство. Процессы асинхронно обращаются к общей памяти как с запросами на чтение, так и с запросами на запись, что создает проблемы при выборе момента, когда можно будет поместить данные в память, когда можно будет удалить их. Для управления доступом к общей памяти используются стандартные механизмы синхронизации - семафоры и блокировки процессов.
В модели все процессы совместно используют общее адресное пространство, к которому они асинхронно обращаются с запросами на чтение и запись. В таких моделях для управления доступом к общей памяти используются всевозможные механизмы синхронизации типа семафоров и блокировок процессов. Преимущество этой модели с точки зрения программирования состоит в том, что понятие собственности данных (монопольного владения данными) отсутствует, следовательно, не нужно явно задавать обмен данными между производителями и потребителями. Эта модель, с одной стороны, упрощает разработку программы, но, с другой стороны, затрудняет понимание и управление локальноcтью данных, написание детерминированных программ. В основном модель используется при программировании для архитектур с общедоступно памятью.
3.7. Вопросы и задания для самоконтроля
1. Расскажите об общем понятия процесса как математической абстракции взаимодействия системы и ее окружения.
2. Покажите, как с помощью механизма рекурсии можно описывать протяженные во времени и бесконечные процессы.
3. Объясните, как можно представить поведение процесса в виде протокола последовательности его действий.
4. Какие свойства протоколов и операции над ними Вам известны?
5. Каковы правила, помогающие получить реализации процессов, сопровожденные доказательством их соответствия исходным спецификациям?
6. Каковы способы построения из отдельных процессов систем, компоненты которых взаимодействуют друг с другом и с общим окружением?
7. Как можно избежать многих традиционных для параллельного программирования проблем, таких, как взаимное влияние и взаимное исключение, прерывания, зацикливание, многопоточная обработка и т. п.?
8. Как следует вводить понятие параллелизма?
9. Расскажите о понятии взаимодействия как об особом способе взаимосвязи двух процессов.
10. Каким образом достигается синхронизация и буферизация взаимодействия?
11. Расскажите о понятии подчинения и подчиненного процесса.
12. Как известные объекты структурного и объектного программирования, такие, как мониторы, классы, модули, критические участки и заурядные подпрограммы, могут реализовываться в виде последовательных взаимодействующих процессов?
13. Как с помощью модели последовательных взаимодействующих процессов доказывается правильность при проектировании и разработке вычислительных систем?
14. Дайте понятие виртуального ресурса.
15. Какова роль семафоров и мониторов, реальных и виртуальных процессов?
16. Расскажите о моделях параллельных вычислений и их свойствах.
17. Объясните, в чем заключаются недостатки модели общей памяти и как их следует преодолевать.
назад | содержание | вперед