ENCODING OF COLLECTIONS OF MICROOPERATIONS FOR THREE-LEVEL COMBINED AUTOMATON
DOI:
https://doi.org/10.18372/2310-5461.44.14314Keywords:
combined microprogrammed automaton, synthesis, FPGA, LUT, partitioning, collections of microoperationsAbstract
Presently the models of firmware automats (МPА) are widely used for the task of behavior of control (CU) unit. One of these models is a combined MPA (SMPA). Its characteristic feature is the presence of two types of output signals. The output signals of the Mile automaton exist at transitions between states of the automaton. The output of the Moore machine is determined only by the state of the machine and lasts almost a whole cycle. Due to the versatility of this model, it has become the basis for the research presented in this article. The most popular basis used to implement digital systems is FPGA (field-programmable logic arrays). The main elements of the FPGA used to implement MPAs are LUT (look-up table) elements, programmable triggers, and programmable interconnects.
The paper proposes a method of reducing hardware costs in the scheme of a combined machine, implemented in a common base of LUT elements and blocks of memory EMB. The method is based on replacement of logical conditions and partition of the set of states by classes. Each class corresponds to a single block of the circuit. This approach leads to circuits with regular structure and three levels of logic.
The proposed model leads to schemes with regular connections. This simplifies the placement and tracing tasks when implementing the SMPA scheme. A positive feature of the proposed model is the fact that the Clock and Start signals are associated with only one block of the circuit. This avoids the problems associated with the so-called distortion synchronization.
Analysis of the special library showed that the proposed method is appropriate to use for 78% of test cases. Studies were performed for chips of the Virtex-6 family (S = 6). In this case, the developed SMPA models differed at high speed than their counterparts having the previous structure. For the remaining 22% of the test cases, the payoff was much smaller, as the specialized LUT units were implemented in the form of multilevel schemes.
A further direction of research is related to: 1) the replacement of some LUTs by EMBs and 2) the use of logical conditions encoding methods to reduce the parameter K.
References
Grout I. Digital Systems Design with FPGAs and CPLDs. Amsterdam: Elseveit, 2008. 784 pp.
Баркалов А.А., Титаренко Л. А., Визор Я. Е., Матвиенко А. В., Горина В. В. Уменьшение числа LUT элементов в схеме совмещенного автомата. Управляющие системы и машины. 2016. №3.
С. 16–22.
Грушницкий Р. И., Мурсаев А. Х., Угрюмов Е. П. Проектирование систем с использованием микросхем программируемой логики. СПб: БХВ. Петербург, 2002. 608 с.
Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA–based circuits using Hierarchical Finite State Machines. Tallinn: TUT Press, 2012. 240 pp.
Jozwiak L., Chojnski A. Effective and efficient FPGA synthesis through general functional decomposition. Journal of System Architecture. 2003. №4. Pp. 247–265.
Баркалов А. А., Титаренко Л. А., Визор Я.Е., Матвиенко А.В. Уменьшение аппаратурных затрат в совмещенных автоматах. Управляющие системы и машины. 2017. №4. С. 43–50.
Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Реализация схемы совмещенного автомата в базисе FPGA. Комп’ютернi засоби, мережi та системи. К.: Ін-т кібернетики імені
В. М. Глушкова НАН України, 2016. С. 10–19.
Baranov S. Logic Synthesis for Control Automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 pp.
Intel. FPGAs and Programmable Devises. URL: www.altera.com (date access 15.09.2019).
Xilinx. Adaptable & Real-Time AI Inference Acceleration. URL: www.xilinx.com (date access 15.09.2019).
Yang S. Logic Synthesis and optimization benchmarks user guide. Microelectronics Center of North Carolina. 1991. 43 pp.
Kubica M., Kania D., Kulisz J. A technology mapping of FSMs based on a graph of excitations and outputs. IEEE Access. 2018. №6. Pp. 16123–16131.
Rawski M., Tomaszewicz P., Borowski G., Łuba T. Logic Synthesis Method of Digital Circuits Designed for Implementation with Embedded Memory Blocks on FPGAs. Design of Digital Systems and Devises. LNEE 70. Berlin: Springer, 2011. Pp. 121–144.
Barkalov A., Titarenko L. Logic Synthesis for FSM–based Control Units. Berlin: Springer, 2009. 233 pp.
Barkalov A., Titarenko L., Mazurkiewicz M. Foundations of embedded systems. Berlin: Springer, 2019. 196 pp.
Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Реализация схемы совмещенного микропрограммного автомата в базисе FPGA. Проблеми інформатизації та управління. 2015. Вип. 3(51). С. 5–13.
Соловьев В.В. Проектирование цифровых схем на основе программируемых логических интегральных схем. М. : Горячая линия ТЕЛЕКОМ, 2001. 636 с.
Jozwiak L. Using FPGAs in Cyber-Physical Synthesis. Journal of System Architecture. 2013. №2. Pp. 124–1365.
Opara A., Kubica M., Kania D. Method of improving time efficiency of decomposition dedicated at FPGA structures and using BDD in process of cyber-physical synthesis. IEEE Access. 2019. №1. Pp. 18101–18113.
Barkalov A., Titarenko L., Mielcatek K. Twofold state assignment for FPGA - based Mealy FSMs. Proceedings of International Conference
MOCAST-18 (Thessaloniki, Greece. – New York). IEEE Explore. 2018. Pp. 1–4.
Barkalov A., Titarenko L., Mielcatek K. Hardware Reduction for LUT-based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2018. V. 28. № 3. Pp. 595–607. doi.org/10.2478/amcs-2018-0046.
Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and Optimization of FPGA-based Systems. Berlin: Springer, 2014. 432 pp.
