Параллельное программирование на Фортране GNS

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ

имени М. В. Келдыша

Российской академии наук

Параллельное программирование на Фортране GNS

В. Ю. Вершубский

В. А. Фисун

Москва 2006

Аннотация

Описаны элементы языка Фортран GNS, ориентированного на программирование параллельных вычислительных процессов методом передачи сообщений. Этот язык входит в систему программирования GNS для многопроцессорных систем МВС-100, МВС-1000.

V.Yu. Vershubskii, V. A. Fisun

Parallel programming on the Fortran GNS

Abstract

The aspects of the Fortran GNS language are described. The language is designed to program parallel computing processes using the message passing technique. It is a part of the programming system for multiprocessors MVS-100 and MVS-1000.

1. Введение

В ИПМ им. В.М. Келдыша РАН для вычислительных комплексов МВС-100, МВС-1000 была разработана система программирования GNS на концепции абстрактной GENESIS модели, ориентированной на мультипроцессорные машины с распределенной памятью [1]. В рамках этой работы были реализованы языки Фортран GNS [2] , Си GNS [3] и средства отображения вычислительных процессов на процессорные узлы вычислителей [4].

Фортран GNS представляет собою расширение языка Фортран 77 средствами для образования параллельных процессов и обмена сообщениями между процессами. В Фортран 77 добавлены новые программные единицы, предназначенные для явного описания параллельных процессов, средства для порождения процессов и средства для обмена сообщениями между процессами. Порождать процессы может динамически любой процесс. По образцу одной программной единицы можно породить один или несколько параллельных процессов. Если несколько параллельных процессов порождены одним актом коллективной операции, то все порожденные процессы начнут выполняться одновременно и параллельно с порождающим процессом. Процессы порождаются на виртуальных процессорах, которые могут быть топологически структурированы в виде многомерных решеток. На одном виртуальном процессоре допускается размещение нескольких процессов. Порождение процессов может начаться с запуска процесса, соответствующего главной программной единице задачи (древовидная, иерархическая система порождения процессов). Другому способу инициализации задачи соответствует одновременный старт многих процессов, созданных по образцу единственной программной единицы для всего решающего поля (классическая модель статического параллелизма SPMD).

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

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

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

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

2. Тип данных - TASKID

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

Формально эти имена представляют собою специально введенного в язык Фортран GNS переменные встроенного типа - TASKID. Переменные этого должны быть описаны в операторе TASKID, синтаксис которого аналогичен синтаксису операторов объявления типов в Фортране 77. В языке определена константа .NOTASKID., которая представляет собой "нулевое" значение для объектов типа TASKID. Переменные этого типа могут использоваться в операторах EQUIVALENCE, но при этом могут быть эквивалентными только переменным типа TASKID. Допускается использование слова TASKID в качестве описателя типа подпрограммы-функции. Переменные типа TASKID могут использоваться в качестве фактических параметров процедуры.

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

Переменные типа TASKID используются в операторах приема-передачи сообщений - SEND и RECEIVE для указания получателя или отправителя. Переменные этого типа могут быть переданы от одного процесса другим процессам в телах сообщений, которыми они обмениваются с помощью операторов SEND и RECEIVE. Значения типа TASKID не могут использоваться в списках параметров операторов ввода-вывода, так как не имеют внешнего представления.

Начальная инициализация переменных этого типа не предусматривается, поэтому использование данных до присваивания им значений некорректно. Присваивание начальных значений этим данным в операторах DATA не предусмотрено.

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

Для задания массовых операций над подмассивом (над частью массива) можно выделить его и присвоить имя оператором EQUIVALENCE. Например:

TASKID T1(100),T2(100),TM

DIMENSION TM(100,2)

EQUIVALENCE (TM(1,1),T1(1)),(TM(1,2),T2(1))

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

3. Задачи и процессы

В языке вводится дополнительный вид программных единиц - программные единицы-задачи (TASK PROGRAM). Программа может содержать (помимо традиционных для Фортрана программных единиц) одну или несколько программных единиц-задач.

Главная программная единица (PROGRAM) определяет главный и единственный - начальной процесс программы. Эта единица может иметь заголовок:

PROGRAM n, где n - имя программы.

По Фортрану, заголовок программы может отсутствовать.

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

При запуске начального процесса ему присваивается имя - системный идентификатор, по которому на него могут ссылаться другие процессы программы при передаче сообщений или при выполнении функций редукции. Имя начального процесса может быть получено любым процессом при помощи встроенной функцией MASTER без параметров. Результат этой функции имеет тип TASKID.

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

Первым оператором программной единицы-задачи является оператор заголовка, имеющий вид: TASK PROGRAM n, где n - имя программной единицы-задачи.

В остальном структура программной единицы-задачи не отличается от структуры главной программной единицы Фортрана 77. В частности, последним оператором, как обычно, является оператор END.

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

3.1 Создание процессов

Для создания процессов в динамической модели параллелизма используется стандартная функция NEWTASK. Обращение к этой функции производится операторами присваивания вида:

it = NEWTASK(n, ia) , где

n - имя программной единицы-задачи;

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

it - имя переменной, элемента массива или массива типа TASKID, в которую заносятся имена порожденных процессов.

Функция NEWTASK создает по описанию задачи с именем n вычислительные процессы, количество которых определяется числом номеров виртуальных процессоров. Это число равно количеству элементов массива параметра ia или равно единице для скалярного параметра.

Результатом выполнения функции NEWTASK является одно имя процесса или массив имен созданных процессов. Эти имена присваиваются переменной it. Если it - массив, то массив ia должен совпадать с ним по рангу и размеру.

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

TASK EXTERNAL n [, ni ]... где

n, ni - имена программных единиц-задач.

Имена, указанные в списке этого оператора, разрешается использовать в качестве фактических параметров процедур (в том числе в качестве параметров функций NNAME и NEWTASK) и в качестве получателей в операторе SEND. Таким образом, передать сообщение процессу можно, идентифицируя его именем программной единицы-задачи, по которой он был образован (по имени класса), или по системному имени. Оператор TASK EXTERNAL должен быть размещен в программной единице-задаче до первого исполняемого оператора. Процесс может узнать собственное имя с помощью функции MYTASKID, имя процесса-родителя - с помощью функции РАRENT, и имя главного процесса программы с помощью функции МАSTER. Если известен номер виртуального процессора, то имя размещенного на нем процесса можно узнать с помощью функции GETTASKID.

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

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

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

TASK PROGRAM C

TASK EXTERNAL A,B,READING,PRINTING

TASKID TI, TM(100),TM2(100,2)

INTEGER K,KM(100),KM2(100,2)

.............

END

Инициализация процессов:

1 TI = NEWTASK(A,K)

2 TМ = NEWTASK(A,KМ)

3 TМ2 = NEWTASK(A,KМ2)

4 DO 10 I=1,100

10 TМ(I) = NEWTASK(A,KМ(I))

DO 20 I=1,100

5 TМ2(I,1)= NEWTASK(A,KМ2(I,1))

20 TМ2(I,2) = NEWTASK(B,KМ2(I,2))

Операторы с метками 2 и 4 (3 и 5) производят одинаковые действия, но использование формы 2 (3) предпочтительнее, так как эта запись позволяет операции инициализации процессов выполнять параллельно. Инициализацию элементов массива TМ2 можно записать в виде массовой операции (вместо цикла с меткой 20), если использовать пример раздела 2. Отсутствие в Фортране 77 аппарата вырезок из массивов не позволяет иметь такую эффективную запись для алгоритмов, в которой имена порождаемых переменных заносятся в элементы массива, для которого нельзя описать массив, ассоциированный по памяти с этими элементами.

DO 6 I=1,99,2

TМ(I) = NEWTASK(A,KМ(I))

6 TМ(I+1) = NEWTASK(В,KМ(I+1))

или

TМ(1) = NEWTASK(READING,KМ(1))

TМ(100) = NEWTASK(PRINTING,KМ(100))

DO 7 I=2,99

7 TМ(I) = NEWTASK(В,KМ(I))

В результате выполнения операторов:

TI = NEWTASK(PRINTING,1)

8 TI = NEWTASK(READING,2))

на виртуальном процессоре с номером 1 будет образован и запущен процесс PRINTING, внутреннее имя которого потеряно и недоступно программе из-за выполнения оператора 8. Доступ к нему для передачи сообщений возможен только по имени программной единицы задачи, заказать от него прием сообщений невозможно. C процессом на втором процессоре возможен двусторонний обмен сообщениями.

Описана только одна синтаксическая конструкция использования функции NEWTASK - в операторе присваивания. Тем не менее, версии языка могут разрешать использование этой функции и в других контекстах, там, где употребляются переменные типа TASKID. Например, оператор:

SEND(NEWTASK(PRINTING,MI)) RES

породив процесс печати, передает ему данные через RES.

3.2 Виртуальные номера процессоров

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

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

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

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

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

3.3 Завершение программы и завершение процессов

Выполнение программы на языке Фортран GNS завершается в следующих случаях:

при завершении выполнения главного процесса (процедурой STOP или выходом через END главной программной единицы);

при "авосте" в главном процессе;

при выполнении в каком-либо процессе программы стандартных процедур ABORT и FINISH.

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

Выполнение одного процесса завершается в следующих случаях:

если выполняется одно из указанных выше условий, приводящих к завершению всей программы;

при выполнении оператора STOP в данном процессе;

при выполнении оператора END в задаче, по которой образован процесс;

в случае аварийного завершения в данном процессе.

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

При статической модели параллелизма работа программы завершается выполнением в одном из процессов процедур ABORT или FINISH.

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

3.4 Ввод-вывод

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

4. Передача сообщений

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

SEND - послать сообщение; RECEIVE - принять сообщение.

4.1 Способы передачи сообщений

Предусмотрено три способа (протокола) передачи сообщений: синхронный, асинхронный и без ожидания.

4.1.1 Синхронный способ

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

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

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

4.1.2 Асинхронный способ

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

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

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

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

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

Для организации селекции и установки режимов ожидания заданных сообщений можно использовать также конструкции выбора (см. раздел 5.).

4.1.3 Передача без ожидания

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

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

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

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

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

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

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

Замечание:

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

4.2 Идентификация отправителей и получателей

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

Идентификация по имени процесса. Основным способом идентификации сторон обмена при передаче сообщений является задание имени процесса переменными типа TASKID и встроенными функциями этого типа: MYTASKID, РАRENT и МАSTER. Для порожденных процессов использование этих функций является единственным первоначальным способом узнать имена порождающих процессов, так как начальный диалог между процессами возможен только на уровне порожденный - порождаемый. Процесс, породивший несколько потомков, может передать одним потомкам имена других. В дальнейшем путем обмена сообщениями можно организовать передачу имен по всему множеству процессов. Переменные типа TASKID в качестве параметров операторов передачи сообщений могут:

ссылаться на функционирующий процесс,

ссылаться на завершенный процесс,

иметь значение .NOTASKID.,

не быть инициализированными.

Реакция программы на три последних случая в языке не оговаривается и определяется реализацией. Одно из решений - игнорировать оператор обмена с такими параметрами (для синхронного режима обмена такие случаи считаются аварийным завершением программы). Процесс-отправитель может передать сообщение одновременно нескольким процессам-получателям. Для этого нужно задать множество получателей в параметрах оператора передачи сообщений в виде массива типа TASKID. В этом случае сообщение будет передано всем процессам, на которые есть ссылки в элементах массива. Данная массовая операция предпочтительнее передачи сообщений, организованной поэлементной циклической конструкцией. Цикл предписывает порядок перебора элементов массива получателей, а для синхронного обмена еще и ожидание завершения акта начатого обмена до начала посылки следующего сообщения. Массовая операция обмена может проводиться параллельно и независимо для всех указанных получателей. Массовые операции ассиметричны, нельзя заказать ожидание сообщения от нескольких процессов сразу. Использование тегов для идентификации сообщений и конструкция выбора допускает некоторую вольность в указаниях имен отправителей.

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

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

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

4.3 Операторы передачи сообщений

Операторы SEND и RECEIVE имеют вид:

SEND (sm [,ss]...) [список] RECEIVE (rm [,rs]...) [список]

где

sm - спецификация сообщения - определяет процесс-отправитель или процессы-отправители и способ синхронизации.

rm - спецификация сообщения - определяет процесс-получатель или процессы-получатели и способ синхронизации.

список - список передаваемых данных похож на список вывода в операторах ввода-вывода Фортрана 77, т.е. элементом списка может быть константа, имя переменной, переменная с индексом, имя массива или неявный цикл, но не может быть выражение.

ss или rs - дополнительная спецификация.

Вид спецификации сообщения sm и rm зависит от протокола передачи сообщений:

Синхронный способ.

sm есть [TASKID =] адресат

где адресат есть adr или ALL. adr - ссылка на функцию, имя переменной, элемент массива или имя массива типа TASKID или имя программной единицы-задачи. rm есть [TASKID =] t, где t - переменная или элемент массива типа TASKID; параметр специфицирует процесс - отправитель. Когда adr (rm) - значение типа TASKID, оно должно ссылаться на незавершенный процесс.

Асинхронный способ

sm есть [TAG=] ie, [TASKID =] адресат

или TASKID = адресат, [TAG =] ie

rm есть [TAG=] ie [,[TASKID =] t]

или TASKID = t, [TAG =] ie

где адресат и t определяются как rm для синхронного способа;

ie - выражение целого типа, значение которого определяет тег сообщения.

Способ без ожидания

sm есть [TASKID =] адресат, FLAG = f

rm есть [TASKID =] adr, FLAG = f

или [FLAG =] f

где

адресат и adr определяется, как и для предыдущего способа;

f - имя логической переменной. Наличие этой переменной обязательно.

Переменная f может использоваться также во встроенных процедурах MSGDONE(f) и TESTFLAG(f) (см. раздел 6.). В других ситуациях ее использование не допускается.

Дополнительная спецификация ss и rs , как видно из синтаксиса, является необязательной.

ss есть ERR = l

и / или SRSTAT = ios

где

l - задает метку оператора, которому передается управление в случае ошибки при передаче сообщения;

ios - имя переменной или элемента массива целого типа, характеризующей состояние (аналог спецификации IOSTAT в операторах ввода-вывода).

В результате выполнения оператора, переменной ios присваивается значение 0 (нуль), если не было обнаружено ошибки, или положительное целое число (код ошибки), если обнаружена ошибка. Классификация видов ошибок определяется реализацией языка. Если спецификация SRSTAT отсутствует, то значение статуса состояния присваивается системной переменной.

Если спецификация ERR отсутствует, то в случае ошибки, задача (и вся программа) завершается выполнением стандартной процедуры ABORT.

В качестве дополнительной спецификации rs для оператора RECEIVE, помимо аналогичных спецификаций ERR и SRSTAT, можно также использовать необязательную спецификацию SENDER, т.е.

rs есть ERR = l

и / или SRSTAT = i

и / или SENDER = t

где t - переменная типа TASKID.

Ключевой параметр SENDER полезно использовать, если отсутствует имя процесса-отправителя. Переменной t после выполнения оператора RECEIVE присваивается значение имени процесса-отправителя.

Замечание.

1. Способ передачи сообщения и число элементов в списках оператора SEND и соответствующего оператора RECEIVE должны совпадать; для каждого элемента - тип, а для массивов также размерность и размер по каждому измерению (массивы должны быть согласованы).

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

2. Если значение переменной с именем получателя есть .NOTASKID. или ссылка на завершенный процесс, оператор обмена для этого процесса не выполняется, а параметр SENDER получает значение .NOTASKID. .

3. Не считается ошибкой наличие в почтовом ящике невостребованных сообщений при завершении процесса.

4.3 Использование операторов передачи сообщений

4.3.1 Синхронный способ передачи сообщений

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

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

Для этого в процессе, управляющем синхронизацией, следует выполнить оператор: SEND(ALL), во всех процессах программы - RECEIVE(T1),где Т1 должен ссылаться на управляющую задачу. Управляющий процесс продолжиться только после выполнения во всех задачах оператора RECEIVE. Оператор SEND(А) требует синхронизации только от процессов, образованных по программе-задаче А, а SEND(ТМ) - от процессов, на которые ссылаются элементы массива ТМ. Если процессам известно, что рандеву будет требовать начальный процесс, то их синхронизирующий оператор может быть записан: RECEIVE (МАSТЕR()). Точная синтаксическая запись:

Т1=МАSTER()

RECEIVE (T1)

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

RECEIVE (<...>) N, (KM(I),I=1,N)

4.3.2 Асинхронный способ передачи сообщений

Использование асинхронного способа обмена сообщениями делает программу менее критичной к согласованию операторов обмена сообщениями, так как процесс-отправитель продолжает работу после передачи сообщения, не дожидаясь конца фактической передачи сообщения (и даже начала, так как система интерпретации сразу же, копирует предназначенные для передачи данные в буфер и отпускает процесс). Получатель сообщений в этом случае может выдавать директиву приема только при наличии нужного сообщения в почтовом ящике процесса, что он может проверить при помощи функций: TESTMSG, TESTTAG, PROBE. Выполнение оператора RECEIVE без проверки наличия сообщения в почтовом ящике процесса, по аналогии с синхронным способом обмена, приводит к задержке выполнения процесса до поступления сообщения с заказанным тегом и, возможно, с заданным именем отправителя. В отличие от синхронного способа, асинхронный способ позволяет проводить селекцию поступающих сообщений при помощи встроенной конструкции выбора SELECT MESSAGE. Конструкция выбора подробно описана в разделе 5 ниже.

Пусть процесс может получать сообщения с тегом 1, но от процесса TI - скаляр целого типа, а от процесса TM(1) - массив из 100 целых чисел. Тогда, прием таких сообщений может быть запрограммирован так:

IF (TESTTAG(1)) THEN

SELECT MESSAGE

CASE(1,TI)

RECEIVE (1) K

CASE(1,TM(1))

RECEIVE (1) KM

END SELECT

END IF

или:

SELECT MESSAGE

CASE(1,TI)

RECEIVE (1) K

CASE(1,TM(1))

RECEIVE (1) KM

CASE DEFAULT

GO TO 2

END SELECT

2 CONTINUE

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

SELECT MESSAGE

CASE(1,TI)

RECEIVE (1) K

CASE(1,TM(1))

RECEIVE (1) KM

END SELECT

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

SELECT MESSAGE

CASE(1)

RECEIVE (1) K

CASE(2,TM(1))

RECEIVE (2) KM

END SELECT

4.3.3 Способ передачи сообщений без ожидания

Этот способ рекомендуется использовать для передачи данных "впрок", заблаговременно. Если после операторов SEND - RECEIVE без ожидания, поместить операторы: CALL MSDONE(f), семантика операторов будет совпадать с семантикой асинхронных операторов. Следует иметь в виду, что при использовании операторов данного вида в цикле без использования процедур ожидания фактической передачи сообщений возможно искажение передаваемых данных; семантика функции TESTFLAG при этом будет двусмысленной, так как в случае выполнения оператора SEND повторно, теряется значение флага f от предыдущего выполнения.

4.3.4 Структура элементов списка передаваемых сообщений

Структура элементов списка передаваемых (принимаемых) сообщений, как объявлено, похожа на список ввода-вывода операторов ввода-вывода Фортрана. Широкие возможности предоставляет аппарат неявных циклов. Пусть имеются описания:

REAL A(10),B(5,5)

тогда оператор:

SEND(ALL)A,(B(I),I=1,5),(B(I,1),I=1,5),(B(I,I),I=1,5)

перешлет всем процессам программы следующие объекты:

- массив А целиком,

- первый столбец массива В,

- диагональные элементы массива В

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

SEND(ALL)(B,I=1,5)

программирование вычислительный сообщение

5. Конструкция выбора

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

Конструкция выбора имеет вид:

SELECT MESSAGE

[CASE(селектор)

блок]...

[CASE DEFAULT

блок]

END SELECT

где

селектор есть [TAG=] ie

и / или [TASKID=] t

и / или COND= le

где

ie - выражение целого типа (тег);

t - переменная или элемент массива типа TASKID;

le - логическое выражение;

блок - это последовательность выполняемых операторов, которая должна удовлетворять тем же требованиям, что и блоки конструкции IF-ENDIF в Фортране 77, а именно: передача управления внутрь блока извне запрещена, однако внутри блока переходы допускаются; разрешается выход из конструкции, допускаются операторы CALL и обращения к функциям; если блок содержит управляющую конструкцию IF-ENDIF или SELECT MESSAGE - END SELECT, то эта конструкция должна целиком принадлежать блоку. На оператор CASE нельзя передавать управление. Переход на оператор END SELECT разрешен только внутри конструкции.

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

Если в операторе CASE отсутствует COND-спецификация, полагается что COND=.TRUE.

Если оператор CASE DEFAULT отсутствует и значения всех логических выражений - .FALSE., то это ошибка периода выполнения. Если (при отсутствии блока CASE DEFAULT) для всех тех логических выражений, значение которых - .TRUE., соответствующее сообщение еще не поступило, то процесс переходит в состояние ожидания.

6. Встроенные процедуры

В разделе приводится список процедур, встроенных в язык Фортран GNS для реализации механизма управления работой процессов. В динамической модели параллелизма процедура NEWTASK порождает вычислительный процесс и вырабатывает его имя. С помощью встроенных функций MYTASKID(), MASTER(), РАRENT() можно получить имя процесса, вызвавшего функцию (имя текущего процесса), имя начального процесса или имя процесса, породившего текущий, соответственно.

В статическом режиме, т.е. при отсутствии вызова функции NEWTASK, результат выполнения функций PARENT() и MASTER() - константа .NOTASKID..

Функция GETTASKID(processor) возвращает имя процесса, расположенного на виртуальном процессоре с номером processor. Тип результата функции - TASKID. Семантика функции уточняется при реализации на конкретной установке.

Целая функция NNAME(name) возвращает количество процессов, созданных из программной единицы-подзадачи с именем name. Аргумент функции должен быть упомянут в операторе TASK EXTERNAL. Если он равен '*', то возвращается число всех виртуальных процессоров программы.

Целая функция NVIRPR(name, array, array_lengr) возвращает количество процессов, созданных из программной единицы-подзадачи с именем name. Этот аргумент функции должен быть указан в операторе TASK EXTERNAL. Если он равен '*', то возвращается число всех виртуальных процессоров программы. Функция также заносит в массив array (идентификатор массива или переменная с индексом) номера виртуальных процессоров, на которых образованы процессы с именем name или всех процессоров программы (для name = '*'). Значение параметра array_lengr задает целое число элементов массива array, куда следует записать номера процессоров. Если параметр больше, чем число записываемых процессоров, то значение функции - фактическое число процессоров, а в массив заносятся только эти номера. Если параметр array_lengr меньше, чем число записываемых процессоров, то значение функции - фактическое число процессоров, умноженное на -1, а в массив заносятся только заданное число процессоров. Данная функция отличается от функции NNAME наличием побочного эффекта.

Целая функция NTASKS() возвращает количество всех процессов (число виртуальных процессоров) в выполняемой программе.

Целая функция MYVP() возвращает номер виртуального процессора для процесса, вызвавшего эту функцию.

Результат функции TESTMSG(i,t) - .TRUE. или .FALSE. в зависимости от того, находится ли в почтовом ящике процесса, вызвавшего функцию, сообщение от задачи с именем t с тегом, равным i.

Результат функции TESTTAG(i) - .TRUE. или .FALSE. в зависимости от того, находится ли в почтовом ящике задачи сообщение с тегом, равным i.

Функция PROBE() последовательно выдает значение тега тех сообщений, которые уже содержатся в почтовом ящике. Если функция вызывается несколько раз, сканируется почтовый ящик; когда почтовый ящик пуст (или перебрано все содержимое ящика) - выдается признак -1. (Из этого следует рекомендация не использовать константу -1 в качестве тега.) При реализации возможно уточнение семантики функции, например, определения правила начальной установки указателя функции, порядка перебора содержимого ящика, например, функция PROBE работает с очередью асинхронных сообщений, поступивших в почтовый ящик процесса. Каждый элемент очереди идентифицирован тегом сообщения и TASKID-ом процесса-отправителя. Функция использует внутренний, недоступный пользователю, указатель на текущий элемент очереди. Функция PROBE возвращает тег текущего элемента очереди и сдвигает указатель на следующий элемент очереди. Если очередь исчерпана (или была пуста), то функция возвращает значение -1. Указатель устанавливается на начало очереди в следующих случаях:

первоначально, при инициализации процесса;

при выполнении асинхронного оператора RECEIVE;

при обращении к любой функции редукции.

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

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

Процедура MSGDONE(f) организует режим ожидания (прерывание выполнения процесса) до тех пор, пока передача сообщения с FLAG = f не будет фактически выполнена.

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

Функция TESTFLAG(f) выдает значение .TRUE. или .FALSE. в зависимости от того, выполнена ли фактически передача сообщения с FLAG=f.

Использование функций с параметром FLAG = f корректно только после выполнения операторов SEND - RECEIVE с этим флагом.

Процедура SETNAME(c) присваивает имя (строку символов - с) текущему процессу, а функция MYNAME() выдает это имя или символ ", если имя не присваивалось. Эти две функции предназначаются для отладки.

Процедура ABORT() - вызывает аварийное завершение всей программы.

Процедура FINISH() - вызывает завершение всей программы.

Для выдачи информации из часов реального времени имеется подпрограмма SYSTEM_CLOCK(COUNT, COUNT_RATE, COUNT_MAX)

Процедура имеет три аргумента, все три аргумента - выходные и они целого типа. Первому аргументу (COUNT) присваивается текущее значение процессорных часов. Значение процессорных часов увеличивается на единицу для каждого такта часов, пока не достигнет максимального значения (COUNT_MAX) и устанавливается в нуль для следующего такта (т.е. значение находится в интервале от 0 до COUNT_MAX).

Второму аргументу (COUNT_RATE) присваивается значение равное количеству тактов процессорного времени в секунду, третьему (COUNT_MAX) - максимальное значение, которого может достигнуть COUNT.

7. Функции редукции

В язык введены функции редукции с двумя параметрами, реализующие массовые поэлементные операции.

Перечень функций редукции

Имя процедуры	Тип аргументов	Тип результата	Назначение
PMAXVAL	REAL | DOUBLE | INTEGER	TASKID	REAL | DOUBLE | INTEGER	Максимальное значение
PMINVAL	REAL | DOUBLE | INTEGER	TASKID	REAL | DOUBLE | INTEGER	Минимальное значение
PALL	LOGICAL	TASKID	LOGICAL	Конъюнкция элементов массива
PANY	LOGICAL	TASKID	LOGICAL	Дизъюнкция элементов массива
PCOUNT	LOGICAL	TASKID	INTEGER	Число элементов, имеющих значение .TRUE.
PPRODUCT	REAL | DOUBLE | INTEGER	TASKID	REAL | DOUBLE | INTEGER	Произведение элементов массива
PSUM	REAL | DOUBLE | INTEGER	TASKID	REAL | DOUBLE | INTEGER	Сумма элементов массива
TSORT		-	-	Упорядочение массивов среды

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

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

Функции редукции используются следующим образом. Если из порожденных оператором: TI = NEWTASK(G,MI) процессов задачи G один из них, с наименьшим значением S, на некотором этапе работы должен исключатся из дальнейшей работы - завершаться авостом (изменять алгоритм счета, передавать свои результаты на печать и т.д.), то если:

- в задаче G описать TASKID LTI(<длина, равная длине TI>),

- в процессе, порождающем процессы класса G, выполнить после их порождения:

SEND(TI) TI

а в процессах класса G перед началом работы:

RECEIVE(PARENT) LTI

то с помощью функций редукции можно скорректировать работу процессов оператором:

IF(S .EQ. PMINVAL (S,LTI)) ABORT()

Из определения функций редукции не следует требование выполнения редукции для процессов одного класса (образованных по одному описанию задачи).

Так, функции суммирования, одновременно выполненные в разных процессах в среде из двух процессов:

1 A = PSUM(B,T)

2 A1 = PSUM(B1,T1)

поэлементно просуммируют массивы В,В1 и результаты занесут в массивы А,А1, т.е. А(i) = A1(i) = B(i)+B1(i) , если: - массивы А,А1,В,В1 имеют одинаковый тип, размер и конфигурацию. Обе задачи, по которым были образованы процессы, выполняющие операторы 1 и 2, содержат описание массивов: TASKID T(2), TASKID T12) элементам которых присвоены значения - имена процессов среды.

8. Использование статической модели параллелизма

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

TASK PROGRAM SUM

C Параметризация максимальной длины суммируемого массива и тега

PARAMETR (NA=100000,NT=13)

REAL A(NA)

TASKID T

C Ожидание вызова, N - длина массива, подлежащая суммированию

C Фиксация в T имени вызывающего процесса, асинхронно

1 RECEIVE (TAG=NT,SENDER=T) N

...