malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

fa модуль modа. Такая фиксация уменьшает мобильность

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

Для обеспечения мобильности ПП в этом случае надо уметь либо автоматически преобразовывать modа, что далеко не всегда можно сделать, либо использовать другой модуль вместо modа. В

общем случае необходимо синтезировать подходящий алгоритм для вычисления fa и реализующий его modа.

Нужно уметь также изменять интерпретацию некоторых операций. Пусть, например, на ПВМ С определен (V,W)-план Т,

задающий алгоритм вычисления определенного интеграла с подынтегральной функцией fa =I(а), операция а используется в Т.

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

Для решения указанных задач используется понятие

298

структурной интерпретации ПВМ. Пусть G — конечное множество ПВМ, в каждой ПВМ В=(XB,FB), В G, существует

(VB,WB)-план ТB. Структурной интерпретацией ПВМ С=(XC,FC)

называется функция SI, которая сопоставляет:

1)каждой операции b, b FC, − вычислительную модель

В=SI(b), В G;

2)каждой переменной x in(b) − переменную v=SI(x), v VB;

каждой переменной у out(b) − переменную w=SI(y), w WB,

и, кроме того,

u (u ((VB (WB)→x(x in(a) out(a) u=SI(x))).

Операция b называется структурированной операцией и

говорится, что операция b раскрывается ПВМ В. Далее предполагается также, что в В нет операции b и при раскрытии структурированных операций В никогда не встретится операция b. Таким образом, все ПВМ из G должны быть описаны до момента определения структурированной операции b. Здесь это чисто техническое ограничение, введенное для упрощения описаний1. В отличие от структурной интерпретации SI

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

1 Если снять это ограничение, то будет определен класс рекурсивных ВМ [5]. В контексте текущего рассмотрения они мало интересны и потому не обсуждаются.

299

естественным образом.

Пусть заданы интерпретация IB ПВМ В в области интерпретации DB и интерпретация IC ПВМ С в области интерпретации DC, причем функция fb =IC(b) вычисляется алгоритмом, заданным (VB,WB)-планом ТB. Если t=b(ti,...,tn) —

некоторый терм из множества TVW , построенного на ПВМ С,

in(b)={x1,...,xn}, out(b)={y1,...,ym}, то при вычислении dyi =val(t,yi),

Для корректности этого доопределения необходимо, чтобы выполнялось условие

Интерпретации IC и IB называются согласованными. Таким образом, структурная интерпретация SI(b)=В задает внутреннюю структуру операции b, а в качестве алгоритма вычисления функции fb=IC(b) может быть взят любой (VB,WB)-план,

построенный па ПВМ В.

Раскрытием b называется построение множества ТB. При раскрытии b могут выполняться оптимизирующие преобразования структурированной операции. Рассмотрим

300

несколько таких преобразований. Введенные в начале параграфа обозначения сохраняют свой смысл. Предполагается также, что ПВМ С=(XC,FC) и В=(ХB,FB) представлены таблицами ТХC и ОПС,

ТХB и ОПB соответственно и, кроме того, операция b

используется в некотором (V,W)-плане Т, построенном на С. При всех преобразованиях структурная интерпретация переменных из

XC не изменяется.

Открытая подстановка. Строится ПВМ С1=(X1,F1),

ТХC1=ТХCÅТХB, значок Å обозначает объединение таблиц, при этом если и=SI(z), и uÎVBÈWB,

ZÎ(in(b)Èout(b)), то переменная и переименовывается и получает имя z везде, где и встречается в ТХC1 и ОПC1. Строка и из ТХC1

вычеркивается, а в строке z множество

A(z)={аÎ(FCÈFB)½zÎin(a)}, a comp(z)={аÎ(FCÈFB)½zÎout(a)}.

Строка b также вычеркивается из ОПC1, а операция b удаляется из всех множеств. Предполагается, что в С и в B нет одноименных переменных и операций. Такое раскрытие аналогично открытой подстановке макроопределения вместо макровызова. При планировании на C1 будет построено и множество TB.

Раскрытие структурированной операции b открытой подстановкой возможно не всегда, в частности, тогда, когда функция fa должна в синтезированной ПП вычисляться процедурой. В этом случае планирование на ПВМ В (построение

TB) ведется отдельно от планирования на ПВМ С.

301

Рис. 7.21.

302

a

x1

Рис. 7.22.

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

выполняется строгое включение out(b) out(b). Множество переменных ПВМ В, которые соответствуют в структурной интерпретации переменным из out(b), обозначим WB. ТОгда из

ТХB и ОПB могут быть в нисходящей части алгоритма планирования на В удалены переменные и операции, которые не используются в термах, вычисляющих WB, при этом вместо VB

303

может быть взято меньшее в общем случае множество VB VB.

Такая чистка b делается описанным алгоритмом планирования и может существенно улучшить ПП, реализующую Т, так как из термов Т можно удалить подтермы, вычисляющие переменные из множества in(b)\in(b) (через in(b) обозначено множество тех переменных из in(b), которым в структурной интерпретации соответствуют переменные из VB). Кроме того, в ПП вместо процедуры, реализующей (VB,WB)-план TB, может быть использована процедура, реализующая (VB,WB)-план TB для которого справедливо строгое включение TB TB.

На рис. 7.21 приведена ПВМ В, раскрывающая структурированную операцию b ПВМ, показанной на рис. 7.17,

терм t на рис. 7.22 вычисляет переменную x10 из переменных {x1,

х2}. Так как в t для вычисления x10 используется из двух выходных переменных операции b только одна переменная x8, то при раскрытии b строятся только термы, вычисляющие y8=SI(x8),

вданном случае построится терм y5→g2→y3→g3→y8 и,

следовательно, переменная y6 не нужна для вычисления y8. После

чистки операции b образуется операция b', in(b')={х5}, out(b')={x8}, и в t становится ненужным подтерм x2→f→x6. В

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

чем t, термом x1→a→x3→c→x5→b′→x8→d→x10.

Выделение подопераций. В ПП, реализующей (V,W)-план Т, нет

в общем случае необходимости ожидать вычисления значений

304

всех переменных из in(b) для того, чтобы начать выполнение modb, реализующего (VB,WB)-план ТB. Выполнение modb может начаться, когда известны значения лишь части переменных из in(b) (смешанные или частичные вычисления). Это можно делать динамически, но здесь рассматриваются только статические методы конструирования программ и потому частичность вычислений выливается в изменений структуры ВМ.

Для конструирования такого modb используется прием выделения подопераций, когда b разделяется на несколько структурированных операций. Выделение подопераций производится в процессе планирования на ПЭВМ C.

Алгоритм планирования модифицируется следующим образом. Всякий раз, когда завершено построение множества VI, i=0, ..., k, в восходящей части алгоритма планирования строится множество V bi =ViÇin(b). Если оно пусто, то планирование на С продолжается дальше, если же нет — планирование на С

прерывается, образуется множество Vb1, 0 = SI(х), и

x Vb1

начинается планирование на В (восходящая часть алгоритма), при котором строятся множества переменных V bi , j1 и операций

F bi , ji , j1=0, ..., k1; k1 таково, что F b1 , k1 =Æ. В этот момент планирование на В завершается, образуется структурированная операция b1, SI(b1)=В1, где В1 — есть ПВМ, определяемая всеми

305

Множество in(b1) содержит все переменные из V b1 , a out(b1) —

все переменные уÎXC такие, что SI(у)ÎW b1 , где

b1 называется подоперацией структурированной операции b.

Операция b1 добавляется в FC и FI, переменные out(b1) — в ХC и в

(при необходимости переменные из W b1 могут быть переименованы).

Если zÎWb, то считается, что SI(z)=z. После этого возобновляется планирование на С с прерванного места. Если

прервать планирование на С; образовать множество переменных

306

построить множества Vb2 , j2 и Fb2 , j2 , j=0, ..., k2, Fb2 ,k2 = ;

образовать подоперацию b2, SI(b2)=В2, где ПВМ В2 определена

После завершения восходящей части алгоритма планирования на

С из ТХC и ОПC удаляется b. В результате после планирования в таблицах ТХC и ОПC появляются подоперации структурированной операции b, если, конечно, они не будут удалены в нисходящей части алгоритма планирования на С. Для всех оставшихся в таблицах структурированных операций после завершения планирования (когда станет известно, какие из их выходных переменных используются в термах из TVW ) проводится чистка.

307