malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

а)

рис. 7.23

Пример выделения подопераций показан на рис. 7.23. В

результате выделения подопераций (рис. 7.23а) из ПВМ на рис. 7.17 будет удалена операция b, а вместо нее появятся операции b1, b2 (рис. 7.23б), что позволит построить ПП, в которой вычисления “ внутри” b можно начинать сразу же, как только это станет возможным. Поскольку для вычисления x10 (см. рис. 7.17)

нужна только переменная x out(b), то в нисходящей части алгоритма планирования проводится чистка b2, в результате которой из операции b2 (имеется в виду из F b2 , где

SI(b2)=B2=(X b2 ,F b2 )) удаляется операция g4, вычисляющая у9, а

для оставшейся после чистки операции b2′, in(b2′)={x5}, out(b2′)={x8}, не требуется вычислять переменную y1, и операция b1 оказывается не нужной для вычисления х10 (не используется в

308

терме, вычисляющем x10, рис. 7.24).

x10

d

x8

w

b2'

a2

309

Наряду с (Vb,0,Wb) -планом в B может, к примеру, существовать и (Wb,Vb,0)-план, и в этом случае было бы возможно вычислять переменные in(b) из переменных out(b). Поэтому основанием для образования подоперации b1 лучше считать непустоту множества

Vb′1 =ViÇ(in(b)Èout(b)) (этот критерий называется критерием планировщика), и его же переменные должны войти в in(b1).

Аналогичным образом определяются и множества Vb′m , m = 2, 3,

.... Такое решение позволяет строить новые алгоритмы

310

вычисления W из V, его полезность иллюстрирует следующий пример.

Пусть в ПВМ С (рис. 7.25) есть структурированная операция b, SI(b)=В (ПВМ В показана на рис. 7.26), in(b)={x}, out(b)={y, z}, SI(x)={x1}, SI(y)={y1}, SI(z)={z1}.

Если на С поставлена задача построения ({v},{w})-плана, то она может быть решена только выделением подопераций b'1 и b2′, in(b1′)={у}, out(b′2)={z}, out(b1′)=in(b′2)={x} (рис. 7.27).

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

А. Раннее время вычисления значений переменных. В

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

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

311

подоперацию b2. Для этого в Tb1 отбираются все термы,

вычисляющие SI{x}, и образуется подоперация b1; in(b1)

содержит все переменные из множества

{y|SI(y)Îin(t)Ù(tÎ Tb1 )Ù(SI(x)Îout(t))};

ПВМ B1=(XB1,FB1) Определена всеми переменными и операциями, используемыми в TB1.

ПВМ В1 строится следующим образом. Сначала в XB1

попадает переменная SI(x), а в FB1 — все операции из множества comp (SI(х)). Затем в XB1 добавляется множество In(comp(SI(х))),

объединяющее все входные переменные операций из comp(SI(х)),

а в FB1 - все новые операции из множества comp( y ) , т.е.

некотором шаге новых операций не окажется.

Аналогичным образом строится ПВМ В2, out(b2)=out(b)\{х}. Если существуют термы t1ÎTB1 и t2ÎТB2 такие,

что sbt(t1)Çsbt(t2)¹Æ, то может быть выделена подоперация b12

подопераций b1 и b2, причем алгоритм вычисления функции I(b12)

задается общими для t1 и t2 подтермами. Общие подтермы выявляются при построении TB1 и TB2 алгоритмом выбора (V,W)-

плана;

В. Чистка циклов. Пусть в циклическом участке синтезированной ПП есть обращение к modb, вычисляющем

312

функцию fa=I(b), и b — структурированная операция, SI(b)=В.

Если в множестве in(b) есть переменные y1, ..., ут, значения которых вычисляются за пределами циклического участка и не перевычисляются внутри него, то из b могут быть удалены не массовые вычисления. Для этого следующим образом выделяется подоперация b1:

-формируется множество переменных V0={z|z=SI(yi), i=1, ...,

m};

-проводится восходящая часть алгоритма планирования на В

-из множества Fb удаляются операции F*, после этого производится чистка структурированной операции b.

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

-задать критерий выделения подопераций; эта директива может иметь различные параметры, например, может

313

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

которые назначены на некоторый процессор;

-указать количество подопераций, которые необходимо выделить, например, выделить по критерию планировщика не более трех подопераций структурированной операции b;

-указать список переменных из out(b), для вычисления которых необходимо выделить подоперацию структурированной операции.

Объединение структурированных операций. Это

преобразование применяется для того, чтобы уменьшить затраты ресурсов на реализацию управления в ПП и сделать операции,

используемые в Т, более “ однородными”. Пусть b1 и b2 -

структурированные операции, SI(b1)=B1, SI(b2)=В2. При объединении b1 и b2 образуется структурированная операция b, in(b)=in(b1)Èin(b2), out(b)=(out(b1)Èout(b2))\(in(b1)Èin(b2)),

SI(b)=B. Здесь ПВМ В определена всеми переменными и операциями B1 и B2, причем если переменная xÎ(in(b1)Èout(b1))Ç(in(b2)Èout(b2)), то все переменные B1 и B2,

соответствующие х в структурной интерпретации,

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

314

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

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

Например, описание

b=(на В вычислить w1,...,wm из v1, ..., vn) вх x1, ..., xn вых y1, ..., ym;

определяет структурированную операцию b, SI(b)=В, SI(xi)=vi,

SI(yj)=wj, i=1, ..., n, j=1, ..., т. Изменение интерпретации некоторой операции b ПВМ С, необходимое для решения сформулированной задачи, можно сделать при формулировке задачи, например, так:

на С (b=(на D вычислить...)) вычислить w из v;

В этом описании определяется (а может быть, и

переопределяется) структурная интерпретация операции b, b FC.

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

переменные {у ХC|SI(y) Wb}. При решении различных задач различные переменные будут объявляться входными

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

315

b=(на С вычислить переменные v1, ..., vm+n) вхвых x1, ...,

xm+n;.

7.2.5.Проблема компиляции параллельной программы

Конструирование ПП на вычислительных моделях состоит из построения (V,W)-плана Т (выбор алгоритма) и записи на некотором алгоритмическом языке ПП ПT, реализующей Т

(компиляция ПП).

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

(V,W)-планы, достигал экстремума на ПT. Лишь для некоторых простых функционалов Ф (например, глубина термов (V,W)-

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

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

Кроме того, для оптимального решения сформулированной на ПВМ задачи при различных входных данных (значениях входных переменных) в общем случае необходимо использовать

316

различные алгоритмы Т и реализующие их ПП (имеется в виду,

что для разных входных данных функционал Ф достигает

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

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

(тестовое испытание ПП).

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

317