4624
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Участок экономии''' (''Economy region'') - фрагмент программы, который содержит все ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Участок экономии''' (''Economy region'') | '''Участок экономии''' (''[[Economy region]]'') — фрагмент программы, который содержит все изменяемые части программы и семантика которого гарантирует корректность и целесообразность данной оптимизации по отношению ко всей программе. По существу, оптимизирующее преобразование, | ||
фрагмент программы, который содержит все изменяемые части | рассмотренное как преобразование участка экономии, является бесконтекстным. | ||
программы и семантика которого гарантирует корректность и | |||
целесообразность данной оптимизации по отношению ко всей | |||
программе. По существу, оптимизирующее преобразование, | |||
рассмотренное как преобразование участка экономии, является | |||
бесконтекстным. | |||
Понятно, что ограничение на размер участка экономии сужает | Понятно, что ограничение на размер участка экономии сужает возможности улучшения программы (в этом случае говорят о глобальной оптимизации), и поэтому наилучшим участком экономии является вся программа. Однако глобальность оптимизации, как правило, не только приводит к существенному | ||
возможности улучшения программы (в этом случае говорят о | увеличению объема рассматриваемой информации, но и не позволяет разработать обоснованный и эффективный [[алгоритм]] реализации этой оптимизации. Поэтому на практике обычно рассматривают следующие участки экономии. | ||
глобальной оптимизации), и поэтому наилучшим участком | |||
экономии является вся программа. Однако глобальность | |||
оптимизации, как правило, не только приводит к существенному | |||
увеличению объема рассматриваемой информации, но и не | |||
позволяет разработать обоснованный и эффективный алгоритм | |||
реализации этой оптимизации. Поэтому на практике обычно | |||
рассматривают следующие участки экономии. | |||
''Оператор''. Арифметические операции | ''Оператор''. Арифметические операции — основной источник оптимизации в операторе. | ||
''Линейный участок, или луч''. Свойства луча быть последовательностью операторов, выполняемых в порядке их перечисления, существенно упрощает выполнение большинства оптимизаций. | ''Линейный участок, или луч''. Свойства луча быть последовательностью операторов, выполняемых в порядке их перечисления, существенно упрощает выполнение большинства оптимизаций. | ||
Строка 27: | Строка 15: | ||
''Иерархия вложенных зон''. Представление, выявляющее циклическую структуру программы вне зависимости от языковых конструкций, использованных для программирования циклов. Строится | ''Иерархия вложенных зон''. Представление, выявляющее циклическую структуру программы вне зависимости от языковых конструкций, использованных для программирования циклов. Строится | ||
на основе анализа управляющего графа программы. | на основе анализа [[управляющий граф|управляющего графа]] программы. | ||
''Процедура''. Ряд оптимизаций (в частности, экономия памяти и другие оптимизации, связанные с перераспределением памяти) требует для своего эффективного применения рассмотрения | ''Процедура''. Ряд оптимизаций (в частности, экономия памяти и другие оптимизации, связанные с перераспределением памяти) требует для своего эффективного применения рассмотрения | ||
Строка 37: | Строка 25: | ||
''Иерархия вложенных интервалов''. Фрагмент, называемый ''интервалом'', моделирует правила композиции структурного программирования в терминах управляющего графа. Многие | ''Иерархия вложенных интервалов''. Фрагмент, называемый ''интервалом'', моделирует правила композиции структурного программирования в терминах управляющего графа. Многие | ||
алгоритмы глобальной оптимизации упрощаются, если программа ''регуляризуема'' | алгоритмы глобальной оптимизации упрощаются, если программа ''регуляризуема'' — представима в виде иерархии вложенных интервалов. | ||
''Иерархия вложенных альтов''. Не менее естественной единицей факторизации является ''альт'' | ''Иерархия вложенных альтов''. Не менее естественной единицей факторизации является ''альт'' — фрагмент с единственной ''[[начальная вершина|начальной вершиной]]''. Если программа регуляризуема, то подмножество ее альтов образует ''[[зонно-интервальное представление]]'' программы, выявляющее как | ||
циклическую, так и интервальную ее структуру. Любая программа представима в виде иерархии альтов, являющихся гамаками. Такое представление не требует изменения алгоритма оптимизации при его факторизации и выделяет фрагменты, являющиеся обобщенными преобразователями. | циклическую, так и интервальную ее структуру. Любая программа представима в виде иерархии альтов, являющихся [[гамак|гамаками]]. Такое представление не требует изменения алгоритма оптимизации при его факторизации и выделяет фрагменты, являющиеся обобщенными преобразователями. | ||
''Группа процедур''. Совместное рассмотрение процедур часто предоставляет дополнительные возможности для оптимизации, например позволяет выявить процедуры, не являющиеся рекурсивными, или осуществить открытую подстановку тел процедур на места их вызовов. При этом помимо ''уграфов'', кодирующих потоки управления между лучами внутри тел процедур, рассматриваются межпроцедурные связи, например в виде ''графа вызовов процедур''. | ''Группа процедур''. Совместное рассмотрение процедур часто предоставляет дополнительные возможности для оптимизации, например позволяет выявить процедуры, не являющиеся рекурсивными, или осуществить открытую подстановку тел процедур на места их вызовов. При этом помимо ''[[уграф|уграфов]]'', кодирующих потоки управления между лучами внутри тел процедур, рассматриваются межпроцедурные связи, например в виде ''[[граф процедур|графа вызовов процедур]]''. | ||
==Литература== | ==Литература== | ||
* Векторизация программ: теория, методы, реализация. — М.: Мир, 1991. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизация программ // Прикладная информатика. — М.: Финансы и статистика, 1983. — Вып. 2. | |||
* Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. |