Параметризація граф-схем алгоритмів цифрових пристроїв керування
DOI:
https://doi.org/10.31558/2786-9482.2024.2.1Ключові слова:
граф-схема алгоритму, цифрові пристрої керування, оптимізація схеми, параметри, псевдовипадкова генераціяАнотація
Розглядається науково-практична задача визначення множини параметрів граф-схем алгоритмів у контексті подальшої псевдовипадкової генерації граф-схем для дослідження ефективності методів синтезу і оптимізації цифрових пристроїв керування. Розглянуто структурні компоненти та визначено загальні параметри граф-схем алгоритмів, які традиційно використовуються для опису алгоритмів роботи цифрових пристроїв керування. Проаналізовано основні класи цифрових пристроїв керування, як-от мікропрограмний автомат (автомат з жорсткою логікою), мікропрограмний пристрій керування (автомат з програмувальною логікою) та композиційний мікропрограмний пристрій керування. Для зазначених класів пристроїв розглянуто основні методи оптимізації апаратурних витрат, серед яких кодування наборів мікрооперацій, заміна вхідних змінних, операційне перетворення кодів станів тощо. Для кожного з розглянутих класів пристроїв керування та методів оптимізації запропоновані набори параметрів граф-схеми алгоритму, які впливають на ефективність застосування відповідних структур і методів та характеризують як функцію переходів, так і функцію виходів пристрою керування. Для окремих параметрів визначено допустимий діапазон змін та співвідношення або взаємовиключність з іншими параметрами граф-cхем. Наведені ілюстративні приклади визначення окремих параметрів за заданою граф-схемою. Надано рекомендації щодо використання запропонованих параметрів для псевдовипадкової генерації граф-схем алгоритмів. Визначено такі загальні вимоги щодо коректної псевдовипадкової генерації граф-схем алгоритмів: можливість досягнення кінцевої вершини з будь-якої іншої вершини; відсутність вершин, у яких вхід не зв’язаний з виходом іншої вершини; відсутність повторення логічних умов у послідовно розташованих вершинах; наявність хоча б однієї операторної вершини тощо.
Посилання
Bailliul, J., Samad, T. (2015). Encyclopedia of Systems and Control. Springer: London, UK, 1554 p. https://doi.org/10.1007/978-1-4471-5058-9
Suh, S. C., Tanik, U. J., & Carbone, J. N. (2013). Applied Cyber-Physical Systems. New York, USA: Springer, 253 p. https://doi.org/10.1007/978-1-4614-7336-7
Kam, T., Villa, T., Brayton, R., & Sangiovanni-Vincentelli, A. (1997). A Synthesis of Finite State Machines: Functional Optimization. Boston, MA, USA: Springer, 282 p. https://doi.org/10.1007/978-1-4757-2622-0
Baranov, S. (1994). Logic Synthesis for Control Automata. Dordrecht: Kluwer Academic Publishers, 312 p.
Hartmanis, J., Stearns, R. E. (1966). Algebraic Structure Theory of Sequential Machines. New Jersey: Prentice-Hall, 211 p.
Czerwinski, R., Kania, D. (2013). Finite State Machine Logic Synthesis for Complex Programmable Logic Devices. Berlin: Springer, 172 p. https://doi.org/10.1007/978-3-642-36166-1
Sklyarova, I., Sklyarov, V., & Sudnitson, A. (2012). Design of FPGA-based Circuits using Hierarchical Finite State Machines. Tallin: TUT Press, 240 p.
Nelson, V., Nagle, H., Irwin, J., & Carroll, B. (1995). Digital logic circuit analysis and design. New Jersey: Prentice Hall, 842 p.
DeMicheli, G. (1994). Synthesis and Optimization of Digital Circuits. NY: McGraw-Hill, 576 p.
Baranov, S. (2008). Logic and System Design of Digital Systems. TUTPress: Tallinn, Estonia, 267 p.
Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis. Boston, MA, USA: Kluwer Academic, 264 p. https://doi.org/10.1007/978-1-4757-3393-8
Barkalov, A. A., Titarenko, L. A., Babakov, R. M., & Baiev, A. V. (2016). Logic synthesis for FPGA-based finite state machines: monograph. Vinnytsia: DonNU Vasyl' Stus, 195 p.
Baranov, S. (2018). Finite State Machines and Algorithmic State Machines. Seattle, WA, USA: Amazon, 185 p.
Yang, S. (1991). Logic synthesis and optimization benchmarks User Guide Version 3.0. Tech. rep. Microelectronics Center of North Carolina, P. O. Box 12889, Research Triangle Park, NC 27709.
Minns, P., Elliot, I. (2008). FSM-Based Digital Design Using Verilog HDL. New Jersey: J. Wiley & Sons, 408 p.
Barkalov, A., Titerenko, L. (2009). Logic synthesis for FSM-based control units. Berlin: Springer, 233 p.
Barkalov, A., Wegrzyn, M. (2006). Design of control units with programmable logic. Zielona Gora: University of Zielona Gуra Press, 150 p.
Barkalov, A., Titerenko, L. (2008). Logic synthesis for compositional microprogram control units. Berlin: Springer, 272 p.
Babakov, R. M. (2019). Development and Hardware Optimization of Control Units for IOT Devices in Industry Systems. Internet of Things for Industry and Human Applications. Vol. 1. Assessment and Implementation / V. S. Kharchenko (ed.). Ministry of Education and Science of Ukraine, National Aerospace University KhAI, p. 834–865.
Barkalov, A. A., Titarenko, L. A., & Babakov, R. M. (2023). Synthesis of VHDL-Model of a Finite State Machine with Datapath of Transitions. Radio Electronics, Computer Science, Control. Volume 4, p. 135–147. https://doi.org/10.15588/1607-3274-2023-4-13
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
