Получение рационального кода управляющих программ микропроцессорных систем

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Получение рационального кода управляющих программ микропроцессорных систем

Чашин Ю.Г., Константинов И.С.

В связи с переходом на рыночные отношения, к выпускаемой продукции предъявляются следующие требования: повышение качества и снижение себестоимости. Это накладывает ряд требований, по эффективности работы, на микропроцессорные автоматизированные системы управления технологическими процессами и производствами (АСУ ТПП), работающие в реальном режиме времени, среди которых, такие как: уменьшение времени реакции системы на события, более “качественная” обработка первичной информации, и т.д.

Наиболее простым и распространенным решением этих задач, является использование более “мощных” аппаратных средств, что популярно в связи с быстрым ростом производительности современных микропроцессоров. Недостатком данного подхода является, в конечном итоге, увеличение себестоимости выпускаемой продукции.

Другим, альтернативным решением является оптимизация программного кода микропроцессорных систем АСУ ТП. Данное решение является менее популярным в связи с распространенными заблуждениями:

- вера в оптимизационное могущество компиляторов. На самом деле такое мнение безосновательно, хороший оптимизирующий компилятор может похвастаться лишь своим умением эффективно транслировать грамотно спроектированный код;

- максимальная эффективность достижима лишь при программировании на чистом ассемблере, но отнюдь не на языке высокого уровня. На самом деле перенос программы на ассемблер только в исключительных случаях увеличивает ее эффективность. При трансляции качественного исходного кода, оптимизирующие компиляторы, отстают от идеальной ручной оптимизации не более чем на 10%-20%. Конечно, это весьма ощутимая величина, но все же не настолько, чтобы оправдать трудоемкость программирования на чистом ассемблере.

Для популяризации данного подхода, использования оптимизации программного кода, ко всем оптимизирующим алгоритмам целесообразно предъявлять следующие жесткие требования [1]:

- оптимизация должна быть максимально машинно-независимой и переносимой на другие платформы (операционные системы) без дополнительных затрат и существенных потерь эффективности;

- оптимизация не должна увеличивать трудоемкость разработки (в т. ч. и тестирования) приложения более чем на 10%-15%;

- оптимизация должна давать ощутимый выигрыш в скорости выполнения или размере программы.

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

Анализируя используемые преобразования для оптимизации программ [1-3], можно сделать вывод, что в основном используются локальные методы оптимизации, направленные на «улучшение» конкретных программных «конструкций». Методы глобальной оптимизации программ не достаточно широко используются и не достаточно изучены.

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

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

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

Для решения вышеописанной задачи необходимо уметь преобразовывать одни информационные модели в другие с сохранением их некоторых характеристик. Назовем такие модели эквивалентными.

Рис. 1

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

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

Рассмотрим для примера следующие два класса систем соотношений определенных на множестве .

1. где и некоторые несовпадающие символы из алфавита , а - все символы из .

Такую систему соотношений назовем соотношениями типа перестановочность.

2. где - удовлетворяют выше описанным условиям.

Такую систему соотношений назовем - типа сокращения.

Две модели и считаются эквивалентными , если множество путей этих моделей совпадают над выбранной системой соотношений.

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

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

Содержательно фрагмент представляет из себя часть информационной модели с указанием связей. Формальное описание можно почерпнуть, в частности, в работе [4].

Понятие фрагмента позволяет аксиомизировать задание системы преобразований, а именно, единственное правило вывода - правило подстановки, позволяет один фрагмент заменить другим, ему эквивалентным. Если то .

Аксиомы, описывающие пары эквивалентных фрагментов для системы соотношений типа перестановочность, задаются в виде изображенном на рисунке 2 [5].

микропроцессорный автоматизированный информационный

Рис. 2

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

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

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

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

На рис. 1 приведены эквивалентные информационные модели над следующими алфавитами и системой соотношений: .

При рассмотрении системы соотношений типа сокращение основополагающим является следующее утверждение.

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

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

Рис. 3

Фрагменты моделей и , содержащие лишь используемые вершины и дуги, изображены на рисунке 3.

Теорема. , при .

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

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

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

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

- числа сопоставленные символам и ;

, - характеристики и - ой дуг, соответственно вершин и .

Обозначим через - сумму всех числовых характеристик вершин и дуг, входящих в структуру модели .

,

где - количество вершин, наделенных метками и ;

- максимальная метка дуг вершин наделенными символами и в модели ;

- количество дуг отсутствующих в модели с метками , и соответствующих вершинам и ;

- сумма характеристик всех остальных вершин и дуг.

Теорема. Если модель получена из лишь за счет преобразований , то

где - количество удаленных (добавленных) вершин с метками и .

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

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

В данной работе мы остановились лишь на описании основных определений информационных моделей и рассмотрении самых простых случаев - моделях без циклов. Так как, управляющая программа, как правило, содержит большое количество операторов, которые могут находиться в циклах, то и информационная модель получаемая из нее, также будет представлять сложный объект с циклами. Поэтому решение задач информационных моделей является довольно сложной задачей. Но, стоит отметить, что решение таких задач, даже для некоторых классов информационных моделей может привести к значительному улучшению характеристик исходной управляющей программы.

Литература

1. К. Касперски Техника оптимизации программ. Эффективное использование памяти. БХВ-Петербург, серия: Мастер программ. 2003. 464с.

2. В.Н. Касьянов Оптимизирующие преобразования программ. -М. 1988, Наука. 334с.

3. А.А. Саркисян Машинонезависимая оптимизация исходных программ. -М. Радио и связь, 1985. -208с.

4. В.Е. Хачатрян Однородные логические графы. Прикладная математика. - Ереван; Изд. ЕГУ, 1981.

5. В.Е. Хачатрян, Ю.Г. Чашин Преобразования, сохраняющие перестановочность логических графов. Сборник научных трудов. БелГТАСМ. Белгород 1996. стр 10-15.

6. Ю.Г. Чашин Разработка нового подхода к оптимизации программ на этапе компиляции для микропроцессорных систем управления. Тезисы конференции «Новые информационные технологии в научных исследованиях и в образовании». Рязань. 2000. 76-78с.

Размещено на Allbest.ru