Основы параллельного программирования вычислительных систем с распределенной и разделяемой памятью

if (b==0) c=a; else c = a/b;

должны быть выполнены  в два шага. На первом шаге все  процессорные элементы, чье локальное  значение b равно нулю, выполняют часть then. На втором шаге все остальные процессорные элементы выполняют часть else. MIMD-компьютеры являются более гибкими, так как каждый процессорный элемент может выполнять свой поток команд. Большинство параллельных компьютеров основаны на концепции MIMD.

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

2.2 Организация памяти параллельных  компьютеров

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

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

Компьютеры с  распределенной организацией памяти

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

Рисунок 1 – Структура  компьютера с распределенной памятью

Данные программы хранятся только в локальной памяти одного или нескольких узлов. Только локальный процессор имеет прямой доступ к локальной памяти. Когда процессор нуждается в данных из локальной памяти других узлов для выполнения своих вычислений, должна быть осуществлена передача сообщений по сети межсоединений. Следовательно, машины с распределенной памятью жестко связаны с моделью программирования, основанной на передаче сообщений, то есть на коммуникации взаимодействующих последовательных процессов. Так, для организации передачи сообщений два процесса Р_А и Р_В на различных узлах А и В отвечают за соответствующие операции передачи и приема. Когда Р_В нужны данные из локальной памяти узла А, Р_А осуществляет операцию пересылки этих данных. Р_В осуществляет операцию приема, задающую буфер для хранения данных, получаемых от процесса Р_А.

Архитектура компьютеров с распределенной памятью за историю своего развития претерпела много изменений, особенно касаемо сети межсоединений и присоединения узлов к данной сети. Сеть межсоединений первых мультикомпьютеров часто основывалась на непосредственном (прямом) соединении между узлами. В этом случае узел с определенным набором других узлов путем физических соединений. Типичная структура такой сети межсоединений – гиперкуб. Структура сетей с прямым соединением определяет возможные взаимодействия, так как каждый узел может обмениваться данными только со своим непосредственным соседом. Прямое соединение узлов ограничивает параллельное программирование, так как топология сети в этом случае определяет возможности обмена данными, и параллельные алгоритмы должны соответствовать данной структуре сети межсоединений.

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

Дальнейшее отделение коммуникационных операций от операций процессора может  быть осуществлено путем введения в  сеть маршрутизаторов (рис. 2, а). Маршрутизаторы формируют сеть, между узлами которой  может быть осуществлена передача сообщений. Узлы соединены с маршрутизаторами (рис. 2, б). Аппаратно поддерживаемая маршрутизация сокращает время передачи сообщений, так как сообщения для процессоров удаленных узлов могут быть доставлены маршрутизаторами по заранее определенному пути без задействования процессоров узлов, входящих в данный путь. При использовании маршрутизаторов нет большой разницы между временем передачи сообщений между соседними узлами и между удаленными узлами.

Рисунок 2 – Компьютеры с  распределенной памятью: а – узел, связанный с маршрутизатором; б – сеть межсоединений в форме сети маршрутизаторов

 различных узлов.

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

Совокупность компьютеров  со специальной сетью межсоединений  часто называют кластерами. Кластеры обычно основаны на стандартных компьютерах и даже на стандартных топологиях сетей. Кластер адресуется и программируется как единый блок. Популярность кластеров приходит с доступностью таких стандартных высокоскоростных межсоединений как FCS (Fiber Channel Standard, стандарт на волоконно-оптические каналы), SCI (Scalable Coherent Interface, масштабируемый когерентный интерфейс) и других (Switched Gigabit Ethernet, Myrinet,  InfiniBand). Естественной моделью программирования машин с распределенной памятью является модель, основанная на передаче сообщений, и поддерживаемая такими библиотеками, как MPI и PVM. Данные библиотеки часто основаны на стандартных протоколах, например на TCP/IP.

Разница между кластерными  системами и распределенными системами заключается в том, что в кластерах узлы используют одну и ту же операционную систему и обычно не могут быть адресованы индивидуально (то есть обратиться к какому-то отдельному узлу нельзя); в данном случае необходимо использование специального планировщика задач (job scheduler). Несколько кластерных систем могут быть соединены в решетчатые системы (grid systems) с помощью использования связующего программного обеспечения, такого как Globus Toolkit.

Компьютеры с  разделяемой памятью

Машины с разделяемой памятью состоят из некоторого количества процессоров или ядер, разделяемой физической памяти (глобальной памяти) и сети межсоединений, в данном случае соединяющей процессоры с памятью. Разделяемая память может быть реализована как множество модулей памяти (рис. 3).

Рисунок 3 – Компьютеры с  разделяемой памятью: а – абстрактная  структура; б – структура с  реализацией разделяемой памяти в виде модулей памяти

Естественная модель программирования машин с разделяемой памятью  – использование разделяемых переменных, доступ к которым может быть осуществлен всеми процессорами. Обмен данными между процессорами организуется путем чтения и записи разделяемых переменных, хранящихся в глобальной памяти. Следует избегать одновременного доступа нескольких процессоров к разделяемым переменным, так как в этом случае могут возникнуть состязания (race conditions), эффект от которых непредсказуем.

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

Частным случаем машин  с разделяемой памятью являются симметричные мультипроцессоры (SMPs, Symmetric Multiprocessors). Они имеют одну разделяемую память, обеспечивающую для каждой области памяти постоянное время доступа из любого процессора. SMP обычно содержат небольшое количество процессоров, соединенных центральной шиной, которая также обеспечивает доступ к разделяемой памяти. Обычно процессоры не имеют собственной памяти, а также отсутствуют специальные процессоры, ориентированные на операции ввода/вывода (процессоры ввода/вывода), но каждый процессор имеет собственную кэш-память. Как правило, доступ к локальному кэшу осуществляется быстрее, чем доступ к глобальной памяти. Можно сказать, что каждый многоядерный процессор – SMP-система.

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

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

2.3 Сети межсоединений

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

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

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

Различают статические и динамические сети межсоединений. Статическая сеть межсоединений соединяет узлы (процессоры или модули памяти) друг с другом напрямую путем физических связей. Такая сеть также называется прямой сетью или сетью с соединениями типа «точка-точка». Статические сети часто используются для систем с распределенным адресным пространством, где узел включает в себя процессор и соответствующий модуль памяти. Динамические сети межсоединений соединяют узлы посредством коммутаторов и связей. Такие сети также называются косвенными. Они используются как для систем с распределенным адресным пространством, так и для систем с разделяемым адресным пространством.

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

Алгоритм маршрутизации, стратегия  коммутации и топология сети в  совокупности определяют в значительной мере производительность сети.

2.3.1 Свойства сетей межсоединений. Статические сети межсоединений

Статическая сеть межсоединений может  быть представлена графом G = (V, E), где   V – множество вершин, E – множество ребер. Рассмотрим некоторые характеристики сетей.