2023, випуск 3, c. 88-100
Одержано 20.07.2023; Виправлено 12.08.2023; Прийнято 26.09.2023
Надруковано 29.09.2023; Вперше Online 19.10.2023
https://doi.org/10.34229/2707-451X.23.3.8
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Оптимізація схеми автомата Мілі у змішаному базисі
О.О. Баркалов 1 
, Л.О. Тітаренко 1, 2 , О.М. Головін 3 , О.В. Матвієнко 3 *
1 Університет Зеленогурський, Зелена Гура, Польща
2 Харківський національний університет радіоелектроніки, Харків, Україна
3 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Пристрій управління це один із найважливіших блоків будь-якої цифрової системи. Основна функція пристрою управління – координування взаємодії інших блоків системи. Тому характеристики схеми пристрою управління мають значний вплив на якість системи в цілому.
Для представлення закону функціонування пристрою керування використовуються моделі мікро-програмного автомата (МПА) Мура та Мілі. При синтезі схем МПА необхідно вирішити низку оптимізаційних завдань: зменшення апаратурних витрат, підвищення швидкодії, мінімізація споживаної потужності, спільна оптимізація апаратурних швидкісних характеристик. Методи вирішення цих завдань значною мірою залежать від використовуваного елементного базису. В даний час одним з основних базисів, в якому реалізуються сучасні цифрові системи, є базис FPGA.
Основні блоки у складі FPGA це логічні блоки, що конфігуруються, програмована матриця між-з'єднань, дерево синхронізації і програмовані входи-виходи. Для реалізації схем МПА можна використовувати логічні блоки, що конфігуруються, двох типів: табличні логічні елементи (ТЛЕ), і вбудовані блоки пам'яті (ВБП), що володіють властивістю реконфігурації. Проте ВБП широко використовуються реалізації різних операційних блоків цифрових систем. Тому розробник схеми пристрою управління може використовувати обмежену кількість таких блоків пам'яті.
Мета статті. У статті розглянуті питання синтезу МПА, коли є обмежена кількість "вільних" блоків ВБП. І тут схема микропрограммного автомата представляється мережею з блоків ВБП і ТЛЕ. Запропоновано метод синтезу МПА з оптимізацією числа ТЛЕ, коли у схемі мікропрограмного автомата можна використовувати лише один ВБП.
Пропонований метод заснований на використанні вбудованого блоку пам'яті, який здійснює заміну вхідних змінних та кодування виходів автомата.
Результати. Дослідження ефективності запропонованого методу проводилися на стандартних автоматах. Як елементний базис використовувалися FPGA сімейства Virtex-7 фірми Xilinx. Для реалізації МПА застосовано пакет Vivado. Результати досліджень показали, що використання блоку ВБП дозволило зменшити кількість блоків ТЛЕ в середньому на 14 % – 18 % порівняно зі схемами, що складаються лише з ТЛЕ. Для FPGA сімейства Virtex-7 було достатньо числа входів ТЛЕ Io= 6 для однорівневої реалізації системи виходів.
Висновки. Ефективність запропонованого методу дозволяє рекомендувати його для використання при синтезі мікропрограмних автоматів в умовах граничного обмеження числа БВП.
Ключові слова: автомат Мілі, синтез, кодування входів, кодування наборів виходів.
Цитувати так: Баркалов О.О., Тітаренко Л.О., Головін О.М., Матвієнко О.В. Оптимізація схеми автомата Мілі у змішаному базисі. Cybernetics and Computer Technologies. 2023. 3. С. 88–100. https://doi.org/10.34229/2707-451X.23.3.8
Список літератури
1. Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p.
2. DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.
3. Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA-based circuits using hierarchical finite state machines. Tallinn: TUT Press, 2012. 240 p.
4. Czerwinski R., Kania D. Finite state machines logic synthesis for complex programmable logic devices. Berlin: Springer, 2013. 172 p.
5. Wiśniewski R., Bazydło G., Szcześniak P., Wojnakowski M. Petri net-based specification of cyber-physical systems oriented to control direct matrix converters with space vector modulation. IEEE Access, 2019. Vol. 7. 23407–23420.
6. 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.
7. 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.
8. Rawski M., Tomaszewicz P., Borowski G., Luba T. Logic synthesis method of digital circuits designed for implementation with embedded memory blocks on FPGAs. In: Design of Digital Systems and Devises. Lecture Notes in Electrical Engineering. Adamski M., Barkalov A., Wegrzyn M. (Eds.). Vol. 79. Berlin: Springer, 2011. P. 121–144.
9. Maxfield C. The design warrior’s guide to FPGAs. Orlando: Academic Press, 2004. 542 p.
10. 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.
11. 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
12. 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.
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–728.
14. Kuon I., Tessier R., Rose J. FPGA Architecture: Survey and Challenges. Foundations and Trends in Electronic Design Automation. 2008. Vol. 2, No. 2. P. 135–253.
15. Kubica M., Opara A., Kania D.. Technology Mapping for LUT- based. FPGA. Berlin: Springer, 2021.
16. Barkalov O., Titarenko L., and Barkalov Jr., A Structural Decomposition as a tool for the optimization of an FPGA–based implementation of a Mealy FSM. Cybernetics and Systems Analysis. 2012. Vol. 48, No. 2. P. 313–322.
17. Barkalov A., Titarenko L., Mielcarek K. Hardware reduction for LUT–based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2018. P. 595–607. https://doi.org/10.2478/amcs-2018-0046
18. 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.
19. Vivado Design Suite. https://www.xilinx.com/products/design-tools/vivado.html (звернення: 15.01.2023)
20. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 1991. 43 p.
21. Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В., Горина В.В. Уменьшение числа LUT элементов в схеме совмещенного автомата. Управляющие системы и машины. 2016. № 3. C. 16–22. https://doi.org/10.15407/usim.2016.03.016
22. Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Уменьшение аппаратурных затрат в совмещенных автоматах. Управляющие системы и машины. 2017. № 4. C. 43–50. https://doi.org/10.15407/usim.2017.04.043
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна