12 Обмен границами распределенных массивов

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

{I₁ О M₁: I_1,нач<= I₁ <= I_1,кон } x . . . x {I_m О M_m: I_m,нач <= I_m <= I_m,кон} x . . . x
{I_n О M_n: I_n,нач <= I_n <= I_n,кон} ,

где:

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

LSB_k =

Здесь:

Аналогично, верхняя граница локальной части распределённого массива по измерению k определяется множеством индексных кортежей

HSB_k =

Нижняя (верхняя) граница по измерению k называется полной, если FS=1, или нижней (верхней) теневой гранью по измерению k, если FS=0. Объединение полных границ всех измерений называется полной границей локальной части распределённого массива:

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

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

12.1 Создание группы границ

ShadowGroupRef crtshg_ (long *StaticSignPtr);

*StaticSignPtr - признак создания статической группы границ.

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

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

12.2 Включение границы распределенного массива в группу границ

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

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

Допускается включение распределённого массива в несколько групп границ, а также повторное включение его в одну и ту же группу. В последнем случае ширины границ, заданные при обращении к функции inssh_, должны совпадать с ширинами границ, заданными при предыдущем включении его в эту группу. Запрещается включение массива в группу, находящуюся в состоянии обмена границами, а также в группу, находящуюся в состоянии приёма импортируемых или локальных, либо передачи экспортируемых или граничных элементов. Включение новых массивов в такую группу становится возможным только после завершения этих операций (см. описание функций strtsh_, recvsh_, sendsh_, recvla_, sendsa_ и waitsh_ в п.п. 12.3-12.8).

Ширины границ массивов, задаваемые параметрами LowShdWidthArray и HiShdWidthArray, не должны превосходить ширин границ, заданных при создании рассматриваемого массива с помощью функции crtda_. Ширина границы, равная –1, означает, что будет использована ширина границы, заданная при создании массива.

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

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

Обмен границами, являющимися объединением теневых граней, требует взаимодействия текущего процессора с 2*n "соседями" (n – размерность распределённого массива, 2*n - число теневых граней), а обмен полными границами - с 3ⁿ - 1 "соседями". Поэтому для случая, когда граница как объединение теневых граней не покрывает потребностей задачи, а обмен полной границей неприемлем по накладным расходам, система поддержки предусматривает возможность выбора достаточной и оптимальной схемы обмена границами, основанной на представлении границы в виде объединения элементарных теневых n-мерных параллелепипедов.

Пусть Q = (q₁, ... ,q_k, ... ,q_n) - n-размещение с повторениями из элементов множества {0,1,2} (размещение (0, ... ,0) не рассматривается). Поставим ему в соответствие n-мерный параллелепипед P_Q = M₁ x ... x M_k x ... x M_n , где:

Здесь:

Параллелепипед P_Q называется элементарным теневым n-мерным параллелепипедом.

Полная граница распределённого массива - это объединение всех элементарных теневых параллелепипедов (кроме параллелепипеда, соответствующего размещению (0, ... ,0) и являющегося локальной частью распределённого массива). Число элементарных параллелепипедов, составляющих полную границу, есть A₃ⁿ - 1 = 3ⁿ - 1.

Нижняя (верхняя) теневая грань по измерению k - это элементарный теневой параллелепипед, соответствующий n-размещению, в котором q_k = 1(2), а остальные q_i равны нулю.

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

Ширины границ массивов, задаваемые параметрами LowShdWidthArray и HiShdWidthArray, не должны превосходить ширин границ, заданных при создании рассматриваемого массива с помощью функции crtda_. Ширина границы, равная –1, означает, что будет использована ширина границы, заданная при создании массива.

Код участия (i+1)-го измерения массива в формировании границы, задаваемый в i-м элементе массива ShdSignArray, может принимать значения:

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

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

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

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

Замечание. Включение в группу границ теневых граней распределённого массива с помощью функции inssh_ эквивалентно выполнению функции insshd_ с равным единице значением параметра *MaxShdCountPtr и с массивом ShdSignArray, каждый элемент которого равен 7. Для включения в группу границ полной границы распределённого массива с помощью функции insshd_ параметр *MaxShdCountPtr должен быть равен размерности распределённого массива, а каждый элемент массива ShdSignArray также должен быть равен 7.

12.3 Запуск обмена границами заданной группы

long strtsh_ (ShadowGroupRef *ShadowGroupRefPtr);

*ShadowGroupRefPtr - ссылка на группу границ.

Функция strtsh_ инициализирует системный буфер обмена границами (если обмен границами данной группы запускается в первый раз), размещает в нём все зарегистрированные с помощью функции inssh_ (inshsd_) границы и запускает операцию обмена границами.

Все элементы всех процессорных систем, в которые отображены массивы, зарегистрированные в запускаемой группе, должны принадлежать текущей процессорной системе. Обмен границами заданной группы может быть запущен только в том случае, если предыдущие операции обмена границами этой группы, приёма локальных или импортируемых элементов и передачи граничных или экспортируемых элементов завершены с помощью функции waitsh_ (см. п.п. 12.4-12.8).

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

12.4 Инициализация приема импортируемых элементов заданной группы границ

long recvsh_(ShadowGroupRefPtr *ShadowGroupRefPtr);

*ShadowGroupRefPtr - ссылка на группу границ.

Все элементы всех процессорных систем, в которые отображены массивы, зарегистрированные в заданной группе, должны принадлежать текущей процессорной системе. Приём импортируемых элементов группы может быть запущен только в том случае, если предыдущие операции обмена границами этой группы, приёма импортируемых и передачи граничных элементов завершены с помощью функции waitsh_ (см. п.п. 12.3, 12.7 и 12.8).

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

Ожидание завершения приёма импортируемых элементов осуществляется с помощью функции waitsh_ (см.п.12.8).

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

12.5 Инициализация передачи экспортируемых элементов заданной группы границ

long sendsh_(ShadowGroupRefPtr *ShadowGroupRefPtr);

*ShadowGroupRefPtr - ссылка на группу границ.

Все элементы всех процессорных систем, в которые отображены массивы, зарегистрированные в заданной группе, должны принадлежать текущей процессорной системе. Передача экспортируемых элементов группы может быть запущена только в том случае, если предыдущие операции обмена границами этой группы, передачи экспортируемых и приёма локальных элементов завершены с помощью функции waitsh_ (см. п.п. 12.3, 12.6 и 12.8).

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

Ожидание завершения передачи экспортируемых элементов осуществляется с помощью функции waitsh_ (см.п.12.8).

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

Замечание. Последовательность обращений

recvsh_(ShadowGroupRefPtr);
sendsh_(ShadowGroupRefPtr);

эквивалента вызову strtsh_(ShadowGroupRefPtr).

12.6 Инициализация приема локальных элементов распределенных массивов заданной группы границ

long recvla_(ShadowGroupRefPtr *ShadowGroupRefPtr);

*ShadowGroupRefPtr - ссылка на группу границ.

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

Все элементы всех процессорных систем, в которые отображены массивы, зарегистрированные в заданной группе, должны принадлежать текущей процессорной системе. Приём локальных элементов группы может быть запущен только в том случае, если предыдущие операции обмена границами этой группы, приёма локальных и передачи экспортируемых элементов завершены с помощью функции waitsh_ (см. п.п. 12.3, 12.5 и 12.8).

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

Ожидание завершения приёма локальных элементов осуществляется с помощью функции waitsh_ (см.п.12.8).

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

12.7 Инициализация передачи граничных элементов распределенных массивов заданной группы границ

long sendsa_(ShadowGroupRefPtr *ShadowGroupRefPtr);

*ShadowGroupRefPtr - ссылка на группу границ.

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

Все элементы всех процессорных систем, в которые отображены массивы, зарегистрированные в заданной группе, должны принадлежать текущей процессорной системе. Передача граничных элементов группы может быть запущена только в том случае, если предыдущие операции обмена границами этой группы, передачи граничных и приёма импортируемых элементов завершены с помощью функции waitsh_ (см. п.п. 12.3, 12.4 и 12.8).

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

Ожидание завершения передачи экспортируемых элементов осуществляется с помощью функции waitsh_ (см.п.12.8).

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

12.8 Ожидание завершения обмена границами заданной группы

long waitsh_ (ShadowGroupRef *ShadowGroupRefPtr);

*ShadowGroupRefPtr - ссылка на группу границ.

Функция waitsh_ завершает операцию обмена границами заданной группы, инициированную функцией strtsh_, и разрешает новый запуск обмена границами этой группы. Данной функцией осуществляется также ожидание завершения операций приёма локальных или импортируемых элементов и передачи граничных или экспортируемых элементов, инициированных функциями recvla_, recvsh_, sendsa или sendsh_ (см. п.п. 12.4-12.7). После выполнение функции waitsh_ группа становится открытой для включения в неё распределённых массивов.

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

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

12.9 Уничтожение группы границ

long delshg_ (ShadowGroupRef *ShadowGroupRefPtr);

*ShadowGroupRefPtr - ссылка на группу границ.

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

Группа границ может быть уничтожена функцией delshg_ только в том случае, если она была создана в текущей подзадаче и в текущем программном блоке (или его подблоке) (см. п. 8 и п. 10). Нельзя уничтожить группу границ, если не завершены запущенные ранее обмен границами, операции передачи граничных или экспортируемых элементов и приёма локальных или импортируемых элементов (см. п.п. 12.3-12.8).

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

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

13 Доступ к элементам распределенных массивов

13.1 Копирование элемента распределенного массива

13.1.1 Чтение элемента распределенного массива и присвоение ему значения

При использовании функции rwelm_ для чтения элемента распределённого массива:

При использовании функции rwelm_ для присвоения значения элементу распределённого массива:

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

Число задаваемых в массиве IndexArray индексов должно быть равно размерности читаемого или модифицируемого массива.

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

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

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

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

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

13.1.2 Копирование элемента одного распределенного массива в элемент другого распределенного массива

Типы читаемого и записываемого элементов должны совпадать.

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

Возвращается число скопированных байтов.

13.1.3 Обобщенная пересылка элемента распределенного массива

Функция elmcpy_ является обобщением рассмотренных выше более специализированных функций rwelm_ и copelm_ .

Если FromArrayHeader и ToArrayHeader являются заголовками распределённых массивов, то типы элементов этих массивов должны совпадать.

Если FromArrayHeader (ToArrayHeader) является указателем на область памяти, то содержимое массива FromIndexArray (ToIndexArray) игнорируется. Копирование в этом случае определяется значением *CopyRegimPtr: ненулевое значение *CopyRegimPtr означает, что область памяти предполагается размещённой только на процессоре ввода/вывода. FromArrayHeader и ToArrayHeader не могут быть оба указателями на области памяти.

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

Возвращается число скопированных байтов.

13.2 Копирование распределенных массивов

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

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

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

Если один из массивов не является распределённым, то способ копирования определяется значением *CopyRegimPtr:

• при нулевом значении *CopyRegimPtr "обычный" массив считается размещённым на всех процессорах текущей процессорной системы;
• положительное значение *CopyRegimPtr означает, что "обычный" массив предполагается размещённым только на процессоре ввода/вывода;
• отрицательное значение *CopyRegimPtr (допустимо только для читаемого "обычного" массива) устанавливает режим росписи распределённого массива, определённого параметром ToArrayHeader, элементом, адрес которого задан параметром FromArrayHeader.

Если оба массива не являются распределёнными, то копирование не производится.

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

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

Функция возвращает число скопированных элементов.

13.3 Асинхронное копирование распределенных массивов

Описанные выше функции arwelm_ , arwelf_ , acopel_ , aelmcp_ и aarrcp_ осуществляют запуск операций копирования, выполняемых функциями rwelm_, rwelmf_, copelm_, elmcpy_, и arrcpy_ . Все параметры рассматриваемых функций, кроме последнего, аналогичны одноименным параметрам их синхронных аналогов. Последний параметр, CopyFlagPtr, является указателем на флаг завершения запущенной операции копирования.

Ожидание завершения копирования осуществляется с помощью функции

long waitcp_ (AddrType *CopyFlagPtr);

*CopyFlagPtr - флаг завершения операции копирования, заданный при её запуске.

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

13.4 Доступ к элементам локальной части распределенного массива

Пусть n - размерность распределённого массива. Тогда его заголовок, задаваемый при обращении к функции crtda_ c нулевым значением параметра *ExtHdrSignPtr, может быть объявлен, например, как

long ArrayHeader[n+1]; /* стандартный заголовок */

Пусть также базовый указатель, соответствующий типу элементов распределённого массива, есть BasePtr. Тогда обращение к элементу локальной части распределённого массива, определённому индексным вектором (I₁,...,I_n), осуществляется по линейному индексу следующим образом:

Для языка C п ри обращении к функции crtda_ значение базового указателя можно задавать равным NULL. Тогда доступ к элементу локальной части распределённого массива можно произвести разименованно:

где Type - тип элементов распределённого массива.

Коэффициенты ArrayHeader[1], ... , ArrayHeader[n-1] и адресная константа ArrayHeader[n] вычисляются системой поддержки при выполнении функций выравнивания массива align_ и realn_ следующим образом.

Пусть:

Тогда:

При обращении к функции crtda_ с ненулевым значением параметра *ExtHdrSignPtr заголовок распределённого массива может быть статически задан как

long ArrayHeader[2*n+2]; /* расширенный заголовок */

Первые (n+1) слов расширенного заголовка совпадают с рассмотренным выше стандартным заголовком. Слова от (n+2)-го до (2*n+1)-го должны быть заданы программой пользователя до размещения массива в памяти с помощью функции align_ (malign) (предполагается, что в этих словах задаются нижние значения индексов распределённых массивов, используемых в Фортране). (n+1)-е слово расширенного заголовка вычисляется системой поддержки при отображении или переотображении массива в процессорную систему как

Отметим, что система поддержки при выполнении функций align_ и realn_ размещает в памяти локальную часть распределённого массива таким образом, чтобы разность (ArrayPtr - BasePtr) была кратна TypeSize.

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

13.4.1 Опрос принадлежности элемента распределенного массива его локальной части

Число задаваемых индексов должно быть равно размерности распределённого массива.

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

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

Длины массивов InitIndexArray и LastIndexArray должны быть равны размерности распределённого массива.

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

13.4.3 Чтение элемента локальной части распределенного массива

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

Возвращается длина элемента распределённого массива в байтах (число прочитанных байтов).

13.4.4 Присвоение значения элементу локальной части распределенного массива

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

Возвращается длина элемента распределённого массива в байтах.

13.4.5 Копирование элемента локальной части одного распределенного массива в элемент локальной части другого распределенного массива

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

Возвращается число скопированных байтов.

13.4.6 Опрос адреса элемента локальной части распределенного массива

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

Возвращается указатель на первый байт элемента.

13.5 Макрокоманды доступа к элементам локальных частей распределенных массивов размерностей от 1 до 7

В программах, написанных на языке C, для доступа к локальным элементам распределённых массивов размерностей от 1 до 7 можно воспользоваться макрокомандами вида

Семь вышеописанных макрокоманд являются L-выражениями языка C.

Доступ к локальной части распределённого массива посредством макрокоманд эффективнее доступа с помощью описанных в п.13.4 функций.

Предполагается, что при создании массива с заголовком ArrayHeader базовый указатель был задан равным NULL.

13.6 Последовательный опрос значений индексов элементов распределенного массива

Функция setind_ устанавливает начальные и конечные значения и шаги изменения индексов элемента распределённого массива для последующего последовательного их опроса и продвижения с помощью рассмотренной ниже функции getind_.

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

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

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

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