RU UA EN

Введение

В настоящее время известно большое количество методов оптимизации управляющих автоматов, которые, в частности, рассмотрены в работах Баркалова А.А. [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 приведены результаты, полученные для моделей, обладающих следующими характеристиками: Nx=10, Kx=2, Ny=20, Ky=2, Ns={20, 22,...30}.

Рисунок 3 – Пример результатов исследования метода замещения символов входного алфавита (параметры Nx=10, Kx=2, Ny=20, Ky=2 базис - Altera Stratix III)

Согласно результатам на рис. 3 можно сделать вывод об эффективности применения данного метода в базисе ПЛИС семейства Stratix III.

Рисунок 4 – ПЛИС фирмы ALTERA 6 кадров. Задержка после последнего кадра = 2 сек. Задержка после остальных кадров = 1 сек. Размер анимации: 535px х 252px. Размер файла: 28.5 Kbytes. Создано при помощи Adobe ImageReady.

Заключение

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

Алгоритм исследования представляет собой последовательность шагов, выполнение которых позволяет охватить все необходимые технологические процессы, которые связаны, с одной стороны, с применением метода оптимизации, а с другой – с работой в базисе ПЛИС 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