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

Оглавление

1. Введение

2. Цели и задачи

3. Научная новизна и практическая ценность

4. Существующие исследования

5. Обзор платформы Eclipse

6. О методе элементаризации линейных последовательностей

7. Текущие и планируемые результаты по теме

8. Выводы

9. Литература

Введение

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

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

Семантический разрыв передачи знаний между стадиями технического дизайна и написания кода заключается в том, что разработчик реализует систему в соответствии со своим пониманием технического задания [1].

Уже давно существует язык моделирования UML, который облегает работу программиста, помогая ему разбить структуру программы на упрощенные структуры и представить, как эти структуры будут взаимодействовать. Именно UML представляется полезным и при проектировании. Он позволит стандартизировать разные представления об одних и тех же объектах моделируемой системы.

Есть один большой недостаток UML – это статическая картинка, чертеж модели, «безжизненная сущность». В последнее время растет спрос на «запускаемый» UML, что привело к появлению такого направления в программной инженерии как «проектирование на базе моделей» (Model-Driven Design). Основной идеей такого подхода является независимое рассмотрение моделей, создаваемых при проектировании системы, от деталей их реализации на конкретной программно-аппаратной платформе. Проектирование на базе моделей должно привести к появлению универсальных графических языков программирования [1].

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

Микросхемы, программируемые пользователем, открыли новую страницу в истории современной микроэлектроники и вычислительной техники. Вследствие этого БИС/СБИС, предназначенные для решения специализированных задач, стандартной продукцией электронной промышленности со всеми вытекающими из этого положительными последствиями: массовое производство, снижение стоимости микросхем, сроков разработки и выхода на рынок продукции на их основе.

В данный момент существует множество классов ПЛИС, но наиболее часто используются следующие ИС: SPLD, CPLD, FPGA. [3]

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

Связующим звеном между конечным автоматом и аппаратной реализацией автомата является ПЛИС.

В настоящее время рост использования ПЛИС для реализации автоматов приостанавливается дороговизной микросхем. Поэтому конструкторам-программистам приходится решать задачу уменьшения аппаратных затрат (в данном случае – площадь кристалла ПЛИС или число вентилей) с большими затратами времени разработки.

Существует множество методов уменьшить аппаратные затраты путем использования дополнительных элементов (например мультиплексоров, ППЗУ), которые придают алгоритму гибкость автомата с программируемой логикой (АПЛ) и скорость автомата с жесткой логикой (АЖЛ).

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

Цели и задачи

•  Анализ современного элементного базиса и существующих методов синтеза управляющих автоматов на ПЛМ, ПЛИС для определения способов уменьшения стоимости логических схем;

•  Исследование эффективности выбранных методов

•  Выбор среды разработки UML редактора с поддержкой «запускаемого» UML

•  Тестирование программного продукта на удобство интерфейса

•  Исследование эффективности работы программного продукта по минимизации аппаратурных затрат для существующих ПЛИС.

Научная новизна и практическая ценность

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

Существующие исследования

Об актуальности темы конечных автоматов (УА) свидетельствует наличие редакторов FSM (finite state machine) в таких продуктах как AHDL и Riviera. Наиболее распространенными среди языков описания аппаратуры являются языки VHDL и Verilog. Однако непосредственная реализация управляющих автоматов на этих языках является трудоемким процессом. Поэтому в состав многих зарубежных САПР были включены специальные инструменты, позволяющие упростить разработку управляющих автоматов. Так в состав САПР Active - HDL фирмы Aldec включен модуль FSM. Этот модуль обладает многофункциональным графическим интерфейсом, для описания управляющих автоматов. Однако модуль FSM обладает рядом недостатков. В частности, форма записи управляющего автомата требует знания языка HDL. Подобным образом организованы системы проектирования управляющих автоматов и в других САПР.

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

Сравнительные результаты параметров синтезированных устройств при одинаковых исходных граф-схемах, реализованные средствами FSM A - HDL (finite state machine) и посредством структурного описания результирующей схемы, показывают определенное уменьшение числа используемых элементов FPGA при реализации вторым способом.

Результаты синтеза(для ПЛИС Lattice ispGDX 2 Part LX 256 V):

Недостаток FSM-редактора A - HDL – генерация программного кода в поведенческом стиле, что делает невозможным предсказать результат синтеза. Структурное же описание схемы, полученной в результате тривиальной реализации, дает возможность предсказания результатов еще до синтеза – на этапе генерации программного кода, что дает возможность генерировать код для кристалла или числа вентилей FPGA заданной размерности.[4]

Что касается UML редакторов для конечных автоматов, то одной из таких разработок является исполняемый графический язык на основе SWITCH-технологий и UML-нотации – UniMod, который описывает поведение объекта с помощью графов переходов структурных автоматов с нотацией, а графы переходов строятся с помощью нотации диаграммы состояний UML.

Пакет UniMod обеспечивает разработку и выполнение автоматно-ориентированных программ. Он позволяет создавать и редактировать UML - диаграммы классов и состояний, которые соответствуют схеме связей и графу переходов, и поддерживает два типа реализации — на основе интерпретации и компиляции. В первом случае имеется возможность:

• преобразовывать диаграммы в формат XML;

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

Во втором случае диаграммы непосредственно преобразуется в код на целевом языке программирования, который впоследствии компилируется и запускается.

Проектирование программ с использованием пакета UniMod предполагает следующий подход: логика приложения описывается структурным конечным автоматом, заданным в виде набора указанных выше диаграмм, построенных с использованием UML-нотации. Источники событий и объекты управления задаются кодом на целевом языке программирования. [1]

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

Еще одним UML редактором является UMLet построенный группой разработчиков на базе платформы Eclipse, разработка охватывает весь UML, что весьма неудобно для данной обсуждаемой темы.

Обзор платформы Eclipse

Платформа Eclipse (или просто "Платформа", когда нет риска неоднозначности) разработана и построена для выполнения следующих требований:

• Поддержка конструирования разнообразных инструментов для разработки приложений.
• Поддержка неограниченного ряда поставщиков инструментария, включая независимых поставщиков программного обеспечения (ISV).
• Поддержка инструментов в манипулировании произвольным типом содержимого (т.е., HTML, Java, C, JSP, EJB, XML и GIF).
• Обеспечение "бесшовной" интеграции инструментов c различными типами содержимого и разными поставщиками инструментария.
• Поддержка сред разработки приложений как с графическим интерфейсом пользователя (GUI), так и без GUI.
• Выполнение на широком спектре операционных систем, включая Windows и Linux .
• Использование популярности языка программирования Java для написания инструментария. [5]

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

Рисунок 1 показывает главные компоненты и API Платформы Eclipse.

Рисунок 1. Архитектура Платформы Eclipse.

Подключение (plug-in) - наименьшая единица функциональности Платформы Eclipse, которая может быть разработана и поставлена отдельно. Обычно небольшой инструмент пишется как одно подключение, тогда как функциональность сложного инструмента разносится по нескольким подключениям. За исключением небольшого ядра, называемого Средой Выполнения Платформы (Platform Runtime Environment), вся функциональность Платформы Eclipse находится в подключениях. [5]

Подключения кодируются на языке Java. Типовое подключение состоит из кода Java в библиотеке JAR, нескольких доступных только для чтения файлов и других ресурсов, таких, как изображения, web-шаблоны, каталоги сообщений, библиотеки в кодах аппаратной платформы и т.д.. Некоторые подключения вообще не содержат кода. Одним из примеров такого подключения является подключение, которое предоставляет онлайновую помощь в форме страниц HTML. Библиотеки кодов одного подключения и информация, доступная только для чтения, располагаются вместе в каталоге файловой системы или по базовому URL на сервере. Этот механизм также предохраняет подключение от составления его из нескольких разных фрагментов, каждый из которых находится в собственном каталоге или по собственному URL. Это также и механизм для поставки раздельных языковых пакетов для интернационализированных подключений.

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

• SWT - набор элементов и графическая библиотека, интегрированные с оконной системой базовой платформы, но независимые от API ОС.
• JFace - инструментальное средство UI, реализованное при помощи SWT, которое упрощает общие задачи программирования UI. [5]

О методе элементаризации линейных последовательностей

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

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

Применение элементарицации вместе с формированием классов псевдоэквивалентных ЛПС порождает PtYC4 - автомат с преобразователем кодов ЛПС (рис. 2) или PeYC4-автомат с оптимальной кодировкой ЛПС.

В PtYC4-автомате Р-подсхема формирует только функции Ф, то есть коды элементарных ЛПС. Ввиду того, что адресация компонентов, которые входят к ЛПС, всегда начинается с нулевого адреса, на счетчик СТ подается только сигнал Inc. В другом схема аналогичная приведенной на рис.2.

Применение метода элементарицации к какой-нибудь ГСА приводит к формированию множества элементарных ЛПС Пае={a1 ,... a Ge} и является целесообразным только в случае выполнения уравнения Re=R1, где Re = ]log 2 Ge[. В работе предложенные правила формирования множества входов элементарных ЛПС Ie(Г):

Правило 3: Состояние аm является единственным входом ЛПС Ag, то есть am принадлежит Ie(Г), если вход вершины, отмеченной состоянием am, связан:

•  с состоянием а0 ;

•  с условной вершиной;

•  с вершиной, отмеченной состоянием aj, где aj не принадлежит Ag;

•  с вершиной, отмеченной состояниями aj, где aj не принадлежит Ag и для пары компонентов <aj ,am> ЛПС a g выполняется отношение К(aj)>K(am).

Правило 4: Если начальная вершина ГСА связана со следующей условной вершиной, то а0 не принадлежит Ie(Г), в противоположном случае а0 не принадлежит Ie(Г).

Рис.2. Структура PtYC 4 -автомата Мура

Разработанная методика синтеза PtYC4-автомата Мура включает этапы, аналогчные методике синтеза PtYC3-автомата, но на первом этапе выполняется разбивка множества состояний исходной ГСА на элементарные ЛПС, что влияет на выполнение всех следующих этапов.

Если для некоторых ГСА есть возможность оптимальной кодировки ЛПС, то аппаратурные расходы в соответствующей схеме автомата будут еще меньше за счет отсутствия преобразователя кодов. Предложенный метод синтеза PеYC4-автомата, основанный на оптимальной кодировке ЛПС, содержит те же этапы, что и метод синтеза PeYC3-автомата, но с предыдущей элементаризацией ЛПС.

Структура PеYC4-автомата отличается от структуры PtYC4-автомата отсутствием подсхемы преобразователя кодов Pz, за счет чего уменьшаются аппаратурные расходы в схеме автомата. [6]

Текущие и планируемые результаты по теме

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

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

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

Рисунок 3 - Структура разрабатываемой САПР

Разрабатываемая система должна состоять из следующих частей:

•  Графический редактор, который реализует возможность графического отображения, редактирования и создания требуемой граф-схемы (FSM).

•  Компилятор, который дает возможность текстуального набора графа и приведение текстуального представления во внутренний язык программы (XML , XMI , или др.).

•  Генератор кода с различными оптимизаторами, которые преобразуют внутренний код графа в конкретную (Мура или Мили) реализацию автомата. [4]

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

Рисунок 4 - Этапы разработки УА

Выводы

Результатом работы будет программное обеспечение, построенное на платформе Eclipse с открытым кодом и реализующая генерацию кода на языке HDL. Программный код будет сгенерирован с учетом существующих алгоритмов оптимизации управляющих автоматов и специфицирован под конкретную ПЛИС. Входными параметрами для ПО будет являться UML схема реализации управляющего автомата.

При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение: январь 2007 года. Полный текст работы и все материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Литература

1)  Гуров В.С., Мазин М.А., Нарвский А.С., Шалыто А.А. UniMod: метод и средство разработки реактивных объектно-ориентированных программ с явным выделением состояний//МЕТОДЫ И СРЕДСТВА ОБРАБОТКИ ИНФОРМАЦИИ. – Московский государственный университет им. М.В. Ломоносова, М. – 2005. – С 361-366.

2) Ю.Г. Карпов Теория автоматов. – С-Пб., Питер, 2002. – 206 с.

3) Е.А. Суворова, Ю.Е. Шейнин Проектирование цифровых систем на VHDL. – С-Пб., БХВ-Петербург, 2003. – 560 с.

4)  Бережок А.Ю. Система автоматического проектирования в среде A - HDL устройств, представленных конечными автоматами//Інформатика та комп'ютерні технології – ДонНТУ, Донецк – 2005

5) Часть 1. Технический обзор Платформы Eclipse – http://khpi-iip.mipk.kharkiv.edu/library/extent/prog/ETO/I.html

6)  Зеленева И.Я. – «Методы синтеза многоуровневых структур управляющих автоматов на программируемых логических устройствах» – диссертационная работа.