Оптимизация линейных участков программ

 

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

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

- удаление бесполезных присваиваний;

- исключение избыточных вычислений (лишних операций);

- свертка операций объектного кода;

- перестановка операций;

- арифметические преобразования.

Удаление бесполезных присваиваний заключается в том, что если в составе ли­нейного участка программы имеется операция присвоения значения некоторой произвольной переменной А с номером i, а также операция присвоения значения той же переменной А с номером j, i< j и ни в одной операции между i и j не ис­пользуется значение переменной А, то операция присвоения значения с номером i является бесполезной. Фактически бесполезная операция присваивания значе­ния дает переменной значение, которое нигде не используется. Такая операция может быть исключена без ущерба для смысла программы.

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

Например, во фрагменте программы

А: = В * С;

D: = В + С;

А: = D * С;

операция присвоения А: =В*С; является бесполезной и может быть удалена. Вме­сте с удалением операции присвоения здесь может быть удалена и операция ум­ножения, которая в результате также окажется бесполезной.

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

Например, в следующем фрагменте программы

Р: = @А;

А: = В * С;

D: = Р^ + С;

А: = D * С;

операция присвоения А: = В*С; уже не является бесполезной, хотя это и не столь очевидно. В этом случае неверно следовать простому принципу о том, что если переменная, которой присвоено значение в операции с номером i, не встречается ни в одной операции между i и j, то операция присвоения с номером i является бесполезной.

Исключение избыточных вычислений (лишних операций) заключается в нахож­дении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды. Операция линейного участка с порядковым номером i считается лишней, если существует идентичная ей операция с порядковым но­мером j, j< i и никакой операнд, обрабатываемый этой операцией, не изменялся никакой операцией, имеющей порядковый номер между i и j.

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

Например, выражение А: =2*В*С*3; может быть преобразова­но к виду А: =6*В*С.

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

Хорошим стилем программирования является объединение вместе операций, про­изводимых над константами, чтобы облегчить компилятору выполнение свертки.

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

Например, операции умножения в выражении А: =2*В*3*С; можно переставить без изменения конечного результата и " выполнить в порядке А: =(2*3)*(В*С). То­гда представляется возможным выполнить свертку и сократить количество опе­раций.

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

Например, выражение A: =B*C+B*D; может быть заменено на А: =В*(С+D):. Конеч­ный результат при этом не изменится, но объектный код будет содержать на одну операцию умножения меньше.

К арифметическим преобразованиям можно отнести и такие действия, как за­мена возведения в степень на умножение; а целочисленного умножения на кон­станты, кратные 2, — на выполнение операций сдвига. В обоих случаях удается повысить быстродействие программы заменой сложных операций на более про­стые.

 

Свертка объектного кода

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

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

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

Алгоритм свертки триад последовательно просматривает триады линейного участка и для каждой триады делает следующее:

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

2 Если операнд есть ссылка на особую триаду типа С(k, 0), то операнд заменяет­ся на значение константы k.

3 Если все операнды триады являются константами, то триада может быть
свернута. Тогда данная триада выполняется и вместо нее помещается особая
триада вида С(k, 0), где k — константа, являющаяся результатом выполнения
свернутой триады. (При генерации кода для особой триады объектный код не
порождается, а потому она в дальнейшем может быть просто исключена.)

Если триада является присваиванием типа А: =В, тогда:

- если В — константа, то А со значением константы заносится в таблицу Т
(если там уже было старое значение для А, то это старое значение исключается);

- если В — не константа, то А вообще исключается из таблицы Т, если оно
там есть.

Рассмотрим пример выполнения алгоритма.

Пусть фрагмент исходной программы (записанной на языке типа Pascal) имеет вид:

I: =1+1;

I: =3;

J: =6*I+I

Ее внутреннее представление в форме триад будет иметь вид:

1 +(1, 1);

2: =(I, ^1);

3: = (I, 3);

4 *(6, I);

5 +(^4, I);

6: =(J, ^5).

Процесс выполнения алгоритма свертки показан в табл. 4.7.

Таблица 4.7 Пример работы алгоритма свертки

 

 

Триада	Шаг 1	Шаг 2	ШагЗ	Шаг 4	Шаг 5	Шаг 6
	С (2, 0)	С (2, 0)	С (2, 0)	С (2, 0)	С (2, 0)	С (2, 0)
	: = (I, ^1)	: =(I, 2)	: =(I, 2)	: =(I, 2)	: =(I, 2)	: =(I, 2)
	: =(I, 3)	: =(I, 3)	: =(I, 3)	: =(I, 3)	: =(I, 3)	: =(I, 3)
	*(6, I)	* (6, I)	*(6, I)	С (18, 0)	С (18, 0)	С (18, 0)
	+ (^4, I)	+ (^4, I)	+ (^4, I)	+ (^4, I)	С (21, 0)	С (21, 0)
	: =(J, ^5)	: =(J, ^5)	: =(J, ^5)	: =(J, ^5)	: =(J, ^5)	: =(J, 21)
Т	(, )	(I, 2)	(I, 3)	(I, 3)	(I, 3)	(I, 3) (J, 21)

 

Если исключить особые триады типа С(k, 0) (которые не порождают объектного кода), то в результате выполнения свертки получим следующую последователь­ность триад:

1: = (I, 2)

2: = (I, 3)

3: = (J, 21)

 

 

Исключение лишних операций

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

Рассмотрим алгоритм исключения лишних операций для триад.

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

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

2) после обработки i-й триады, в которой переменной А присваивается некоторое значение, число зависимости A (dep(A))получает значение i, так как зна­
чение А теперь зависит от данной i-й триады;

3) при обработке 1-й триады ее число зависимости (depd)) принимается равным значению 1+(максимальное из чисел зависимости операндов).

Таким образом, при использовании чисел зависимости триад и переменных можно утверждать, что если i-я триада идентична j-й триаде (j< i), то i-я триада счита­ется лишней в том и только в том случае, когда dep(i)=dep(j).

Алгоритм исключения лишних операций использует в своей работе триады осо­бого вида SAME(j, 0). Если такая триада встречается в позиции с номером i, то это означает, что в исходной последовательности триад некоторая триада i идентич­на триаде j.

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

1 Если какой-то операнд триады ссылается на особую триаду вида SAME(j, 0), то
он заменяется на ссылку на триаду с номером j (^j).

2 Вычисляется число зависимости текущей триады с номером i, исходя из чисел зависимости ее операндов.

3 Если в просмотренной части списка триад существует идентичная j-я триада,
причем j< i и dep(i)=dep(j), то текущая триада i заменяется на триаду особого вида SAME(j, 0).

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

Рассмотрим работу алгоритма на примере:

D: =D+C*B;

A: =D+C*B;

C: =D+C*B;

Этому фрагменту программы будет соответствовать следующая последователь­ность триад:

1) * (С, В)

2) + (D, ^1)

3): =(D, ^2)

4)* (С, В)

5)+ (D, ^4)

6): =(А, ^5)

7)* (С, В)

8)+ (D, ^7)

9): = (С, ^8)

 

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

 

Таблица 4.8 Пример работы алгоритма исключения лишних операций

 

Обрабатываемая триада i	Числа зависимости переменных	Числа зависимости триад dep(i)	Триады, полученные после выполнения алгоритма
А	В	С	D
1)*(С, В)						1) * (С, В)
2)+(D, ^l)						2) + (D, ^1)
3): = (D, ^2)						3): =(D, ^2)
4) * (С, В)						4) SAME (1, 0)
5) + (D, ^4)						5) + (D, ^1)
6): = (А, ^5)						6): = (А, ^5)
7) * (С, В)						7) SAME (1, 0)
8) + (D, ^7)						8) SAME (5, 0)
9): =(С, ^8)						9): = (С, ^5)

 

Теперь, если исключить триады особого вида SAME( j, 0), то в результате выполне­ния алгоритма получим следующую последовательность триад:

1) * (С, В)

2) + (D, ^1)

3): = (D, ^2)

4) + (D, ^1)

5): = (А, ^4)

6): = (С, ^4)

 

⇐ Предыдущая14151617181920212223Следующая ⇒

Поделиться:

Популярное:

1. III. Перечень программных мероприятий
2. VPN на базе программного обеспечения
3. Автор: М.Т. Шихиева, Рабочая программа Государственной итоговой аттестации выпускников - Королев МО: «МГОТУ», 2015 - 22 с.
4. Автор: М.Т. Шихиева, Рабочая программа Государственной итоговой аттестации выпускников - Королев МО: «МГОТУ», 2015 - 22 с.
5. Алгоритм решения задач линейного программирования с помощью Excel
6. Алгоритм формирования техники двигательных действий легкоатлетических упражнений. Характеристика и технология обучения технике легкоатлетического вида из школьной программы (по выбору).
7. АНАЛИЗ ОДНОМЕРНЫХ ПОТОКОВ ПРИ НЕЛИНЕЙНЫХ
8. Анализ результатов экспериментального исследования по реализации программы педагогического сопровождения молодой семьи
9. Анализ формирования и выполнения производственной программы
10. АППАРАТНОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
11. Аренда земельных участков (ст. 22 ЗК РФ)
12. Архитектура промежуточного программного обеспечения