Эволюционное управление сложными системами. 2
| Вид материала | Документы |
- Программа проведения письменного экзамена по «Теории менеджмента» с абитуриентами,, 61.66kb.
- Учебно-методический комплекс дисциплины опд. Ф. 09. «Управление системами и процессами», 1084.9kb.
- Образец оформления материалов основы структурного синтеза систем иваненко И. И., Петров, 104.66kb.
- Учебно-тематический план «Диспетчеризация, автоматизация и управление инженерными системами», 211.18kb.
- Учебный план повышения квалификации по программе "Управление системами ипотечного жилищного, 33.24kb.
- Карельский Государственный Педагогический Университет, 231.3kb.
- «большую», 135.42kb.
- 05. 13. 10 Управление в социальных и экономических системах, 91.88kb.
- Работа рассчитана как на специалистов-теоретиков по управлению сложными системами,, 2285.97kb.
- Управление качеством роста российской экономики, 669.33kb.
1 2
Глава 2. Онтология оптимизации программ.
Проблема оптимизации программ была впервые осознана практически одновременно с построением первых трансляторов с языков программирования. Практика показала, что повышение уровня исходного языка программирования отрицательно сказывается на эффективности объектных программ, полученных в результате трансляции. В связи с этим в конце 50-х годов в области программирования была поставлена задача повышения эффективности программ с помощью выполнения над ними в процессе трансляции ряда преобразований. Эту задачу принято называть задачей оптимизации программ, а преобразования, выполнение которых над программами может повысить их эффективность, – оптимизирующими преобразованиями (ОП). Под системой оптимизирующих преобразований будем в дальнейшем понимать набор ОП вместе со стратегией их применения. К настоящему времени теория оптимизации программ обогатилась фундаментальными результатами (развит аппарат схем программ, выделен богатый набор оптимизирующих преобразований, найдены достаточные условия корректности применения ряда преобразований и т.д.), а практика - примерами эффективно работающих оптимизирующих компиляторов.
В силу наличия большого числа языков программирования, теоретические результаты в области оптимизации программ обычно формулируются в терминах абстрактных математических моделей программ, независимых от конкретных алгоритмических языков, причем число таких моделей исчисляется десятками. Это приводит к тому, что оптимизирующие преобразования описываются в терминах различных моделей, что затрудняет объединение различных преобразований в рамках одной системы ОП, а также затрудняет изучение различных оптимизирующих преобразований студентами. Кроме того, для многих преобразований не опубликованы формальные описания, условия применимости и описание результатов их применения. Систематизация и унификация знаний об оптимизации программ позволяет описать все преобразования в единой терминологии и, как следствие, облегчает изучение основных понятий предметной области "Оптимизация программ", поэтому является актуальной задачей.
Описание терминологии некоторой предметной области вместе с определением смысла терминов в современном мире получило название модели онтологии. Термины предметной области "Оптимизация последовательных программ" можно разбить на две группы: термины, при помощи которых описываются свойства программ (термины этой группы будем называть терминами для описания объекта оптимизации), и термины, при помощи которых описываются свойства процесса оптимизации, то есть модель онтологии данной предметной области состоит из двух частей.
2.1 Термины для описания объекта оптимизации.
Объектом оптимизации является некоторая программа. Свойства программы всегда формулируются в терминах математической модели этой программы. Характеристикой любой программы является язык (множество программ), которому эта программа принадлежит. Свойства языка также формулируются в терминах математической модели этого языка. Тем самым, множество терминов для описания объекта оптимизации может быть разбито на две группы: термины для описания модели языка и термины для описания модели конкретной программы. Прежде чем будет оптимизироваться конкретная программа, должен быть определен язык, которому эта программа принадлежит. Следовательно, термины для описания модели языка являются параметрами модели онтологии, а термины для описания модели программы – неизвестными модели онтологии. Тогда язык задается указанием значений параметров, а конкретная программа – указанием значений неизвестных.
Очевидно, что модель программы описывает не одну программу, а множество программ, обладающих одинаковыми свойствами, а модель языка – множество языков, обладающих одинаковыми свойствами. Поэтому к модели языка предъявляются следующие требования:
- она должна позволять представлять основные конструкции императивных языков программирования, существенные для описания последовательных ОП.
- она должна быть гибкой и расширяемой с тем, чтобы при необходимости класс моделируемых программ мог быть легко расширен
- форма представления моделей программ должна быть удобна для анализа как информационных потоков, так и потоков управления в программе.
В соответствии с этими принципами и была построена наша модель.
Как и любая онтология, она состоит из терминов, описывающих структуру знаний о программах, данных о конкретных программах и связей между ними.
Описание онтологии моделей программ будем вести при помощи формализма.
Любая программа состоит из фрагментов, причем каждый фрагмент, в свою очередь, также состоит из фрагментов, т.е. любая программа имеет синтаксическую структуру, которую отражает математическая модель этой программы.
Каждый фрагмент, как элемент программы, обладает рядом свойств. Прежде всего, у него есть адрес фрагмента – некоторая уникальная характеристика, однозначно определяющая каждый фрагмент в программе. Будем считать, что все фрагменты могут быть разбиты на три группы: операторы описания, исполнимые операторы и элементы операторов. Каждый фрагмент характеризуется своим классом, например, фрагмент может иметь класс оператор присваивания, оператор цикла, оператор описания функций и т.д. Функция FragClass возвращает для указанного адреса фрагмента класс этого фрагмента. Множество названий классов фрагментов (каждой группы) в программе задают значения параметров Операторы описания, Исполнимые операторы, Элементы операторов.
Синтаксическую структуру программы задают дуги управления. Каждая дуга управления связывает два фрагмента программы. Каждая дуга управления имеет метку, которая определяет тип связи между фрагментами. Для задания дуги управления используется функция, имя которой совпадают с меткой дуги. Значение параметра Имена дуг управления задает, какие метки могут иметь дуги управления в программе. Для каждой дуги управления определена область действия дуги управления. Эту область задает значение функционального параметра Область действия дуг управления –функция, которая сопоставляет каждой метке дуги пару, состоящую из двух множеств имен классов фрагментов: первое множество определяет, фрагменты каких классов могут быть аргументами, а второе – результатами дуги управления с данной меткой.
В программе всегда присутствует множество различных Идентификаторов. Идентификаторы могут быть разных видов, например, идентификаторы переменных, функций, констант и типов данных. Идентификаторы каждого вида образуют в программе множество, название которого совпадает с названием вида. Значение параметра Виды идентификаторов задает, идентификаторы каких видов могут быть в программе.
На множестве фрагментов и идентификаторов программы определены функции и отношения, которые позволяют определить структуру программы и некоторые ее свойства.
Функции, имеющие один аргумент (фрагмент или идентификатор) называются атрибутами. Каждый атрибут имеет имя. Значение параметра Имена атрибутов задает, какие атрибуты могут использоваться для описания свойств идентификаторов или фрагментов в программе. Для каждого атрибута определяются область определения и область значений атрибута. Эти области задаются значениями функциональных параметров Область определения атрибута и Область значения атрибута.
Значение параметра Имена функций задает, какие функции, имеющие два и более аргументов, могут использоваться при описании свойств фрагментов или идентификаторов программы. Для каждой функции определяется область определения и область значений. Эти области задаются значениями параметров Область определения функции и Область значений функции.
Значение параметра Имена отношений задает, какие отношения могут быть определены на множестве фрагментов и идентификаторов программы. Значения параметров Определение отношения для каждого имени отношения задают формулу определения истинности отношения между фрагментами и идентификаторами программы.
Еще одним свойством фрагмента является его корректность. Значение корректности задает предикат Корректность, который сопоставляет адресу фрагмента истину, если у него имеются все дуги управления и атрибуты, необходимые для этого фрагмента. Значение параметра Определение корректности задает для каждого класса фрагмента, какие дуги управления и атрибуты должны быть определены для фрагмента этого класса.
Значение параметра Элементарные типы задает для языка множество идентификаторов типов данных, являющимися базовыми для всех остальных типов данных этого языка.
Значение параметра Способы порождения задает множество названий конструкторов типов данных в языке. Для каждого идентификатора типа данных в программе определены значения таких свойств, как базовый тип и метод конструирования типа из базового. Значение первого свойства задает функция BaseType, которая сопоставляет каждому идентификатору типа последовательность идентификаторов типов, которые использованы при конструировании этого типа данных. Значение второго свойства задает функция ConstructMethod, которая сопоставляет каждому идентификатору типа название конструктора.
Значение параметра Зарезервированные имена задает множество имен ролей, которые могут играть фрагменты или идентификаторы программы. Значение параметра Область значения зарезервированного имени сопоставляет каждому имени роли предикат, определяющий, какими свойствами должен обладать фрагмент или идентификатор, играющий в программе эту роль.
Значение параметра Знаки операций задает множество символов, использующихся в программе для обозначения каких-либо операций в выражениях (арифметических, логических, преобразования и т.д.) программы. Функциональные параметры Число аргументов и Приоритет, сопоставляют каждому символу операции количество аргументов и приоритет.
2.2 Определение языка описания структурных программ
Теперь, пользуясь описанной выше терминологией, мы можем определить вполне конкретную реализацию Языка Описания Структурных Программ. В дальнейшем будем ее называть языком модели структурных программ (ЯМСП1). К ней предъявляются следующие требования: оно должна содержать средства для представления языковых конструкций языков высокого уровня, существенных для проведения классических оптимизирующих преобразований и при этом быть достаточно простой для дальнейшего анализа и обработки.
Опишем свойства этого языка неформально.
Он разработан на основе таких языков программирования, как Паскаль и Си и является структурным языком программирования, где в качестве первичных примитивов выбраны последовательность, циклы 3-х видов и ветвление.
В нем принято обычное понятие статической блочной среды; все переменные должны быть описаны до их использования в каком-либо операторе описания функции либо вне любой функции в начале программы; допускаются вложенные процедуры и функции; если функция не возвращает результат, то она считается процедурой. Функция с именем Main считается главной, все остальные функции должны быть вложены в нее.
Любая переменная может иметь либо простой тип, либо сложный. К простым типам относятся такие типы, как целый, вещественный и логический. Все эти типы являются неявно приводимыми друг к другу. К операндам простого типа применимы следующие операции: +, -, *, /, взятие адреса, обращение по указателю, AND, OR, NOT. Разрешены динамические переменные, операции New и Dispose, а также адресная арифметика.
Сложные типы данных конструируются на основе ранее определенных типов путем объединения их в массивы и создания ссылочных типов. Элементы массивов могут иметь как простой, так и сложный тип. Массивы могут быть только одномерными. Индексы массивов - только целые переменные. Над массивами может применяться только одна операция - обращение к элементу массива по индексу. В отношении переменных применяется принцип именной эквивалентности, т.е. две переменные эквивалентны, если они имеют один и тот же тип. Исключения из этого правила - все простые типы эквивалентны между собой.
Функции могут возвращать результат только скалярного типа, т.е. целого, вещественного, логического и произвольного ссылочного (например, указатель на 3-х мерный массив, компонентами которого являются указатели на указатель). Параметры функций могут иметь любой тип и передаваться по ссылке либо по значению. Все имена функций, переменных, констант, типов уникальны в пределах программы.
Данный язык описания структурных программ позволяет достаточно полно представлять программы на языках высокого уровня. Далее рассмотрим модель онтологии процесса оптимизации.
2.3 термины для описания процесса оптимизации программ
Термины для описания процесса оптимизации могут быть разделены на 2 группы – описывающие собственно знания об оптимизирующих преобразованиях, и термины, определяющие параметры эксперимента. В нашем понимании к первой группе относятся термины, описывающие контекстные условия (КУ) и правила трансформации (ПТ), а ко второй – термины, определяющие порядок применения оптимизирующих преобразований (ОП).
Под процессом оптимизации будем понимать последовательность шагов, на каждом из которых происходит применение к оптимизируемой программе одного преобразования. Каждый такой шаг будем называть шагом истории оптимизации. Каждое оптимизирующее преобразование обладает следующими свойствами: участком экономии, контекстным условием, характеристической функцией, стратегией применения, трансформацией и множеством последующих ОП. Опишем эти составные части более детально.
Участок экономии: обычно ОП проводится не над всей программой, а над каким-то локальным ее участком, не обязательно непрерывным. Множество фрагментов программы, необходимых и достаточных как для принятия решения об оптимизации, так и собственно оптимизации, будем называть участком экономии (УЭ). Обычно один участок экономии имеет вид декартового произведения одного кортежа значений на множество кортежей значений.
Контекстное условие: под контекстным условием будем понимать совокупность трех предикатов – простой формулы КУ, множественной формулы КУ и отрицательной множественной формулы КУ. Простая формула КУ представляет собой предикат, в котором в качестве аргументов используются фрагменты МСП. Подстановка, при которой эта формула становится истинной, называется значением простых параметров ОП. Кроме того, существуют так называемые множественные параметры. Они используются, когда необходимо одной формулой описать участок экономии, состоящих из неограниченного числа фрагментов, удовлетворяющих, тем не менее, одному и тому же условию. Например, при оптимизации функций участком экономии может быть как сама функция, так и все фрагменты ее вызова, причем число вызовов может быть произвольным. В этом случае условие на тело функции является простой формулой КУ, а условие, описывающее ее вызовы – множественной. Множество подстановок идентификаторов из модели конкретной программы, таких, что множественная формула КУ становится истинной, при зафиксированных значениях простых параметров для этого же ОП, называется значениями множественных параметров ОП.
При этом участком экономии является декартовое произведение кортежа значений простых параметров ОП и множества кортежей множественных параметров ОП.
Кроме того, есть еще отрицательная множественная формула. Она устроена так же, как и обычная множественная, за исключением того, что кортеж значений, при котором она истинна, не входит в участок экономии. Более того, контекстное условие считается выполненным, если определены значения параметров простой формулы КУ, множество значений параметров множественной формулы КУ и при этом не существует ни одной подстановки, при которой бы отрицательная множественная формула стала бы истинной.
Характеристическая функция: так как результат выполнения контекстного условия представляет собой множество участков экономии, то необходим критерий для выбора одного из них. Характеристическая функция (ХФ) - это формула над фрагментами из участка экономии. Она сопоставляет каждому участку экономии рациональное число.
Стратегия оптимизации – это формула, которая из множества рациональных чисел - результатов характеристической функции для разных участков экономии, выбирает одно. Соответственно, участок экономии с выбранной характеристикой и подвергается оптимизации на этом шаге истории.
Формула трансформации: - это терм специального вида, который определяет, какими свойствами должен обладать оптимизированный участок экономии.
Следующие ОП: Для каждого оптимизирующего преобразования задается последовательность ОП, которые, в случае применения этого преобразования, должны быть выполнены на следующем шаге истории.
Первые ОП: последовательность преобразований, применяемых на первом шаге истории оптимизации.
Критерий оптимальности: для того, чтобы сравнивать между собой различные системы оптимизирующих преобразований, необходим критерий оценки оптимальности программ. В данном случае критерий задается функцией, сопоставляющей любой программе некоторую оценку.
На каждом шаге истории имеется последовательность текущих преобразований. В порядке следования, для них ведется поиск участков экономии. Если существует ОП, для которого множество участков экономии не пусто, то для каждого участка экономии при помощи характеристической функции строится его оценка, из множества которых затем в соответствии со стратегией оптимизации выбирается характеристика выбранного УЭ. Далее для этого участка экономии в соответствии с формулами трансформации строится оптимизированный УЭ, который и заменяет выбранный при переходе к следующему шагу истории. Процесс продолжается до тех пор, пока для всех преобразований из множества текущих ОП множество участков экономии будет пустым.
Функционирование системы Инструментальной Моделирующей Экспертной системы Оптимизации Программ (И_МЭСОП), основанной на этой онтологии, будет происходить следующим образом.
- Студенты, ознакомившись с моделью структурных программ, заполняют базу знаний оптимизирующих преобразованиях. Они изучают предложенные преподавателем преобразования, и описывают для них контекстные условия, трансформации, характеристические функции и т.д.
- Далее они смогут проверить на практике правильность и эффективность своих преобразований, а также поэкспериментировать с различными вариантами стратегий.
Таким образом, в рамках данного подхода удалось достаточно полно описать знания в предметной области "оптимизация программ". Данная онтология позволяет легко изменять моделируемый язык программирования, описания оптимизирующих преобразований, стратегии их применения и критерии оптимальности получаемых программ, что позволяет обучаемым получать более глубокие знания в данной предметной области.