malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

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

пример 1: (z, у, x1, ..., xm: real;

операция a in x1, …, xm out z;

операция b1 in у out x1, ..., xm;

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

операция bn in у out x1, ..., xm;);.

Здесь m и n — натуральные числа, многоточия понимаются

обычным образом. Если V={у}, W={z}, то TVW содержит nm

термов. Понятно, что построение TVW быстро становится нецелесообразным при росте n и m. Поэтому следует строить и

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

параграфе 7.2.2, описан алгоритм планирования, который удаляет из таблиц ТХ и ОП все те переменные и операции, которые не

используются ни в каком терме из TVW , а также приведен алгоритм выбора, предназначенный для построения (V,W)-плана.

Таким образом, после планирования в ТХ и ОП остается описание ПВМ, каждая переменная и операция которой используются хотя

бы в одном терме из TVW .

На последних двух этапах конструируется ПП решения

278

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

реализующей Т. Множество термов TVW определяет множество

TVW всех (V,W)-планов, каждому (V,W)-плану R TVW

соответствует множество ПТ всех тех ПП, которые реализуют Т.

На рис. 7.15 показана ПВМ, если V={z1,z2}, a W={x}, то

множество TVW ={a(b(z1), b(z1)), a(b(z1), c(z2))}, множество

TVW={a(b(z1), b(z1))}, {a(b(z1), c(z2))}}, a (V,W)-план {a(b(z1), c(z2))} реализует каждая из трех следующих программ:

1)begin y1:=b(z1); y2:=c(z2); x:=a(y1,y2) end;

2)begin y2:=c(z2); y1:=b(z1); x:=a(y1,y2) end;

3)begin fork y1:=b(z1); y2:=c(z2) join; x:=a(y1,y2) end;.

x

a

y 1y 2

Рис. 7.15

Здесь и везде далее имеется в виду, что операции a при интерпретации сопоставляется функция fa=I(а), которая может

279

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

при задании ПП для единообразия используется запись вида

у1=a(z1), которая обозначает обращение к moda с входной переменной z1, для вычисления значения выходной переменной

у1, значения других выходных переменных не

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

означает, что для выполнения модуля moda в мультикомпьютере есть ресурсы.

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

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

Условной операции а при интерпретации сопоставляется функция fa=I(a), которая может быть вычислена условной процедурой вида: if qa then moda, модуль moda вычисляет функцию fa в области истинности предиката qa. Понятно, что если для вычисления функции fa полезно использовать, к примеру, три разных модуля, то в ПВМ появляются три разные условные операции, которым сопоставляется при интерпретации одна и та же функция fa, но вычисляется она разными условными

280

процедурами. Наличие в ПВМ условных операций должно учитываться, конечно же, при построении плана вычислений.

Чтобы избежать двусмысленности там, где это может случиться,

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

7.2.2.Планирование алгоритма

Разработано много различных алгоритмов планирования. В

параграфе рассматривается хорошо реализуемый алгоритм,

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

так как на его основе строится еще ряд алгоритмов планирования на вычислительных моделях.

Пусть задана ПВМ С=(X,F), которая после трансляции представлена в виде двух таблиц ТХ и ОП. Каждая строка таблицы ТХ имеет вид (х,А(х),соmр(x)), а таблицы ОП - (a,in(a),out(a)), хÎX, aÎF, comp(x)={aÎF xÎout(a)},

A(x)={aÎF xÎin(a)}.

Чтобы не делать далее несущественных оговорок,

предполагается, что in(a)¹Æ для любых aÎF. Алгоритм планирования состоит из двух частей: восходящей и нисходящей.

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

281

ТV=T(V,F).

Обозначим V0=V, тогда

F0={a F in(a) V0}= {a A(x) in(a) V0}

x V 0

содержит все операции ПВМ такие, что in(a) V0. Далее формируется множество V1={х Х х out(а) a F0} V0, на

основе V1 строится множество

F1= {a А(х) in(a) V1}

xV 1 \ V 0

ит. д. до тех пор, пока при некотором целом положительном k не окажется, что Fk=. На этом завершается восходящая часть алгоритма планирования. Множества Vi и FI, i=0,...,k, содержат все переменные и операции, используемые в термах из

множества ТV.

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

используемых в термах из TVW . Обозначим F*= Fi, и

i = 0

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

282

Построение множеств GI и Hi завершается, когда при некотором целом положительном r окажется Gr = . Множества GI и Hi, i = 1, ..., r, содержат все переменные и операции, используемые в

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

На рис. 7.16 показаны множества Fi и Vi, образовавшиеся в результате восходящей части алгоритма планирования на ПВМ

(рис. 7.17) при V={ x1 , x2 }, W={ x10 }, а на рис.7.18 - множества GI

и Hi, сформированные в нисходящей части алгоритма планирования. После завершения планирования в таблицах ТХ и

ОП остаются лишь переменные и операции из множеств Hi и GI,

остальные удаляются (рис. 7.19).

283

284

Рис.7.19.

Таким образом, результатом планирования является ПВМ,

оставшаяся от С после удаления из ТХ и ОП “ лишних” переменных и операций. Множество TVW не строится,

подходящий в некотором смысле (V,W)-план Т строится в каждом конкретном случае процедурой выбора алгоритма.

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

285

такие новые переменные, что станут вычислимыми все переменные из W. Для уменьшения затрат на расширение V

может быть использован алгоритм планирования. Для этого необходимо выполнить его нисходящую часть из множества переменных W'=W\Vk с использованием всех операций из F. Все переменные из построенных при этом множеств Hi, i=1, 2, ..., r,

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

Нетрудно также построить человеко-машинные алгоритмы,

помогающие сделать такой выбор.

Из описания алгоритма следует, что проверка условия in(a)ÍVi делается не более одного раза для каждой входной дуги произвольно взятой операции а, а проверка условия out(a)ÇHi-

1¹Æ - не более одного раза для каждой выходной дуги а.

Понятно, что алгоритм планирования имеет линейную относительно числа дуг в графическом представлении ПВМ временную сложность, если в качестве элементарных шагов алгоритма взять проверки in(a)ÍVi и out(a)ÇHi-1¹Æ.

Алгоритм эффективно реализуется. При реализации алгоритма переменные и операции в ТХ и ОП могут кодироваться целыми положительными числами. Например, если в ходе трансляции в тексте встретилось j переменных, то очередная переменная получает номер j+1. Таким образом, п-я строка таблицы ТХ содержит описание n-й переменной, а m-я строка

286

таблицы ОП – описание m-й операции. Для представления всевозможных множеств — А(х), in(a), Vi, Fi и т. д., можно использовать битовые шкалы. Шкала Vi, к примеру, содержит в k-

й позиции единицу, если переменная номер k принадлежит Vi.

Применение битовых шкал сводит проверку условий in(a)ÍVi и out(а)ÇHi-1¹Æ к двум логическим операциям.

Как можно было бы определить вычисления на вычислительной модели? Самый естественный способ следующий. Вначале вносятся значения во все переменные из V.

Затем выполняются все операции из F1 (выполняются модули moda для всех aÎF1), при этом (в соответствии с определением интерпретации) вычисляются значения переменных из V1\V0.

Далее выполняются все операции из F2 и т.д. до Fk. Ясно, что такие вычисления могут быть весьма неэффективными,

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

которые определены моделью - и самые хорошие и самые плохие.

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

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

а)удалить операции и переменные, не участвующие в вычислении W,

и

287