Одержано 30.09.2023; Виправлено 17.10.2023; Прийнято 28.11.2023

Надруковано 04.12.2023; Вперше Online 05.12.2023

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

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

 

УДК 004.274

Розділення вхідних змінних для оптимізації схеми автомата Мілі

О.О. Баркалов ¹ ,   Л.О. Тітаренко ^{1, 2} ,   О.М. Головін ³ ,   О.В. Матвієнко ³ ,   С.О. Сабурова ²

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

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

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

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

 

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

У практиці інженерного проектування поведінка ПУ часто визначається за допомогою моделі мікропрограмного автомата (МПА) Милі. Особливість МПА Мілі це залежність систем булевих функцій, що задають схему, від входів та станів. Ця особливість враховується при оптимізації характеристик схеми в базисі мікросхем FPGA.

Під час розробки схеми автомата необхідно оптимізувати його характеристики, такі як швидкодія та апаратурні витрати.

FPGA – один із найпоширеніших базисів при побудові цифрових систем. Для реалізації схеми ПУ достатньо таких компонентів FPGA, як логічні елементи табличного типу (LUT), програмовані тригера, вбудовані блоки пам'яті (EMB) і програмовані міжз'єднання.

Мета роботи. У цій роботі пропонується метод зменшення апаратурних витрат у схемі МПА Мілі, що реалізується у базисі FPGA. Розглянуто завдання реалізації схеми у змішаному елементному базисі. Під змішаним базисом розуміється спільне використання елементів табличного типу LUT та блоків пам'яті EMB. Розглядається ситуація, коли кількість доступних блоків EMB вкрай обмежена. Це цілком можливо, оскільки блоки EMB широко використовуються реалізації різних операційних блоків цифрових систем.

Основний недолік елементів LUT це мала кількість входів. Сучасні цифрові системи можуть генерувати сигнали логічних умов, які поступають до ПУ, і кількість яких у десятки разів перевищує число входів LUT. Така невідповідність між характеристиками алгоритму керування та кількістю входів елементів LUT призводить до багаторівневих схем ПУ з нерегулярною структурою міжз'єднань. Для оптимізації багаторівневих схем може бути застосованим метод заміни вхідних змінних та спільне використання елементів LUT та блоків EMB.

Результати. Аналіз ефективності запропонованого методу проводився за допомогою бібліотек стандартних МПА платформи САПР Vivado. Як показали дослідження, запропонований метод дозволяє зменшити кількість елементів LUT у діапазоні від 100 % до 82 %. Для 37 % автоматів метод заміни вхідних змінних можна застосувати лише разом із розділенням вхідних змінних.

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

 

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

 

Цитувати так: Баркалов О.О., Тітаренко Л.О., Головін О.М., Матвієнко О.В., Сабурова С.О. Розділення вхідних змінних для оптимізації схеми автомата Мілі. Cybernetics and Computer Technologies. 2023. 4. С. 84–96. https://doi.org/10.34229/2707-451X.23.4.10

 

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

           1.     Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA-based circuits using hierarchical finite state machines. Tallinn: TUT Press, 2012. 240 p. https://doi.org/10.1109/IranianCEE.2013.6599683

           2.     Baranov S. Logic and System Design of Digital Systems. Tallinn: TUT Press, 2008.

           3.     Baranov S. Finite State Machines and Algorithmic State Machines. Amazon, 01 2018.

           4.     DeMicheli G. Synthesis and Optimization of Digital Circuits. McGraw–Hill, 1994. 576 p.

           5.     Wolf W. FPGA-Based System Design. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2004. 548 p.

           6.     Maxfield C. FPGAs: Instant access. Newnes, 2008. 204 p.

           7.     Trimberger S. Three ages of FPGA: A retrospective on the first thirty years of FPGA technology. IEEE Proceedings Solid-State Circuits Magazine. 2018. Vol. 10, No. 2. P. 16–29. http://dx.doi.org/10.1109/mssc.2018.2822862

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

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

       10.     Barkalov A., Titarenko L. Logic synthesis for FSM-based control units. Berlin: Springer, 2009. 233 p.

       11.     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. Berlin: Springer. 2020. https://doi.org/10.1007/978-3-030-38295-7

       12.     Marwedel P. Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things. 3rd ed. Springer International Publishing, 2018. https://doi.org/10.1007/978-3-030-60910-8

       13.     Garcia-Vargas I., Senhadji-Navarro R., Jim Бnez-Moreno G., Civit-Balcells A., Guerra-Gutierrezz P. ROM-based finite state machines implementation in low cost FPGAs. IEEE Intern. Simp. on Industrial Electronics (ISIE’07) (Vigo, 2007). 2007. P. 2342–2347. https://doi.org/10.1109/ISIE.2007.4374972

       14.     Garcia-Vargas L., Senhaji-Navarro R. Finite state machines with input multiplexing: A performance study. IEEE Transactions on CAD of Integrated Circuits and Systems. 2015. Vol. 34, Iss. 5. P. 867–871. https://api.semanticscholar.org/CorpusID:14095082

       15.     Xilinx. https://www.xilinx.com/products/silicon-devices.html (звернення: 01.01.2023)

       16.     Xilinx. Virtex-7 Family Overview. PDF, Xilinx Corporation. 2021. http://www.xilinx.com/support/documentation/ data_ sheets/ds183_Virtex_7_Data_Sheet.pdf (звернення: 01.01.2023)

       17.     Chapman K. Multiplexer Design Techniques for Datapath Performance with Minimized Routing Resources. Xilinx All Programmable, 2014. https://api.semanticscholar.org/CorpusID:61416418 (звернення: 01.01.2023)

       18.     Feng W., Greene J., Mishchenko A. Improving FPGA Performance with a S44 LUT Structure. In Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (NewYork: NY, USA, 02 2018), FPGA’18, Association for Computing Machinery. 2018. P. 61–66. http://dx.doi.org/10.1145/3174243.3174272

       19.     Islam M.M., Hossain M.S., Shahjalal M., Hasan M.K., Jang Y.M. Area-time e_cient hardware implementation of modular multiplication for elliptic curve cryptography. IEEE Access. 2020. Vol. 8. P. 73898–73906. http://dx.doi.org/10.1109/ACCESS.2020.2988379

       20.     Machado L., Cortadella J. Support-Reducing Decomposition for FPGA Mapping. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Vol. 39, No. 1. P. 213–224. http://dx.doi.org/10.1109/TCAD.2018.2878187

       21.     Czerwinski R., Kania D. Finite state machines logic synthesis for complex programmable logic devices. Bulletin of the polish academy of sciences technical sciences. 2010. Vol. 58, No. 4. 172 p. http://dx.doi.org/10.2478/v10175-010-0067-6

       22.     Kolopienczyk M., Titarenko L., Barkalov A. Design of EMB-based Moore FSMs. Journal of Circuits, Systems and Computers. 2017. Vol. 26, No. 7. P. 1–23. https://api.semanticscholar.org/CorpusID:22752093

       23.     Tiwari A., Tomko K.A. 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

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

       25.     Vivado. https://www.xilinx.com/products/design-tools/vivado.html (звернення: 01.01.2023)

       26.     Xilinx. Vitis Platform. https://www.xilinx.com/products/design-tools/vitis/vitis-platform.html (звернення: 01.01.2023)

       27.     Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В., Горина В.В. Уменьшение числа LUT элементов в схеме совмещенного автомата. Управляющие системы и машины. 2016. № 3. C. 16–22. https://doi.org/10.15407/usim.2016.03.016

       28.     Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Уменьшение аппаратурных затрат в совмещенных автоматах. Управляющие системы и машины. 2017. № 4. C. 43–50. https://doi.org/10.15407/usim.2017.04.043

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

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