Смекни!
smekni.com

Оптимизация программ (стр. 2 из 4)

Методы первой категории применимы почти к любому алгебра­ическому языку - ФОРТРАНу, АЛГОЛу, PL/1 и.т.д.

На практике используется весьма широкий набор машинно-не­зависимых оптимизирующих преобразований, что связано с большим разнообразием неоптимальностей. К ним относятся:

- разгрузка участков повторяемости;

- упрощение действий;

- реализация действий;

- чистка программы;

- экономия памяти;

- сокращение программы.

4.1. Разгрузка участков повторяемости

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

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

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

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

Примеры.

а) Чистка вниз преобразует цикл

для K:=1, K+1 пока K<=100

цикл

начало

X:=X*K;

если Z>0 то Y:=sin(X);

иначе A[I]:=X+2;

конец

к виду

для K:=1, K+1 пока K<=100

цикл X:=X*K;

если Z>0 то Y:=sin(X);

иначе A[I]:=X+2;

б) Чистка вверх преобразует цикл

для K:=1, K+1 пока K<=100

цикл

начало

если Z>0 то Y:=1;

иначе Y:=Z+2;

X[K]:=X[K] - Y; конец

к виду

если Z>0 то Y:=1;

иначе Y:=Z+2;

для K:=1, K+1 пока K<=100

цикл X[K]:=X[K] - Y;

Примером чистки тела рекурсивной функции может быть сле­дующий:

тело рекурсивной функции

цел функция Ф(N)

начало

целые Z,W;

W:=1;

если X>0 то W:=Y;

если N<=0 то Ф:=1

иначе

начало

Z:=N-W; Ф:=Z*Ф(Z) конец

конец

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

цел функция Ф(N)

начало

целое N;

цел функция F(M)

начало

целое Z;

если M<=0 то F:=1;

иначе

начало

Z:=M-W; F:=Z*F(Z) конец

конец

W:=1;

если X>0 то W:=Y;

Ф:=F(N); конец;

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

Например, с помощью этих преобразований фрагмент

для K:=1, K+1 пока K<=100

цикл

начало

N:=A[K];

если N>0 то переход на L; N:=N*N;

L: если Z=0 то ВЫВОД(N); конец

N:=100;

может быть преобразован к виду:

для K:=1, K+1 пока K<=100

цикл

если Z=0 то

начало

N:=A[K];

если N>0 то переход на L; N:=N*N;

L: ВЫВОД(N); конец;

N:=100;

4.1.1 Сдвиг инвариантных операторов

Рассмотрим подробнее преобразование сдвига инвариантных операторов, входящее в группу преобразований по разгрузке участков повторяемости.

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

1) сдвиг оператора не приводит к тому, что результат сдвигаемого оператора перемещается через оператор, в котором результат используется.

Например, для блока

(mi) * A,B

.

.

.

(mk) := C,(mi)

если ни A, ни B не определяются в области, то оператор mi может быть сдвинут вниз, но не может быть поставлен после опе­ратора mk.

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

(mi) := A,1

.

.

(mj) := A,10

.

.

(mk) := C,A

если больше никакой оператор после mj не присваивает зна­чение переменной A, то оператор mj может быть сдвинут вниз, но не может быть поставлен после оператора mk, операторами mi, а также вверх, но не выше оператора, использующего значение пе­ременной A, присвоенное оператором mi.

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

Таким образом, оператор инвариантен в области, если его операнды не зависят от места определения переменных в данной области.

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

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

сдвига операторов.

Рассмотрим условия, достаточные для сдвига операторов

I. Сдвиг оператора, не являющегося оператором присваива­ния, из области назад (на его входные пути) производится, если операнды оператора не зависят от места определения переменных в области, т.е.:

1) mi - идентификаторы, используемые в качестве аргумента оператора, не определены в блоке ни одним предшествующим опе­ратором;

2) программные переменные оператора не определены в об­ласти.

Если оба эти условия выполняются, то операнды оператора не зависят от места определения переменных в области.

II. Сдвиг оператора присваивания, из области назад (на его входные пути) производится, если:

1) mi - идентификаторы, используемые в качестве аргумента оператора, не определены в блоке ни одним предшествующим опе­ратором;

2) программные переменные, используемые в качестве опе­ранда оператора не определены в области;

3) блок является артикуляционным, т.е. лежит на пересече­нии всех входных или всех выходных путей сильно связанной об­ласти;

4) не существует другого определения или использования программной переменной на любом пути от входа в область до этого определения.

III. Сдвиг оператора, не являющегося оператором присваи­вания, из области вперед (на его выходные пути) производится, если:

1) mi - идентификаторы, используемые в качестве аргумента оператора, не переопределяются ни на одном пути между операто­ром и точкой выхода из области;

2) программные переменные, используемые в качестве аргу­мента оператора не переопределяются ни на одном пути между оператором и точкой выхода из области;

3) mi - указатель, являющийся результатом действия опера­тора, не используется на пути между оператором и концом блока.

IV. Сдвиг оператора присваивания, из области назад (на его входные пути) производится, если:

1) mi - идентификаторы, используемые в качестве аргумента оператора, не переопределяются ни на одном пути между операто­ром и точкой выхода из области;

2) программные переменные, используемые в качестве аргу­мента оператора не переопределяются ни на одном пути между оператором и точкой выхода из области;

3) блок является артикуляционным пунктом области;

4) не существует другого определения

программной переменной ни на одном пути между определением и

точкой выхода из области;

5) программная переменная не используется в области.

4.1.2. Сокращение глубины операции

Сокращение глубины операции - процедура выноса за пределы цикла операторов, аргументы которых являются функциями ре­курсивно определяемых переменных, и замена их внутри цикла простыми рекурсивными операторами присваивания, аргументы ко­торых не зависят от других переменных.

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

Приведем пример сокращения глубины операции применительно к оператору t4:=K*10+I из n-го блока :

n-й блок

L:t4:=K*10+I t5:=t6+K z(t2):=z(t2)+x(t4)+y(t5) K:=K+1

переход на L

в результате выполнения этой операции оператор t4:=K*10+I сдвигается в (n-1)-й блок, а в n-м блоке он заменяется опера­тором t4:=t4+10:

(n-1)-й блок

. . .

t4:=K*10+I

n-й блок

L: z(t2):=z(t2)+x(t4)+y(t5)

K:=K+1 t4:=t4+10 t5:=t6+K переход на L

4.2. Упрощение действий

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

4.2.1. Удаление индуктивных переменных и выражений

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

Например, применение указанных преобразований переводит фрагмент

для I:=1, I+1 пока I<100

цикл

начало

K:=I+J; A[K]:= A[K]+1 конец;

K:=10;

во фрагмент

I:=1;

для K:=I+J, K+1 пока K<100+J

цикл

начало

A[K]:= A[K]+1 конец;

K:=10;

Здесь I,K - индуктивные переменные. В данном случае из цикла удалено индуктивное выражение K:=I+J.

4.2.2. Замена сложных операций на более простые

Весьма важным преобразованием из этой группы является по­нижение силы операций, заменяющее в индуктивных вычислениях сложные операции на более простые; например, возведение в сте­пень или деление заменяется умножением ( например, выражение Х/4.О заменяется на выражение Х* О.25), а умножение - сложени­ем.