2022, випуск 2, c. 83-94

Одержано 14.08.2022; Виправлено 14.09.2022; Прийнято 29.09.2022

Надруковано 30.09.2022; Вперше Online 05.10.2022

https://doi.org/10.34229/2707-451X.22.2.9

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 004.274

Оптимізація схеми автомата Мура у змішаному елементному базисі

О.О. Баркалов 1 ORCID ID favicon Big,   Л.О. Тітаренко 1, 2 ORCID ID favicon Big,   О.М. Головін 3 ORCID ID favicon Big,   О.В. Матвієнко 3 * ORCID ID favicon Big

1 Університет Зеленогурський, Зелена Гура, Польща

2 Харківський національний університет радіоелектроніки, Харків, Україна

3 Інститут кібернетики імені В.М. Глушкова НАН України, Київ

* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. Пристрій управління – один з найважливіших блоків будь-якої цифрової системи. Основна функція пристрою управління є координування взаємодії інших блоків системи. Тому характеристики схеми пристрою керування мають значний вплив на якість системи в цілому.

Для подання закону функціонування пристрою управління використовуються моделі мікропрограмного автомата Мура та Мілі. При синтезі схем мікропрограмних автоматів необхідно вирішити ряд оптимізаційних задач: зменшення витрат апаратури, підвищення швидкодії, мінімізація споживаної потужності, спільна оптимізація апаратурно-часових характеристик. Методи вирішення цих завдань у значній мірі залежать від використовуваного елементного базису.

В даний час одним з основних базисів, в якому реалізуються сучасні цифрові системи є базис FPGA. Основними блоками в складі FPGA, які використовуються при синтезі мікропрограмних автоматів є блоки вбудованої пам'яті EMB (embedded memory blocks), логічні блоки LUT (look-up table) і система програмованих міжпоєднань. Найкращі характеристики мають схеми автоматів, реалізовані за допомогою блоків вбудованої пам'яті EMB. Однак блоки EMB широко використовуються для реалізації різних операційних блоків цифрових систем. Тому розробник схеми пристрою керування може використовувати обмежену кількість таких блоків пам'яті.

Мета роботи. У статті розглянуто крайній випадок, коли в наявності є тільки один "вільний" блок EMB. У цьому випадку схема мікропрограмного автомата представляється мережею, що складається з блоків EMB і елементів LUT. Також запропоновано метод синтезу мікропрограмного автомата з оптимізацією числа елементів LUT, коли в схемі мікропрограмного автомата можна використовувати тільки один блок EMB.

Пропонований метод заснований на використанні класів псевдоеквівалентних станів автомата Мура. Стани кодуються таким чином, що код стану складається з коду класу псевдоеквівалентних станів і коду набору мікрооперацій.

Результати. Дослідження ефективності запропонованого методу проводилися на стандартних автоматах. Як елементний базис використовувалися FPGA сімейства Virtex-7 фірми Xilinx. Результати досліджень показали, що запропонований метод дозволяє зменшити число LUT у схемах МПА на 12 % 19 % у порівнянні з відомими методами. У всіх випадках використовувався тільки один блок EMB.

Висновки. Ефективність запропонованого методу дозволяє рекомендувати його для використання при синтезі мікропрограмних автоматів в умовах крайнього обмеження числа EMB.

 

Ключові слова: автомат Мура, FPGA, LUT, EMB, псевдоеквівалентні стани, синтез.

 

Цитувати так: Баркалов О.О., Тітаренко Л.О., Головін О.М., Матвієнко О.В. Оптимізація схеми автомата Мура у змішаному елементному базисі. Cybernetics and Computer Technologies. 2022. 2. С. 83–94. https://doi.org/10.34229/2707-451X.22.2.9

 

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

           1.     Соловьев В.В. Проектирование цифровых схем на основе программируемых логических интегральных схем. М.: Горячая линия ТЕЛЕКОМ, 2001. 636 с.

           2.     Czerwinski R., Kania D. Finite state machines logic synthesis for complex programmable logic devices. Berlin: Springer, 2013. 172 p.

           3.     Kubica M., Opara A., Kania D. Technology Mapping for LUT- based. FPGA. Berlin: Springer, 2021.

           4.     Grout I. Digital systems design with FPGAs and CPLDs. Amsterdam: Elsevier, 2008. 784 p.

           5.     Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. 476 с.

           6.     Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p.

           7.     Barkalov A., Titarenko L., Mielcarek K., and Chmielewski S.. Logic Synthesis for FPGA–Based Control Units. – Structural Decomposition in Logic Design. Vol. 636 of Lecture Notes in Electrical Egineering. Springer, 2020. https://doi.org/10.1007/978-3-030-38295-7

           8.     Barkalov A.A., Titarenko L.A. Code transformation in compositional microprogram control units. Cybernetics and Systems Analysis. 2011. 47 (5). P. 763–772. https://doi.org/10.1007/s10559-011-9355-x

           9.     Maxfield C. The design warrior’s guide to FPGAs. Orlando: Academic Press. 2004. 542 p.

       10.     Ruiz-Rosero J., Ramirez-Gonzalez G., Khanna R. Field Programmable Gate Array Applications – A Scientometric Review. Computation 2019. 7 (4). 63. https://doi.org/10.3390/computation7040063

       11.     UG473 (v1.14. July 3. 2019). https://www.xilinx.com/ (звернення: 14.08.2022)

       12.     Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and optimization of FPGA-based systems. Berlin: Springer. 2014. 432 p. https://doi.org/10.1007/978-3-319-04708-9_6

       13.     Sklyarov V. Synthesis and Implementation of RAM-based Finite States Maсhines in FPGAs. in Proceeding of Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing. Villach: Springer-Verlag. 2000. P. 718–727.

       14.     Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 1991. 43 p.

       15.     Ачасова С.М. Алгоритмы синтеза автоматов на программируемых матрицах. М.: Радио и связь, 1987. 136 с.

       16.     Vivado Design Suite. https://www.xilinx.com/products/design-tools/vivado.html (звернення: 01.01.2020)

       17.     VC709 Evaluation Board for the Virtex-7 FPGA. User Guide; UG887 (v1.6); Xilinx, Inc.: San Jose, CA, USA, 2019.

       18.     Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Реализация схемы совмещенного автомата в базисе FPGA. Комп’ютернi засоби, мережi та системи. 2016. С. 10–19. http://dspace.nbuv.gov.ua/handle/123456789/122858

       19.     Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Кодирование выходных переменных в совмещенном автомате. Комп’ютернi засоби, мережi та системи. 2018. С. 73–80. http://dspace.nbuv.gov.ua/handle/123456789/150610

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

 

            Випуски

 

© Вебсайт та оформлення. 2019-2024,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.