Анализ эффективности методов кодирования состояний при синтезе автоматов мили на FPGA

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

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

Анализ эффективности методов кодирования состояний при синтезе автоматов Мили на FPGA

А.А. Баркалов

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

Автомат Мили, кодирование состояний, XST, аппаратурные затраты, быстродействие, KISS2, FPGA

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

Микросхемы FPGA (Field-Programmable Gate Array) фирмы Xilinx являются современным базисом построения цифровых систем разного функционального назначения [4, 5]. В этом случае процесс проектирования осуществляется с использованием САПР Xilinx ISE Design Suite [6], одной из компонент которой является средство синтеза XST (Xilinx Synthesis Technology) [7]. Назначение XST состоит в преобразовании описания системы на одном из языков описания аппаратуры (HDL от Hardware Description Language) в набор микросхемно-независимых функциональных и запоминающих элементов из библиотеки Xilinx. После осуществления синтеза может быть получена информация о необходимом для реализации количестве LUT-элементов (Look-Up Table) и триггеров, а также предполагаемая максимальная частота функционирования.

Проблемы эффективной реализации автоматов Мили в базисе FPGA рассмотрены в работах многих отечественных и зарубежных исследователей. Например, в работах [8-11] предлагаются способы специфического кодирования состояний, структуры имплементации на встроенных блоках памяти, методы многоуровневой реализации схем автоматов. Однако, в настоящее время отсутствуют результаты анализа эффективности непосредственно поддерживаемых XST алгоритмов кодирования состояний, которые могут применяться к автоматам, заданным согласно специальным техникам описания [7]. Такой анализ необходим для разработки новых методов кодирования состояний, дающих лучшие результаты, чем стандартные методы из XST.

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

Методика проведения исследований

Средство синтеза XST поддерживает способы спецификации автоматов с использованием одного, двух и трех процессов, а также позволяет управлять общим критерием оптимизации (быстродействие, аппаратурные затраты), а также алгоритмом кодирования состояний (автоматическое, унитарное, кодирование Грея, компактное, кодирование Джонсона, последовательное, скоростное). Кроме того возможно управление способом реализации логической схемы (LUT-элементы, встроенные блоки памяти) [7].

При автоматическом кодировании состояний, которое применяется по умолчанию, XST реализует собственный алгоритм выбора наилучшего метода кодирования, в зависимости от цели оптимизации и конфигурации автомата. Для исследования эффективности, как данного алгоритма, так и остальных методов, был использован набор тестовых автоматов IWLS LGSynth93, представленных в формате KISS2 (рис. 1) [12]. Преобразование автоматов из формата KISS2 в двухпроцессные VHDL-модели было выполнено с помощью разработанной программы KISS2 Converter, а их синтез проведен системой XST 11.3 для микросхемы XC5VLX30.

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

Рисунок 1 - Методика исследования эффективности алгоритмов кодирования состояний

Анализ эффективности методов кодирования

В рамках исследований было проведено более 300 экспериментов, результаты которых отражены в табл. 1. В этой таблице методы кодирования обозначены следующим образом: «auto» - автоматическое, «one-hot» - унитарное, «compact» - компактное, «sequential» - последовательное, «gray» - кодирование Грея, «johnson» - кодирование Джонсона, «speed1» - скоростное. Для каждого тестового автомата и алгоритма кодирования приведены значения количества LUT-элементов («LUT»), необходимых для реализации, и максимальной частоты функционирования логической схемы в МГц («MHz»). автомат микросхема затрата

Тестовые автоматы «donfile», «modulo12», «s1a» и «s8» обладают константными выходными сигналами, что в процессе синтеза привело к реализациям в виде подключенных к выходным линиям уровней нуля или единицы.

С точки зрения уменьшения аппаратурных затрат (рис. 2) и повышения быстродействия (рис. 3), лучшие результаты показало

Таблица 1 - Результаты исследований на тестовых автоматах

Рисунок 2 - Эффективность методов при оптимизации аппаратурных затрат

Рисунок 3 - Эффективность методов при оптимизации быстродействия

Рисунок 4 - Эффективность методов при двухцелевой оптимизации

автоматическое кодирование, которое привело к оптимальным реализациям в 58,54% и 39,02% случаев соответственно. Среди методов аппаратурной минимизации следует отметить компактное кодирование, продемонстрировавшее эффективность в 46,34%. Скоростное кодирование привело к максимальному быстродействию в 36,59% экспериментов, что всего на 2,43% хуже показателя автоматического кодирования, однако не обеспечило ни одного аппаратурно-оптимального решения (0,00%).

Лучшие результаты по одновременному достижению минимальной аппаратурной реализации и максимального быстродействия показали методы автоматического и компактного кодирования (29,27%). Широко используемый метод унитарного кодирования имеет сбалансированные результаты по аппаратурным затратам (31,71%) и быстродействию (34,15%), но всего в 12,20% случаев приводит к одновременной оптимизации обоих факторов. Таким образом, получены данные для сравнения вновь разрабатываемых алгоритмов кодирования состояний с известными подходами.

Заключение

Проведенные в работе эксперименты показали, что используемый XST по умолчанию алгоритм выбора оптимального кодирования состояний, при скорости функционирования как целевом параметре и LUT-ориентированной реализации логической схемы, приводит к неэффективным результатам в 60,98% (быстродействие) и 41,46% (аппаратурные затраты) случаев, а двухцелевая оптимизация достигается менее чем для трети автоматов (29,27%).

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

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

Список литературы

Баркалов А.А. Синтез микропрограммных автоматов на заказных и программируемых СБИС / А.А. Баркалов, Л.А. Титаренко. - Донецк: ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2009. - 336 с.

Barkalov A.A. Synthesis of operational and control automata / A.A. Barkalov, L.A. Titarenko. - Donetsk: DonNTU, TechPark DonNTU UNITECH, 2009. - 256 pp.

Adamski M. Design of digital systems and devices / M. Adamski, A. Barkalov,M. Wegrzyn. - Springer-Verlag, 2011. - 365 pp.

Grout I. Digital systems design with FPGAs / I. Grout. - Elsevier, 2008. - 724 pp.

FPGA, CPLD and EPP solutions from Xilinx, Inc. [Электронный ресурс]. - Режим доступа: http://www.xilinx.com.

Xilinx ISE Design Suite Software [Электронный ресурс]. - Режим доступа: http://www.xilinx.com/products/design-tools/ise-design-suite.

XST User Guide, v. 11.3 [Электронный ресурс]. - Режим доступа: http://www.xilinx.com/support/documentation/sw_manuals/xilinx11/xst.pdf.

Kubatova H. FEL-Code: FSM internal state encoding method / H. Kubatova,
M. Becvar // Proceedings of 5th International Workshop on Boolean Problems. - Freiberg, 2002. - pp. 109-114.

Sklyarov V. Synthesis and implementation of RAM-based finite state machines in FPGAs / V. Sklyarov // Proceedings of Conference on Field Programmable Logic. - Villach, 2000. - pp. 718-728.

Bukowiec A. State machines synthesis and implementation into FPGAs with multiple encoding of states / A. Bukowiec, A. Barkalov, L. Titarenko // Radioelectronics and Informatics. - 2008. - № 4. - pp. 43-48.

Selvaraj H. FSM implementation in embedded memory blocks of programmable logic devices using functional decomposition / H. Selvaraj, M. Rawski, T. Luba // Proceedings of International Conference on Information Technology: Coding and Computing. - Las Vegas, 2002. - pp. 355-360.

International workshop on logic synthesis benchmark suite (LGSynth93). [Электронный ресурс]. - Режим доступа: http://www-lab13.kuee.kyoto-u.ac.jp/eda/benchmark/mcnc/benchmarks/LGSynth93/LGSynth93.tar.

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