Участок экономии: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Участок экономии''' (''[[Economy region]]'') -
'''Участок экономии''' (''[[Economy region]]'') фрагмент программы, который содержит все изменяемые части программы и семантика которого гарантирует корректность и целесообразность данной оптимизации по отношению ко всей программе. По существу, оптимизирующее преобразование,
фрагмент программы, который содержит все изменяемые части
рассмотренное как преобразование участка экономии, является бесконтекстным.
программы и семантика которого гарантирует корректность и
целесообразность данной оптимизации по отношению ко всей
программе. По существу, оптимизирующее преобразование,
рассмотренное как преобразование участка экономии, является
бесконтекстным.


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


''Оператор''. Арифметические операции - основной источник оптимизации в операторе.
''Оператор''. Арифметические операции основной источник оптимизации в операторе.


''Линейный участок, или луч''. Свойства луча быть последовательностью операторов, выполняемых в порядке их перечисления, существенно упрощает выполнение большинства оптимизаций.
''Линейный участок, или луч''. Свойства луча быть последовательностью операторов, выполняемых в порядке их перечисления, существенно упрощает выполнение большинства оптимизаций.
Строка 37: Строка 25:


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




''Иерархия вложенных альтов''. Не менее естественной единицей факторизации является ''альт'' - фрагмент с единственной ''[[начальная вершина|начальной вершиной]]''. Если программа регуляризуема, то подмножество ее альтов образует ''[[зонно-интервальное представление]]'' программы, выявляющее как
''Иерархия вложенных альтов''. Не менее естественной единицей факторизации является ''альт'' фрагмент с единственной ''[[начальная вершина|начальной вершиной]]''. Если программа регуляризуема, то подмножество ее альтов образует ''[[зонно-интервальное представление]]'' программы, выявляющее как
циклическую, так и интервальную ее структуру. Любая программа представима в виде иерархии альтов, являющихся [[гамак|гамаками]]. Такое представление не требует изменения алгоритма оптимизации при его факторизации и выделяет фрагменты, являющиеся обобщенными преобразователями.
циклическую, так и интервальную ее структуру. Любая программа представима в виде иерархии альтов, являющихся [[гамак|гамаками]]. Такое представление не требует изменения алгоритма оптимизации при его факторизации и выделяет фрагменты, являющиеся обобщенными преобразователями.




''Группа процедур''. Совместное рассмотрение процедур часто предоставляет дополнительные возможности для оптимизации, например позволяет выявить процедуры, не являющиеся рекурсивными, или осуществить открытую подстановку тел процедур на места их вызовов. При этом помимо ''[[уграф|уграфов]]'', кодирующих потоки управления между лучами внутри тел процедур, рассматриваются межпроцедурные связи, например в виде ''[[граф вызовов процедур|графа вызовов процедур]]''.
''Группа процедур''. Совместное рассмотрение процедур часто предоставляет дополнительные возможности для оптимизации, например позволяет выявить процедуры, не являющиеся рекурсивными, или осуществить открытую подстановку тел процедур на места их вызовов. При этом помимо ''[[уграф|уграфов]]'', кодирующих потоки управления между лучами внутри тел процедур, рассматриваются межпроцедурные связи, например в виде ''[[граф процедур|графа вызовов процедур]]''.
==Литература==
==Литература==
[Касьянов/88],
* Векторизация программ: теория, методы, реализация. — М.: Мир, 1991.


[Касьянов-Поттосин],
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев-Касьянов/94],
* Касьянов В.Н. Оптимизация программ // Прикладная информатика. — М.: Финансы и статистика, 1983. — Вып. 2.


[Векторизация],}
* Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.


[Касьянов/83],
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.


[Касьянов/86]
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.

Навигация