Improving LUT count of FPGA-based sequential blocks

• Autorzy: Barkalov Alexander , Titarenko Larysa , Mazurkiewicz Małgorzata , Krzywicki Kazimierz

Identyfikatory

DOI

10.24425/bpasts.2021.136728

• Języki publikacji: EN

Abstrakty

EN

Very often, a digital system includes sequential blocks which can be represented using a model of the finite state machine (FSM). It is very important to improve such FSM characteristics as the number of used logic elements, operating frequency and consumed energy. The paper proposes a novel technology-dependant design method targeting LUT-based Mealy FSMs. It belongs to the group of structural decomposition methods. The method is based on encoding the product terms of Boolean functions representing the FSM circuit. To diminish the number of LUTs, a partition of the set of internal states is constructed. It leads to three-level logic circuits of Mealy FSMs. Each function from the first level requires only a single LUT to be implemented. The method of constructing the partition with the minimum amount of classes is proposed. There is given an example of FSM synthesis with the proposed method. The experiments with standard benchmarks were conducted. They show that the proposed method can improve such FSM characteristics as the number of used LUTs. This improvement is accompanied by a decrease in performance. A positive side effect of the proposed method is a reduction in power consumption compared with FSMs obtained with other design methods.

Słowa kluczowe

EN

FPGA; LUT; Mealy FSM; synthesis; structural decomposition; product terms; partition

PL

FPGA; LUT; automat Mealy'ego; synteza; rozkład strukturalny; warunki produktu; przegroda

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2021
• Tom: Vol. 69, nr 2
• Strony: art. no. e136728
• Opis fizyczny: Bibliogr. 55 poz., rys., tab.

Twórcy

autor

Barkalov Alexander

• University of Zielona Góra, ul. Licealna 9, 65-417 Zielona Góra, Poland
• Vasyl’ Stus Dohetsk National University, 21, 600-richya str., Vinytsia, 21021, Ukraine

• https://orcid.org/0000-0002-4941-3979

autor

Titarenko Larysa

• University of Zielona Góra, ul. Licealna 9, 65-417 Zielona Góra, Poland
• Kharkiv National University of Radio Electronics, Nauky avenye, 14, 6166, Kharkiv, Ukraine

• https://orcid.org/0000-0001-9558-3322

autor

Mazurkiewicz Małgorzata

• University of Zielona Góra, ul. Licealna 9, 65-417 Zielona Góra, Poland

• https://orcid.org/0000-0001-5487-5468

autor

Krzywicki Kazimierz

• The Jacob of Paradies University, ul. Teatralna 25, 66-400 Gorzów Wielkopolski, Poland

• https://orcid.org/0000-0002-1088-5784

Bibliografia

• [1] J. Baillieul and T. Samad, Encyclopedia of Systems and Control, Springer, 2015.
• [2] M. Arora, Embedded System Design, Introduction to SoC System Architecture, Learning Bytes Publishing, 2016.
• [3] V. Chakravarthi, A Practical Approach to VLSI System on Chip (SoC) Design, A Comprehensive Guide, Springer, 2020.
• [4] P. Minns and I. Elliot, FSM-based digital design using Verilog HDL, John Wiley and Sons, 2008.
• [5] S. Baranov, Logic and System Design of Digital Systems, Tallinn: TUT Press, 2008.
• [6] B.D. Brown and H.C. Card, “Stochastic neural computation. I computational elements”, IEEE Trans. Comput. 50(9), 891‒905 (2001).
• [7] O. Barkalov, L. Titarenko, and M. Mazurkiewicz, Foundations of Embedded Systems, Springer, 2019.
• [8] A. Ardakani, F. Leduc-Primeau, N. Onizawa, T. Hanyu, and W.J. Gross, “VLSI Implementation of Deep Neural Network Using Integral Stochastic Computing”, IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 25(10), 26882699 (2017).
• [9] P. Li, D.J. Lilja, W. Qian, M.D. Riedel, and K. Bazargan, “Logical computation on stochastic bit streams with linear finitestate machines”, IEEE Trans. Comput. 63(6), 1474‒1486 (2014).
• [10] Y. Xie, S. Liao, B. Yuan, Y. Wang, and Z. Wang, “Fully-parallel area-efficient deep neural network design using stochastic computing”, IEEE Trans. Circuits Syst. II-Express Briefs 64(12), 1382‒1386 (2017).
• [11] N. Das and P.A. Priya, “FPGA Implementation of Reconfigurable Finite State Machine with Input Multiplexing Architecture Using Hungarian Method”, Int. J. Reconfigurable Comput. 2018, 6831901 (2018).
• [12] J. Glaser, M. Damm, J. Haase, and C. Grimm, “TR-FSM: Transition-Based Reconfigurable Finite State Machine”, ACM Trans. Reconfigurable Technol. Syst. 4, 23:1‒23:14 (2011).
• [13] R. Czerwinski and D. Kania, Finite State Machine Logic Synthesis for Complex Programmable Logic Devices, Springer, 2013.
• [14] V. Sklyarov, I. Skliarova, A. Barkalov, and L. Titarenko, Synthesis and optimization of FPGA-based systems, Springer, 2014.
• [15] M. Kubica, D. Kania, and J. Kulisz, “A Technology Mapping of FSMs Based on a Graph of Excitations and Outputs”, IEEE Access 7, 16123‒16131 (2019).
• [16] A. Opara, M. Kubica, and D. Kania, “Methods of Improving Time Efficiency of Decomposition Dedicated at FPGA Structures and Using BDD in the Process of Cyber-Physical Synthesis”, IEEE Access 7, 20619‒20631 (2019).
• [17] M. Kubica and D. Kania, “Area-oriented technology mapping for LUT-based logic blocks”, Int. J. Appl. Math. Comput. Sci. 27(1), 207‒222 (2017).
• [18] M. Kubica, A. Opara, and D. Kania, “Logic Synthesis for FPGAs Based on Cutting of BDD”, Microprocess. Microsyst. 52, 173‒187 (2017).
• [19] I. Skliarova, V. Sklyarov, and A. Sudnitson, Design of FPGAbased circuits using Hierarchical Finite State Machines, Tallinn: TUT Press, 2012.
• [20] Altera, [Online]. http://www.altera.com (accesed: May, 2020).
• [21] Atmel, [Online]. http://www.atmel.com (accesed: May, 2020).
• [22] Xilinx, [Online]. http://www.xilinx.com (accesed: May, 2020).
• [23] I. Kuon, R. Tessier, and J. Rose, “FPGA architecture: Survey and Challenges”, Found. Trends Electron. Design Automat. 2(2), 135‒253 (2008).
• [24] I. Grout, Digital Systems Design with FPGAs and CPLDs, Elsevier Science, 2011.
• [25] S. Kilts, Advanced FPGA Design: Architecture, Implementation, and Optimization, Wiley-IEEE Press, 2007.
• [26] Intel, “Intel SoC FPGA Embedded Development Suite User Guide”. [Online]. https://www.intel.com/content/www/us/en/ programmable/documentation/lro1402536290550.html (accesed: May, 2020).
• [27] Xilinix, “Zynq UltraScale+MPSoC”. [Online]. https://www.xilinx.com/products/silicon-devices/soc/zynq-ultrascale-mpsoc. html#productTable (accesed: May, 2020).
• [28] G. Stringham, Hardware/firmware Interface Design: Best Practices for Improving Embedded Systems Development, Newnes, 2010.
• [29] I. Skliarova and V. Sklyarov, FPGA-BASED hardware accelerators, Springer, 2019.
• [30] T. Łuba, M. Rawski, and Z. Jachna, “Functional Decomposition as a universal method for logic synthesis of digital circuits”, in Proceedings of IX International Conference MIXDES’02, 2002, p. 285290.
• [31] A. Ling, D.P. Singh, and S.D. Brown, “FPGA technology mapping: a study of optimality”, in Proceedings 42nd Design Automation Conference (DAC05), 2005, pp. 427‒432.
• [32] M. Kubica and D. Kania, “Technology mapping oriented to adaptive logic modules”, Bull. Pol. Acad. Sci. Tech. Sci. 67(5), 947‒956 (2019).
• [33] O. Barkalov, L. Titarenko, K. Mielcarek, and S. Chmielewski, Logic Synthesis for FPGA-Based Control Units: Structural Decomposition in Logic Design, Springer, 2020.
• [34] S. Yang, “Logic Synthesis and Optimization Benchmarks User Guide”, tech. rep., Microelectronic Center of North Carolina, 1991.
• [35] G.D. Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1994.
• [36] E. Testa, L. Amaru, M. Soeken, A. Mishchenko, P. Vuillod, J. Luo, C. Casares, P. Gaillardon, and G.D. Micheli, “Scalable boolean methods in a modern synthesis flow”, in 2019 Design, Automation Test in Europe Conference Exhibition (DATE), 2019, pp. 1643‒1648.
• [37] R. Brayton and A. Mishchenko, “ABC: An Academic Industrial-Strength Verification Tool”, in Computer Aided Verification, pp. 24‒40 eds. T. Touili, B. Cook, and P. Jackson, Springer, 2010.
• [38] A. Opara, M. Kubica, and D. Kania, “Methods of Improving Time Efficiency of Decomposition Dedicated at FPGA Structures and Using BDD in the Process of Cyber-Physical Synthesis”, IEEE Access 7, 20619‒20631 (2019).
• [39] O. Barkalov, L. Titarenko, and K. Mielcarek, “Hardware reduction for LUT-based Mealy FSMs”, Int. J. Appl. Math. Comput. Sci. 28(3), 595‒607 (2018).
• [40] Xilinix, “Virtex-7 family overview”. [Online]. https://www.xilinx.com/products/silicon-devices/fpga/virtex-7.html (accesed: May, 2020).
• [41] A. Mishchenko, R.K. Brayton, J.H.R. Jiang, and S. Jang, “Scalable Don’t-Care-Based Logic Optimization and Resynthesis”, ACM Trans. Reconfigurable Technol. Syst. 4(4), 34(1‒23) (2011).
• [42] A. Mishchenko, S. Chatterjee, and R.K. Brayton, “Improve-ments to Technology Mapping for LUT-based FPGAs”, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 26(2), 240253 (2007).
• [43] C. Scholl, Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publishers, 2001.
• [44] L. Machado and J. Cortadella, “Support-Reducing Decomposition for FPGA Mapping”, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 39(1), 213‒224 (2020).
• [45] R. Czerwinski, D. Kania, and J. Kulisz, “FSMs state encoding targeting at logic level minimization”, Bull. Pol. Acad. Sci. Tech. Sci. 54(4), 479‒487 (2006).
• [46] R. Czerwinski and D. Kania, “Synthesis method of high speed finite state machines”, Bull. Pol. Acad. Sci. Tech. Sci. 58(4), 635‒644 (2010).
• [47] A. Opara and D. Kania, “Decomposition-based logic synthesis for PAL-based CPLDs,” Int. J. Appl. Math. Comput. Sci. 20(2), 367‒384 (2010).
• [48] E. Sentowich, et al., “SIS: a system for sequential circuit synthesis”, in Proc. of the Inter. Conf. of Computer Design (ICCD’92), 1992, p.328333.
• [49] Xilinx, “XST User Guide. V. 11.3”. [Online]. http://www.xilinx.com/support/documentation/sw_manuals/xilinx11/xst.pdf (accesed: May, 2020).
• [50] Vivado. [Online]. https://www.xilinx.com/products/design_tools/ vivado.html (accesed: May, 2020).
• [51] A. Barkalov, L. Titarenko, M. Mazurkiewicz, and K. Krzywicki, “Encoding of terms in EMB-Based Mealy FSMs”, Appl. Sci. 10(8), 21 (2020).
• [52] S. Achasova, Synthesis algorithms for automata with PLAs, M: Soviet radio, 1987.
• [53] LGSynth93, “International Workshop on logic synthesis benchmark suite (LGSynth93)”. [Online]. https://people.engr.ncsu. edu/brglez/CBL/benchmarks/LGSynth93/LGSynth93.tar, 1993 (accesed: February, 2018).
• [54] B. Lin, “Synthesis of multiple-level logic from symbolic highlevel description languages”, in IFIP International Conference on Very Large Scale Integration, 1989, pp. 187‒196).
• [55] M. Rawski, L. Jozwiak, M. Nowicka, and T. Łuba, “Nondisjoint decomposition of boolean functions and its application in FPGA-oriented technology mapping”, in EUROMICRO 97. Proceedings of the 23rd EUROMICRO Conference: New Frontiers of Information Technology (Cat. No.97TB100167), 1997, pp. 24‒30.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).