Оптимизация последовательных программ



Скачать 243.09 Kb.
Дата20.05.2015
Размер243.09 Kb.
ТипДокументы



И.Л. Артемьева, М.А. Князева, О.А. Купневич


МОДЕЛЬ ОНТОЛОГИИ ПРЕДМЕТНОЙ ОБЛАСТИ "ОПТИМИЗАЦИЯ ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ". Ч. 3. Примеры описания некоторых оптимизирующих преобразований
Описываются контекстные условия и правила трансформации для некоторых классических оптимизирующих преобразований последовательных программ как обогащение модели онтологии.
ВВЕДЕНИЕ

В работах [1,2] описана модель онтологии предметной области "Оптимизация последовательных программ", в ней определены термины для описания объекта оптимизации и термины для описания процесса оптимизации.

Целью данной работы является описание фрагмента второй части базы знаний данной предметной области, а именно определение настройки модели процесса оптимизации на модель объекта, задаваемую [3], а также примеров определения некоторых классических оптимизирующих преобразований.

При описании оптимизирующих преобразований используется формализм, определенный в работах [5,6].


1. ОПРЕДЕЛЕНИЕ ОПТИМИЗИРУЮЩЕГО ПРЕОБРАЗО-ВАНИЯ "ЗАМЕНА ПЕРЕМЕННЫХ ИХ ЗНАЧЕНИЯМИ"
Описание ОП: все вхождения некоторой переменной заменяются ее значением, если оно известно во время компиляции

Пример:

Было до выполнения оптимизирующего преобразования

n=64

for i=1 to n do



k[i]=i

end


стало после выполнения оптимизирующего преобразования

for i=1 to 64 do

k[i]=i
Неформальное описание контекстного условия: если переменная инициализируется выражением-правой частью некоторого оператора присваивания, причем значение выражения известно до выполнения присваивания, и эта переменная нигде больше не получает значения и не используется, то все вхождения этой переменной (кроме вхождения в этот оператор присваивания), заменяются на результат вычисления значения

выражения.

Данное оптимизирующее преобразование применяется к участку экономии, обладающему следующими свойствами (см. также рис. 1):

- участок экономии содержит оператор присваивания (обозначим его через Р), левой частью которого является переменная (обозначим ее через A), а правая часть (обозначим ее через F) может быть вычислена на этапе трансляции; переменная А входит как фрагмент в простую часть участка экономии;

- переменная A получает значение только в данном операторе присваивания и нигде больше, т.е. результатное множество любого фрагмента K, не вложенного в P, не содержит переменную A;

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






Рис. 1. Структура участка экономии для оптимизирующего преобразования "Замена переменных их значениями"


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

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

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

в базе знаний определено только одно оптимизирующее преобразование – замена переменных их значениями


2. Число простых параметров ОП ((v: {замена переменных их значениями }) / (v = замена переменных их значениями 3)/)

у данного преобразования простая часть участка экономии содержит три фрагмента


3. Число множественных параметров ОП ((v: {замена переменных их значениями}) / (v = замена переменных их значениями 1)/)

у данного преобразования каждый кортеж множественной части участка экономии содержит 1 фрагмент


4. Классы простых параметров ОП ((v: {замена переменных их значениями}) / (v = замена переменных их значениями <{Dass}, {Dexpr}, {Dexpr}>)/)

первый фрагмент простой части участка экономии является оператором присваивания, а второй и третий – выражениями


5. Классы множественных параметров ОП ((v: { замена переменных их значениями }) / (v = замена переменных их значениями {Dexpr}>)/)

фрагмент множественной части участка экономии является - выражением


6. Формула КУ ((v1: {замена переменных их значениями}) / (v1 = замена переменных их значениями ((v: {(v': ( Шаги истории, Кортежи, {} Кортежи)) (2, v') Кортежи значений((1,v')) & (3, v') Кортежи значений((1, v'))}) Свойства участка экономии(замена переменных их значениями, v) &
оптимизирующее преобразование "замена переменных их значениями" применимо к участку экономии, обладающему следующими свойствами:

- простая часть участка экономии состоит из трех простых фрагментов, причем первый фрагмент P является оператором присваивания, а второй фрагмент A – выражением-левой частью оператора P, а F – выражением-правой частью оператора P;

- каждый элемент множественной части состоит из фрагмента-выражения
(let (J = (1, v)), (P = (1, (2, v))), (A = (2, (2,v))), (F = (3, (2,v))) A= LvalueExpr(J, P) & F = Expr(J, P) & Left(J, A) = Var & Eval(J,F)<> Null &
выражение A является левой частью оператора присваивания P, причем A является переменной. а правая часть оператора P вычислима на этапе компиляции
(& (D: (3, v)) Left(J, D ) = Var & LeftExpr(J, D ) = LeftExpr(J, A) & Not(<(J, P, D )))
каждый элемент множественной части обладает следующими свойствами:

- он является выражением, которое не входит в оператор P, а его левая часть является переменной А.



& (&(K:{(v: Адреса фрагментов(J)) NOT(<(P, K))) R(J, K) Id(J, LeftExpr(A))= )))))/)
результатное множество любого фрагмента K, не входящего в состав оператора присваивания, не содержит переменную А
7. Число элементов простой части ОУЭ ((v: {замена переменных их значениями }) / (v = замена переменных их значениями 0)/)
у данного преобразования кортеж фрагментов простой части оптимизированного участка экономии (ОУЭ) имеет нулевую длину
8. Классы элементов простой части ОУЭ ((v: {замена переменных их значениями }) / (v = замена переменных их значениями <>)/)

первый фрагмент простой части оптимизированного участка экономии является оператором присваивания, а второй и третий – выражениями


9. Число элементов множественной части ОУЭ ((v: {замена переменных их значениями}) / (v = замена переменных их значениями 1)/)
у данного преобразования каждый кортеж множественной части оптимизированного участка экономии содержит один фрагмент
10. Классы элементов множественной части ОУЭ ((v: {замена переменных их значениями}) / (v = замена переменных их значениями {Dexpr}>)/)

первый фрагмент множественной части оптимизированного участка экономии является выражением


11. Параметры с одинаковым контекстом ((v1: {замена переменных их значениями}) / (v1 = замена переменных их значениями {<4, 1>})

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


12. Формула трансформации ((v1: {замена переменных их значениями }) / (v1 = замена переменных их значениями ((v: {(v': ( Шаги истории, ( Кортежи, {}Кортежи), ( Кортежи, {}Кортежи)) (1, (2, v')) Кортежи значений((1, v')) & (2, (2, v')) Кортежи значений((1, v')) & (1, (3, v')) Кортежи значений((1, v') + 1) & (2, (3, v')) Кортежи значений((1, v') + 1)}) Свойства оптимизированного участка экономии(замена переменных их значениями, v) &

(let (J = (1,v)), (S = (1, (3, v))), (P = (1, (1, (2, v))))



введем обозначения: J – номер шага истории, S – простая часть оптимизированного участка экономии, P - первый простой фрагмент участка экономии



S = <> &

простая часть оптимизированного участка экономии является пустым кортежем





(&(Q1: (2, (3, v)))) Left(J+1, Q1) Consts(J+1) & Name(LeftExpr(J+1, Q1)) = Eval(J, Expr(J, P)) & LeftExpr(J+1, Q1) Новые идентификаторы(J, Consts) &

а каждый элемент Q1 каждой множественной части ОУЭ является выражением, таким, что его левая часть является новым идентификатором константы, значение которой равно значению правой части оператора P из участка экономии;


13. Характеристическая функция ((v1: {замена переменных их значениями }) / (v1 = замена переменных их значениями ( (v: {(v': ( Шаги истории, Кортежи, {} Кортежи)) <(2, v), (3, v)> Участки экономии((1,v), замена переменных их значениями)}) Level((1,v), LeftExpr((1,v), (1, (2, v))))


характеристика УЭ вычисляется как уровень вложенности оператора присваивания P
14. Стратегия ОП ((v1: { замена переменных их значениями })
/ (v1 = замена переменных их значениями ((v: {(v': ( Шаги истории, {} R)) (2, v') = {(v": Участки экономии(замена переменных их значениями, (1, v'))) Характеристическая функция(замена переменных их значениями)((1, v'), (1, v"), (2, v"))})}) Inf((1,v)))/)

стратегия ОП заключается в выборе наименее вложенного участка экономии


  1. ОПРЕДЕЛЕНИЕ ОПТИМИЗИРУЮЩЕГО ПРЕОБРАЗО-ВАНИЯ "ВЫНОС ИНВАРИАНТНОГО ОПЕРАТОРА ИЗ ЦИКЛА ВПЕРЕД"


Описание ОП: операторы, не зависящие от переменной цикла For, и не влияющие на остальное тело цикла, могут быть вынесены из него.

Пример:

Было до выполнения оптимизирующего преобразования

for i=1 to n do

b=k+c[n]

a[i]=a[i]+b

end


стало после выполнения оптимизирующего преобразования

b=k+c[n]

for i=1 to n do

a[i]=a[i]+b

end

Неформальное описание контекстного условия: если существует непрерывная непустая последовательность операторов, принадлежащих остову цикла For, и выполнены условия, сформулированные ниже, то эту последовательность можно вынести из цикла вперед.

Обозначим Z – последовательность операторов, X – цикл типа for, B – тело этого цикла, являющееся последовательностью операторов D, Y – последовательность операторов (кандидат на вынесение из цикла), Y1 и Y2 – последовательности операторов, предшествующие и следующие за Y, соответственно.


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

- заранее известно, что цикл выполнится хотя бы один раз

- последовательность операторов Z состоит из одного оператора цикла X;

- результат выносимого фрагмента Y не влияет на предшествующие ему операторы из последовательности Y1;

- результаты выносимого фрагмента Y и предшествующих операторов из последовательности Y1 не пересекаются;

- предшествующие операторы из последовательности Y1 не влияют на вычисление выносимого фрагмента У;

- результаты выносимого фрагмента Y не являются аргументами и результатами для последующих фрагментов из последовательности Y2 одновременно;

- результаты последующих фрагментов из последовательности Y2 не являются аргументами выносимого фрагмента Y;

- результаты выносимого фрагмента Y не являются аргументами заголовка цикла X;

- результаты заголовка цикла Х не являются аргументами выносимого фрагмента Y.


Таким образом, участок экономии имеет 7 простых параметров и ни одного множественного, типы элементов определяются приведенными выше условиями.

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

- последовательность ZQ состоит из двух подпоследовательностей, первая подпоследовательность – это последовательность Y из участка экономии, а вторая – оператор X;

- последовательность DQ (тело оптимизированного цикла) содержит две подпоследовательности Y1 и Y2, причем последовательность Y2 следует за последним фрагментом последовательности Y1.

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

Опишем значения параметров модели онтологии для данного оптимизирующего преобразования.


1. ОП {"вынос инвариантного оператора из цикла вперед"}
в базе знаний определено только одно оптимизирующее преобразование – вынос инвариантного оператора из цикла вперед
2. Число простых параметров ОП ((v: {вынос инвариантного оператора из цикла вперед}) / (v = вынос инвариантного оператора из цикла вперед 7)/)

у данного преобразования простая часть участка экономии содержит 7 фрагментов


3. Классы простых параметров ОП ((v: {вынос инвариантного оператора из цикла вперед}) / (v = вынос инвариантного оператора из цикла вперед <{DSCH}, {Dfor}, {Dbody}, {DSCH}, {DSCH}, {DSCH}, {DSCH}>)/)

первый, четвертый, пятый, шестой и седьмой фрагменты простой части участка экономии являются последовательностью операторов, второй – оператором цикла for, а третий – телом цикла


4. Число множественных параметров ОП ((v: {вынос инвариантного оператора из цикла вперед}) / (v = вынос инвариантного оператора из цикла вперед 0)/)

у данного преобразования нет множественных параметров


5. Классы множественных параметров ОП ((v: {вынос инвариантного оператора из цикла вперед}) / (v = вынос инвариантного оператора из цикла вперед <>)/)

у данного преобразования нет множественных параметров


6. Формула КУ ((v1: {вынос инвариантного оператора из цикла вперед}) / (v1 = вынос инвариантного оператора из цикла вперед ((v: {(v': ( Шаги истории, Кортежи, {} Кортежи)) (2, v') Кортежи значений((1,v')) & (3, v') Кортежи значений((1, v'))}) Свойства участка экономии(вынос инвариантного оператора из цикла вперед, v) &
оптимизирующее преобразование "вынос инвариантного оператора из цикла вперед" применимо к участку экономии, обладающему следующими свойствами:

- простая часть участка экономии состоит из семи простых фрагментов;

- множественная часть пуста
(let (J = (1,v)), (Z = (1, (2, v))), (X = (2, (2,v))), (B = (3, (2, v))), (D = (4, (2, v))), (Y = (5, (2, v))), (Y1 = (6, (2, v))), (Y2 = (7, (2, v)))

обозначим: J – шаг истории, Z, X, B, D, Y, Y1, Y2 соответственно 1-7 простые параметры оптимизирующего преобразования



& Calc(Calc(Calc(Eval(J,Until(X)), -, Eval(J, For(X))), *, Eval(J, Step(X))), >=, 0) &
если значение выражения (until-for) * step >= 0, то цикл выполнится хотя бы один раз
Begin(J, Z) = X & End(J, Z) = X
последовательность операторов Z состоит из оператора цикла X
& IsLine(J, Y) & IsLine(J, Y1) & IsLine(J, Y2) & Begin(J, Y1) = Begin(J, D) & End(J, Y2) = End(J, D) & <(J, End(J, Y1), Begin(J, Y)) & <(J, End(J, Y), Begin(J, Y2)) & YNull
Y, Y1, Y2 образуют непрерывные последовательности фрагментов, причем начало последовательности Y1 совпадает с началом последовательности D, конец последовательности Y2 совпадает с концом последовательности D, первый оператор последовательности Y следует за последним оператором последовательности Y1, первый оператор последовательности Y2 следует за последним оператором последовательности Y, последовательность Y не является пустой
& D = Sch(J, B) & B=Body(J, X)
тело цикла B состоит из последовательности операторов, входящих в последовательность D
& [R(J, Y) A(J, Y1) = ] & [R(J, Y) R(J, Y1) = ] & [R(J, Y1) A(J, Y) = ] & [R(J, Y) RR(J, Y2) A(J, Y2)= ] & [R(J, Y2) A(J, Y) = ] & [R(J, Y) (A(J, For(J, X)) A(J, Until(J, X)) A(J, Step(J, X)))= ] & [A(J, Y) (R(J, For(J, X)) R(J, Until(J, X)) R(J, Step(J, X)))= ] ))/)
результат выносимого фрагмента Y не влияет на предшествующие ему операторы из последовательности Y1; результаты выносимого фрагмента Y и предшествующих операторов из последовательности Y1 не пересекаются; предшествующие операторы из последовательности Y1 не влияют на вычисление выносимого фрагмента У; результаты выносимого фрагмента Y не являются аргументами и результатами для последующих фрагментов из последовательности Y2 одновременно; результаты последующих фрагментов из последовательности Y2 не являются аргументами выносимого фрагмента Y; результаты выносимого фрагмента Y не являются аргументами заголовка цикла X; результаты заголовка цикла Х не являются аргументами выносимого фрагмента Y
7. Число простых параметров оптимизированного УЭ ((v: {вынос инвариантного оператора из цикла вперед}) / (v = вынос инвариантного оператора из цикла вперед 7)/)

простая часть оптимизированного участка экономии состоит из 7 фрагментов


8. Классы элементов простой части ОУЭ ((v: {вынос инвариантного оператора из цикла вперед}) / (v = вынос инвариантного оператора из цикла вперед <{DSCH}, {DSCH}, {Dfor}, {Dbody}, {DSCH}, {DSCH},{DSCH}>)/)

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

9. Число множественных параметров оптимизированного УЭ ((v: {вынос инвариантного оператора из цикла вперед}) / (v = вынос инвариантного оператора из цикла вперед 0)/)
у данного преобразования множественная часть оптимизированного участка экономии пуста
10. Классы элементов множественной части ОУЭ ((v: {вынос инвариантного оператора из цикла вперед}) / (v = вынос инвариантного оператора из цикла вперед <>)/)

у данного преобразования множественная часть оптимизированного участка экономии пуста


11. Параметры с одинаковым контекстом) ((v1: {вынос инвариантного оператора из цикла вперед}) / (v1 = вынос инвариантного оператора из цикла вперед {<1, 1>})

для данного преобразования контексты сохраняются у первого простого параметра


12. Формула трансформации ((v1: {вынос инвариантного оператора из цикла вперед}) / (v1 = вынос инвариантного оператора из цикла вперед ((v: {(v': ( Шаги истории, ( Кортежи, {}Кортежи), ( Кортежи, {}Кортежи)) (1, (2, v')) Кортежи значений((1, v')) & (2, (2, v')) Кортежи значений((1, v')) & (1, (3, v')) Кортежи значений((1, v') + 1) & (2, (3, v')) Кортежи значений((1, v') + 1)}) Свойства оптимизированного участка экономии(вынос инвариантного оператора из цикла вперед, v) &

(let (J = (1,v)), (Z = (1, (1, (2, v)))), (X = (2, (1, (2,v)))), (B = (3, (1, (2, v)))), (D = (4, (1, (2, v)))), (Y = (5, (1, (2, v)))), (Y1 = (6, (1, (2, v)))), (Y2 = (7, (1, (2, v)))), (ZQ = (1, (1, (3, v)))), (YQ = (2, (1, (3, v)))), (XQ = (3, (1, (3, v)))), (BQ = (4, (1, (3, v)))), (DQ = (5, (1, (3, v)))), (Y1Q = (6, (1, (3, v)))), (Y2Q = (7, (1, (3, v))))

обозначим: J – шаг истории, Z, X, B, D, Y, Y1, Y2 соответственно 1-7 простые параметры оптимизирующего преобразования; ZQ, YQ, XQ, BQ, DQ, Y1Q, Y2Q соответственно 1-7 элементы простой части оптимизированного участка экономии




& Begin(J+1, ZQ) = Begin(J+1, YQ)
первым элементом последовательности DQ является первый элемент последовательности YQ
& <( J+1, End(J+1, YQ), XQ)
оператор цикла следует за последним оператором последовательности YQ
& End(J+1, ZQ) = XQ
последним оператором последовательности ZQ является оператор цикла XQ
& DQ = Sch(J+1, BQ) & BQ = Body(J+1, XQ)
тело цикла BQ состоит из последовательности операторов, входящих в последовательность DQ
& Begin(J+1, Y1) = Begin(J+1, DQ) & End(J+1, Y2Q) = End(J+1, DQ) & <( J+1, End(J+1, Y1Q), Begin(J+1, Y2Q))
начало последовательности DQ совпадает с началом последовательности Y1Q, конец последовательности DQ совпадает с концом последовательности Y2Q; первый оператор последовательности Y2Q следует за последним оператором последовательности Y1Q
& XQ = X
заголовок цикла XQ совпадает с заголовком цикла X
& (J, Y, J+1, YQ) & (J, Y1, J+1, Y1Q) & (J, Y2, J+1, Y2Q) ))/)
последовательности Y и YQ состоят из одних и тех же операторов; последовательности Y1 и Y1Q состоят из одних и тех же операторов; последовательности Y2 и Y2Q состоят из одних и тех же операторов
13. Характеристическая функция ((v1: {вынос инвариантного оператора из цикла вперед}) / (v1 = вынос инвариантного оператора из цикла вперед ((v: {(v': ( Шаги истории, Кортежи, {}Кортежи)) <(2, v), (3, v)> Участки экономии((1,v))})
(let (J = (1,v)), (Z = (1, (2, v))) Level(J, LeftExpr(J, Z))

характеристика участка экономии вычисляется как уровень вложенности фрагмента Z


14. Стратегия ОП =((v1: {вынос инвариантного оператора из цикла вперед}) / (v1 = вынос инвариантного оператора из цикла вперед ((v: {(v': ( Шаги истории, {} R)) (2, v') = {(v": Участки экономии(вынос инвариантного оператора из цикла вперед, (1, v'))) Характеристическая функция(вынос инвариантного оператора из цикла вперед)((1, v'), (1, v"), (2, v"))})}) Sup((2,v)))/)
стратегия ОП заключается в выборе наиболее вложенного участка экономии
3 ОПРЕДЕЛЕНИЕ ОПТИМИЗИРУЮЩЕГО ПРЕОБРАЗО-ВАНИЯ "ЭКОНОМИЯ ОБЩИХ ПОДВЫРАЖЕНИЙ"
Описание ОП: в двух операторах присваивания семантически эквивалентные подвыражения заменяются на новую переменную, добавляется новый оператор присваивания, предшествующий обоим операторам присваивания, левой частью которого является эта новая переменная, а правой частью – найденное общее подвыражение.

Пример:

было до выполнения оптимизирующего преобразования

X1=A+B*D+C*K

X2=C*B*D-5

стало после выполнения оптимизирующего преобразования

T=B*D


X1=A+T+C*K

X2=T*D-5



Неформальное описание контекстного условия. Данное оптимизирующее преобразование применяется к участку экономии, состоящему из следующих фрагментов (см. также рис.3):

- Z - последовательность, на концах которой стоят операторы присваивания Y1 и Y3, между которыми есть последовательность Y2 (которая может быть пустой);

- в правые части обоих операторов присваивания Y1 и Y3 входят подвыражения Z2 и Q2 (соответственно), которые являются подобными друг другу;

- Z1 – последовательность подвыражений, входящих в правую часть оператора Y1, состоящая из подвыражений, предшествующих Z2; эта последовательность может быть пустой;

- Z3 - последовательность подвыражений, входящих в правую часть оператора Y1, состоящая из подвыражений, следующих за Z2.

- Q1 – последовательность подвыражений, входящих в правую часть оператора Y3, состоящая из подвыражений, предшествующих Q2; эта последовательность может быть пустой;

- Q3 - последовательность подвыражений, входящих в правую часть оператора Y3, состоящая из подвыражений, следующих за Q2;

- результат Z2 не должен влиять на вычисление Z1;

- результаты Z3,Y2, Q1 не должны влиять на вычисление Q2;

- результат Z1 не должен влиять на вычисление Z2;

- результат Z1 не должен пересекаться с результатом Z2;

- результаты Z3, Y2, Q1 не должны пересекаться с результатом Z2.

Таким образом, данное оптимизирующее преобразование имеет 10 простых параметров и ни одного множественного.

Оптимизированный участок экономии имеет следующий вид: перед последовательностью Y1 добавлен новый оператор присваивания W, левой частью W1 которого является новая переменная, тип которой совпадает с типом выражения Z2, а правой части W2 является выражение Z2. В операторах Y1 и Y3 все вхождения фрагментов Y2 и Q2 заменены на новую переменную. Таким образом, простая часть оптимизированного участка экономии состоит из 13 фрагментов, а множественная часть пуста.





Рис. 3. Структура участка экономии для оптимизирующего преобразования "Экономия общих подвыражений"


Определим значения параметров модели онтологии.
1. ОП {экономия общих подвыражений}
в базе знаний определено только одно оптимизирующее преобразование – экономия общих подвыражений
2. Число простых параметров ОП ((v: {экономия общих подвыражений}) / (v = экономия общих подвыражений 10)/)

у данного преобразования 10 простых параметра участка экономии


3. Число множественных параметров ОП ((v: {экономия общих подвыражений}) / (v = экономия общих подвыражений 0)/)

у данного преобразования нет множественных параметров


4. Классы простых параметров ОП ((v: {экономия общих подвыражений}) / (v = экономия общих подвыражений <{Dsch}, {Dass}, {Dsch}, {Dass}, {Dsch}, {Dexpr}, {Dsch}, {Dsch}, {Dexpr}, {Dsch}>)/)

первый и третий фрагменты простой части участка экономии являются последовательностью операторов, второй и четвертый – операторами присваивания, пятый и седьмой – последовательностями подвыражений, шестой – выражением, восьмой и десятый – последовательностями подвыражений, а девятый - выражением


5. Классы множественных параметров ОП ((v: {экономия общих подвыражений}) / (v = экономия общих подвыражений <>)/)

у данного преобразования нет множественных параметров


6. Формула КУ ((v1: {экономия общих подвыражений}) /(v1 = экономия общих подвыражений ((v: {(v': ( Шаги истории, Кортежи, {} Кортежи)) (2, v) Кортежи значений((1,v)) & (3, v) Кортежи значений((1, v))}) Свойства участка экономии(экономия общих подвыражений, (1, v)) & (let (J = (1,v)), (Z = (1, (2, v))), (Y1 = (2, (2,v))), (Y2 = (3, (2, v))), (Y3 = (4, (2, v))), (Z1 = (5, (2, v))), (Z2 = (6, (2, v))), (Z3 = (7, (2, v))), (Q1 = (8, (2, v))), (Q2 = (9, (2, v))), (Q3 = (10, (2, v)))


обозначим: J – номер шага истории, Z, Y1, Y2, Y3, Z1, Z2, Z3, Q1, Q2, Q3 соответственно 1-10 простые параметры оптимизирующего преобразования


IsLine(J, Z) & Y1 = Begin(J, Z) & Y3 = End(J, Z) & <(J, Y1, Y2) & <(J, End(J, Y2), Y3)


Z является непрерывной последовательностью фрагментов, началом последовательности Z является оператор присваивания Y1, концом последовательности Z является оператор присваивания Y3, первый оператор последовательности Y2 следует за оператором присваивания Y1, последовательность Y2 следует за оператором присваивания Y1, оператор присваивания Y3 следует за последним оператором последовательности Y2,
& <( J, Expr(J, Y1), Z2) & Pred(J, Expr(J, Y1), Z2, Z1) & Posl(J, Expr(J, Y1), Z2, Z3)
Z2 входит в правую часть оператора присваивания Y1, Z1 лежит между началом Y1 и Z2, Z3 лежит между концом выражения Z2 и концом правой части оператора Y1,
& <( J, Expr(J, Y3), Q2) & Pred(J, Expr(J, Y3), Q2, Q1) & Posl(J, Expr(J, Y3), Q2, Q3)
Q2 входит в правую часть оператора присваивания Y3, Q1 лежит между началом Y3 и Q2, Q3 лежит между концом выражения Q2 и концом правой части оператора Y3,
& (J, Z2, J, Q2) &
выражения Z2 и Q2 подобны
[R(J, Z2) A(J, Z1)= ] & [(R(J, Z3) R(J, Y2) R(J, Q1) A(J, Q2)= ] & [R(J, Z1) A(J, Z2)= ] & [R(J, Z1) R(J, Z2)= ] & [(R(J, Z3) R(J, Y2) R(J, Q1) R(J, Q2)= ]
результат Z2 не должен влиять на вычисление Z1; результаты Z3,Y2, Q1 не должны влиять на вычисление Q2; результат Z1 не должен влиять на вычисление Z2; результат Z1 не должен пересекаться с результатом Z2; результаты Z3, Y2, Q1 не должны пересекаться с результатом Z2
7. Число простых параметров оптимизированного УЭ ((v: {экономия общих подвыражений}) / (v = экономия общих подвыражений 13)/)

простую часть оптимизированного участка экономии образуют 13 фрагментов


8. Число множественных параметров оптимизированного УЭ ((v: {экономия общих подвыражений}) / (v = экономия общих подвыражений 0)/)
множественная часть оптимизированного участка экономии пуста
9. Классы элементов простой части ОУЭ ((v: {экономия общих подвыражений}) / (v = экономия общих подвыражений <{Dsch}, {Dass}, {Dsch}, {Dass}, {Dsch}, {Dexpr}, {Dsch}, {Dsch}, {Dexpr}, {Dsch}, {Dass}, {Dexpr}, {Dexpr}>)/)

первый и третий фрагменты простой части оптимизированного участка экономии являются последовательностью операторов, второй и четвертый – операторами присваивания, пятый и седьмой – последовательностями подвыражений, шестой – выражением, восьмой и десятый – последовательностями подвыражений, девятый – выражением, одиннадцатый – оператором присваивания, двенадцатый и тринадцатый - выражениями


10. Классы элементов множественной части ОУЭ ((v: {экономия общих подвыражений}) / (v = экономия общих подвыражений <>)/)

множественная часть оптимизированного участка экономии пуста


11. Формула трансформации ((v1: {экономия общих подвыражений}) / (v1 = экономия общих подвыражений ((v: {(v': ( Шаги истории, ( Кортежи, {}Кортежи), ( Кортежи, {}Кортежи)) (2, v) Участки экономии((1,v)) & (1, (3, v)) Кортежи значений((1,v)+1) & (2, (3, v)) Кортежи значений((1,v)+1)}) Свойства оптимизированного участка экономии(экономия общих подвыражений, v) & (let (J = (1,v)), (Z = (1, (1, (2, v)))), (Y1 = (2, (1, (2,v)))), (Y2 = (3, (1, (2, v)))), (Y3 = (4, (1, (2, v)))), (Z1 = (5, (1, (2, v)))), (Z2 = (6, (1, (2, v)))), (Z3 = (7, (1, (2, v)))), (Q1 = (8, (1, (2, v)))), (Q2 = (9, (1, (2, v)))), (Q3 = (10, (1, (2, v)))), (ZQ = (1, (1, (3, v)))), (Y1Q = (2, (1, (3,v)))), (Y2Q = (3, (1, (3, v)))), (Y3Q = (4, (1, (3, v)))), (Z1Q = (5, (1, (3, v)))), (Z2Q = (6, (1, (3, v)))), (Z3Q = (7, (1, (3, v)))), (Q1Q = (8, (1, (3, v)))), (Q2Q = (9, (1, (3, v)))), (Q3Q = (10, (1, (3, v)))) (W = (11, (1, (3, v)))) (W1 = (12, (1, (3, v)))) (W2 = (13, (1, (3, v))))

обозначим: J – шаг истории, Z, Y1, Y2, Y3, Z1, Z2, Z3, Q1, Q2, Q3 соответственно 1-10 простые параметры оптимизирующего преобразования, ZQ, Y1Q, Y2Q, Y3Q, Z1Q, Z2Q, Z3Q, Q1Q, Q2Q, Q3Q, W, W1, W2 соответственно 1-13 элементы простой части оптимизированного участка экономии


IsLine(J+1, ZQ) & W = Begin(J+1, ZQ) & Y3Q = End(J+1, ZQ) & <(J+1, W, Y1Q) & <(J+1, Y1Q, Begin(J+1, Y2Q)) & <( J+1, End(J+1, Y2Q), Y3Q)
ZQ является линейной последовательностью, состоящей из оператора присваивания W, оператора присваивания Y1Q, последовательности Y2Q и оператора присваивания Y3Q
& <( J+1, Expr(J+1, Y1Q), Z2Q) & Pred(J+1, Expr(J+1, Y1Q), Z2Q, Z1Q) & Posl(J+1, Expr(J+1, Y1Q), Z2Q, Z3Q)
правая часть оператора присваивания Y2Q состоит из трех фрагментов Z1Q, Z2Q, Z3Q, причем Z1Q предшествует выражению Z2Q, а Z3Q следует за Z2Q
& <( J+1, Expr(J+1, Y3Q), Q2Q) & Pred(J+1, Expr(J+1, Y3Q), Q2Q, Q1Q) & Posl(J+1, Expr(J+1, Y3Q), Q2Q, Q3Q)
правая часть оператора присваивания Q2Q состоит из трех фрагментов Q1Q, Q2Q, Q3Q, причем Q1Q предшествует выражению Q2Q, а Q3Q следует за Q2Q


& (J, Z1, J+1, Z1Q) & (J, Z3, J+1, Z3Q) &(J, Q1, J+1, Q1Q) & (J, Q3, J+1, Q3Q) & (J, Y2, J+1, Y2Q)

последовательности Z1Q и Z1, Z3Q и Z3, Q1Q и Q1, Q3Q и Q3, Y2Q и Y2 поэлементно совпадают
& Y1 = Y1Q & Y3 = Y3Q
фрагменты Y1Q и Y1 равны; фрагменты Y3Q и Y3 также равны
& W Новые фрагменты(J) & W1 Новые идентификаторы(J) & Z2Q Новые фрагменты(J) & Q2Q Новые фрагменты(J)
фрагменты W, W1, Z2Q, Q2Q являются новыми для J+1 шага истории
& W1 = LValueExpr(J+1, W) & W2 = Expr(J+1, W) &

& Left(J+1, W1) = Var & LeftExpr(J+1, W1) Новые фрагменты(J, J+1, Var) & Type(J+1, LeftExpr(J+1, W1)) = Type(J, Y2) & W2 = Z2
выражение W1 является левой частью оператора присваивания W, а выражение W2 – его правой частью; левая часть выражения W1 представляет собой идентификатор новой переменной, тип которой совпадает с типом результата выражения Y2; W2 равно Z2
& Left(J+1, Z2Q) = Var & LeftExpr(J+1, Z2Q) = LeftExpr(J+1, W1) & Left(J+1, Q2Q) =Var & LeftExpr(J+1, Q2Q) = LeftExpr(J+1, W1)))/)
выражения Z2Q и Q2Q представляют собой идентификаторы новой переменной, являющейся левой частью оператора присваивания W
12. Параметры с одинаковым контекстом ((v1: {экономия общих подвыражений}) / (v1 = экономия общих подвыражений {<1, 1>})
для данного преобразования контексты сохраняются у первого простого параметра
13. Характеристическая функция ((v1: {экономия общих подвыражений}) / (v1 = экономия общих подвыражений ((v: {(v': ( Шаги истории, Кортежи, {} Кортежи)) <(2, v), (3, v)> Участки экономии((1,v))}) (let (J = (1,v)), (Z = (2, (2, v))) ParentLevel(J, LeftExpr(J, Y1))


характеристика участка экономии вычисляется как число предков оператора присваивания Y1
14. Стратегия ОП ((v1: {экономия общих подвыражений}) / (v1 = экономия общих подвыражений ((v: {(v': ( Шаги истории, {} R)) (2, v') = {(v": Участки экономии(вынос инвариантного оператора из цикла вперед, (1, v'))) Характеристическая функция(вынос инвариантного оператора из цикла вперед)((1, v'), (1, v"), (2, v"))})}) Sup((2, v)))/)
стратегия ОП заключается в выборе участка экономии, имеющего наибольшую вложенность
ЛИТЕРАТУРА


  1. Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области "Оптимизация последовательных программ". Часть 1. Термины для описания объекта оптимизации // Научно-техническая информация, сер. 2, 2002, № 12, с. 23-28

  2. Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области «Оптимизация последовательных программ». Ч.2. Термины для описания процесса оптимизации // Научно-техническая информация, Сер.2., 2003, №1.- С.22-29

  3. Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области «Оптимизация последовательных программ». Термины для описания объекта оптимизации. Препр., Владивосток: ИАПУ ДВО РАН, 2000.

  4. Клещев А.С., Артемьева И.Л. Математические модели онтологий предметных областей. Часть 2. Компоненты модели. // Научно-техническая информация, сер.2. 2001, № 3, с. 19-28.

  5. Клещев А.С., Артемьева И.Л. Необогащенные системы логических соотношений. Ч.1. // Научно-техническая информация, сер.2. 2000, № 7, с.18-28.

Похожие:

Оптимизация последовательных программ iconОсновная образовательная программа магистратуры по профилю «Исследование операций и оптимизация»
Нормативные документы для разработки магистерской программы «Исследование операций и оптимизация»
Оптимизация последовательных программ iconТема и основные цели и результаты обучения. Какие знания, умения и понимания вы хотели бы сформировать в Ваших учениках по завершению серии последовательных уроков Активные формы работы. (ГР, пр,ИР)
Тема и основные цели и результаты обучения. Какие знания, умения и понимания вы хотели бы сформировать в Ваших учениках по завершению...
Оптимизация последовательных программ iconМатематические и инструментальные методы экономики
Системы массового обслуживания: описание, модель многоканальной смо и ее оптимизация
Оптимизация последовательных программ icon1. Цели и задачи дисциплины
В результате изучения и освоения дисциплины “Дискретная оптимизация“ дипломированный специалист должен
Оптимизация последовательных программ iconОптимизация результатов образовательного процесса в доу посредством организации системы методической работы
Е приобретает усиление непрерывного характера обучения и профессионального совершенствования педагога как условия его активной адаптации...
Оптимизация последовательных программ iconПланы семинарских занятий по философии для студентов всех специальностей Уфа 2013
Целью данных рекомендации является оптимизация процесса изучения курса философии студентами в соответствии с требованиями Государственного...
Оптимизация последовательных программ icon1. Примерные программы учебных предметов обязательной части дополнительных предпрофессиональных образовательных программ в области искусств находятся в стадии разработки, которую планируется завершить к концу 2012 года
Ых программ в области искусств», а также с «Рекомендациями по разработке программ учебных предметов дополнительных предпрофессиональных...
Оптимизация последовательных программ iconИ. о директора департамента культуры Костромской области
Услуга по показу спектаклей, концертов и концертных программ, иных зрелищных программ
Оптимизация последовательных программ iconМетодические рекомендации по применению алгоритма разработки взаимоувязанных программ спортивной подготовки и предпрофессиональных программ для спортивных школ

Оптимизация последовательных программ iconКонкурс программ и проектов «Создание центров местного сообщества на базе библиотек»
По направлению Предоставление возможностей дистанционного обучения и проведения просветительских программ
Разместите кнопку на своём сайте:
docs.likenul.com


База данных защищена авторским правом ©docs.likenul.com 2015
обратиться к администрации
docs.likenul.com