ПРИМЕНЕНИЕ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ ДЛЯ АНАЛИЗА ЭФФЕКТИВНОСТИ ОПТИМИЗАЦИИ УПРАВЛЯЮЩИХ АВТОМАТОВ

Автор: Перкин П.В.

Руководитель: Зеленева И.Я.

Источник: Наукові публікації кафедри комп'ютерної інженерії ДонНТУ

Год: 2011

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

Ключевые слова: управляющий автомат, распределенные вычисления.

Обзор способов оптимизации управляющих автоматов и анализ возможности распараллеливания процесса решения.

Как известно, одноуровневые схемы управляющих автоматов, реализованные на одной микросхеме БИС обладают максимальным быстродействием [1], но вместе с тем они также и наиболее дороги по затратам для аппаратной реализации. Это связано с дублированием входных и выходных переменных. Для оптимизации схемы, если критерием является минимум аппаратных затрат, используются многоуровневые схемы.

В настоящее время применяются три группы методов оптимизации логической схемы автомата [1 ]:

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

На базе одноуровневых автоматов, или по-другому Р-автоматов, строятся двухуровневые. Они делятся на 5 классов, в зависимости от метода структурной редукции[1]:

• Замена логических условий, порождающая MP-автоматы.
• Кодирование наборов микроопераций, порождающее PY-автоматы.
• Кодирование полей совместимых микроопераций, порождающее PD-автоматы.
• Кодирование строк ПСТ, порождающее PF-автоматы.
• Нестандартное представление термов ПСТ, порождающее PR-,TZ- и ZZ-автоматы.

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

Анализ особенностей распределенных вычислений и применения их для решения задач синтеза управляющих автоматов.

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

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

На рисунке 1 приведен последовательный алгоритм оптимизации и синтеза управляющих автоматов.

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

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

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

После оптимизации необходимо сгенерировать формальное описание модели. Для этих целей лучше всего использовать один из языков описания аппаратуры, например VHDL. Причем описание модели должно строго соответствовать рекомендациям для конкретного языка[3].

Для проверки правильности полученной модели выполняется верификация идентичности оригинальной модели по отношению к формальному описанию. Так как оба автомата имеют одинаковые входные данные, то есть количество символов входного алфавита и количество состояний, то и результаты работы при идентичных входных данных должны быть одинаковы. Необходимо проверить работу обеих моделей на всех наборах. Для этого можно использовать итерационный алгоритм, включающий в себя не более чем Ns*2^Nx итераций, где Ns - количество состояний, а 2^Nx - максимальное количество исходящих переходов[3].

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

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

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

Решение задачи распределенной обработки ГСА на кластере, с целью исследования структур УА и сбора статистических данных.

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

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

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

• для генерации модели на кластер одновременно передаются входные параметры каждой из ГСА. На кластере параллельно выполняется генерация модели.
• по завершении генерации на кластер передаются готовые модели, и проводится их оптимизация, причем она так же выполняется параллельно.
• на следующем шаге необходимо выполнить генерацию формального описания каждой из моделей. Выходными данными будут служить файлы, содержащие HDL-код каждой модели.
• так же нужно выполнить верификацию каждой из сгенерированных моделей, чтобы удостовериться в правильности результатов, которые планируется получить по окончании работы системы для анализа. Верификация является набором однотипных операций и её, также как и предыдущие шаги, рационально выполнять с помощью распределенных вычислений[2].
• последним этапом является синтез получившихся моделей. Синтез включает в себя реализацию оптимизированной модели в заданном базисе и получение интересующих характеристик.

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

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

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

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

Выбор способа хранения данных предполагается организовать в пользовательском меню.

Заключение

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

Список источников

• Баркалов А.А. Синтез устройств управления на программируемых логических устройствах// А.А. Баркалов. – Донецк. : ДонНТУ, 2002. – 262с.
• Баркалов А.А. Синтез управляющих автоматов с использованием распределенных и параллельных систем / А.А. Баркалов, И.Я. Зеленева, А.А. Гриценко // Радіоелектроніка, управління, інформатика. – 2010. – № 22. – С. 128-134. – ISSN 1607-3274
• Гриценко А.А. Методика исследования способов оптимизации управляющих автоматов в базисе ПЛИС FPGA// Гриценко А.А., Зеленева И.Я., Сероштан С.Ю., Татолов С.Р. – Донецк: ДонНТУ.