1 Введение

Прежде чем перейти к описанию функций библиотеки Lib-DVM, опишем кратко используемую модель параллельных вычислений.

Последовательная программа на исходном языке Fortran-77 или Си превращается в программу на том же языке, содержащую вызовы функций Lib-DVM, и выполняющуюся в соответствии с моделью SPMD на каждом выделенном задаче процессоре.

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

Многопроцессорной системой (или системой процессоров) будем называть ту машину, которая предоставляется программе пользователя аппаратурой и базовым системным программным обеспечением. Для распределённой ЭВМ примером такой машины может служить MPI-машина. В этом случае, многопроцессорная система - это группа MPI-процессов, которые создаются при запуске параллельной программы на выполнение. Число процессоров многопроцессорной системы и её представление в виде многомерной решетки задаётся в командной строке при запуске программы.

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

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

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

2 Инициализация системы поддержки и завершение с ней работы

Инициализация из программы на языке C:

Инициализация из программы на языке Фортран:

long linit_ (long *InitParamPtr);

где:

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

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

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

long lexit_ (long *UserResPtr);

*UserResPtr - код завершения пользовательской программы.

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

Возврата из функции не происходит.

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

Пусть размерность многопроцессорной системы задана равной n, а размер по измерению k - равным PSSize_k (1 <= k <= n). Тогда при инициализации системы поддержки каждому процессору будет присвоен внутренний номер ProcNumber_int:

где I_k - значение индекса процессора по измерению k индексного пространства многопроцессорной системы (0 <= I_k <= PSSize_k-1). То есть, внутренний номер - это линейный индекс процессора в индексном пространстве многопроцессорной системы.

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

ProcNumber_int => ProcIdent

возвращается системе поддержки системой передачи сообщений (Message Passing System) при её инициализации.

Среди процессоров выделенного задаче решающего поля функционально выделены два: процессор ввода/вывода и центральный процессор. Процессор ввода/вывода предназначен для непосредственного общения с файловой системой (см.п.16) и имеет нулевой внутренний номер. Центральный процессор осуществляет вычисление редукционных функций (см.п.11) и определяется индексным вектором ([PSSize₁/2], ... , [PSSize_n/2]).

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

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

В языках C-DVM и Fortran-DVM термин "абстрактная машина" не введён. Вместо него, как и в других языках с параллелизмом данных, используется термин "шаблон" ("TEMPLATE"). Каждый описанный в программе "шаблон" представлен в Lib-DVM соответствующей абстрактной машиной. Для каждого явно распределяемого массива (специфицированного DVM-указанием "DISTRIBUTE") создается соответствующая абстрактная машина.

3.1 Опрос ссылки на текущую абстрактную машину

AMRef getam_ (void);

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

3.2 Создание представления абстрактной машины

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

Родительская абстрактная машина, заданная ссылкой *AMRefPtr, должна быть текущей абстрактной машиной или её потомком (прямым или косвенным). Если AMRefPtr = NULL или *AMRefPtr = 0, то будет создано представление текущей абстрактной машины.

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

3.3 Опрос ссылки на элемент представления абстрактной машины

Число элементов массива IndexArray должно быть равно размерности заданного представления абстрактной машины.

3.4 Уничтожение представления абстрактной машины

long delamv_ (AMViewRef *AMViewRefPtr);

*AMViewRefPtr - ссылка на представление абстрактной машины.

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

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

Представление абстрактной машины может быть уничтожено также с помощью функции delobj_ (см.п.17.5).

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

4 Многопроцессорные системы

4.1 Опрос ссылки на многопроцессорную систему

PSRef getps_ (AMRef *AMRefPtr);

*AMRefPtr - ссылка на абстрактную машину.

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

Если AMRefPtr = NULL или *AMRefPtr = 0, то возвращается ссылка на процессорную систему, на которую отображена текущая абстрактная машина (т. е. возврат ссылки на текущую процессорную систему).

При *AMRefPtr, равном –1, функция возвращает ссылку на начальную процесорную систему.

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

4.2 Создание подсистемы заданной многопроцессорной системы

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

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

Внутренние значения координат элементов любой процессорной системы начинаются с нуля. Поэтому элемент (P₁, ... ,P_j, ... ,P_n) создаваемой подсистемы будет являться элементом (P₁ + InitIndexArray[0], ... , P_j + InitIndexArray[j-1], ... , P_n + InitIndexArray[n-1]) исходной процессорной системы (n - размерность исходной и создаваемой систем). Размер создаваемой подсистемы по измерению i равен LastIndexArray[i-1] - InitIndexArray[i-1] + 1.

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

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

Отметим, что процессорные системы, создаваемые функцией crtps_, могут пересекаться по составу процессоров.

4.3 Реконфигурация (изменение формы) многопроцессорной системы

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

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

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

4.4 Уничтожение многопроцессорной системы

long delps_ (PSRef *PSRefPtr);

*PSRefPtr - ссылка на уничтожаемую процессорную систему.

Функция уничтожает созданную функцией crtps_ (или psview_) процессорную систему. Вместе с уничтожением процессорной системы уничтожаются все её подсистемы, а также все отображённые в неё представления абстрактных машин и распределённые массивы. Абстрактные машины, отображённые в уничтоженную процессорную систему функцией mapam_, не уничтожаются, но созданные этой функцией подзадачи существовать перестают (см. п. 10).

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

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

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

4.5 Веса элементов многопроцессорной системы

Пусть многопроцессорная система представлена n-мерным массивом, для каждого измерения i которого задана функция WEIGHT_i, определённая на множестве значений индексной переменной этого измерения и принимающая большие или равные единице вещественные значения. Значение функции WEIGHT_i(P_i) будем называть весом координаты P_i (1 <= i <= n , 0 <= P_i < PSSIZE_i , PSSIZE_i - размер i-го измерения многопроцессорной системы).

Тогда, по определению, вес процессора (P₁, ... , P_i, ... , P_n) есть

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

Значение параметра AMViewRefPtr определяет два варианта выполнения функции setpsw_ .

1. AMViewRefPtr # NULL и *AMViewRefPtr # 0.

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

   Абстрактная машина (родительская), представление которой задано ссылкой *AMViewRefPtr, на момент обращения к функции setpsw_ должна быть отображена.

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

2. AMViewRefPtr = NULL или *AMViewRefPtr = 0.

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

Все процессоры системы, заданной ссылкой *PSRefPtr, должны входить в состав текущей процессорной системы. Равное NULL значение указателя PSRefPtr или нулевое значение ссылки *PSRefPtr означают, что задаются веса координат элементов текущей процессорной системы.

Вес координаты P_i i-го измерения процессорной системы задаётся значением

элемента массива CoordWeightArray. Число элементов массива CoordWeightArray с весами координат процессоров должно быть равно сумме размеров всех измерений многопроцессорной системы. Веса координат в массиве CoordWeightArray могут быть любыми вещественными положительными числами. При выполнении функции setpsw_ система поддержки корректирует каждый вес P_i делением его на минимальный вес координаты в массиве CoordWeightArray.

Если CoordWeightArray = NULL или CoordWeightArray[0] = 0, то в качестве устанавливаемых весов координат будут приняты веса, заданные параметрами запуска системы поддержки (для начальной процессорной системы), или единичные веса координат (для процессорной системы, не являющейся начальной).

Если CoordWeightArray[0] = - 1, то веса всех координат будут установлены равными единице и не будут подвергнуты дальнейшей коррекции, т. е. будут приняты за оптимальные веса координат процессоров (см. ниже).

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

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

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

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

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

1. пропорционален весу производительности процессора;
2. при любой производительности процессора равен произведению весов его координат.

Будем считать также, что "вклад" веса производительности процессора в веса его координат одинаков.

Поэтому значение веса производительности процессора WEIGHT_perf(P₁, ... , P_i, ... ,P_n) требует увеличения вычислительного веса любой его координаты в WEIGHT_perf^1/n(P₁, ... , P_i, ... , P_n) раз.

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

Решение в области больших или равных единице вещественных чисел есть

Использование оптимальных весов координат процессоров для неравномерного распределения элементов представления абстрактной машины (и, как следствие, элементов распределённого массива и витков параллельного цикла) рассмотрено в п.5.7.

Кроме рассмотренной ранее функции setpsw_, вычислительные веса координат процессоров могут быть заданы с помощью функций

и

Параметры PSRefPtr и AMViewRefPtr этих функций аналогичны одноимённым параметрам функции setpsw_. Веса координат процессоров задаются в отдельном для каждого измерения процессорной системы массиве, адрес которого содержится в массиве AxisWeightAddr: i-й элемент массива AxisWeightAddr является приведённым к типу AddrType указателем на массив с весами координат процессоров (i+1)-го измерения заданной процессорной системы. Функция genbli_ предполагает представление весов координат процессоров в виде целых положительных чисел (integer), а функция genbld_ - в виде положительных вещественных (double).

Нулевое значение i-го элемента массива AxisWeightAddr означает, что для (i+1)-го измерения процессорной системы будут установлены веса координат процессоров, равные весам, заданым параметрами запуска системы поддержки (для начальной процессорной системы), или равные единице (для процессорной системы, не являющейся начальной).

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

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

Замечание. Выполнение функций genbli_ и genbld_ сводится к обращению к функции

первые четыре параметра которой идентичны одноимённым параметрам функций genbli_ и genbld_, а последний, *DoubleSignPtr, является ненулевым признаком представления весов координат процессоров в виде вещественных положительных чисел (double).

4.6 Задание весов координат процессоров по весам их загрузки

Функция setelw_ определяет вычислительные веса координат элементов процессорной системы, заданной ссылкой *PSRefPtr, и затем устанавливает их с помощью функции genbld_ (см.п.4.5).

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

Абстрактная машина (родительская), представление которой задано ссылкой *AMViewRefPtr, на момент обращения к функции setelw_ должна быть отображена.

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

Равное NULL значение указателя PSRefPtr или нулевое значение ссылки *PSRefPtr означают, что задаются веса координат элементов текущей процессорной системы.

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

Формально: для каждого (i+1)-го измерения заданной процессорной системы функция setelw_ решает (относительно I_k,init и I_k,last) задачу

где:

После нахождения решения задачи (1) (обозначим его I_k,init,even , I_k,last,even; k = 0, ... , n-1) вычислительный вес координаты k (i+1)-го измерения заданной процессорной системы полагается равным

I_{k,last,even -} I_k,init,even + 1           (k = 0, ... , n - 1).

Координатные веса загрузки должны быть заданы в виде вещественных неотрицательных чисел (double).

Нулевое значение i-го элемента массива LoadWeightAddr означает, что для (i+1)-го измерения заданной процессорной системы будут установлены веса координат процессоров, равные весам, заданым параметрами запуска системы поддержки (для начальной процессорной системы), или равные единице (для процессорной системы, не являющейся начальной).

Значение параметра *AddrNumberPtr не может превосходить размерности заданной процессорной системы. Недостающие до размерности процессорной системы элементы массива LoadWeightAddr будут считаться нулевыми. В частности, равное нулю значение параметра *AddrNumberPtr означает, что веса всех координат всех процессоров будут установлены либо единичными, либо равными весам, заданным в параметрах запуска системы поддержки.

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

4.7 Виртуальные многопроцессорные системы (многопроцессорные системы программы пользователя)

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

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

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

UserPS = <список размеров измерений, разделённых запятыми>;

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

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

В этом случае:

• все процессорные подсистемы, создаваемые функциями crtps_ и psview_ (см. п.п. 4.2 и 4.3), являются виртуальными, исходной для которых (на верхнем уровне иерархии) является виртуальная начальная процессорная система;
• при создании виртуальной процессорной подсистемы создаётся соответствующая ей реальная процессорная подсистема (при инициализации системы поддержки виртуальной начальной процессорной системе соответствует реальная начальная процессорная система);
• вычислительные веса координат процессоров любой процессорной системы полагаются равными единице (вне зависимости от их значений, заданных в параметрах запуска системы поддержки или при обращении к функциям setpsw_, genbli_, genbld_ и genblk_, см. п. 4.5);
• веса загрузки процессоров, задаваемые при обращении к функции setelw_ (см. п. 4.6), игнорируются и считаются равными единице;
• функции getsiz_ и locsiz_ (см. п. 17.2) возвращают размеры виртуальных процессорных систем.

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

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

5 Отображение представления абстрактной машины

5.1 Задание отображения представления абстрактной машины на многопроцессорную систему (распределение ресурсов)

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

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

Абстрактная машина (родительская), представление которой задано при обращении к функции, на момент обращения к функции distr_ должна быть отображена. Все процессоры системы, заданной ссылкой *PSRefPtr, должны входить в состав элементного пересечения текущей процессорной системы с процессорной системой, в которую отображена родительская абстрактная машина. При нулевом значении ссылки *PSRefPtr или при равном NULL значении указателя PSRefPtr для распределения ресурсов будет использована текущая процессорная система.

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

Число параметров, задаваемое в массивах AxisArray и DistrParamArray, должно быть равно *ParamCountPtr, которое не может превосходить размерности многопроцессорной системы, но может быть меньше её. В последнем случае недостающие до размерности многопроцессорной системы правила отображения будут считаться размножениями (2-е из рассмотренных ниже правил отображения).

Распределение ресурсов абстрактной машины достигается реализацией функционального соответствия

{представление абстрактной машины} => {многопроцессорная система} ,

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

Здесь:

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

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

1. F_j(I₁, ... ,I_n) = { [I_k/BLSIZE_k] } , где:

В этом случае образом элемента (i₁, ... , i_n) индексного пространства представления абстрактной машины является множество, содержащее один элемент - [I_k/BLSIZE_k], принадлежащий множеству значений индексной переменной j-го измерения многопроцессорной системы.

Значение BLSIZE_k определяется следующим образом. Пусть:

Тогда:

Отметим, что максимально допустимое значение I_k есть

min( (PSSIZE_j * BLSIZE_k -1) , AMSIZE_k -1 ).

Поэтому для полного охвата правилом отображения k-го измерения представления абстрактной машины требуется выполнение неравенства

AMSIZE_k <= PSSIZE_j * BLSIZE_k ,

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

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

3. F_j(I₁, ... , I_n) = { Const } , где 0 <= Const <= PSSIZE_j-1 .

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

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

Примеры.

1. Пусть абстрактная машина и многопроцессорная система представлены матрицами:

   AM[9][8]	(0 <= I1 <= 8 , 0 <= I2 <= 7);
   PS[3][4]	(0 <= J1 <= 2 , 0 <= J2 <= 3).

   Тогда функция F((I₁,I₂)) = { [I₁ / 3]} x {[I₂ / 2] } установит соответствие:
   элемент PS[J₁][J₂] <=> подматрица AM[3*J₁ <= I₁ <= 3*J₁ + 2][2*J₂ <= I₂ <= 2*J₂ + 1] (блок [3][2]).

2. Пусть абстрактная машина и многопроцессорная система представлены массивами:

   AM[12]	(0 <= I <= 11);
   PS[4][3]	(0 <= J1 <= 3 , 0 <= J2 <= 2).

   Тогда функция F((I)) = {2} x {[I/4]} установит соответствие:
   элемент PS[2][J₂] <=> отрезок AM[4*J₂ <= I <= 4*J₂ + 3] (блок [4]).
   Строки 0,1 и 3 многопроцессорной системы в образ отображения F не войдут.

3. Пусть абстрактная машина и многопроцессорная система представлены массивами:

   AM[8][12]	(0 <= I1 <= 7 , 0 <= I2 <= 11);
   PS[3]	(0 <= J <= 2).

   Тогда функция F((I₁,I₂)) = {[I₂/4]} установит соответствие:
   элемент PS[J] <=> подматрица AM[0 <= I₁ <= 7][4*J <= I₂ <= 4*J + 3] (блок [8][4]).

4. Пусть абстрактная машина и многопроцессорная система представлены массивами:

   AM[12]	(0 <= I <= 11);
   PS[4][3]	(0 <= J1 <= 3 , 0 <= J2 <= 2).

   Тогда функция F((I)) = {*} x {[I/4]} установит соответствие:
   элемент PS[J₁][J₂] <=> отрезок AM[4*J₂ <= I <= 4*J₂ + 3] (блок [4]).
   То есть, в данном случае образ отображения F из примера b) размножен по строкам многопроцессорной систем.

5. Пусть абстрактная машина и многопроцессорная система представлены матрицами:

   AM[9][8]	(0 <= I1 <= 8 , 0 <= I2 <= 7);
   PS[3][4]	(0 <= J1 <= 2 , 0 <= J2 <= 3).

   Тогда функция F((I₁,I₂)) = {*} x {*} установит соответствие:
   элемент <=> подматрица AM[0 <= I₁ <= 8][0 <= I₂ <= 7] (блок[9][8]), PS[J₁][J₂] т.е. все представление абстрактной машины.

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

При обращении к функции distr_ координатное правило отображения F_j(I₁, ... , I_n) = {[I_k/BLSIZE_k]} для j-го измерения многопроцессорной системы задается следующим образом:

Если DistrParamArray[j-1] задан нулевым, то система поддержки вычислит BLSIZE_k так, как было показано выше.

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

Правило отображения F_j(I₁, ... , I_n) = { Const } задается так:

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

5.2 Изменение отображения представления абстрактной машины на многопроцессорную систему (перераспределение ресурсов)

Функция redis_ отменяет распределение ресурсов родительской абстрактной машины, установленное ранее с помощью функции distr_ (или mdistr_ , см.п.5.4) для дочерних абстрактных машин, которые входят в состав представления, заданного ссылкой *AMViewRefPtr, и осуществляет новое отображение указанного представления в соответствии с заданными параметрами. Все распределённые массивы, ранее выравненные по рассматриваемому представлению с помощью функций align_ и malign_ (как непосредственно, так и косвенно), будут отображены заново по прежним правилам выравнивания (см.п.7).

Содержимое перераспределённых массивов, в зависимости от значения *NewSignPtr, будет:

• сохранено (при *NewSignPtr = 0);
• считаться неопределённым (при *NewSignPtr = 1);
• расписано "нулевым" байтом, то есть байтом, все биты которого имеют нулевые значения (при *NewSignPtr = 2).

При NewSignPtr = 1 все перераспределённые массивы будут , тем не менее, расписаны "нулевым" байтом, если система поддержки была запущена с ненулевым значением параметра DisArrayFill (файлы sysdebug.* базовых наборов параметров).

При переотображении массивов содержимое их границ (см. п. 12) не сохраняется.

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

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

Переотображаемое представление может быть задано косвенно, если в качестве параметра *AMViewRefPtr использовать заголовок распределённого массива, созданного функцией crtda_ с равным 1 или 3 значением параметра *ReDistrParPtr (см.п.6).

Представление абстрактной машины, заданное при обращении к функции, может быть ранее не отображено. В этом случае функция redis_ выполняется как функция distr_ , а значение параметра *NewSignPtr несущественно.

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

5.3 Опрос карты отображения

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

Карта отображения представления абстрактной машины содержит, в частности, следующую информацию:

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

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

5.4 Задание отображения представления абстрактной машины по карте отображения

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

Абстрактная машина (родительская), представление которой задано ссылкой *AMViewRefPtr, на момент обращения к функции mdistr_ должна быть отображена.

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

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

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

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

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

5.5 Изменение отображения представления абстрактной машины по карте отображения

Функция mredis_ отменяет распределение ресурсов абстрактной машины, установленное ранее с помощью функции mdistr_ (или distr_ , см.п.5.1) для дочерних абстрактных машин, которые входят в состав представления, заданного ссылкой *AMViewRefPtr, и осуществляет новое отображение указанного представления в соответствии с заданной картой отображения. Все распределённые массивы, ранее выравненные по рассматриваемому представлению с помощью функций align_ и malign_ (как непосредственно, так и косвенно), будут отображены заново по прежним правилам выравнивания (см.п.7).

Содержимое перераспределённых массивов, в зависимости от значения *NewSignPtr, будет:

• сохранено (при *NewSignPtr = 0);
• считаться неопределённым (при *NewSignPtr = 1);
• расписано "нулевым" байтом, то есть байтом, все биты которого имеют нулевые значения (при *NewSignPtr = 2).

При NewSignPtr = 1 все перераспределённые массивы будут, тем не менее, расписаны "нулевым" байтом, если система поддержки была запущена с ненулевым значением параметра DisArrayFill (файлы sysdebug.* базовых наборов параметров).

При переотображении массивов содержимое их границ (см. п. 12) не сохраняется.

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

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

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

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

Переотображаемое представление может быть задано косвенно, если в качестве параметра *AMViewRefPtr использовать заголовок распределённого массива, созданного функцией crtda_ с равным 1 или 3 значением параметра *ReDistrParPtr (см.п.6).

Представление абстрактной машины, заданное при обращении к функции, может быть ранее не отображено. В этом случае функция mredis_ выполняется как функция mdistr_ , а значение параметра *NewSignPtr несущественно.

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

5.6 Уничтожение карты отображения

long delmvm_ (AMViewMapRef *AMViewMapRefPtr);

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

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

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

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

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

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

5.7 Неравномерное блочное распределение

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

Рассмотренное в п.5.1 отображение представления абстрактной машины на многопроцессорную систему представляет собой равномерное распределение ресурсов родительской абстрактной машины по элементам её представления. В этом случае для каждого измерения представления абстрактной машины k величина блока BLSIZE_k считается не зависящей от значения j-й координаты элемента многопроцессорной системы. Такая однородность по каждому измерению многопроцессорной системы является следствием предполагаемой в п.5.1 равновесности всех её элементов: оптимальные веса всех координат процессоров одинаковы и равны единице (см.п.4.5).

Рассмотрим теперь случай неравновесных элементов многопроцессорной системы. Будем, как и в п.5.1, оперировать постоянной для k-го измерения представления абстрактной машины величиной блока BLSIZE_k, но "число" блоков, приходящихся на элемент многопроцессорной системы с координатой по j-му измерению P_j, будем полагать равным оптимальному весу этой координаты. Тогда первое из рассмотренных в п.5.1 правил отображения (то есть функция F_j(I₁, ... , I_n)) определяется неравенствами

где WEIGHT_opt,j(P_j) - оптимальный вес координаты P_j.

Значение BLSIZE_k определяется следующим образом:

где

Поскольку максимально допустимое значение I_k есть

min( ([PSWEIGHT_opt,j * BLSIZE_k] - 1) , AMSIZE_k - 1 ) ,

для полного охвата правилом отображения k-го измерения представления абстрактной машины требуется выполнение неравенства

AMSIZE_k <= PSWEIGHT_opt,j * BLSIZE_k ,