Программирование параллельных вычислений

Основные понятия

Исполнение процессов типичной параллельной программы прерывается значительно чаще, чем процессов, работающих в последовательной среде, так как процессы параллельной программы выполняют еще действия, связанные с обменом данными между процессорами. Манипулирование полновесными процессами в мультипрограммной среде является дорогостоящим действием, поскольку это тесно связанно с управлением и защитой памяти. Вследствие этого большинство параллельных компьютеров использует легковесные процессы, называемые нитямиили потоками управления, а не полновесные процессы. Легковесные процессы не имеют собственных защищенных областей памяти (хотя могут обладать собственными локальными данными), а в результате очень сильно упрощается манипулирование ими. Более того, их использование более безопасно.

В соответствии с возможностями параллельного компьютера процессы взаимодействуют между собой обычно одним из следующих способов:

§ Обмен сообщениями. Посылающий процесс формирует сообщение с заголовком, в котором указывает, какой процессор должен принять сообщение, и передает сообщение в сеть, соединяющую процессоры. Если, как только сообщение было передано в сеть, посылающий процесс продолжает работу, то такой вид отправки сообщения, называется неблокирующим. Если же посылающий процесс ждет, пока принимающий процесс не примет сообщение, то такой вид отправки сообщения, называется блокирующим. Принимающий процесс должен знать, что ему необходимы данные, и должен указать, что готов получить сообщение, выполнив соответствующую команду приема сообщения. Если ожидаемое сообщение еще не поступило, то принимающий процесс приостанавливается до тех пор, пока сообщение не поступит.

§ Обмен через общую память. В архитектурах с общедоступной памятью процессы связываются между собой через общую память - посылающий процесс помещает данные в известные ячейки памяти, из которых принимающий процесс может считывать их. При таком обмене сложность представляет процесс обнаружения того, когда безопасно помещать данные, а когда удалять их. Чаще всего для этого используются стандартные методы операционной системы, такие как семафоры или блокировки процессов. Однако это дорого и сильно усложняет программирование. Некоторые архитектуры предоставляют биты занято/свободно, связанные с каждым словом общей памяти, что обеспечивает легким и высокоэффективный способ синхронизации отправителей и приемников.

§ Прямой доступ к удаленной памяти. В первых архитектурах с распределенной памятью работа процессоров прерывалась каждый раз, когда поступал какой-нибудь запрос от сети, соединяющей процессоры. В результате процессор плохо использовался. Затем в таких архитектурах в каждом процессорном элемент стали использовать пары процессоров - один процессор (вычислительный), исполняет программу, а другой (процессор обработки сообщений) обслуживает сообщения, поступающие из сети или в сеть. Такая организация обмена сообщениями позволяет рассматривать обмен сообщениями как прямой доступ к удаленной памяти, к памяти других процессоров. Эта гибридная форма связи, применяется в архитектурах с распределенной памятью, обладает многими свойствами архитектурах с общей памятью.

Рассмотренные механизмы связи необязательно используются только непосредственно на соответствующих архитектурах. Так легко промоделировать обмен сообщениями, используя общую память, с другой стороны можно смоделировать общую память, используя обмен сообщениями. Последний подход известен как виртуальная общая память.

Наиболее желательными (даже скорее обязательными) признаками параллельных алгоритмов и программ являются:

§ параллелизм,

§ масштабируемость,

§ локальность,

§ модульность.

Параллелизм указывает на способность выполнения множества действий одновременно, что существенно для программ выполняющихся на нескольких процессорах.

Масштабируемость - другой важнейший признак параллельной программы, который требует гибкости программы по отношению к изменению числа процессоров, поскольку наиболее вероятно, что их число будет постоянно увеличиваться в большинстве параллельных сред и систем.

Локальность характеризует необходимость того, чтобы доступ к локальным данным был более частым, чем доступ к удаленным данным. Важность этого свойства определяется отношением стоимостей удаленного и локального обращений к памяти. Оно является ключом к повышению эффективности программ на архитектурах с распределенной памятью.

Модульность отражает степень разложения сложных объектов на более простые компоненты. В параллельных вычислениях это такой же важный аспект разработки программ, как и в последовательных вычислениях.

Код, исполняющийся в одиночном процессоре параллельного компьютера, находится в некоторой программной среде такой же, что и среда однопроцессорного компьютера с мультипрограммной операционной системой, поэтому и в контексте параллельного компьютера так же говорят опроцессах, ссылаясь на код, выполняющийся внутри защищенного региона памяти операционной системы. Многие из действий параллельной программы включают обращения к удаленным процессорам или ячейкам общей памяти. Выполнение этих действий может потребовать время, существенное, особенно, по отношению к времени исполнения обычных команд процессора. Поэтому большинство процессоров исполняет более одного процесса одновременно, и, следовательно, в программной среде отдельно взятого процессора параллельного компьютера применимы обычные методы мультипрограммирования.