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