8 Определение программного блока

long begbl_ (void);

Функция begbl_ определяет начало блока локализации следующих системных объектов:

• распределённого массива;
• представления абстрактной машины;
• многопроцессорной системы;
• карты отображения представления абстрактной машины;
• карты отображения распределённого массива;
• редукционной переменной;
• редукционной группы;
• группы границ распределённых массивов;
• буфера удалённых элементов регулярного доступа;
• группы буферов удалённых элементов регулярного доступа;
• буфера удалённых элементов нерегулярного доступа;
• группы буферов удалённых элементов нерегулярного доступа.

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

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

Возвращается нулевое значение.

long endbl_ (void);

Функция endbl_ определяет завершение блока локализации. Возвращается нулевое значение.

9 Описание параллельного цикла

9.1 Создание параллельного цикла

LoopRef crtpl_ (long *RankPtr);

*RankPtr - размерность параллельного цикла.

Функция crtpl_ создает параллельный цикл (определяет его начало) и возвращает ссылку на него. Завершение параллельного цикла осуществляется с помощью функции endpl_ (см. п. 9.5).

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

9.2 Отображение параллельного цикла

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

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

Повторное отображение параллельного цикла не допускается.

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

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

В Фортране массив LoopVarAddrArray может быть сформирован с помощью функции dvmadr_ , рассмотренной в п.17.7.

Типы индексных переменных параллельного цикла, задаваемые в массиве LoopVarTypeArray, могут принимать значения:

0 – переменная типа long;
1 – переменная типа int;
2 – переменная типа short;
3 – переменная типа char.

Если LoopVarTypeArray = NULL, то типы индексных переменных всех измерений цикла полагаются равными единице (int).

Рассмотрим отображение параллельного цикла подробнее. Пусть F - многозначная функция, определённая на индексном пространстве отображаемого цикла и принимающая значения в индексном пространстве образца:

где:

Отображение параллельного цикла по заданному образцу - это указание системе поддержки (посредством задания функции F) о том, что виток параллельного цикла, определённый индексным вектором (i₁, ... , i_n), должен быть выполнен на тех и только тех процессорах, на которых размещён (или на которые отображён) хотя бы один из элементов образца, определённых множеством F((i₁, ... , i_n)) (т.е. множеством-образом, элементами которого являются векторы индексного пространства образца).

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

В этом случае образом элемента (i₁, ... , i_n) индексного пространства параллельного цикла является множество, содержащее один элемент - A_j*I_k + B_j, принадлежащий множеству значений индексной переменной j-го измерения образца.

A_j и B_j должны удовлетворять условиям:

0 <= A_j*MAX_k + B_j <= MAX_j и 0 <= A_j*MIN_k + B_j <= MAX_j , где:

2. F_j(I₁, ... , I_n) = { q О M_j: 0 <= q <= MAX_j } , где:

В этом случае образом любого элемента (i₁, ... , i_n) индексного пространства отображаемого цикла является все множество значений индексной переменной j-го измерения образца (в подобных случаях принято использовать символ "*" , т. е. "любой из допустимых").

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

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

Примеры.

1. Отображение F((I₁,I₂)) = {I₁} x {I₂} означает, что виток двухмерного цикла (i₁,i₂) должен быть выполнен на тех же процессорах, на которые отображён элемент (i₁,i₂) двухмерного образца.
2. Отображение F((I₁,I₂)) = {*} x {I₁+5} x {*} означает, что виток двухмерного цикла будет выполнен на тех же процессорах, на которые отображён элемент трёхмерного образца, если индекс по 2-му измерению образца на 5 больше индекса по 1-му измерению параллельного цикла (вне зависимости от значения индекса параллельного цикла по 2-му измерению и от значений индексов образца по 1-му и 3-му измерениям).
3. Отображение F((I₁,I_2,I₃)) = {*} x {*} означает, что каждый виток трёхмерного цикла будет выполнен на каждом процессоре, на который отображён хотя бы один элемент двухмерного образца (вне зависимости от значений индексов отображаемого цикла и образца).
4. Отображение F((I₁,I₂)) = {0} x {1} x {2} означает, что каждый виток двухмерного цикла (вне зависимости от значений его индексов) будет выполнен на тех процессорах, на которые отображён элемент трёхмерного образца с индексами (0,1,2).

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

При обращении к функции mappl_ правило отображения F_j(I₁, ..., I_n) = A_j*I_k + B_j для j-го измерения образца задается следующим образом:

AxisArray[j-1] содержит значение k;
CoeffArray[j-1] содержит значение A_j;
ConstArray[j-1] содержит значение B_j.

Для задания правила F_j(I₁, ... , I_n), значением которого для любых I₁, ... , I_n является множество всех значений индексной переменной j-го измерения образца, значение AxisArray[j-1] (значение k) должно быть установлено равным -1. Значения CoeffArray[j-1] и ConstArray[j-1] (значения A_j и B_j) в этом случае несущественны.

Число правил отображения, заданных при обращении к функции mappl_ , должно быть равно размерности образца.

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

9.3 Изменение порядка выполнения витков цикла

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

Указанный выше порядок выполнения витков достигается разбиением их на каждом процессоре на 2*n+1 частей (порций) (n – размерность цикла). Информация о каждой порции витков опрашивается с помощью функции dopl_ (см. п. 9.4) и помещается при её выполнении в массивы OutInitIndexArray, OutLastIndexArray и OutStepArray, являющиеся параметрами функции mappl_ . Обращение к функции exfrst_ влечёт следующий порядок опроса порций витков функцией dopl_ : первые 2*n опросов помещают в массивы OutInitIndexArray, OutLastIndexArray и OutStepArray инфомацию о витках цикла, соответствующих экспортируемым элементам распределённых массивов; последний положительный опрос соответствует внутренним элементам распределённых массивов.

Обращение к функции exfrst_ должно предшествовать отображению параллельного цикла функцией mappl_ .

Группа границ, заданная ссылкой *ShadowGroupRefPtr, должна быть создана в текущей подзадаче.

При разбиении выполнения параллельного цикла на части с помощью функции exfrst_ результирующие ширины границ распределённых массивов, необходимые для создания порций витков, вычисляются следующим образом (вычисление осуществляет функция отображения параллельного цикла mappl_). Пусть ShadowArrayGroup – совокупность распределённых массивов, границы которых включены в группу, заданную ссылкой *ShadowGroupRefPtr. Пусть также AMView – представление абстрактной машины, в которое отображён (непосредственно или косвенно) параллельный цикл, а PLAxis – измерение цикла, которое отображено в измерение AMVAxis этого представления. Тогда результирующая нижняя (верхняя) ширина границы для измерения цикла PLAxis равна максимальному значению ширин нижних (верхних) границ тех измерений массивов из совокупности ShadowArrayGroup, которые выравнены по измерению AMVAxis представлений, эквивалентных представлению AMView.

Если системе поддержки не удалось найти ни одного распределённого массива из совокупности ShadowArrayGroup, измерение которого выравнено по измерению AMVAxis представления, эквивалентного представлению AMView, то результирующие ширины нижних и верхних границ для измерения PLAxis полагаются нулевыми. Для измерений параллельного цикла, не отображённых ни в какое измерение представления AMView, ширины нижних и верхних границ также полагаются равными нулю.

Подробно вопрос о границах локальных частей распределённых массивов рассмотрен в п.12.

Функция возвращает нулевое значение.

Замечание. Представления одной и той же абстрактной машины считаются эквивалентными, если они:

• имеют одни и те же размерности и размеры по каждому измерению;
• одинаково отображены в эквивалентные процессорные подсистемы.

Процессорные подсистемы системы одной и той же процессорной системы эквивалентны, если они:

• имеют одинаковые размерности и размеры по каждому измерению;
• состоят из одних и тех же процессоров.

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

Как и для функции exfrst_ , требуемый порядок выполнения витков достигается разбиением их на каждом процессоре на 2*n+1 частей (порций) (n – размерность цикла). Информация о каждой порции витков опрашивается с помощью функции dopl_ (см. п. 9.4) и помещается при её выполнении в массивы OutInitIndexArray, OutLastIndexArray и OutStepArray, являющиеся параметрами функции mappl_ . Обращение к функции imlast_ влечёт следующий порядок опроса порций витков функцией dopl_ : первый опрос помещает в массивы OutInitIndexArray, OutLastIndexArray и OutStepArray инфомацию о витках цикла, соответствующих внутренним элементам распределённых массивов; следующие 2*n опросов соответствуют экспортируемым элементам распределённых массивов.

Обращение к функции imlast_ должно предшествовать отображению параллельного цикла функцией mappl_ .

Группа границ, заданная ссылкой *ShadowGroupRefPtr, должна быть создана в текущей подзадаче.

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

Возвращается нулевое значение.

9.4 Опрос необходимости продолжения выполнения параллельного цикла

long dopl_ (LoopRef *LoopRefPtr);

*LoopRefPtr - ссылка на параллельный цикл.

Функция dopl_ позволяет установить, выполнены ли все части параллельного цикла, на которые разбито его выполнение посредством функций exfrst_ или imlast_. При каждом очередном обращении к функции dopl_ производится корректировка параметров цикла, содержащихся в массивах OutInitIndexArray, OutLastIndexArray и OutStepArray (выходные параметры функции mappl_).

Функция возвращает значение:

При изменённом порядке выполнения витков функция dopl_ последовательно возвращает 2*n+1 положительных значений (см. п. 9.3). Если выполнение цикла не разбивалось на части функциями exfrst_ и imlast_ , то функция dopl_ возвращает ненулевое значение только один раз. При этом информация, помещённая в массивы OutInitIndexArray, OutLastIndexArray и OutStepArray функцией mappl_ и соответствующая локальной части цикла, не меняется.

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

Обращение к функции dopl_ допустимо только для отображённого параллельного цикла.

9.5 Завершение параллельного цикла

long endpl_ (LoopRef *LoopRefPtr);

*LoopRefPtr - ссылка на параллельный цикл.

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

Система поддержки допускает завершение программы с помощью функции lexit_ (см. п. 2) при выполнении любого параллельного цикла без его предварительного завершения функцией endpl_ .

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

Функция возвращает нулевое значение.

9.6 Задание информации о зависимостях по данным между витками параллельного цикла

Разбиение выполнения параллельного цикла на части (необходимое для асинхронного обмена границами распределённых массивов, динамического перераспределения вычислений между процессорами и т. д.) влечёт изменение порядка выполнения его витков, что при наличии зависимостей по данным между витками может привести к неверным вычислениям. Для правильной организации разбиения витков цикла на порции системе поддержки необходима информация о всех точках вида (I₁+D₁, … , I_n+D_n), значения вычисляемой переменной в которых требуются для определения её значения в точке (I₁, ... , I_n) (n – размерность цикла, все D_i – целые числа). Предполагается, что хотя бы два значения D_i отличны от нуля (информация о точках, для которых число ненулевых D_i не превосходит единицы, системе поддержки не требуется).

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

Коды зависимостей по данным, задаваемые в i-м элементе массива DependCodeArray, могут принимать значения:

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

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

Функция возвращает нулевое значение.

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

9.7 Измерение времени выполнения витков параллельного цикла

Время выполнения различных витков параллельного цикла может быть разным. Поэтому для сбалансированной загрузки процессоров требуется неравномерное распределение по ним витков параллельных циклов и элементов распределённых массивов. Неравномерность распределений достигается заданием различных вычислительных весов координат процессоров с помощью функций setpsw_, genbli_, genbld_, genblk_ и setelw_ (см. п.п. 4.5 и 4.6).

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

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

Процесс измерения организован следующим образом. Задание на измерение времени выполнения витков параллельных циклов выдаётся системе поддержки программой пользователя с помощью одного или нескольких обращений к функции setgrn_ (см. п. 9.7.1). При каждом обращении к функции setgrn_ задаются:

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

При выполнении функции setgrn_ система поддержки создаёт массив типа double, длина которого равна заданному числу групп (массив координатных весов загрузки). Все элементы этого массива инициализируются нулевыми значениями.

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

Результаты произведённых измерений (массивы координатных весов загрузки) могут быть опрошены с помощью функций gettar_ и getwar_ (см. п. 9.7.2).

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

9.7.1 Выдача задания на измерение

Функция setgrn_ выдаёт системе поддержки задание на измерение времени выполнения порций витков всех параллельных циклов, имеющих измерение, отображённое в *AxisPtr-е измерение заданного представления абстрактной машины. Измеренные времена будут накапливаться в массиве координатных весов загрузки (внутренний массив системы поддержки).

Допускается повторное обращение к функции с теми же параметрами *AMViewRefPtr и *AxisPtr, что и при предыдущем обращении.

Если значение параметра *GroupNumberPtr превосходит размер *AxisPtr-го измерения, то число групп разбиения полагается равным этому размеру.

Задание на измерение будет проигнорировано, если *AxisPtr-е измерение не является блочно распределённым.

Возвращается нулевое значение.

9.7.2 Опрос результатов измерения (опрос массива координатных весов загрузки)

Функция getwar_ помещает в массив WeightArray, заданный программой пользователя, массив координатных весов загрузки, полученный в результате измерений, и возвращает его длину. Если задание на измерение для *AxisPtr-го измерения заданного представления абстрактной машины ранее не выдавалось, то функция возвращает нулевое значение (запись в массив WeightArray не производится).

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

Замечание.

Выполнение функции getwar_ сводится к последовательному обращению к функциям

и

Функция gettar_ аналогична рассмотренной функции getwar_, но не отменяет задание на измерение для *AxisPtr-го измерения заданного представления абстрактной машины и не уничтожает массив координатных весов загрузки. При повторном опросе результатов измерений возвращается та же длина массива координатных весов загрузки, а в массив WeightArray помещается та же информация, что и при предыдущем опросе.

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

Функция rsttar_ отменяет задание на измерение для *AxisPtr-го измерения представления абстрактной машины, заданного ссылкой *AMViewRefPtr, и уничтожает массив координатных весов загрузки. Если номер измерения *AxisPtr равен нулю, то отмена заданий на измерения и уничтожение массивов координатных весов загрузки осуществляется для всех измерений заданного представления абстрактной машины.

Возвращается нулевое значение.

9.7.3 Использование результатов измерения для динамической балансировки загрузки процессоров

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

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

9.7.4 Глобальная трассировка времен выполнения витков параллельных циклов

Для предсказания производительности DVM-программ в системе поддержки предусмотрена возможность трассировки времён выполнения витков всех параллельных циклов программы пользователя. Вывод информации (при включённой трассировке) осуществляется при завершении каждого параллельного цикла. Трассировка времён выполнения витков всех параллельных циклов управляется параметрами запуска системы поддержки PLGroupNumber и PLTimeTrace.

Параметр PLGroupNumber определяет порции, на которые делятся витки параллельных циклов при измерении времён их выполнения:

PLGroupNumber = N₁, N₂, N₃, N₄;

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

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

Замечание.

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

10 Представление программы в виде совокупности параллельно выполняющихся подзадач

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

Создание подзадач может быть осуществлено с помощью рассмотренных в п. 5 функций отображения представления абстрактной машины в процессорную подсистему (distr_, redis_, mdistr_, mredis_). Активизация созданных таким образом подзадач осуществляется при входе в виток параллельного цикла.

Рассмотрим теперь создание параллельных подзадач путем явного задания соответствия <абстрактная машина> => <процессорная подсистема> и способ их (подзадач) активизации.

10.1 Отображение абстрактной машины (создание подзадачи)

Для успешного создания подзадачи её абстрактная машина и процессорная система должны удовлетворять условиям:

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

Допускается повторное отображение (переотображение) абстрактной машины, не имеющей потомков (абстрактной машины, соответствующей листу дерева абстрактных машин). Нельзя переотобразить абстрактную машину, если она принадлежит представлению родительской абстрактной машины, отображённому функцией distr_ (mdistr_).

Функция возвращает нулевое значение.

10.2 Начало выполнения (активизация, пуск) подзадачи

long runam_ (AMRef *AMRefPtr);

*AMRefPtr - ссылка на абстрактную машину запускаемой подзадачи.

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

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

Функция возвращает значение:

10.3 Завершение выполнения (останов) текущей подзадачи

long stopam_ (void);

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

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

Система поддержки допускает завершение программы с помощью функции lexit_ (см. п. 2) при выполнении любой подзадачи без предварительного её останова функцией stopam_ .

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

Функция возвращает нулевое значение.

11 Редукция

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

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

11.1 Создание редукционной переменной

В качестве редукционной переменной может выступать:

• скалярная переменная;
• элемент "обычного" (размноженного по всем процессорам) массива;
• одномерный "обычный" массив.

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

Создание редукционной переменной - это описание одномерного массива как редукционной переменной, осуществляемое с помощью следующей функции:

Функция crtred_ создает объект, описывающий редукционную переменную, и возвращает ссылку на него (или просто ссылку на редукционную переменную).

Существуют следующие номера редукционных операций (в скобках указаны именованные константы языка C):

1. сумма (rf_SUM);
2. произведение (rf_MULT);
3. максимум (rf_MAX);
4. минимум (rf_MIN);
5. поразрядное логическое "И" (rf_AND);
6. поразрядное логическое "ИЛИ" (rf_OR);
7. поразрядное сравнение (поразрядное сложение по модулю 2, rf_XOR);
8. поразрядная эквивалентность (поразрядное сложение по модулю 2 с последующим инвертированием всех разрядов, rf_EQU);
9. неравенство (rf_NE);
10. равенство (rf_EQ).

Операции с номерами 5, 6, 7 и 8 применимы только для редукционных переменных типа int или long (см. ниже).

Результат операции с номером 9 (rf_NE) имеет ненулевое значение ("ИСТИНА"), если в момент её запуска значения редукционной переменной различны хотя бы на двух процессорах, и нулевое ("ЛОЖЬ") - в противном случае.

Результат операции с номером 10 (rf_EQ) имеет ненулевое значение ("ИСТИНА"), если в момент её запуска значения редукционной переменной одинаковы на всех процессорах, и нулевое ("ЛОЖЬ") - в противном случае.

Дополнительная информация (или информация локализации), сопровождающая редукционную операцию, зависит от алгоритма задачи и формируется программой пользователя. Из перечисленных редукционных операций её задание имеет смысл только для операций rf_MAX и rf_MIN и превращает их в позиционные редукционные операции MAXLOC и MINLOC. Предположительно, дополнительной информацией в этих случаях являются в том или ином виде заданные координаты максимума или минимума. Система поддержки лишь обеспечит пересылку её от процессора, в котором был найден максимум или минимум, всем остальным процессорам. Отсутствие информации локализации указывается равным NULL значением указателя LocArrayPtr или нулевым значением длины элемента массива с информацией локализации.

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

1. int (rt_INT);
2. long (rt_LONG);
3. float (rt_FLOAT);
4. double (rt_DOUBLE);
5. complex float (rt_FLOAT_COMPLEX);
6. complex double (rt_DOUBLE_COMPLEX).

С точки зрения языка C комплексная редукционная переменная (типы 5 и 6) - это одномерный массив типа float или double, состоящий из двух элементов (первый элемент - действительная часть комплексного числа, второй - мнимая). Над комплексными редукционными переменными допустимы только операции сложения и умножения.

Задаваемый ненулевым значением *StaticSignPtr признак статической редукционной переменной означает создание переменной (точнее, описывающего её объекта), не уничтожаемой при выходе из программного блока (см.п.8). Такая редукционная переменная может быть уничтожена только явно, с помощью рассмотренной ниже функции delred_ .

Замечание. Чтобы избежать предупреждений, выдаваемых Фортран-компилятором при обращении к функции crtred_ с различными типами редукционных переменных, в системе поддержки предусмотрена функция

отличающаяся от функции crtred_ вторым параметром:

Остальные параметры функции crtrdf_ аналогичны соответствующим параметрам функции crtred_ .

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

Функция сообщает системе поддержки тип индексных переменных, значения которых определяют координаты локальных максимумов или минимумов редукционных переменных, составляющих массив, заданный при обращении к функции crtred_ (crtrdf_) параметром RedArrayPtr (RedArrayAddrPtr) (см. п. 11.1). Значения этих индексных переменных содержатся в каждом элементе массива с информацией локализации, задаваемого при обращении к функциям crtred_ и crtrdf_ указателем LocArrayPtr.

Параметр *LocIndTypePtr может принимать значения:

0 – индексные переменные типа long,
1 – integer,
2 – short,
3 – char.

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

Возвращается нулевое значение.

Сразу после создания редукционной переменной функцией crtred_ (crtrdf_) тип индексных переменных, значения которых задают координаты локального максимума или минимума, считается равным integer (значение типа по умолчанию).

11.3 Создание редукционной группы

Функция crtrg_ создает пустую редукционную группу (не содержащую ни одной редукционной переменной) и возвращает ссылку на неё.

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

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

11.4 Включение редукционной переменной в редукционную группу

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

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

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

В качестве спецификаторов процессорного пространства могут быть заданы следующие объекты:

1. Процессорная система.

Заданная параметром PSSpaceRefPtr процессорная система становится процессорной системой и процессорным пространством редукционной переменной. Все её элементы должны входить в состав текущей процессорной системы.

2. Распределённый массив.

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

3. Параллельный цикл.

Параллельный цикл, заданный указателем PSSpaceRefPtr, должен быть текущим и отображён (т. е. использование параллельного цикла для спецификации процессорного пространства редукционной переменной допустимо только после его отображения с помощью функции mappl_, см. п. 9.2). Процессорная система, в которую отображён параллельный цикл, полагается процессорной системой редукционной переменной. За процессорное пространство редукционной переменной принимается подмножество элементов её процессорной системы, в которое не входят процессоры, дублирующие выполнение размноженных витков цикла.

4. Представление абстрактной машины.

Если представление абстрактной машины отображено функцией distr_ (redis_, mdistr_, mredis_) , то процессорная система, в которую осуществлено это отображение, принимается за процессорную систему и процессорное пространство редукционной переменной. В случае, когда представление не отображено функцией distr_ (redis_, mdistr_, mredis_), но хотя бы одна его абстрактная машина отображена функцией mappl_, процессорной системой редукционной переменной считается текущая процессорная система, а процессорным пространством – совокупность центральных процессоров подзадач, созданных при отображении элементов представления (редукция по завершившей выполнение группе параллельных подзадач, см. п. 10).

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

При нулевом значении ссылки *PSSpaceRefPtr или при равном NULL значении указателя PSSpaceRefPtr процессорной системой редукционной переменной и её процессорным пространством полагается текущая процессорная система.

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

Функция возвращает нулевое значение.

11.5 Запоминание значений редукционных переменных

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

long saverv_ (RedRef *RedRefPtr);

*RedRefPtr - ссылка на редукционную переменную.

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

Редукционная переменная, заданная ссылкой *RedRefPtr, должна быть создана в текущей подзадаче, а её редукционная группа не должна быть запущена функцией strtrd_ (см. п. 11.6).

Возвращается нулевое значение.

long saverg_ (RedGroupRef *RedGroupRefPtr);

*RedGroupRefPtr - ссылка на редукционную группу.

Функция saverg_ запоминает значения всех переменных заданной редукционной группы. Редукционная группа, заданная ссылкой *RedGroupRefPtr, должна быть создана в текущей подзадаче, а также не может быть пустой или запущенной с помощью функции strtrd_ (см. п. 11.6).

Возвращается нулевое значение.

11.6 Запуск редукционной группы

long strtrd_ (RedGroupRef *RedGroupRefPtr);

*RedGroupRefPtr - ссылка на редукционную группу.

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

Запускаемая редукционная группа должна быть создана в текущей подзадаче и не может быть уже запущенной с помощью функции strtrd_. Повторный запуск редукционной группы возможен лишь после завершения предыдущего запуска функцией waitrd_ (см. п. 11.7). Нельзя запустить пустую редукционную группу.

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

1. Операция сложения (rf_SUM).

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

2. Операция умножения (rf_MULT).

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

3. Операции поразрядного сложения по модулю 2 и поразрядного сложения по модулю 2 с последующим инвертированием всех разрядов (rf_XOR и rf_EQU).

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

Функция возвращает нулевое значение.

11.7 Ожидание завершения редукции

long waitrd_ (RedGroupRef *RedGroupRefPtr);

*RedGroupRefPtr - ссылка на редукционную группу.

Функция waitrd_ выполняет ожидание завершения всех редукционных операций заданной группы и открывает доступ к входящим в неё редукционным переменным.

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

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

Возвращается нулевое значение.

11.8 Уничтожение редукционной группы

long delrg_ (RedGroupRef *RedGroupRefPtr);

*RedGroupRefPtr - ссылка на редукционную группу.

Функция delrg_ уничтожает созданную функцией crtrg_ редукционную группу. После уничтожения группы ссылка на неё может использоваться по усмотрению пользовательской программы.

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

Если редукционная группа была создана функцией crtrg_ с ненулевым значением параметра *DelRedSignPtr, то при её уничтожении будут уничтожены и все включённые в неё редукционные переменные.

Редукционная группа может быть уничтожена также с помощью функции delobj_ (см.п.17.5).

Возвращается нулевое значение.

11.9 Уничтожение редукционной переменной

long delred_ (RedRef *RedRefPtr);

*RedRefPtr - ссылка на редукционную переменную.

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

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

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

Редукционная переменная может быть уничтожена также с помощью функции delobj_ (см.п.17.5).

Возвращается нулевое значение.

11.10 Поддержка асинхронной редукции при выполнении параллельного цикла

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

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

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

Внутренние витки параллельного цикла разбиваются на порции (внутренние витки - это витки, соответствующие внутренним элементам локальной части распределённого массива, по которому отображён цикл, см. п. 9.3). Число порций определяется значением параметра запуска системы поддержки InPLQNumber (целое число, большее единицы). Разбиение внутренних витков на порции достигается делением на min(InPLQNumber, PLAxisSize) частей измерения цикла с наименьшим номером, число координат витков в котором больше единицы (PLAxisSize - число координат витков в таком измерении).

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

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

Опережающее выполнение редукционных операций осуществляется для всех запущенных функцией strtrd_ редукционных групп.

Замечание. Разбиение внутренних витков параллельного цикла на порции осуществляется также с целью опроса завершения всех приёмов и передач сообщений при работе с системой передачи сообщений MPI: при ненулевом значении параметра запуска системы поддержки dopl_MPI_Test каждый вызов функции dopl_ сопровождается обращением к функции MPI_Test для каждого незавершённого обмена сообщением. Обращение к функции MPI_Test применяется для "подталкивания" асинхронной передачи сообщений, т. е. с целью лучшего совмещения обменов сообщениями с вычислениями (специфика MPI).

Если оба параметра dopl_WaitRD и dopl_MPI_Test равны нулю, то внутренние витки параллельных циклов на порции не разбиваются.