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

Введение

 

Язык программирования mpC - это расширение языка Си, разработанное специально для программирования параллельных вычислений на обычных сетях разнородных компьютеров [5]. Основной целью параллельных вычислений является ускорение решения задачи. Именно это отличает параллельные вычисления от распределённых, для которых основной целью является обеспечить совместную работу программных компонент, изначально размещённых на различных компьютерах. В случае параллельных вычислений разбиение программы на компоненты, размещаемые на разных компьютерах, является лишь средством для ускорения работы программы, а не врождённым свойством этой программы. Поэтому, основное внимание в языке mpC уделяется средствам, позволяющим максимально облегчить разработку как можно более эффективных программ для решения задач на обыкновенных сетях компьютеров.

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

Для начала рассмотрим простейшую программу, которая выводит на терминал пользователя текст "Hello, world!". Код этой программы мало отличается от кода программы на Си. Первое отличие - спецификатор [*] перед именем main в определении главной функции. Он специфицирует вид функции, говоря о том, что код этой функции выполняется всеми процессами параллельной программы. Функции, подобные main, называются в mpC базовыми. Корректная работа таких функций возможна только при условии их вызова всеми процессами параллельной программы. Контроль за корректностью вызовов базовых функций осуществляется компилятором.

#include <stdio.h>

int [*]main() {

[host] printf ("Hello, world.\n");

}

 

Второе отличие - это конструкция [ host ] перед именем функции printf в выражении, где эта стандартная библиотечная функция языка Си вызывается. В отличие от функции main, для корректной работы функции printf не требуется ее параллельного вызова всеми процессами параллельной программы. Такие функции называются в mpC узловыми. Язык предоставляет возможность вызова узловой функции, как отдельным процессом параллельной программы, так и её параллельного вызова группой процессов. В нашем случае, функция printf выполняется только одним процессом параллельной программы, а именно, процессом, связанным с терминалом пользователя, из которого он запускал на выполнение эту параллельную программу. Ключевое имя host жёстко связано в языке mpC именно с этим процессом. Изменим программу таким образом, чтобы все процессы параллельной программы выполняли вызов функции printf. Библиотечная узловая функция MPC_Printf языка mpC гарантирует вывод приветствия на терминал пользователя от каждого компьютера, участвующего в процессе параллельной программы.

 

#include <mpc.h>

 int [*]main()

{

MPC_Printf(" Hello, world! \n");

}

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

 

#include <mpc.h>

#include <sys/utsname.h>

int [*]main()

{

struct utsname un;

uname(&un);

MPC_Printf("Hello world! I'm on \"%s\".\n",

                      un.nodename);

}

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

 После выполнения вызова узловой (библиотечной) функции uname, поле nodename структуры un будет содержать ссылку на имя компьютера, на котором этот процесс выполняется.

Каждый из процессов параллельной программы выполняет вызов функции uname, после чего поле nodename соответствующей проекции распределённой структуры un содержит ссылку на имя того компьютера, на котором этот процесс выполняется.

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

 

#include <mpc.h>

#include <sys/utsname.h>

int [*]main()

{

struct utsname un;

repl int one;

repl int number_of_processes;

uname(&un);

one = 1;

number_of_processes = one[+];

MPC_Printf("Hello world! I'm one of %d processes"

                   "and run on \"%s\".\n",

                   number_of_processes, un.nodename);}

Для этого в программе определены две целые распределённые переменные one и number_of_processes. Сначала в результате выполнения присваивания one = 1 всем проекциям переменной one присваивается значение 1. Результатом применения постфиксной операции [+] к переменной one будет распределённое значение, проекция которого на любой из процессов равна сумме значений проекций переменной one. Другими словами, проекция значения выражения one [+] на любой из процессов параллельной программы будет равна их общему количеству. В результате присваивания этого распределённого значения распределенной переменной number_of_processes все проекции последней будут содержать одно и то же значение, а именно, общее число процессов параллельной программы.

Определение распределённой переменной one содержит ключевое слово repl (сокращение от replicated), которое информирует компилятор о том, что в любом выражении проекции значения этой переменной на разные процессы параллельной программы равны между собой. Такие распределённые переменные называются в mpC размазанными (соответственно, значение размазанной переменной называется размазанным значением). Размазанные переменные и выражения играют большую роль в mpC. Компилятор контролирует объявленное программистом свойство размазанности и предупреждает обо всех случаях, когда оно может быть нарушено.

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

 

#include <mpc.h>

#include <sys/utsname.h>

 int [*]main()

{

struct utsname un;

uname(&un);

MPC_Printf("Hello world! I'm one of %d processes" "and run on \"%s\".\n",

                     MPC_Total_nodes(), un.nodename);

}

 

Эта программа эффективней предыдущей программы еще и тем, что параллельный вызов функции MPC_Total_nodes, в отличие от вычисления выражения one [+], не требует обмена данными между процессами программы.

 

Сети. Родитель сети

 

Программы, которые мы до сих пор рассматривали, описывали вычисления, в которых участвовали либо все процессы параллельной программы, либо только хост - процесс. Очень часто число процессов, вовлечённых в параллельное решение задачи, зависит от самой задачи и/или параллельного алгоритма её решения и определяется входными данными. Например, если для параллельного моделирования движения N групп тел под влиянием взаимного притяжения используется отдельный процесс для каждой группы тел, то в соответствующие параллельные вычисления должны быть вовлечены в точности N процессов. Запуск параллельной программы осуществляется средствами внешними по отношению к языку mpC. Общее число составляющих её процессов не определяется разработчиком программы на mpC. У разработчика есть лишь языковые средства для определения этого числа.

Рассмотрим программу, которая даёт первое знакомство с языковыми средствами, позволяющими программисту описывать параллельные вычисления на нужном числе процессов. Сами вычисления, по-прежнему, предельно просты - каждый из участвующих в них процессов просто выводит на терминал пользователя приветствие "Hello, world!". Число же участвующих процессов (N =3) будет задаваться программистом.

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

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

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

 

#include <mpc.h>

#define N 3

int [*]main()

 {

net SimpleNet(N) mynet;

[mynet]MPC_Printf("Hello, world!\n"); }

 

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

Заметим схожесть конструкций [mynet] и [host]. Ключевое слово host можно рассматривать как имя сети из одного виртуального процессора, который всегда отображается на связанный с терминалом пользователя хост - процесс.

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

 

#include <mpc.h>

#include <sys/utsname.h>

#define N 3

int [*]main()

{

net SimpleNet(N) mynet;

struct utsname [mynet]un;

[mynet]uname(&un);

[mynet]MPC_Printf(" Hello world! I'm on \"%s\".\n", un.nodename);

}

Следующая программа семантически полностью эквивалентна предыдущей программе, однако за счет использования специальной распределенной метки [mynet]: имеет более простой синтаксис. Оператор, помеченный такой меткой, полностью выполняется виртуальными процессорами соответствующей сети.

 

#include <mpc.h>

#include <sys/utsname.h>

#define N 3

 int [*]main()

{

net SimpleNet(N) mynet;

[mynet]:

  {

     struct utsname un;

     uname(&un);

     MPC_Printf("Hello world! I'm on \"%s\".\n", un.nodename);

}

}

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

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

 

#include <mpc.h>

#include <sys/utsname.h>

#define Nmin 3

#define Nmax 5

int [*]main()

{

repl n;

for(n=Nmin; n<=Nmax; n++)

{

   auto net SimpleNet(n) anet;

  [anet]:

     {

            struct utsname a;

            uname(&a);

           MPC_Printf("I'm from an automatic network on \"%s\" (n=%d).\n",

                                a.nodename, n);

     }

}

}

 

#include <mpc.h>

#include <sys/utsname.h>

#define Nmin 3

#define Nmax 5

int [*]main() {

repl n;

for(n=Nmin; n<=Nmax; n++) {

static net SimpleNet(n) snet;

[snet]: {

struct utsname s;

uname(&s);

MPC_Printf("I'm from the static network on \"%s\" (n=%d).\n",

                s.nodename, n);

}

}

}

В процессе выполнении первой программы при входе в блок на первом витке цикла создается автоматическая сеть из трёх виртуальных процессоров (n = Nmin = 3), которая при выходе из цикла уничтожается. При входе в блок на втором витке цикла создается новая автоматическая сеть уже из четырёх виртуальных процессоров, которая также прекращает своё существование при выходе из блока, так что к моменту выполнения повторной инициализации цикла (n ++) эта 4-процессорная сеть уже не существует. Наконец, на последнем витке при входе в блок создаётся автоматическая сеть из пяти виртуальных процессоров (n = Nmax = 5).

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

Таким образом, в отличие от первой программы, в которой одно и то же имя mynet на разных витках цикла обозначает совершенно разные сети, во второй программе имя s net обозначает уникальную сеть, существующую с момента первого входа в блок, в котором она определяется, и до конца выполнения программы. Если класс сети не специфицирован явно путём использования ключевого слова auto или static в определении сети, то, по умолчанию, она считается автоматической, если сеть определена внутри функции, и статической, если определена вне функции.

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

Вообще говоря, в программе на mpC нельзя определить просто сеть, а можно определить лишь сеть того или иного типа. Тип является важнейшим атрибутом сети, в частности, конкретизируя операции доступа к её виртуальным процессорам. Указание типа является обязательной частью определения любой сети. Поэтому, всякому определению сети должно предшествовать определение соответствующего сетевого типа. В рассмотренных нами примерах определение используемого сетевого типа SimpleNet находится среди прочих стандартных определений языка mpC в заголовке mpc.h и включается в программу с помощью директивы #include препроцессора. Выглядит это определение следующим образом:

 

nettype SimpleNet(int n)

{

сoord I=n;

};

Оно вводит имя SimpleNet сетевого типа, параметризованного целым параметром n. В теле определения объявляется координатная переменная I, изменяющаяся в пределах от 0 до n-1. Тип SimpleNet является простейшим параметризованным сетевым типом и соответствует сетям, состоящим из n виртуальных процессоров, линейно-упорядоченных своим местоположением на координатной прямой. Рассмотрим следующую программу

#include < mpc. h >

#define N 5

int [*]main()

{

net SimpleNet(N) mynet;

[mynet]:

 {

int my_coordinate;

my_coordinate = I coordof mynet;

if(my_coordinate%2==0)

MPC_Printf("Hello, even world!\n");

else

MPC_Printf("Hello, odd world!\n");

}

}

 Она демонстрирует, каким образом можно запрограммировать выполнение различных вычислений виртуальными процессорами с различными координатами. В этой программе используется бинарная операция coordof, левым операндом которой, в нашем случае, является координатная переменная I, а правым - сеть mynet. Результатом операции будет целое значение, распределённое по сети mynet, такое, что его проекция на любой из виртуальных процессоров будет равна значению координаты I этого процессора в сети. После присваивания my_coordinate = I coordof mynet значения проекций переменной my_coordinate будут равны координатам соответствующих виртуальных процессоров в сети mynet. В результате, виртуальные процессоры с чётными координатами выведут на терминал пользователя приветствие "Hello, even world!", а виртуальные процессоры с нечётными координатами - приветствие "Hello, odd world!".

Ниже приведенная программа демонстрирует сеть, виртуальные процессоры которой привязаны к двумерной системе координат. Каждый из виртуальных процессоров сети выводит на терминал пользователя свои координаты в сети и имя компьютера, на котором его разместила программа. Заметим, что в качестве второго операнда операции coordof в этой программе используется не сеть, а переменная un.

 

#include <mpc.h>

#include <sys/utsname.h>

nettype Mesh(int m, int n)

{

coord I=m, J=n;

};

#define M 2

#define N 3

int [*]main() {

net Mesh(M,N) mynet;

[mynet]:

{

struct utsname un;

uname(&un);

MPC_Printf("I'm on \"%s\" and have coordinates (%d, %d).\n",

          un.nodename, I coordof un, J coordof un);

}

}

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

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

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

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

 

#include <mpc.h>

#include <sys/utsname.h>

nettype Mesh(int m, int n)

{

coord I=m, J=n;

parent [0,0];

};

#define M 2

#define N 3

int [*]main() {

net Mesh(M,N) [host]mynet;

[mynet]:

{

struct utsname un;

uname(&un);

MPC_Printf("I'm on \"%s\" and have coordinates (%d, %d).\n",

          un.nodename, I coordof un, J coordof un);

}

}

 

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

 

Синхронизация процессов

 

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

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

Предположим, что нам нужно построить программу таким образом, чтобы сообщения от виртуальных процессоров с нечётными координатами выводились на терминал пользователя только после того, как будут выведены сообщения от всех виртуальных процессоров с чётными координатами. Язык mpC предоставляет для решения этой задачи библиотечную функцию MPC _ Global _ barrier (void), которая синхронизирует работу всех процессов параллельной программы. Её описание находится в заголовке mpc.h и выглядит следующим образом:

 

int [*]MPC_Global_barrier(void);

 

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

 

#include <mpc.h>

#define N 5

int [*]main()

{

net SimpleNet(N) mynet;

int [mynet]my_coordinate;

my_coordinate = I coordof mynet;

if(my_coordinate%2==0)

[mynet]MPC_Printf("Hello, even world!\n");

MPC_Global_barrier();

if(my_coordinate%2==1)

[mynet]MPC_Printf("Hello, odd world!\n");

}

Литература

1. Вендров А.М. CASE - технологии. Современные методы и средства  

проектирования информационных систем. - http://www.citforum.ru

2. Липаев В.В. Качество программного обеспечения. - М.: Финансы и

статистика, 2005. - 263 с.

3. Кнут Дональд Э. Искусство программирования. Т. 3. Сортировка и

поиск: Уч. пос. - М.: Издательский дом «Вильямс», 2005.-832 с.

 

4. Шилдт Г. Самоучитель С++ - СПб:BHV-Санкт-Петербург, 1998. - 512 с.

 

5. Ластовецкий А.Л. Программирование параллельных вычислений на

неоднородных сетях компьютеров на языке mpC. - http://parallel.ru