Программирование параллельных вычислений на неоднородных сетях компьютеров на языке mpC
Интерактивный учебный курс
А.Л.Ластовецкий (lastov@ispras.ru), ИСП РАН
Что такое mpC?
Язык программирования mpC - это расширение языка Си, разработанное специально для программирования параллельных вычислений на обычных сетях разнородных компьютеров. Основной целью параллельных вычислений является ускорение решения задачи. Именно это отличает параллельные вычисления от распределённых, для которых основной целью является обеспечить совместную работу программных компонент, изначально размещённых на различных компьютерах. В случае параллельных вычислений разбиение программы на компоненты, размещаемые на разных компьютерах, является лишь средством для ускорения работы программы, а не врождённым свойством этой программы. Поэтому, основное внимание в языке mpC уделяется средствам, позволяющим максимально облегчить разработку как можно более эффективных программ для решения задач на обыкновенных сетях компьютеров.
Cмотрите также:
- mpC Tutorial (руководство на английском языке, новая версия от 19 октября 2000 года).
- Web-страница проекта (также на английском).
- Первые программы
- Сети.
- Тип сети.
- Родитель сети.
- Синхронизация процессов.
- Сетевые функции.
- Подсети.
- Векторные вычисления.
- Неоднородные параллельные вычисления.
Параллельная программа - множество параллельных процессов, взаимодействующих (синхронизирующих свою работу и обменивающихся данными) посредством передачи сообщений. Программист на mpC не может управлять тем, сколько процессов составляют программу и на каких компьютерах эти процессы выполняются. Это делается внешними по отношению к языку средствами. Исходный код на mpC управляет лишь тем, какие именно вычисления выполняются каждым из процессов, составляющих программу.
Для начала рассмотрим простейшую программу p1.mpc , которая делает то же самое, что и, пожалуй, самая известная программа на языке Си, выводящая на терминал пользователя текст "Hello, world!".
Код этой программы очень мало отличается от кода программы на Си. Первое отличие - спецификатор [*] перед именем main в определении главной функции. Он специфицирует вид функции, говоря о том, что код этой функции выполняется всеми процессами параллельной программы. Функции, подобные функции main, называются в mpC базовыми. Корректная работа таких функций возможна только при условии их вызова всеми процессами параллельной программы. Контроль за корректностью вызовов базовых функций осуществляется компилятором.
Второе отличие - это конструкция [host] перед именем функции printf в выражении, где эта стандартная библиотечная функция языка Си вызывается. В отличие от функции main, для корректной работы функции printf не требуется ее параллельного вызова всеми процессами параллельной программы. Более того, вполне осмысленен и корректен вызов этой функции любым отдельно взятым процессом параллельной программы. Такие функции называются в mpC узловыми. Язык предоставляет возможность вызова узловой функции как отдельным процессом параллельной программы, так и её параллельного вызова группой процессов. В нашем случае, функция printf выполняется только одним процессом параллельной программы, а именно, процессом, связанным с терминалом пользователя, из которого он запускал на выполнение эту параллельную программу. Ключевое имя host жёстко связано в языке mpC именно с этим процессом.
Таким образом, выполнение программы заключается в том, что за исключением хост-процесса, который выполняет вызов функции printf, все остальные процессы программы просто ничего не делают.
Следующая программа, p2.mpc , внешне ещё меньше отличается от программы "Hello, world!" на языке Си. Однако, содержательно, она описывает больше параллельных вычислений, чем программа p1.mpc . А именно, выполнение программы p2.mpc заключается в том, что все процессы параллельной программы выполняют вызов функции printf. Результат работы этой программы зависит от операционного окружения, в котором выполняется программа. В некоторых окружениях стандартный вывод всех параллельных процессов направляется на терминал пользователя, с которого он запускал программу. В этом случае, пользователь увидит столько приветствий "Hello, world!" на своём терминале, сколько параллельных процессов составлят программу - по одному от каждого процесса. В других окружениях вы увидите приветствия только от процессов, выполняющихся на том же компьютере, что и хост-процесс, или даже только от хост-процесса.
Непереносимость программы p2.mpc (различные результаты работы в разных окружениях) является серьёзным недостатком. Программа p3.mpc, выводящая на терминал пользователя приветствия от всех процессов параллельной программы, лишена этого недостатка. Библиотечная узловая функция MPC_Printf языка mpC гарантирует вывод приветствия на терминал пользователя от каждого выполняющего её процесса параллельной программы.
Следующая программа, p4.mpc, отличается от нашей первой программы p1.mpc лишь тем, что хост-процесс выводит на терминал пользователя более содержательное послание, в то время как остальные процессы параллельной программы по-прежнему ничего не делают. А именно, кроме приветствия "Hello, world!" хост-процесс сообщает имя компьютера, на котором он выполняется. С этой целью в программе определяется переменная un, размещённая в памяти хост-процесса (этот факт специфицируется с помощью конструкции [host] перед именем переменной в её определении). После выполнения хост-процессом вызова узловой (библиотечной) функции uname, поле nodename структуры un будет содержать ссылку на имя компьютера, на котором этот процесс выполняется.
Следующая программа, p5.mpc , выводит на терминал пользователя более содержательные послания уже от всех процессов параллельной программы. Кроме приветствия "Hello, world!" каждый процесс сообщает имя компьютера, на котором он выполняется. С этой целью в программе определяется распределённая переменная un.
Эта переменная называется распределённой, потому что каждый процесс параллельной программы содержит в своей памяти копию этой переменной, и тем самым, область памяти, представляемая этой переменной, распределена между процессами параллельной программы. Таким образом, распределённая переменная un есть не что иное, как совокупность нераспределённых переменных, каждая из которых, в свою очередь, является проекцией распределённой переменной на соответствующий процесс.
Каждый из процессов параллельной программы p5.mpc выполняет вызов функции uname, после чего поле nodename соответствующей проекции распределённой структуры un содержит ссылку на имя того компьютера, на котором этот процесс выполняется.
Значения распределённых переменных и распределённых выражений, таких как un.nodename или &un, естественным образом распределены по процессам параллельной программы и называются распределённми значениями.
Программа p6.mpc расширяет вывод программы p5.mpc информацией об общем числе процессов параллельной программы. Для этого в программе определены 2 целые распределённые переменные one и number_of_processes. Сначала в результате выполнения присваивания one=1 всем проекциям переменной one присваивается значение 1. Результатом применения постфиксной операции [+] к переменной one будет распределённое значение, проекция которого на любой из процессов равна сумме значений проекций переменной one. Другими словами, проекция значения выражения one[+] на любой из процессов параллельной программы будет равна их общему количеству. В результате присваивания этого распределённого значения распределенной переменной number_of_processes все проекции последней будут содержать одно и то же значение, а именно, общее число процессов параллельной программы.
Определение распределённой переменной one содержит ключевое слово repl (сокращение от replicated), которое информирует компилятор о том, что в любом выражении проекции значения этой переменной на разные процессы параллельной программы равны между собой. Такие распределённые переменные называются в mpC размазанными (соответственно, значение размазанной переменной называется размазанным значением). Размазанные переменные и выражения играют большую роль в mpC. Компилятор контролирует объявленное программистом свойство размазанности и предупреждает обо всех случаях, когда оно может быть нарушено.
Заметим, что более простая программа p7.mpc обеспечивает такой же результат, что и программа p6.mpc, используя библиотечную узловую функцию MPC_Total_nodes языка mpC, которая как раз и возвращает общее число процессов параллельной программы. Программа p7.mpc, кроме того, эффективней программы p6.mpc, поскольку параллельный вызов функции MPC_Total_nodes, в отличие от вычисления выражения one[+], не требует обмена данными между процессами программы.
Программа p8.mpc, полученная небольшим изменением программы p6.mpc, наоборот, менее эффективна. Зато она демонстрирует, как в языке mpC присваивание может быть использовано для обмена данными между процессами. Переменная local_one размещена в памяти хост-процесса и инициализируется значением 1. Переменная one размазана по процессам параллельной программы. Выполнение присваивания one=local_one заключается в рассылке значения переменной local_one всем процессам программы с последующим его присваиванием проекциям переменной one.
Программы, которые мы до сих пор рассматривали, описывали вычисления, в которых участвовали либо все процессы параллельной программы, либо только хост-процесс. Очень часто, однако, число процессов, вовлечённых в параллельное решение задачи, зависит от самой задачи и/или параллельного алгоритма её решения и определяется входными данными. Например, если для параллельного моделирования N групп тел под влиянием взаимного притяжения используется отдельный процесс для каждой группы тел, то в соответствующие параллельные вычисления должны быть вовлечены в точности N процессов, независимо от общего числа процессов, составляющих параллельную программу (напомним, что запуск параллельной программы осуществляется средствами, внешними по отношению к языку mpC, и, следовательно, общее число составляющих её процессов не определяется разработчиком программы на mpC - у него есть лишь языковые средства для определения этого числа).
Программа p9.mpc даёт первое знакомство с языковыми средствами, позволяющими программисту описывать параллельные вычисления на нужном числе процессов. Сами вычисления, по-прежнему, предельно просты - каждый из участвующих в них процессов просто выводит на терминал пользователя приветствие "Hello, world!". Число же участвующих процессов (N=3) задаётся программистом и не зависит от общего числа процессов, составляющих параллельную программу.
Группе процессов, совместно выполняющих некоторые параллельные вычисления, в языке mpC соответствует понятие сети. Сеть в mpC - это абстрактный механизм, облегчающий программисту работу с реальными физическими процессами параллельной программы (подобно тому, как понятия объекта данных и переменной в языках программирования облегчают работу с памятью).
В простейшем случае, сеть - это просто множество виртуальных процессоров. Для программирования вычислений на нужном числе параллельных процессов, прежде всего, нужно определить сеть, состоящую из соответствующего числа виртуальных процессоров. И лишь после того, как сеть определена, можно приступать к описанию параллельных вычислений на этой сети.
Определение сети вызывает создание группы процессов, представляющей эту сеть, так что каждый виртуальный процессор представляется отдельным процессом параллельной программы. Описание вычислений на сети вызывает выполнение соответствующих вычислений процессами параллельной программы, представляющими виртуальные процессоры сети. Важное отличие реальных процессов от виртуальных процессоров заключается в том, что в разные моменты выполнения параллельной программы один и тот же процесс может представлять различные виртуальные процессоры различных сетей. Другими словами, определение сети вызывает отображение её виртуальных процессоров на реальные процессы параллельной программы, и это отображение сохраняется всё время жизни сети.
Так, в программе p9.mpc сначала определяется сеть mynet, состоящая из N виртуальных процессоров, а затем на этой сети вызывается узловая библиотечная функция MPC_Printf. Выполнение этой программы заключается в параллельном вызове функции MPC_Printf теми N процессами программы, на которые отображены виртуальные процессоры сети mynet. Это отображение осуществляется системой программирования языка mpC во время выполнения программы. Если система программирования не может выполнить отображение (например, если значение N превышает общее число процессов программы), то программа завершается аварийно с соответствующей диагностикой.
Заметим схожесть конструкций [mynet] и [host]. Действительно, ключевое слово host можно рассматривать как имя предопределённой сети из одного виртуального процессора, который всегда отображается на связанный с терминалом пользователя хост-процесс.
Программа p10.mpc выводит на терминал пользователя более содержательные послания от тех процессов параллельной программы, на которые отображаются виртуальные процессоры сети mynet. Кроме приветствия "Hello, world!", такой процесс сообщает имя компьютера, на котором он выполняется. Для этого, в программе определяется переменная un, распределённая по сети mynet. Только процессы, реализующие виртуальные процессоры сети mynet, содержат в своей памяти копию этой переменной. Только эти процессы выполняют вызов функции uname (это специфицируется конструкцией [mynet] перед именем функции), после чего поле nodename каждой проекции распределённой структуры un будет содержать ссылку на имя того компьютера, на котором соответствующий процесс выполняется.
Программа p11.mpc семантически полностью эквивалентна программе p10.mpc, однако за счет использования специальной, распределенной, метки [mynet]: имеет более простой синаксис. Оператор, помеченный такой меткой (в нашем случае, это составной оператор), полностью выполняется виртуальными процессорами соответствующей сети.
Следующая программа, p12.mpc, демонстрирует, что число виртуальных процессоров сети может задаваться динамически, то есть во время выполнения программы. Эта программа интерпретирует свой единственный внешний параметр как такое число. Этот параметр задаётся пользователем при запуске программы и доступен, по крайней мере, хост-процессу. Выражение [host]atoi(argv[1]) вычисляется хост-процессом, а затем присваивается целой переменной n, размазанной по всем процессам параллельной программы. Выполнение этого присваивания заключается в рассылке вычисленного значения всем процессам программы с последующим его присваиванием проекциям переменной n. Прежде чем определять (создавать) сеть, состоящую из заданного пользователем числа виртуальных процессоров, и выполнять требуемые вычисления на этой сети, программа проверяет корректность исходных данных. Если заданное число виртуальных процессоров некорректно (меньше 1 или больше общего числа процессов параллельной программы), программа выводит на терминал пользователя соответствующее сообщение. В противном случае, определяется сеть mynet, состоящая из n виртуальных процессоров, и определяется переменная un, распределённая по этой сети. Затем на сети mynet вызывается узловая функция uname, после чего поле nodename каждой проекции распределённой структуры un будет содержать ссылку на имя того компьютера, на котором система программирования языка mpC разместила соответствующий виртуальный процессор. Наконец, вызов узловой функции MPC_Printf на сети mynet выводит на терминал пользователя приветствие от каждого виртуального процессора и имя компьютера, на котором он находится.
Время жизни сети mynet, как и время жизни переменной un, ограничено блоком, в котором эта сеть определяется. При выходе из этого блока, все процессы программы, захваченные под виртуальные процессоры сети mynet, освобождаются и могут быть использованы при создании других сетей. Такие сети называются в mpC автоматическими.
В отличие от автоматических, время жизни статических сетей ограничено лишь временем выполнения программы. Программы p13.mpc и p14.mpc демонстрируют различие статических и автоматических сетей. Программы выглядят практически идентичными. Обе они заключаются в циклическом выполнении блока, включающего определение сети и выполнении уже знакомых вычислений на этой сети. Единственным, но существенным, отличием является то, что в первой программе определяется автоматическая сеть, а во второй - статическая.
В процессе выполнении программы p13.mpc, при входе в блок на первом витке цикла создается автоматическая сеть из трёх виртуальных процессоров (n=Nmin=3), которая при выходе из цикла уничтожается. При входе в блок на втором витке цикла создается новая автоматическая сеть уже из четырёх виртуальных процессоров, которая также прекращает своё существование по выходе из блока, так что к моменту выполнения повторной инициализации цикла (n++) эта 4-процессорная сеть уже не существует. Наконец, на последнем витке при входе в блок создаётся автоматическая сеть из пяти виртуальных процессоров (n=Nmax=5).
В процессе выполнении программы p14.mpc, при входе в блок на первом витке цикла также создается сеть из трёх виртуальных процессоров, однако по выходе из блока она не уничтожается, а просто просто перестаёт быть видна. Таким образом, в этом случае блок является не областью существования сети, а областью её видимости. Поэтому, во время выполнения повторной инициализации цикла и проверки условия цикла эта статическая 3-процессорная сеть существует, но недоступна (эти точки программы находятся вне области видимости имени сети mynet). При повторных входах в блок на последующих витках цикла никакие новые сети не создаются, а просто становится видна та статическая сеть, которая была создана при первом входе в блок.
Таким образом, в отличие от программы p13.mpc, в которой одно и то же имя mynet на разных витках цикла обозначает совершенно разные сети, в программе p14.mpc имя mynet обозначает уникальную сеть, существующую с момента первого входа в блок, в котором она определяется, и до конца выполнения программы.
Если класс сети не специфицирован явно путём использования ключевого слова auto или static в её определении, то, по умолчанию, она считается автоматической, если определена внутри функции, и статической, если определена вне функции. Таким образом, все сети из программ p9.mpc, p10.mpc, p11.mpc и p12.mpc неявно определены как автоматические.
В разобранных до настоящего момента программах все виртуальные процессоры сетей параллельно выполняли абсолютно одинаковые вычисления. Поэтому, у нас не было необходимости различать их внутри сети. Если же параллельный алгоритм, который нужно запрограммировать, предполагает, что различные параллельные процессы должны выполнять разные вычисления, то необходимы средства для выделения отдельных виртуальных процессоров внутри сети. Такие средства предусмотрены в языке mpC. Они позволяют привязывать виртуальные процессоры любой сети к некоторой системе координат и выделять отдельный виртуальный процессор путем задания его координат.
Вообще говоря, в программе на mpC нельзя определить просто сеть, а можно определить лишь сеть того или иного типа. Тип является важнейшим атрибутом сети, в частности, конкретизируя операции доступа к её виртуальным процессорам. Указание типа является обязательной частью определения любой сети. Поэтому, всякому определению сети должно предшествовать определение соответствующего сетевого типа. В рассмотренных нами примерах определение используемого сетевого типа SimpleNet находится среди прочих стандартных определений языка mpC в заголовке mpc.h и включается в программу с помощью директивы #include препроцессора. Выглядит это определение следующим образом:
nettype SimpleNet(int n) {
coord I=n;
};
Оно вводит имя SimpleNet сетевого типа, параметризованного целым параметром n. В теле определения объявляется координатная переменная I, изменяющаяся в пределах от 0 до n-1. Тип SimpleNet является простейшим параметризованным сетевым типом и соответствует сетям, состоящим из n виртуальных процессоров, линейно-упорядоченных своим местоположением на координатной прямой.
Программа p15.mpc, полученная путём небольшой модификации программы p9.mpc, демонстрирует, каким образом можно запрограммировать выполнение различных вычислений виртуальными процессорами с различными координатами. В этой программе используется бинарная операция coordof, левым операндом которой, в нашем случае, является координатная переменная I, а правым - сеть mynet. Результатом операции будет целое значение, распределённое по сети mynet, такое, что его проекция на любой из виртуальных процессоров будет равна значению координаты I этого процессора в сети. После присваивания my_coordinate = I coordof mynet значения проекций переменной my_coordinate будут равны координатам соответствующих виртуальных процессоров в сети mynet. В результате, виртуальные процессоры с чётными координатами выведут на терминал пользователя приветствие "Hello, even world!", а виртуальные процессоры с нечётными координатами - приветствие "Hello, odd world!".
Программа p16.mpc демонстрирует сеть, виртуальные процессоры которой привязаны к двумерной системе координат. Каждый из виртуальных процессоров сети выводит на терминал пользователя свои координаты в сети и имя компьютера, на котором его разместила система программирования. Заметим, что в качестве второго операнда операции coordof в этой программе используется не сеть, а переменная un. В общем случае, если вторым операндом операции coordof является не сеть, а выражение, то это выражение не вычисляется, а используется лишь для определения сети, по которой распределено его значение, а операция выполняется так, как если бы в качестве второго операнда использовалась эта сеть.
Мы уже говорили, что время жизни автоматической сети ограничено блоком, в котором она определена. При выходе из этого блока сеть прекращает своё существование, а процессы программы, захваченные под виртуальные процессоры сети, освобождаются и могут быть использованы при создании других сетей.
Возникает вопрос, каким образом результаты вычислений, выполненных на такой автоматической сети, сохраняются и могут быть использованы в дальнейших вычислениях. В уже разобранных программах такой проблемы не возникало, так как единственным результатом вычислений на любой из сетей был вывод на терминал пользователя того или иного сообщения.
На самом деле, сети в языке mpC не являются абсолютно независимыми друг от друга. Каждая вновь создаваемая сеть имеет в точности один виртуальный процессор, общий с уже существующими на момент создания сетями. Этот виртуальный процессор называется родителем создаваемой сети и является тем связующим звеном, через которое передаются результаты вычислений на сети в случае прекращения её существования. Родитель сети явно или неявно специфицируется её определением.
До сих пор ни одна сетей не была определена с явным указанием родителя. Во всех случаях родитель специфицировался неявно, и этим родителем был ни кто иной, как виртуальный хост-процессор. Это решение очевидно, поскольку в любой момент выполнения любой программы гарантируется существование лишь одной сети - предопределенной сети host, состоящей из единственного виртуального процессора, который всегда отображается на связанный с терминалом пользователя хост-процесс.
Программа p17.mpc полностью эквивалентна программе p16.mpc, с той разницей, что в определении сети неявная спецификация родителя сети заменена на явную.
Ещё одно различие можно найти в определении сетевого типа. Там добавлена строка, явно специфицирующая координаты родителя в сетях этого типа (по умолчанию, родитель имеет нулевые координаты в создаваемой сети). Если бы нам по какой-то причине понадобилось, чтобы родитель сети mynet имел не наименьшую, а наибольшую координату, то в определении сетевого типа Mesh вместо спецификации parent [0,0] следовало бы использовать спецификацию parent [m-1,n-1].
В любой из уже разобранных программ в каждый момент времени её выполнения одновременно существует не больше одной сети. Это не ограничение языка. Язык mpC позволяет писать программы с произвольным числом параллельно существующих сетей. Единственным ограничением является общее число процессов, составляющих параллельную программу, на которые отображаются виртуальные процессоры сетей.
В программе p18.mpc параллельно существует три сети - net1, net2 и net3. Родителем сети net1 является виртуальный хост-процессор. Родителем сети net2 является виртуальный процессор сети net1 с координатой 1. Родителем сети net3 является виртуальный процессор сети net1 с координатой 2.
Мы уже говорили, что параллельная программа - это множество параллельных процессов, синхронизирующих свою работу и обменивающихся данными посредством передачи сообщений. Средства языка mpC, с которыми мы уже познакомились, позволяют программисту специфицировать требуемое для параллельного решения задачи число процессов и распределить вычисления между этими процессами. Этих же средств, в принципе, достаточно для описания синхронизации работы процессов в процессе выполнения параллельной программы.
Основным механизмом синхронизации параллельных процессов, взаимодействующих с помощью передачи сообщений, является барьер. Барьер - это точка параллельной программы, в которой процесс ждёт все остальные процессы, с которыми он синхронизирует свою работу. Лишь только после того, как все процессы, синхронизирующие свою работу, достигли барьера, они продолжают дальнейшие вычисления. Если по какой-то причине хотя бы один из этих процессов не достигает барьера, то остальные процессы "зависают" в этой точке программы, а программа в целом уже никогда не сможет завершиться нормально.
Предположим, что нам нужно изменить программу p15.mpc таким образом, чтобы сообщения от виртуальных процессоров с нечётными координатами выводились на терминал пользователя только после того, как будут выведены сообщения от всех виртуальных процессоров с чётными координатами. Программа p19.mpc представляет один из вариантов решения этой задачи. В этой программе в блоке, помеченном меткой Barrier, определяется размещённый на хост-процессе автоматический массив bs, число элементов которого равно числу виртуальных процессоров в сети mynet, и распределённая по этой сети переменная b. Выполнение присваивания bs[]=b заключается в том, что каждый из виртуальных процессоров сети mynet посылает значение своей проекции переменной b виртуальному хост-процессору, где это значение присваивается элементу массива bs, индекс которого равен координате пославшего это значение процессора. Выполнение присваивания b=bs[] заключается в том, что значение i-го элемента массива bs посылается виртуальному процессору сети mynet с координатой I=i, где оно присваивается соответствующей проекции переменной b. Нетрудно показать, что ни один из виртуальных процессоров сети mynet, не покинет этого блока до тех пор, пока все они не войдут в него и не завершат свою часть работы по выполнению первого из присваиваний. Только после этого виртуальный хост-процессор сможет завершить выполнение первого присваивания и перейти ко второму, освобождая задержанные на нём виртуальные процессоры, завершившие свою часть работы по выполнению первого присваивания. Тем самым, этот блок представляет собой барьер, разделяющий операторы, выводящие сообщения на терминал пользователя с четных и нечетных виртуальных процессоров сети mynet соответственно.
В программе p20.mpc аналогичный барьер реализован проще и лаконичней, а по эффективности вряд ли сколько-нибудь серьёзно уступает первому варианту (наиболее очевидная схема реализации операции [+] отличается от барьера из программы p19.mpc лишь дополнительным суммированием на хосте, время выполнения которого пренебрежимо мало по сравнению со временем передачи сообщения).
На самом деле, программисту нет необходимости изобретать различные способы реализации барьеров. Язык mpC предоставляет две библиотечные функции, эффективно реализующие барьерную синхронизацию для той операционной среды, в которой выполняется параллельная программа. Во-первых, это базовая функция MPC_Global_barrier, синхронизирующая работу всех процессов параллельной программы. Её описание находится в заголовке mpc.h и выглядит следующим образом:
int [*]MPC_Global_barrier(void);
Программа p21.mpc демонстрирует использование этой функции для разделения барьером двух уже знакомых параллельных операторов. Заметим, что в этой программе, в отличие от двух предыдущих, на барьере ждут не только процессы, реализующие сеть mynet, но и свободные процессы. Это, естественно, приводит к большему числу сообщений, пересылаемых при выполнении барьера, и, следовательно, к определённому замедлению программы.
Библиотечная функция MPC_Barrier позволяет синхронизировать работу виртуальных процессоров любой сети. Программа p22.mpc демонстрирует использование этой функции. В этой программе, как и в программах p19.mpc и p20.mpc, на барьере ждут только процессы, реализующие сеть mynet.
Вызов функции MPC_Barrier в программе p22.mpc выглядит несколько необычно. Действительно, эта функция принципиально отличается от всех функций, которые встречались до сих пор, и представляет так называемые сетевые функции. В отличие от базовых функций, которые всегда выполняются всеми процессами параллельной программы, сетевые функции выполняются на сетях и, следовательно, могут выполняться параллельно с другими сетевыми или узловыми функциями. В отличие от узловых функций, которые также могут выполнятся параллельно всеми виртуальными процессорами той или иной сети, виртуальные процессоры сети, выполняющей сетевую функцию, могут обмениваться данными и в этом их схожесть с базовыми функциями.
Описание функции MPC_Barrier находится в заголовке mpc.h и выглядит следующим образом:
int [net SimpleNet(n) w] MPC_Barrier( void );
Любая сетевая функция имеет специальный, так называемый, сетевой формальный параметр, представляющий сеть, на которой вызывается эта функция. В описании сетевой функции описание этого формального параметра располагается в квадратных скобках слева от имени функции и выглядит аналогично обычному определению сети. В случае функции MPC_Barrier описание сетевого параметра имеет вид:
net SimpleNet(n) w
Это описание, наряду с формальной сетью w, на которой выполняется функция MPC_Barrier, вводит параметр n этой сети. Этот параметр, как и обычные формальные параметры, доступен в теле функции так, как если бы он был описан со спецификаторами repl и const. Вспомнив, что, согласно определению сетевого типа SimpleNet, параметр n имеет тип int, можно сказать, что параметр n интерпретируется в теле функции MPC_Barrier так, как если бы это был обычный формальный параметер, описанный следующим образом:
repl const int n
Все обычные формальные параметры по умолчанию считаются распределёнными по формальному сетевому параметру.
Таким образом, размазанный по сети w целый неизменяемый параметр n задаёт число виртуальных процессоров этой сети.
Если бы функция MPC_Barrier была не библиотечной, она могла бы быть определена, например, так, как это сделано в программе p23.mpc:
int [net SimpleNet(n) w] MPC_Barrier( void ) {
int [w:parent]bs[n], [w]b=1;
bs[]=b;
b=bs[];
}
В теле функции определяется автоматический массив bs из n элементов (язык mpC допускает динамические массивы), размещённый на родителе сети w (это специфицируется с помощью конструкции [w:parent], помещённой перед именем массива в его определении). Кроме того, там же определяется распределенная по сети w переменная b. Следующая за этим определением пара операторов реализует барьер для виртуальных процессоров сети w.
Вызов сетевой функции MPC_Barrier в программах p22.mpc и p23.mpc задаёт фактический сетевой аргумент - сеть mynet, на которой в действительности вызывается функция, а также фактическое значение единственного параметра сетевого типа SimpleNet. Последнее, на первый взгляд, кажется избыточным. Однако, надо учесть, что фактическим сетевым аргументом функции MPC_Barrier может быть сеть любого типа, а не только типа SimpleNet. Например, в программе p24.mpc таким фактическим аргументом является сеть типа Mesh. По-существу, функция MPC_Barrier лишь интерпретирует ту совокупность процессов, на которой она вызвана, как сеть типа SimpleNet.
В общем случае, фактические значения параметров того сетевого типа, для которого определена вызываемая сетевая функция, позволяющие корректно интерпретировать фактический сетевой аргумент (другого сетевого типа), задаются неоднозначно и, поэтому, требуют явной спецификации при вызове функции. Программа p25.mpc как раз демонстрирует пример такой неоднозначности. В отличие от трёх предыдущих программ, заданные в этой программе при вызове сетевой функции значения параметров сетевого типа не являются единственно возможными.
Вспомним ещё раз, что параллельная программа - это множество параллельных процессов, синхронизирующих свою работу и обменивающихся данными посредством передачи сообщений. Рассмотренные средства языка mpC позволяют программисту специфицировать требуемое для параллельного решения задачи число процессов, распределить вычисления между этими процессами и синхронизировать их работу в процессе выполнения параллельной программы. Этих средств, однако, явно недостаточно для описания обменов данными между процессами.
Действительно, в обменах данными, которые мы до сих пор описывали, участвовали либо все процессы программы, либо все виртуальные процессоры той или иной сети, а сами обмены заключались, в основном, либо в рассылке с одного из процессов какого-нибудь значения всем участвующим процессам, либо в сборе значений со всех участвующих процессов на одном из процессов. Для описания более сложных пересылок данных, например, обмена данными между группами виртуальных процессоров сети или параллельному обмену данными между соседними в той или иной системе координат виртуальными процессорами сети, изученных средств не хватает.
Основным средством языка mpC для описания сложных обменов данными являются подсети. Подсеть - это любое подмножество виртуальных процессоров некоторой сети. К примеру, любая строка или столбец решётки виртуальных процессоров сети типа Mesh(m,n) представляет собой подсеть этой сети.
В программе p26.mpc каждый виртуальный процессор сети mynet типа Mesh(2,3) выводит на терминал пользователя не только имя компьютера, на котором его разместила система программирования, но также имя компьютера, на котором система программирования разместила ближайший виртуальный процессор с соседней строки. С этой целью определяются две подсети row0 и row1 сети mynet. Подсеть row0 состоит из всех виртуальных процессоров сети mynet, у которых значение координаты I равно нулю, то есть соответствует нулевой строке решётки виртуальных процессоров сети mynet. Этот факт специфицируется с помощью конструкции [mynet:I==0], помещённой перед именем подсети в её определении. Аналогично, подсеть row1 соответствует первой строке решётки виртуальных процессоров сети mynet. В общем случае, логические выражения, выделяющие виртуальные процессоры подсетей, могут быть довольно сложными и позволяют описывать самые причудливые подсети. Например, выражение I<J && J%2==0 выделяет виртуальные процессоры решётки, расположенные над главной диагональю в чётных столбцах.
Выполнение присваивания [row0]neighbour[]=[row1]me[] заключается в параллельной пересылке содержимого соответствующей проекции массива me от каждого j-го виртуального процессора строки row1 каждому j-му виртуальному процессору строки row0 с последующим его присваиванием соответствующей проекции массива neighbour. Аналогично, выполнение присваивания [row1]neighbour[]=[row0]me[] заключается в параллельной пересылке содержимого проекций массива me от виртуальных процессоров подсети row0 соответствующим виртуальным процессорам подсети row1 с последующим их присваиванием проекциям массива neighbour. В результате, проекция распределенного массива neighbour на виртуальный процессор сети mynet с координатами (0,j) содержит имя компьютера, на котором система программирования разместила виртуальный процессор с координатами (1,j), a проекция этого массива на виртуальный процессор с координатами (1,j) содержит имя компьютера, на котором оказался виртуальный процессор с координатами (0,j).
Программа p27.mpc отличается от программы p26.mpc лишь тем, что используемые в ней в качестве подсетей строки решётки процессоров сети mynet не определены явно с помощью объявления подсети subnet. В данном случае использование неявно определённых подсетей оправдано, поскольку упрощает программу без потери эффективности или функциональных возможностей. Однако, не всегда можно обойтись без явного определения подсети. Например, сетевые функции можно вызывать лишь на явно определённых подсетях.
В последних двух программах, наряду с подсетями, впервые были использованы средства описания векторных вычислений языка mpC. Подобно другому универсальному языку параллельного программирования - HPF (High Performance Fortran), mpC допускает в качестве операндов большинства операций не только скалярные выражения, но и выражения, представляющие множества скаляров, например, массивы или сегменты массивов. Выражения neighbour[] и me[] в программах p26.mpc и p27.mpc представляют массивы neighbour и me как единое целое, а не просто адреса их начальных элементов. Присваивание вида neighbour[]=me[] заключается в присваивании значения выражения me[] - вектора значений типа char, массиву neighbour.
Векторные выражения, с одной стороны, позволяют программисту упростить описание вычислений над массивами, а с другой - позволяют компилятору сгенерировать код, более эффективно использующий как внутрипроцессорный параллелизм, так и иерархию памяти. В программе p28.mpc одно-единственное векторное выражение [+](v1[]*v2[]) используется для вычисления скалярного произведения двух векторов, хранящихся в массивах v1 и v2. Выполнение бинарной операции * заключается в покомпонентном умножении векторных операндов, а результатом префиксной унарной операции [+] является сумма элементов её векторного операнда.
Программа p29.mpc, реализующая LU-разложение квадратной матрицы методом Гаусса, демонстрирует использование сегментов массивов в векторных вычислениях. Так, выражение a[i][i:n-1] обозначает отрезок i-ой строки массива a, включающий все элементы с a[i][i] по a[i][n-1].
Как уже говорилось, определение сети вызывает отображение её виртуальных процессоров на реальные процессы параллельной программы, которое сохраняется всё время жизни сети. Однако, мы пока не обсуждали, как и на основании чего система программирования осуществляет это отображение, и каким образом программист может управлять им.
Во введении подчёркивалось, что основной целью параллельных вычислений является ускорение решения задачи. Именно это отличало параллельные вычисления от распределённых. Поэтому естественно, что основным критерием при отображении виртуальных процессоров сети на реальные процессы является минимизация времени выполнения соответствующей параллельной программы. При выполнении этого отображения система программирования основывается, с одной стороны, на информации о конфигурации и производительности компонент параллельной вычислительной системы, которая выполняет программу, а с другой стороны, на информации о сравнительном объёме вычислений, которые предстоит выполнить различным виртуальным процессорам определяемой сети.
В рассмотренных до сих пор программах эти объёмы вычислений никак не специфицировались. Поэтому, по умолчанию, система программирования считала, что всем виртуальным процессорам всех определяемых сетей предстояло выполнять одинаковые объёмы вычислений. Исходя из этого, она старалась отобразить их таким образом, чтобы общее число виртуальных процессоров, отображённых в данный момент на различные реальные процессоры было приблизительно пропорционально мощности этих процессоров (естественно, с учётом максимального числа виртуальных процессоров, которые могут быть одновременно размещены на том или ином физическом процессоре). При таком отображении все процессы, представляющие виртуальные процессоры сети, выполняют вычисления приблизительно с одной скоростью. Поэтому, если объёмы вычислений между точками синхронизации или обмена данными являются приблизительно одинаковыми, то в целом параллельная программа оказывается сбалансированной в том смысле, что процессы не ждут друг друга в этих точках.
Это отображение оказывалось вполне приемлемым для всех уже рассмотренных нами программ, поскольку и в самом деле вычисления, выполнявшиеся разными виртуальными процессорами одной сети, были приблизительно одинаковыми, да к тому же и весьма незначительными по объёму. Однако, в случае значительных различий в объёмах вычислений, выполняемых различными виртуальными процессорами, такое распределение может привести к очень существенному замедлению программы, поскольку в этом случае выполнение вычислений процессами с одинаковой скоростью приводит к тому, что быстро выполнившие свои относительно небольшие по объёму вычисления процессы будут ждать в точках синхронизации и точках обмена данными процессы, выполняющие более объёмные вычисления. К более сбалансированной и быстрой программе в этом случае приводит отображение, обеспечивающее скорости процессов, пропорциональные объёмам выполняемых ими вычислений.
Язык mpC предоставляет программисту средства для спецификации относительных объёмов вычислений, выполняемых различными виртуальными процессорами той или иной сети. Система программирования использует эту предоставленную программистом информацию для того, чтобы, по-возможности, отобразить виртуальные процессоры сети на процессы таким образом, чтобы вычисления на различных виртуальных процессорах выполнялись со скоростями, пропорциональными объёмам этих вычислений.
Программа p30.mpc знакомит с этими средствами. В этой программе определяется сетевой тип HeteroNet, параметризованный двумя параметрами - целым скалярным параметром n, задающим число виртуальных процессоров сети, и векторным параметром v, состоящим из n элементов типа double, как раз и используемым при спецификации относительных объёмов вычислений, выполняемых различными виртуальными процессорами. Определение сетевого типа HeteroNet содержит необычное объявление
node { I>=0: v[I] },
которое читается следующим образом: для любого I>=0 относительный объём вычислений, выполняемых виртуальным процессором с координатой I, задаётся значением v[I].
Программа p30.mpc расчитывает массу металлической конструкции, сваренной из N неоднородных рельсов. Для параллельного вычисления общей массы металлического "ежа" создаётся сеть mynet, состоящая из N виртуальных процессоров, каждый из которых вычисляет массу одного из этих рельсов. Вычисление массы рельса осуществляется численным трёхмерным интегрированием с фиксированным шагом заданной функции плотности Density по объёму рельса. Очевидно, что объём вычислений по расчёту массы рельса пропорционален объёму этого рельса. Поэтому, в определении сети mynet в качестве второго фактического параметра сетевого типа HeteroNet используется размазанный массив volumes, i-й элемент которого содержит объём i-го рельса. Тем самым специфицируется, что объём вычислений, выполняемый i-м виртуальным процессором сети mynet пропорционален объёму рельса, массу которого этот виртуальный процессор расчитывает.
Вместе с результатами расчётов программа p30.mpc выводит на терминал пользователя (астрономическое) время, затраченное на их выполнение. Для этого используется библиотечная узловая функция MPC_Wtime, возвращающая выраженное в секундах астрономическое время, прошедшее с некоторого не специфицированного, но фиксированного для вызвавшего её процесса момента в прошлом. Не углубляясь в философские рассуждения об относительности времени, текущем на разных процессах, составляющих параллельную программу, отметим, что, несмотря на простоту, именно астрономическое время, затраченное на параллельное решение задачи, начиная от введения исходных данных и до получения результатов, и замеренное на хост-процессе, представляет наиболее объективную и интересующую конечного пользователя временную характеристику программы. Собственно, минимизация этой характеристики и составляет основную цель параллельных вычислений.
Программа p31.mpc эквивалентна программе p30.mpc за тем исключением, что в ней явно не специфицируются относительные объёмы вычислений, выполняемые различными виртуальными процессорами сети mynet. Поэтому, отображая этих виртуальные процессоры на реальные, система программирования предполагает, что они выполняют одинаковые объёмы вычислений. В данном случае это, как правило, приводит к неоптимальному отображению и, как следствие, к большему времени решения задачи по сравнению с программой p30.mpc. Особенно заметно это замедление на неоднородных вычислительных сетях, включащих процессоры, существенно различающиеся по мощности. Так, при выполнении программы p31.mpc вполне возможна ситуация, когда масса самого большого по объёму рельса будет расчитываться на самом маломощном процессоре, что приведёт к многократному замедлению по сравнению с выполнением этих же расчётов по программе p30.mpc, которая гарантирует использование более мощного процессора для расчёта массы большего по объёму рельса.
Говоря о том, что отображение виртуальных процессоров на реальные процессоры основывается на информации о производительности последних, мы не ничего не сказали о том, что же такое производительность процессоров и каким образом система программирования языка mpC её определяет. Вопрос этот не такой простой, как может показаться на первый взгляд. Действительно, что же имеют в виду, когда говорят, что компьютер A в три раза мощнее компьютера B. Строго говоря, это утверждение достаточно бессмысленно, если только речь не идёт о компьютерах одинаковой архитектуры и конфигурации, отличающиеся лишь тактовой частотой процессора. В противном случае, относительная производительность компьютеров, то есть относительная скорость выполнения вычислений, весьма существенно зависит от того, какие именно вычисления выполняются. Зачастую, компьютер, демонстрировавший наивысшую производительность при выполнении одной программы, оказывается самым медленным при выполнении другой. Это хорошо видно при анализе публикуемых результатов измерения производительности различных компьютеров с помощью довольно широкого спектра специальных тестовых пакетов программ.
По умолчанию, система программирования языка mpC использует одну и ту же оценку производительности участвующих в выполнении программы реальных процессоров, однажды полученную в результате выполнения специальной тестовой параллельной программы при инициализации системы в конкретной параллельной вычислительной среде. Мы уже отмечали, что такая оценка является довольно грубой и может значительно отличаться от реальной производительности, демонстрируемой процессорами при выполнении кода, существенно отличающегося от кода тестовой программы. Поэтому, язык mpC содержит средства, позволяющие программисту изменять оценку производительности реальных процессоров, используемую при отображении на них виртуальных процессоров, настраивая её на те вычисления, которые будут выполняться этими виртуальными процессорами.
Программа p32.mpc демонстрирует использование этих средств. Эта программа отличается от программы p30.mpc, главным образом, не встречавшимся до сих пор оператором recon, выполняемым непосредственно перед определением сети mynet. Выполнение этого оператора заключается в том, что все физические процессоры, выполняющие программу, параллельно выполняют специфицированный в этом операторе код (в нашем случае, это вызов функции RailMass с фактическими аргументами 20.0, 4.0, 5.0 и 0.5), а время, затраченное каждым из процессоров на выполнение этого кода, используется для обновление оценки их производительности. Основной объём вычислений, выполняемых каждым из виртуальных процессоров сети mynet, как раз и приходится на вызов функции RailMass. Поэтому, при создании сети mynet система программирования основывается на оценке производительности физических процессоров, очень близкой к их реальной производительности, демонстрируемой при выполнении этой программы.
Очень важным моментом является то, что оператор recon позволяет обновлять оценку производительности процессоров динамически, во время выполнения программы, непосредственно перед тем моментом, когда эта оценка будет использоваться системой программирования. Особенно это важно, если параллельныя вычислительная система, выполняющая программу, используется и для других вычислений. В этом случае, реальная производительность процессоров, демонстрируемая при выполнения параллельной программы, может динамически меняться в зависимости от их загрузки другими, внешними по отношению к этой программе вычислениями. Использование оператора recon позволяет писать параллельные программы, чувствительные к такому динамическому изменению загрузки системы, в которых вычисления распределяются по процессорам в соответствии с их фактической производительностью на момент выполнения этих вычислений.
