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

Диаметр d(G) сети G – максимальное расстояние между некоторой парой узлов сети. Степень g(G) сети G – максимальная степень узла сети (степень узла – количество узлов, смежных данному узлу). Введем B(G) – минимальное количество ребер, которое должно быть удалено, чтобы разделить сеть G на две части одинакового размера без сохранения каких-либо связей между этими частями. При нечетном числе узлов размер частей может отличаться на 1.

Связность узлов или ребер сети – число узлов или связей, которые должны быть удалены из сети, чтобы нарушить ее работу. Большое значение связности означает большую надежность сети.

Обозначим n = |V| – количество узлов  в сети межсоединений. Рассмотрим разновидности  статических сетей межсоединений.

Полный граф – сеть G, в которой каждый узел непосредственно соединен со всеми другими узлами. В сети типа «линейный массив» узлы выстроены в последовательность, и между каждой парой смежных узлов имеется двунаправленное соединение. В сети типа «кольцо» узлы соединены в кольцо; по сравнению с сетью в виде линейного массива в такой сети присутствует еще одна двунапраленная связь между первым и последним узлами. К более сложным разновидностям относятся d-мерная сетка (или d-мерный массив), d ≥ 1, d-мерный тор, k-мерный куб (или гиперкуб), состоящий из 2^k узлов, соединенных в соответствии с рекурсивной конструкцией и некоторые другие, показанные на рисунке 4.

В таблице 1 показаны характеристики статических сетей межсоединений определенных технологий.

Рисунок 4 – Статические сети межсоединений: а – полный граф; б – линейный массив; в – кольцо; г – двумерная сетка; д – двумерный тор; е – k-мерный куб для k = 1,2,3,4; ж – кубическая сеть с циклами для k = 3; з – полное бинарное дерево; и – сеть с «тасовкой», состоящая из 8 узлов (пунктирные линии представляют обмен, прямые – тасовку)

 

Таблица 1 – Характеристики статических сетей межсоединений  различных топологий

Сеть G с n узлами	Степень g(G)	Диаметр d(G)	Связность ребер	B(G)
Полный граф	n – 1	1	n – 1
Линейный массив	2	n – 1	1	1
Кольцо	2		2	2
m-мерная сетка	2m		m
m-мерный тор	2m		2m
k-мерный гиперкуб           (n = 2k)	lg n	lg n	lg n	n/2
k-мерная кубическая сеть с циклами        (n = k2k для k≥3)	3	2k – 1 +	3
Полное бинарное дерево (n = 2k-1)	3		1	1
k-арный m-куб (n = km)	2m		2m	2km-1

 

2.3.2 Динамические сети межсоединений

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

Сети с шинной архитектурой. Пример такой сети показан на рисунке 5. В данном случае 64-разрядная шина соединяет процессоры P₁,…,P_n (их кэш-памяти – C₁,…,C_n) с модулями памяти M₁,…,M_n.

Рисунок 5 – Сеть с шинной архитектурой

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

Перекрестные сети. Сеть размерности , относящаяся к данному типу, имеет  n входов и m выходов (рисунок 6,а).

Рисунок 6 – Перекрестная сеть с n процессорами и m модулями памяти:

а – структура; б – возможные  состояния коммутатора

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

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

Регулярные многозвенные сети коммутации характеризуются регулярной структурой: число входов и выходов у всех коммутаторов имеет один и тот же  порядок (на рисунке 7 – порядки a и b соответственно).

Рисунок 7 – Многозвенные сети коммутации с коммутаторами в виде матричных переключателей

Идея построения сетей, состоящих  из нескольких ступеней развивается  в омега-сетях (omega networks), сетях с архитектурой типа «сачок» (butterfly networks), магистральных сетях (baseline networks) и некоторых других более сложных сетях, основанных на данных сетях, более сложных сетях. На рисунке 8 показан пример омега-сети.

Рисунок 8 – Омега сеть 16 х 16 (трехмерная)

 

 

 

 

3 Введение в  программирование с использованием передачи сообщений

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

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

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

Коммуникационные библиотеки обычно содержат большой набор коммуникационных функций. В большинстве случаев  используются переносимые библиотеки, определяющие синтаксис и семантику коммуникационных функций, и поддерживаемые широким классом параллельных компьютеров. Наиболее популярной библиотекой является MPI (Message-Passing Interface), также часто используется PVM (Parallel Virtual Machine).

3.1 Введение в MPI

MPI определяет синтаксис и семантику библиотечных подпрограмм для стандартных коммуникационных моделей. Поддерживается связь с языками C, C++, Fortran-77 и Fortran-95. В дальнейшем мы будем рассматривать только интерфейс с языком С. MPI-стандарт включает две версии. Версия MPI-1 определяет стандартные коммуникационные операции и основана на статической модели процессов. MPI-2 расширяет MPI-1 и обеспечивает поддержку управления динамическими процессами, одностороннего взаимодействия и параллельного ввода/вывода.

MPI, являясь интерфейсной спецификацией для синтаксиса и семантики коммуникационных операций, оставляет открытым вопрос реализации. Поэтому в различных MPI-библиотеках могут быть различные реализации, использующие, например, определенную оптимизацию для конкретных аппаратных платформ. Программисту MPI предоставляет стандартный интерфейс, гарантируя тем самым переносимость MPI-программ. Свободно доступными MPI-библиотеками являются MPICH, LAM/MPI и OpenMPI.

MPI-программа состоит из набора процессов, обменивающихся сообщениями. В MPI-1 используется статическая модель процессов, в которой количество процессов устанавливается при запуске MPI-программы и не может быть изменено во время выполнения программы. Таким образом, MPI-1 не поддерживает динамическое создание процессов во время выполнения программы. Такая возможность добавлена в MPI-2. Как правило, каждый процессор параллельной системы исполняет один MPI-процесс, и количество запускаемых процессов должно быть адаптировано к количеству имеющихся процессоров. Обычно все MPI-процессы выполняют одну и ту же программу в стиле SPMD (Single Program, Multiple Data, одна программа – много данных). Каждый процесс может читать и записывать данные из/в файлы. Для координирования ввода/вывода необходимо, чтобы только один определенный процесс осуществлял операции ввода/вывода. Для поддержки переносимости MPI-программа должна быть написана для произвольного количества процессов. Реальное количество процессов, используемых для выполнения программы, устанавливается при запуске этой программы.

Во многих параллельных системах MPI-программа может быть запущена из командной строки. Часто используются следующие команды:

mpiexec -n 4 <имя программы> <аргументы программы>

mpirun -np 4 <имя программы> <аргументы программы>

Данные команды запускают MPI-программу с 4 процессами. Команды для запуска программы в разных параллельных системах могут отличаться.

Пример. Если вам уже не терпится скомпилировать и выполнить свою первую простейшую MPI-программу, то вы можете легко это сделать на своем домашнем компьютере. Рассмотрим процессы установки OpenMPI в операционной системе Linux (в данном случае использовалась Linux Mint 9.0, основанная на Ubuntu Linux 10.04) и запуска программы “Hello, World”.

Для установки необходимо скачать  с официального сайта (http://www.open-mpi.org/) файл openmpi-1.4.3.tar.gz (к примеру; на момент написания версия 1.4.3 – последняя стабильная версия OpenMPI), зайти через терминал в директорию с этим файлом и последовательно выполнить следующие команды (процесс установки займет некоторое время):

tar -xf openmpi-1.4.3.tar.gz

cd openmpi-1.4.3

./configure --prefix=/usr/local

sudo make all install

По окончании установки понадобится  набрать в терминале еще одну команду:

export LD_LIBRARY_PATH=/usr/local/lib

Теперь можно перейти  к написанию программы. Нужно  создать файл hello.c со следующим содержанием:

#include <stdio.h>

#include "mpi.h"

int main(int argc, char **argv) {

  MPI_Init(&argc, &argv);

  printf("Hello, World!\n");

  MPI_Finalize();

return 0;

}

Теперь, зайдя через терминал в директорию с этим файлом и последовательно  выполнив команды

mpicc -o hello hello.c

mpirun -np 1 hello

увидим результат: Hello, World! #

Значительная часть операций, предоставляемых MPI – операции обмена данными между процессами. Ниже будут рассмотрены основные MPI-операции.

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

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

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

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

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