2024, випуск 2, c. 87-100

Одержано 10.04.2024; Виправлено 04.05.2024; Прийнято 28.05.2024

Надруковано 09.06.2024; Вперше Online 14.06.2024

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

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

 

УДК 004.274

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

О.О. Баркалов 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, які використовуються для реалізації схеми МПА, є елементи LUT (таблиці перегляду) та елементи EMB (блоки вбудованої пам’яті). Тому для вирішення задач оптимізації при розробці схеми автомата необхідно зменшити кількість цих елементів.

Мета роботи. Ця робота представляє підхід до зниження апаратурних витрат при реалізації МПА Мілі в базисі FPGA.

Метод заснований на розширеному кодуванні множин мікрооперацій, в якому код множини включає також код перехідного стану. Код стану є частковим, оскільки він визначається для множини станів при переході, з яких утворюється ця множина. Для реалізації частини схеми МПА використовується вбудований блок пам'яті EMB. Якщо можливостей EMB недостатньо для реалізації схеми, то частина схеми реалізується на елементах LUT. Частину вихідних сигналів (мікрооперацій) пропонується реалізувати на ЕМВ. Наведено приклад синтезу схеми МПА за запропонованим методом.

Результати. Для дослідження ефективності запропонованого методу проведено порівняння ПУ відомої структури (U5) з ПУ, яке отримане із застосуванням запропонованого методу (U7). При цьому використовувалися стандартні бенчмарки із відомої бібліотеки. Дослідження показали, що U7 дозволяє зменшити число LUT на 28 % всіх бенчмарків, а U5 – лише на 9 %. Важливо зазначити, що для реалізації всієї схеми 64 % стандартних МПА досить одного блоку EMB.

Висновки. Запропонований спосіб дозволяє знизити апаратурні витрати (кількість елементів LUT). У статті наведено умови застосування запропонованого методу та результати експериментів з перевірки ефективності запропонованого підходу до реалізації автоматів на мікросхемах сімейства Virtex-7 і промисловому пакеті Vivado.

 

Ключові слова: МПА Мілі, синтез, FPGA, EMB, LUT, розширені коди наборів мікрооперацій.

 

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

 

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

           1.     Tiwari A., Tomko K. Saving power by mapping finite state machines into embedded memory blocks in FPGAs. Proc. Design, Automation and Test in Europe Conference and Exhibition (Paris, France, 6–20 Feb. 2004). 2004. Vol. 2. P. 916–921. https://doi.org/10.1109/DATE.2004.1269007

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

           3.     Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p. https://doi.org/10.1007/978-1-4615-2692-6

           4.     DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.

           5.     Barkalov A., Titarenko L., Kolopienczyk M., Mielcarek K., Bazydlo G. Logic synthesis for FPGA-based Finite State Machine. Studies in Systems, Decision and Control. Vol. 38. Springer International Publishing, Cham Heidelberg, 2015. https://doi.org/10.1007/978-3-319-24202-6

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

           7.     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

           8.     Barkalov A., Titarenko L., Mielcarek K. Improving characteristics of LUT–based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2020. 30 (4). P. 745–759. https://doi.org/10.3390/electronics10080901

           9.     Bacchetta P., Daldos L., Sciuto D., Silvano C. Low-power state assignment techniques for finite state machines. In Proceedings of the 2000 IEEE International Symposium on Circuits and Systems (ISCAS’2000) (Geneva, 2000), vol. 2. IEEE. P. 641–644. https://doi.org/10.1109/ISCAS.2000.856410

       10.     Kubica M., Opara A., Kania D. Technology Mapping for LUT-based. FPGA. Berlin: Springer, 2021. https://doi.org/10.1007/978-3-030-60488-2

       11.     Grout I. Digital systems design with FPGAs and CPLDs. Amsterdam: Elsevier, 2008. 784 p. https://doi.org/10.1016/B978-0-7506-8397-5.X0001-3

       12.     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. https://doi.org/10.1007/3-540-44614-1_76

       13.     Barkalov A. Microprogramcontrol unit as composition of automate with programmable and hardwired logic. Automatics and Computer Science. 1983. 17 (4). P. 36–41.

       14.     Amann R., Baitinger U. Optimal state chains and states codes in finite state machines. IEEE Transactions on Computer-Aided Design. 1989. 8 (2). P. 153–170. https://doi.org/10.1109/43.21834

       15.     Barkalov A., Shwec A. Synthesis of compositional microprogram control unit with modified microinstruction addressing. Automatic Control and Computer Sciences. 1994. 28 (5). P. 22–30.

       16.     Barkalov A.A. Multilevel programmable logic array schemes for microprogrammed automata. Cybern Syst Anal. 1994. 30. P. 489–495. https://doi.org/10.1007/BF02366558

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

       18.     Xilinx. http://www.xilinx.com (https://www.amd.com/en.html) (звернення: 01.01.2024)

       19.     Virtex‐7 T and XT FPGAs Data Sheet. https://docs.xilinx.com/v/u/en-US/ds183_Virtex_7_Data_Sheet (звернення: 01.01.2024)

       20.     Barkalov O., Titarenko L., Mielcarek K. Hardware reduction for LUT based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2018. Vol. 28, No. 3. P. 595–607. https://doi.org/10.2478/amcs-2018-0046

       21.     Barkalov, O., Titarenko, L., and Mielcarek, K. Improving characteristics of LUT-basedMealy FSMs. International Journal of Applied Mathematics and Computer Science. 2020. Vol. 30, No. 4. P. 745–759. https://doi.org/10.34768/amcs-2020-0055

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

       23.     McElvain, Kenneth. IWLS’93 Benchmark Set: Version 4.0. https://www.researchgate.net/publication/238195666_Benchmark_set_Version_40 (звернення: 01.01.2024)

       24.     Machado L., Cortadella J. Support-Reducing Decomposition for FPGA Mapping. IEEE transactions on Computer-Aided Design of Integrated Circuits and Systems. 2020. 39 (1). P. 213–224. https://doi.org/10.1109/TCAD.2018.2878187

       25.     Баркалов А.А., Титаренко Л.А. Преобразование кодов в композиционных микропрограммных устройствах управления. Кибернетика и системный анализ. 2011. № 5. C. 107–118. http://nbuv.gov.ua/UJRN/KSA_2011_47_5_11.

       26.     www.altera.com (звернення: 01.01.2024)

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

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

 

 

            Випуски

 

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

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

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