Методика исследования способов оптимизации управляющих автоматов в базисе ПЛИС FPGA
Алгоритм исследования метода оптимизации управляющего автомата. Генерация формального описания. Доказательство эквивалентности моделей автоматов. Анализ отчетов верификации и синтеза. Описание метода, основанного на замещении символов входного алфавита.
| Рубрика | Коммуникации, связь, цифровые приборы и радиоэлектроника |
| Вид | автореферат |
| Язык | русский |
| Дата добавления | 01.07.2018 |
| Размер файла | 204,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
УДК 004.2
Методика исследования способов оптимизации управляющих автоматов в базисе ПЛИС FPGA
Гриценко А.А., Зеленева И.Я., Сероштан С.Ю., Татолов С.Р.
Донецкий национальный технический университет
Кафедра компьютерной инженерии
E-mail: anthony.grytsenko@gmail.com
Аннотация
В данной статье предложена методика, позволяющая исследовать известные способы оптимизации управляющих автоматов для базиса современных ПЛИС FPGA. Также в статье представлены результаты апробации этой методики.
Ключевые слова: управляющий автомат, FPGA
Введение
В настоящее время известно большое количество методов оптимизации управляющих автоматов, которые, в частности, рассмотрены в работах Баркалова А.А. [1, 2]. Отметим, что управляющие автоматы (УА) имеют широкое применение и, как следствие, они реализуются в различных базисах.
На данный момент один из наиболее распространенных базисов это ПЛИС, которые относятся к классу FPGA [3]. Использование данного базиса было актуально и раньше [3], на что указывают соответствующие разделы в [1] и [2]. Однако сейчас значимость ПЛИС FPGA возросла, что подтверждается, в частности, более детальным их рассмотрением в [4].
Исходя из этого, можно сформулировать проблему, которая заключается в адаптации ранее разработанных и апробированных методов оптимизации схем управляющих автоматов к базису современных ПЛИС FPGA. Проблема адаптации является достаточно сложной, если учитывать, что в каждом конкретном случае она имеет специфичное решение. Тем не менее, при подготовке к решению данной проблемы можно выделить процесс, который необходимо выполнять независимо от того, какой именно метод адаптируется в конкретном случае. Речь идет об исследовании результатов применения конкретного метода оптимизации для базиса ПЛИС FPGA. Соответственно, в данной статье предлагается методика для проведения такого рода исследования.
Отметим, что процесс исследования является достаточно сложным в том отношении, что требует применения большого количества различных технических средств [3], поэтому в статье этот аспект рассматривается достаточно подробно.
Другим важным замечанием является то, что предлагаемая методика разрабатывалась таким образом, чтобы обеспечить возможность для её использования в рамках параллельных систем. В [5] были рассмотрены вопросы, которые касались синтеза управляющих автоматов с использованием параллельных систем. Предложенные в [5] структуры и алгоритмы могут быть адаптированы для совместного использования с предложенной методикой.
Постановка задачи
Под понятием методики исследования в данной статье будем понимать совокупность взаимосвязанных составляющих. Первая составляющая - это множество видов деятельности, которые необходимы для проведения полного и достоверного исследования, а также порядок их выполнения. В свою очередь, вторая составляющая - это комплекс технических средств, требуемых для осуществления определенных ранее видов деятельности.
Поэтому, разработка методики исследования предполагает решение двух подзадач:
1. Декомпозиция процесса исследования на множество отдельных шагов (или же видов деятельности) с определением для каждого из них входных и выходных данных.
2. Определение набора технических средств, необходимых для выполнения всех видов деятельности и выработка способа их организации в единый комплекс.
Немаловажным аспектом является и оценка возможностей применения предлагаемой методики в реальных условиях. Следовательно, третья подзадача - апробация возможностей практического применения методики исследования.
Алгоритм исследования
В основу предлагаемой методики исследования положен алгоритм (рис. 1), который предполагает выполнение шести различных видов деятельности.
Вначале выполняется генерация исходной модели. Способ построения модели может разниться в зависимости от того, какой именно способ оптимизации исследуется, но, базовая её структура может оставаться неизменной. Генератор модели должен позволять выполнить точную настройку процесса генерации по нескольким параметрам. В частности, это должно быть количество состояний, количество символов входного и выходного алфавитов и т.д.
Далее выполняется оптимизация исходной модели. При этом следует учитывать, что в процессе оптимизации модель может расширяться за счет элементов, которые свойственны скорее цифровой технике, чем теории конечных автоматов. Оптимизированная модель будет представлять собой видоизмененную модель УА, которая взаимосвязана с набором моделей, описывающих необходимые цифровые устройства.
Рисунок 1 - Алгоритм исследования метода оптимизации управляющего автомата (диаграмма деятельности UML)
Далее выполняется генерация формального описания моделей. Формальное описание может быть выполнено с использованием одного из языков описания аппаратуры, например, VHDL или Verilog. Данное описание должно соответствовать общепринятым рекомендациям для конкретного языка [6, 7]. Как минимальную оценку качества формального описания УА можно рассматривать его корректное распознавание средствами синтеза.
Следующий вид деятельности это верификация эквивалентности исходной модели её формальному описанию, а также эквивалентности моделей. Доказательство эквивалентности моделей автоматов можно выполнить следующим образом. Примем, что оба управляющих автомата имеют различных состояний и символов входного алфавита. В таком случае, для каждого состояния существует не более чем исходящих переходов. Далее, примем, что существует возможность установки состояния без необходимости изменения описания, что устраняет возможность привнесения дополнительной ошибки. Следовательно, для доказательства эквивалентности двух формальных описаний потребуются не более чем итераций. В этом случае актуальным является вопрос использования параллельных систем [5], поскольку речь идет о большом количестве однообразных действий.
Одновременно с верификацией необходимо выполнить синтез формальных описаний обеих моделей. На данном этапе важным аспектом является выбор базиса, т.е. конкретного семейства или определенной ПЛИС, и задание набора специальных параметров, в частности, способа кодирования состояний, глобальной стратегии оптимизации и т.д.
Последний вид деятельности это анализ отчетов верификации и синтеза. Алгоритм на рис. 1 позволяет обработать только одну модель управляющего автомата. В то же время, для сбора приемлемых статистических данных нужно выполнять обработку нескольких моделей, которые обладают схожими характеристиками. На данной стадии выполняется анализ всех полученных данных.
Структура комплекса программных средств
Для выполнения предложенного алгоритма требуется сложный комплекс технических средств, который состоит из разнородных компонент (рис. 2).
Генератор исходной и оптимизированной моделей и генератор формального описания могут реализовываться с использованием одного из современных языков программирования.
Основным критерием для выбора средства синтеза можно считать конкретную модель ПЛИС или же конкретное семейство ПЛИС, в базисе которого выполняется исследование. В частности, если используется семейство ПЛИС Altera Stratix III, то необходима САПР Altera Quartus II, а для семейства Xilinx Spartan 6 необходима САПР Xilinx ISE.
Средство верификации можно выбирать исходя из рыночных предпочтений. Причем, какая-либо связь между средством верификации и средством синтеза может отсутствовать. В частности, одной из наиболее распространенных сейчас САПР для моделирования, которую можно использовать и для верификации, является Mentor Graphics ModelSim.
Перечисленные средства по умолчанию не взаимосвязаны. Поэтому, при разработке комплекса программного обеспечения требуется средство для управления разными САПР, а также осуществления сбора и обработки данных, что предполагает и возможность создания оболочки вокруг алгоритма исследования, необходимой для сбора статистически значимых данных, что отмечалось в предыдущем разделе.
Рисунок 2 - Структура комплекса программного обеспечения
На данный момент в качестве такого средства может выступать язык Tcl\Tk, который, для некоторых САПР (например, Altera Quartus II или Mentor Graphics ModelSim), является основным средством автоматизации.
Все перечисленные и показанные на рис. 2 компоненты являются обязательными. Но, комплекс также может включать дополнительные компоненты. В частности, на рис. 1 было показано, что определенные виды деятельности могут выполняться параллельно. Кроме того, отдельные виды деятельности, например, верификация, сами по себе обладают свойствами параллельных алгоритмов. Поэтому, можно использовать компоненты, обеспечивающие ту или иную степень параллелизма [5].
Структура, приведенная на рис. 2, является масштабируемой. То есть, она позволяет выполнять исследование нескольких различных методов оптимизации. При этом алгоритм, приведенный на рис. 1, применяется к множеству пар моделей, в каждой из которых первой является исходная модель, а второй - одна из оптимизированных моделей.
Исследование метода замещения символов входного алфавита
управляющий автомат верификация синтез
Метод оптимизации, основанный на замещении символов входного алфавита, описан в [1] и [2]. Его идея заключается в замещении исходного входного алфавита новым , который включает меньшее количество символов (то есть ), определяемое максимальным количеством символов, необходимым для управления любым переходом внутри автомата.
Генератор модели УА был разработан так, чтобы обеспечить возможность изменения следующих параметров: - количество символов входного алфавита, - максимальное количество символов входного алфавита на переход, - количество символов выходного алфавита, - максимальное количество символов выходного алфавита на переход и - это количество состояний управляющего автомата.
Процесс оптимизации приводит к необходимости создания дополнительной модели коммутирования. Она может быть описана как ассоциативный массив, где ключом является состояние УА, а значениями - другие ассоциативные массивы, для которых ключом является символ входного алфавита, а значением - символ замещающего алфавита: . Данная модель является достаточно простой и дополняет модель автомата.
Верификация формального описания моделей выполнялась с использованием САПР Mentor Graphic ModelSim. Для работы с "внутренними" (т.е. недоступными непосредственно через внешний интерфейс) сигналами использовались сценарии на Tcl\Tk [8]. Хотя текущий стандарт VHDL [9] позволяет работать с такими сигналами, он поддерживается средствами моделирования лишь частично. Поэтому генерация тестовых сценариев не на языке, который использовался для формального описания управляющего автомата, в данном случае является необходимой, хотя и нежелательной.
В качестве базиса были выбраны современные высокопроизводительные ПЛИС FPGA семейства Altera Stratix III [10]. Одна из основных архитектурных особенностей этих ПЛИС то, что они построены на генераторах функции от шести аргументов. Это дает возможность эффективно реализовывать сложные схемы коммутирования, характерные для исследуемого метода оптимизации.
В соответствии с базисом, в качестве САПР синтеза использовалась Altera Quartus II [11]. Причем, для управления данной САПР, как и в случае с Mentor Graphics ModelSim, был использован язык Tcl\Tk.
Во избежание излишней сложности язык Tcl\Tk использовался также для выполнения сбора, обработки и анализа отчетов САПР моделирования и синтеза.
Для получения статистически корректных данных для каждого набора характеристик выполнялась генерация десяти разных моделей управляющих автоматов. После выполнения исследования всех этих моделей, результаты упорядочивались в зависимости от полученных выгоды или потерь. После этого лучший и худший результаты отбрасывались, а остальные усреднялись.
На рис. 3 приведены результаты, полученные для моделей, обладающих следующими характеристиками: , , , , .
Согласно результатам на рис. 3 можно сделать вывод об эффективности применения данного метода в базисе ПЛИС семейства Stratix III.
Рисунок 3 - Пример результатов исследования метода замещения символов входного алфавита (параметры , , , , базис - Altera Stratix III)
Заключение
В статье была предложена методика, позволяющая выполнять исследование способов оптимизации схем управляющих автоматов, которая включает две составляющие: алгоритм проведения исследования и структуру комплекса технических средств, которые необходимы для его проведения.
Алгоритм исследования представляет собой последовательность шагов, выполнение которых позволяет охватить все необходимые технологические процессы, которые связаны, с одной стороны, с применением метода оптимизации, а с другой - с работой в базисе ПЛИС FPGA. Предложенный алгоритм разработан таким образом, чтобы он мог быть реализован с использованием параллельных вычислительных систем, что является важным фактором.
Предложенная в статье структура комплекса технических средств охватывает полный набор программных средств, необходимых для выполнения рассмотренного алгоритма. При этом, описание структуры включает достаточно детальный анализ реальных САПР, которые могут быть использованы. Также рассмотрены процессы автоматизации работы комплекса с использованием специализированных языков высокого уровня.
Кроме того, в данной статье показана апробация предложенной методики для одного из достаточно известных методов оптимизации. В данном разделе освещен ряд практических вопросов использования методики. Также апробация доказывает необходимость разработки предложенной в статье методики.
Последующими направлениями работы являются исследования различных способов оптимизации управляющих автоматов и изучение возможностей реализации предложенной методики с использованием параллельных вычислительных систем.
Список источников
1. Баркалов О.О.Синтез пристроїв керування на програмованих логічних пристроях / Баркалов О.О. - Донецьк. : РВА ДонНТУ, 2002. - 262 с. - ISBN 966-7559-62-9
2. Баркалов А.А. Синтез микропрограммных автоматов на заказных программируемых СБИС / А.А. Баркалов, Л.Д. Титаренко. - Донецк. : ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2009 - 336 с. - ISBN 966-8248-21-X
3. Maxfield C. FPGAs: Instant Access / Clive Maxfield. - Oxford : Newnes, 2008. - 216 pp. - ISBN 978-0-7506-8974-8
4. Adamski M. Design of Digital Systems and Devices / Adamski M., Barkalov A., Wegrzyn M. - Berlin. : Springer-Verlag, 2011. - 366 pp. - ISBN 978-3-642-17544-2
5. Баркалов А.А. Синтез управляющих автоматов с использованием распределенных и параллельных систем / А.А. Баркалов, И.Я. Зеленева, А.А. Гриценко // Радіоелектроніка, управління, інформатика. - 2010. - № 22. - С. 128-134. - ISSN 1607-3274
6. Smith D.J. HDL Chip Design: A Practical Guide for Designs, Synthesizing and Simulating ASICs and FPGAs Using VHDL or Verilog / Smith D.J. - Austin, USA : Doone Pubns, 1998. - 448 pp. - ISBN 978-0965193436
7. Chu P.P. RTL Hardware Design Using VHDL: Coding for Efficiency, Portability, and Scalability / Chu P.P. - New Jersey, USA : John Wiley and Sons, 2006. - 694 pp. - ISBN 978-0471720928
8. Mentor Graphics ModelSim User's Manual [Electronic resource]. - Mode of access http://www.actel.com/documents/modelsim_ug.pdf. - Title from screen
9. Ashenden P.J. VHDL 2008: Just the New Stuff (Systems on Silicon) / P.J. Ashenden, J. Lewis - Burlington, USA : Morgan Kaufmann, 2008. - 256 pp. - ISBN 978-0123742490
10. Stratix III Device Handbook, Volume 1 [Electronic resource]. - Mode of access: http://www.altera.com/literature/hb/stx3/stx3_siii5v1.pdf. - Title from screen
11. Quartus II Handbook Version 10.1 Volume 1: Design and Synthesis [Electronic resource]. - Mode of access: http://www.altera.com/literature/hb/qts/quartusii_handbook.pdf. - Title from screen
Размещено на Allbest.ru
...Подобные документы
Принципы организации управляющих автоматов. Разработка и проектирование автомата с жесткой и программируемой логикой. Разработка таблицы прошивки ПЗУ для УА с естественной адресацией микрокоманд. Структурный и абстрактный синтез управляющего автомата.
курсовая работа [508,5 K], добавлен 16.03.2011Синтез цифровых схем, выбор элементной базы и анализ принципов построения управляющих автоматов с жесткой логикой. Граф-схемы алгоритмов умножения и деления чисел. Создание управляющего автомата типа Мили; выбор триггера, кодирование сигналов автомата.
курсовая работа [1,8 M], добавлен 18.09.2012Проектирование конечного автомата, заданного оператором соответствия, с использованием канонического метода структурного синтеза автоматов. Тактирование от генератора синхронизирующих импульсов для устранения гонок в функциональной схеме автомата Мили.
курсовая работа [1,6 M], добавлен 22.10.2012Управляющий автомат и его связь с операционным автоматом. Разработка алгоритма работы управляющего автомата. Построение кодированной ПТП, синтез функций возбуждения и выходов. Реализация управляющего автомата с жесткой логикой на заданной элементной базе.
курсовая работа [57,9 K], добавлен 29.12.2011Основные понятия теории клеточных автоматов, анализ программных и аппаратных реализаций. Разработка методов синтеза и логического проектирования модулей сигнатурного мониторинга. Программа моделирования сетей клеточных автоматов на языке Delphi.
дипломная работа [1,9 M], добавлен 06.06.2011Знакомство с табличными и графическими способами задания многофункциональных абстрактных детерминированных автоматов. Рассмотрение сфер использования абстрактных автоматов с памятью. Анализ особенностей многофункциональных автоматов Мараховского.
контрольная работа [787,5 K], добавлен 28.03.2018Проектирование цифровых автоматов Мили и Мура с памятью в булевом базисе по заданной ГСА. Составление частично структурированной таблицы переходов-выходов. Построение функций выходов, логической схемы автомата. Особенности его экспериментальной проверки.
курсовая работа [628,7 K], добавлен 14.07.2012Изучение основных понятий теории автоматов. Анализ работы цифровых машин с программным управлением на примере автоматов Мили и Мура. Устройство преобразователей дискретной информации (RS-триггера). Разработка схемы цифрового автомата для сложения чисел.
курсовая работа [449,2 K], добавлен 16.09.2017Основные понятия абстрактных детерминированных автоматов Мили и Мура, как монофункциональных так и многофункциональных, реализуемых на триггерах. Понятия многофункциональных детерминированных автоматов 1-го, 2-го и 3-го рода на схемах автоматной памяти.
контрольная работа [495,3 K], добавлен 28.03.2018Основные понятия теории клеточных автоматов. Анализ подходов встроенного самотестирования цифровых схем. Модули сигнатурного мониторинга на сетях клеточных автоматов. Программа моделирования одномерной сети клеточных автоматов на языке Borland Delphi.
дипломная работа [1,9 M], добавлен 31.08.2011Функциональная схема и механизм работы цифрового устройства обработки данных. Синтез управляющего автомата, выбор типа триггера, описание управляющего автомата и счётчиков на языке Verilog. Процесс тестирования и моделирования управляющего автомата.
курсовая работа [3,2 M], добавлен 05.12.2012Выполнение синтеза цифрового автомата Мура, осуществляющего отображение информации, приведение алфавитного отображения к автоматному. Построение формализованного описания автомата, минимизация числа внутренних состояний. Функциональная схема автомата.
курсовая работа [2,8 M], добавлен 04.02.2013Основные понятия абстрактных цифровых автоматов, их классификация и способы задания. Связь между моделями Мили и Мура. Эквивалентные автоматы и эквивалентные их преобразования. Минимизация числа внутренних состояний автомата, алгоритм Ауфенкампа-Хона.
контрольная работа [278,3 K], добавлен 22.01.2011Исследование структурной схемы цифрового автомата и операционного устройства. Алгоритм функционирования цифрового автомата в микрооперациях. Кодирование его состояний. Характеристика функций возбуждения триггеров и формирования управляющих сигналов.
курсовая работа [3,6 M], добавлен 06.12.2013Изучение истории развития теории конечных автоматов. Методы логического проектирования дискретных устройств. Алфавитный способ преобразования информации. Кодирование информации в двоичном алфавите. Многофункциональные автоматы Мараховского с памятью.
контрольная работа [103,6 K], добавлен 28.03.2018Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Составление списка простых классов совместимости, таблицы переходов и выходов минимального автомата. Обзор получения логических функций выходов конечного автомата.
контрольная работа [1,2 M], добавлен 23.06.2012Структурная схема и синтез цифрового автомата. Построение алгоритма, графа и таблицы его функционирования в микрокомандах. Кодирование состояний автомата. Функции возбуждения триггеров и формирования управляющих сигналов. Схема управляющего устройства.
курсовая работа [789,4 K], добавлен 25.11.2010Блок обработки данных: общее устройство, выбор элементной базы. Структура операционного автомата. Расчет нагрузочной способности шины данных. Расчет длительности такта управляющего автомата. Память: построение, контроллер. Интерфейс шины процессор-память.
курсовая работа [3,7 M], добавлен 07.01.2015Управляющий цифрового автомат типа Мура. Абстрактный и структурный синтез автомата, построена функциональная схема. Функции выходов и возбуждения элементов памяти. Моделирование на ПК с использованием симулятора ModelSim. Описание автомата на языке VHD.
курсовая работа [214,2 K], добавлен 07.11.2010Установка компонентов на печатные платы при помощи автоматов укладчиков или интегрированных монтажно-сборочных комплексов, их характеристики. Автомат с блоком монтажных головок. Роторно-башенная схема построения автоматов (Rotary Turret Placement System).
реферат [161,7 K], добавлен 21.11.2008
