RUS | UKR | ENG || ДонНТУ > Портал магистров ДонНТУ
Магистр ДонНТУ Черныш Игорь Игоревич

Черныш Игорь Игоревич

Факультет: Компьютерных наук и технологий
Кафедра: Компьютерной инженерии

Тема выпускной работы:

Исследование структур композиционных микропограммных устройств управления с общей адресацией в базисе стандартных БИС

Научный руководитель: Зеленева Ирина Яковлевна

Материалы по теме выпускной работы: Об авторе | Библиотека | Ссылки | Отчет о поиске | | Индивидуальный раздел

Реферат по теме выпускной работы

Введение

На сегодняшний день просматривается мощная тенденция в сторону развития web-технологий. Одной из главных задач этого направления является перенос функциональных блоков обработки на сервер, а также максимальное упрощение интерфейса пользователя [20, 21]. В результате пользователю предоставляется система, в которой простые команды становятся следствием выполнения сложных алгоритмов, требующих затраты большего количества ресурсов. Эти затраты полностью переносятся на сервер, что практически не сказывается на ресурсах ПК. Java-Applet используются для предоставления интерактивных возможностей веб-приложений, которые не могут быть предоставлены HTML [22, 23]. Так как байт-код Java платформонезависим, то Java-Applet могут выполняться с помощью плагинов браузерами многих платформ, включая Microsoft Windows, UNIX, Apple Mac OS и GNU/Linux. Такие программы с открытым исходным кодом, как applet2app, могут быть использованы для преобразования апплета в самостоятельные программы на Java или исполняемые файлы Linux и Windows [22, 23].

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

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

Одним из методов реализации устройства управления цифровой системы является использование модели композиционного микропрограммного устройства управления (КМУУ) [24, 25].

Цель и задачи работы

Актуальность темы

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

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

Active-HDL в своей программной реализации имеет средства для создания и редактирования FSM-структур (finite state machine, конечный автомат). Основная идея автоматной реализации – это описание процесса в виде граф-схемы с генерацией программного кода на языке VHDL или Verilog, с последующей возможностью синтеза полученного кода на заданной серии ПЛИС.

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

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

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

Предполагаемая научная новизна

Научная значимость исследования для нашего проекта заключается в определении наиболее оптимального управляющего автомата для реализации заданного алгоритма. Алгоритм задается в виде граф-схемы (ГСА). Интерфейс пользователя содержит в себе все графические компоненты, из которых в процессе обработки строится ГСА. Параллельно с этим процессом генерируется XML-файл, содержащий информацию об алгоритме(количество операторных и условных вершин, структура ГСА), который в итоге пересылается на сервер. На сервере в соответствии со статистикой в базе данных выполняется анализ XML-файла и подбирается управляющий автомат наиболее подходящий для реализации предложенного пользователем алгоритма. В ответ с сервера пользователю приходит ссылка на VHDL-файл, являющийся моделью выбранного типа УА.

Для интерпретации ГСА Г можно использовать модель КМУУ с общей памятью [29]. (Рис.1).

Структурная схема КМУУ с общей памятью

Рисунок 1 — Структурная схема КМУУ с общей памятью.

Это устройство функционирует следующим образом. По сигналу Start в счётчик СТ загружается нулевой адрес первой микрокоманды микропрограммы, соответствующей ГСА Г. Одновременно триггер выборки TF устанавливается в единичные состояния (Fetch=1). Очередная микрокоманда (МК) выбирается из управляющей памяти СМ. Если эта МК соответствует вершине bq Og, то одновременно с набором микроопераций Y(bq) формируется переменная y0=1. Если y0=1, то содержимое СТ увеличивается на 1 по сигналу Clock это соответствует режиму (3), то есть переход происходит внутри некоторой операторной линейной цепи (ОЛЦ) g С. Если bq=Og, то переменная y0=0. В этом случае комбинационная схема СС формирует функции возбуждения СТ.

Ф=Ф(Т,Х) необходимые для загрузки в СТ адреса входа некоторой ОЛЦ. Адрес устанавливается в СТ по сигналу Clock. Если , где bE — конечная вершина ГСА Г, то формируется переменная yE=1. Если yE=1, то триггер TF устанавливается в нулевое состояние (Fetch=0). В этом случае выборка микрокоманд из СМ прекращается и КМУУ U1 прекращается.

Очевидно, данное КМУУ является автоматом мура, т.к. выходные сигналы y0, yE и Y зависят только от содержимого СТ. При этом адрес микрокоманды может рассматриваться, как код состояния автомата. Однако в отличии от классического автомата Мура, память КМУУ реализуется на счётчике.

Планируемые практические разультаты

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

Система автоматизированного проектирования структуры управляющего автомата (САПР СУА) делится на две части: клиентская и серверная. Такой подход наиболее оправдан с экономической точки зрения и сточки зрения вычислительных затрат. Сервер, который берет на себя функцию преобразования пространственного представления граф-схемы алгоритма в автоматное представление и, в конечном счете, в результирующий VHDL-код. Клиент, имея графический интерфейс, позволяет ввести граф-схему алгоритма в графической форме и преобразовать ее в пространственную.

Сервер имеет возможность динамического обновления или добавления методов генерации VHDL-кода.

В результате планируется получить web-приложение, которое будет реализовано с использованием технологии Java-Applet. Эта технология позволяет использовать приложение без необходимости его установки, а просто набрав определенный URL в строке адреса браузера. Технология Java-Applet является кросплатформенной. Таким образом пользователь получает возможность работы непосредственно в окне браузера в любой операционной системе.

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

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

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

В результате тестирования работы программы были получены следующие данные. В качестве входного параметра были взятии три граф-схемы: граф-схема на 5 состояний, 3 входных сигнала, 6 выходных сигналов, проверки условия не повторяются; граф-схема на 15 состояний, 3 входных сигнала, 6 выходных сигналов, проверки условия не повторяются; граф-схема на 35 состояний, 3 входных сигнала, 6 выходных сигналов, проверки условия не повторяются.

Синтез устройств на интегральной схеме Xilinx CoolRunner XPLA3:

Таблица 1 — Результат синтеза



Рисунок 2 — Диаграмма сравнения

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

Результаты, полученные с помощью САПР СУА, показывают, что средства синтеза имеют достаточно развитые алгоритмы поиска во входном VHDL-коде структур конечных автоматов. А некоторые типы ПЛИС имеют вентили, позволяющие упростить аппаратную структуру генерируемого кода. Благодаря чему поведенческий метод не уступает тривиальному. Но это верно не для всех типов ПЛИС.

Обзор существующих разработок по теме

Глобальный

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

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

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

В ходе проведения исследования было установлено, что генерируемое модулем FSM поведенческое описание управляющего автомата реализуется средствами синтеза ( Synplify ) как автомат Мура с унарным кодированием состояний. Достоинством такой реализации является повышенное быстродействие, недостатком большие аппаратные затраты.

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

Таким образом, достоинствами этого метода, является меньшая сложность функций возбуждения (особенно проявляется при уменьшении разветленности автомата) и соответсвенно более высокое быстродействие автомата. Недостатками являются значительно большое количество используемых триггерных схем (особенно проявляется при увеличении состояний графа : R ~ M , при унарном кодировании; R ~ log 2 M , при бинарном кодировании ); и большая аппаратная затратность схем формирования выходных сигналов (при отсутствии в ПЛИС элементов XOR ).

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

Рисунок 3 — Классификация методов оптимизации автоматов

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

Одним из наиболее перспективных способов разрешения этой проблемы является использование для проектирования аппаратных систем, средств основанных на ранее разработанных средствах проектирования сложных систем для программного обеспечения, таких как использование управляемой моделями архитектуры (MDA–Model-Driven Architecture) и унифицированный язык моделирование ( UML–Unified Modeling Language ).

MDA была предложена группой OMG (Object Management Group) в 2000 году. Главной идеей MDA является описание сложных систем в виде набора моделей, стоящих на различных уровнях абстракции, относительно друг друга, и возможность преобразования моделей одного уровня в модели другого уровня абстракции. Результатом таких преобразований является получение реализаций независимой от платформы модели, для различных платформ.

В настоящее время существует множество сред проектирования, поддерживающих управляемую моделями архитектуру и язык UML для описания моделей, которые ориентированы на разработку программного обеспечения (Eclipse, NetBeans, JBuilder_X, Poseidon, ArgoUML и т.д.). Многие из этих сред являются расширяемыми продуктами (т.е. к ним можно подключать дополнительные модули сторонних разработчиков), поэтому было принято решение построить САПР для управляющих автоматов на базе одной из имеющихся сред проектирования. В качестве базовой среды был выбран JBuilder 2006.

Локальный

К подобным разработкам можно отнести работы следующих Магистров ДонНТУ:

Ссылки на их работы представлены в этом разделе в перечне источников в подразделе работ магистров прошлых лет

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

Рассмотри пример синтеза КМУУ по ГСА Г1 (рис.4.)

Исходная ГСА Г1

Рисунок 4 — Исходная ГСА Г1

Используя методы из [4], можно получить множество С={a1, a2, a3}, где d1={b1,b2} I =b1, I =O1=b2; a2={b3, b4, b5}, I =b3, I =b4, O2 = b5; a3=={b6, b7, b8}, I =b6, O3=b8. Итак, G=3, M=8, R=3, T={T1, T2, T3}, ={D1, D2, D3}, X={x1, x2}, L=2, Y={y1, y2, y3, y4, y5, y6}, N=6, I( )={b1, b2, b3, b4, b6}, O( )={b2, b5, b8}, C1={a1, a2}.

Естественная адресация микрокоманд [3] позволяет получить следующие адреса: A(b1)=000, A(b2)=001, …, A(b8)=111. Формулы перехода строятся для выходов ОЛЦ , то есть для О1 и О3. Эта система имеет следующий вид: O1 > x1 b3 x2 b4 b6.

Система имеет H=4 терма, следовательно, таблица переходов КМУУ имеет H=4 строки (Табл.1).

Таблица 1 — Таблица переходов КМУУ

Таблица переходов КМУУ

Из таблицы 2 формируется система формул переходов, имеющая следующий вид для U1 (Г1):

Содержимое управляющей памяти КМУУ показано в Табл.2, имеющей М=8 строк.

Таблица 2 — Содержимое управляющей памяти КММУ

Содержимое управляющей памяти КММУ

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

Содержимое XML файла

Рисунок 5 — Содержимое XML-файла

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

Процесс разработки УА на ПЛИС изображен на рисунке 6

Рисунок 6 — Процесс разработки УА на ПЛИС

Анимация: 8 кадров, вес — 47492 байта, размер — 760х241

Заключение

В результате выполнения задачи получается VHDL–файл и статистика, по которой можно наглядно определить наиболее оптимальные архитектуры УА для реализации алгоритмов управления, заданных пользователем. Так как приложения реализовывается на Java с использованием технологии Java-Applet, в итоге получается кросплатформенное приложение, т.е. приложение, работающее в любой операционной системе.

Источники

    Работы магистров прошлых лет с аналогичными темами

  1. Бережок Алексей Юрьевич:
  2. Боровлев Артем Сергеевич:
  3. Войтенко Сергей Аркадьевич:
  4. Лаврик Александр Сергеевич:
  5. Мирошкин Александр Николаевич:
  6. Данилов Максим Васильевич:
  7. Костянок Тятьяна Николаевна:
  8. Силуанов Антон Федорович:
  9. Скоропад Александр Сергеевич:
  10. Цололо Сергей Алексеевич:
  11. Шишко Сергей Николаевич:

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

  12. Университет Аугзбурга
  13. Факультет компьютерных наук Дрезденского технического университета
  14. Лаборатория систем управления университета Карлсруэ (Германия)
  15. Израильская ассоциация автоматического управления (IAAC)
  16. Центр исследования комплексных автоматизированных систем (Болонский университет, Италия)
  17. Зеленогурский университет (Польша)
  18. Владимирский государственный университет
  19. Московский Государственный Институт Электронной Техники

    Печатные источники и ссылки

  20. Кей С. Хорстман, Гарри Корнелл «Java 2. Библиотека профессионала»;
  21. Г. Шилдт «Полный справочник по Java»;
  22. Баркалов А.А. Микропрограммное устройство управления как композиция автоматов с программируемой и жёсткой логикой. Автоматика и вычислительная техника, 1983, №4.-с.36-41.
  23. Barkalov A.A., Titarenko L.A. Synthesis of operational and control automate. — Donets’с: Untech, 2005.-25pp.
  24. Maxfield C. The Design Warrior’s Guide for FPGA.-Amsterdam: Elsevier, 2004.-541 p.
  25. Smith M. Application – Specific Integrated Circuits. — Boston: Addison — Wesley, 1997.-836 pp.
  26. Baranov S. Logic Synthesis for Control Automate. — Boston: Kluwer Academic Publishers, 1984.-312pp.
  27. lexvit.dn.ua / Исследование структур управляющих автоматов с элементаризацией линейных последовательностей состояний / [Электронный ресурс] — режим доступа: http://www.lexvit.dn.ua/arhiv/articles.php?art_id=ua_java1
ДонНТУ > Портал магистров ДонНТУ || Об авторе | Библиотека | Ссылки | Отчет о поиске | | Индивидуальный раздел