Improving characteristics of LUT-based Mealy FSMs

• Autorzy: Barkalov Alexander , Titarenko Larysa , Mielcarek Kamil
• Języki publikacji: EN

Abstrakty

EN

Practically, any digital system includes sequential blocks represented using a model of finite state machine (FSM). It is very important to improve such FSM characteristics as the number of logic elements used, operating frequency and consumed energy. The paper proposes a novel technology-dependent design method targeting a decrease in the number of look-up table (LUT) elements and their levels in logic circuits of FPGA-based Mealy FSMs. It produces FSM circuits having three levels of logic blocks. Also, it produces circuits with regular systems of interconnections between the levels of logic. The method is based on dividing the set of internal states into two subsets. Each subset corresponds to a unique part of an FSM circuit. Only a single LUT is required for implementing each function generated by the first part of the circuit. The second part is represented by a multi-level circuit. The proposed method belongs to the group of two-fold state assignment methods. Each internal state is encoded as an element of the set of states and as an element of some of its subsets. A binary state assignment is used for states corresponding to the first part of the FSM circuit. The one-hot assignment is used for states corresponding to the second part. An example of FSM synthesis with the proposed method is shown. The experiments with standard benchmarks are conducted to analyze the efficiency of the proposed method. The results of experiments show that the proposed approach leads to diminishing the number of LUTs in the circuits of rather complex Mealy FSMs having more than 15 internal states. The positive property of this method is a reduction in energy consumption (without any overhead cost) and an increase in operating frequency compared with other investigated methods.

Słowa kluczowe

EN

FPGA; LUT; Mealy FSM; structural decomposition; two fold state assignment; energy consumption

PL

FPGA; LUT; FSM; dekompozycja strukturalna; zużycie energii

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2020
• Tom: Vol. 30, no. 4
• Strony: 745--759
• Opis fizyczny: Bibliogr. 69 poz., rys., tab.

Twórcy

autor

Barkalov Alexander

• Institute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. Szafrana 2, 65-516 Zielona Góra, Poland

autor

Titarenko Larysa

• Institute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. Szafrana 2, 65-516 Zielona Góra, Poland

autor

Mielcarek Kamil

• Institute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. Szafrana 2, 65-516 Zielona Góra, Poland

Bibliografia

• [1] ABC System (2020). https://people.eecs.berkeley.edu/~alanmi/abc/.
• [2] Agrawal, R., Borowczak, M. and Vemuri, R. (2019). A state encoding methodology for side-channel security vs. power trade-off exploration, 32nd International Conference on VLSI Design and 18th International Conference on Embedded Systems (VLSID), Delhi, India pp. 70–75.
• [3] Altera (2020). Cyclone IV Device Handbook, http://www.a ltera.com/literature/hb/cyclone-iv/cyclone4-handbook.pdf.
• [4] Ardakani, A., Leduc-Primeau, F., Onizawa, N., Hanyu, T. and Gross, W.J. (2017). VLSI implementation of deep neural network using integral stochastic computing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 25(10): 2688–2699.
• [5] Baranov, S. (1994). Logic Synthesis of Control Automata, Kluwer, Boston, MA.
• [6] Baranov, S. (2008). Logic and System Design of Digital Systems, TUT Press, Tallinn.
• [7] Barkalov, A.A. and Barkalov Jr., A.A. (2005). Design of Mealy finite-state machines with the transformation of object codes, International Journal of Applied Mathematics and Computer Science 15(1): 151–158.
• [8] Barkalov, A. and Titarenko, L. (2009). Logic Synthesis for FSM based Control Units, Springer, Berlin.
• [9] Barkalov, A., Titarenko, L., Kołopieńczyk, M., Mielcarek, K. and Bazydło, G. (2015). Logic Synthesis for FPGA-Based Finite State Machines, Springer, Cham.
• [10] Barkalov, A., Titarenko, L., Mazurkiewicz, M. and Krzywicki, K. (2020a). Encoding of terms in EMB-based Mealy FSMs, Applied Sciences 10(8): 21.
• [11] Barkalov, A., Titarenko, L., Mielcarek, K. and Chmielewski, S. (2020b). Logic Synthesis for FPGA-Based Control Units—Structural Decomposition in Logic Design, Springer, Berlin.
• [12] Barkalov, O., Titarenko, L. and Mielcarek, K. (2018). Hardware reduction for LUT-based Mealy FSMs, International Journal of Applied Mathematics and Computer Science 28(3): 595–607, DOI: 10.2478/amcs-2018-0046.
• [13] Benini, L., Bogliolo, A. and Micheli, G. (2000). A survey of design techniques for system-level dynamic power management, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 8(3): 299–316.
• [14] Benini, L. and De Micheli, G. (1995). State assignment for low power dissipation, IEEE Journal of Solid-State Circuits 30(3): 258–268.
• [15] Benini, L., De Micheli, G. and Macii, E. (2001). Designing low-power circuits: Practical recipes, IEEE Circuits and Systems Magazine 1(1): 6–25.
• [16] Borowik, G. (2018). Optimization on the complementation procedure towards efficient implementation of the index generation function, International Journal of Applied Mathematics and Computer Science 28(4): 803–815, DOI: 10.2478/amcs-2018-0061.
• [17] Brayton, R. and Mishchenko, A. (2010). ABC: An academic industrial-strength verification tool, in T. Touili et al. (Eds), Computer Aided Verification, Springer, Berlin/Heidelberg, pp. 24–40.
• [18] Brown, B.D. and Card, H.C. (2001). Stochastic neural computation. I: Computational elements, IEEE Transactions on Computers 50(9): 891–905.
• [19] Choudhury, P. and Pradhan, S. (2012). Power modeling of power gated FSM and its low power realization by simultaneous partitioning and state encoding using genetic algorithm, in H. Rahaman et al. (Eds), Progress in VLSI Design and Test, Springer, Berlin/Heidelberg, pp. 19–29.
• [20] Chow, S., Ho, Y.-C., Hwang, T. and Liu, C. (1996). Low power realization of finite state machines—A decomposition approach, ACM Transactions on Design Automation of Electronic Systems 1(3): 315–340.
• [21] Cong, J. and Yan, K. (2000). Synthesis for FPGAs with embedded memory blocks, Proceedings of the 2000 ACM/SIGDA Eighth International Symposium on Field Programmable Gate Arrays, FPGA’00, Monterey, CA, USA, pp. 75–82.
• [22] Czerwiński, R. and Kania, D. (2013). Finite State Machine Logic Synthesis for Complex Programmable Logic Devices, Springer, Berlin.
• [23] Das, N. and Priya, P.A. (2018). FPGA implementation of reconfigurable finite state machine with input multiplexing architecture using Hungarian method, International Journal of Reconfigurable Computing 2018: 1–15.
• [24] Gajski, D. D., Abdi, S., Gerstlauer, A. and Schirner, G. (2009). Embedded System Design: Modeling, Synthesis and Verification, Springer, Berlin.
• [25] Garcia-Vargas, I. and Senhadji-Navarro, R. (2015). Finite state machines with input multiplexing: A performance study, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34: 867–871.
• [26] Garcia-Vargas, I., Senhadji-Navarro, R., Jiménez-Moreno, G., Civit-Balcells, A. and Guerra-Gutierrez, P. (2007). ROM-based finite state machine implementation in low cost FPGAs, IEEE International Symposium on Industrial Electronics ISIE 2007, Vigo, Spain, pp. 2342–2347.
• [27] Glaser, J., Damm, M., Haase, J. and Grimm, C. (2011). TR-FSM: Transition-based reconfigurable finite state machine, ACM Transactions on Reconfigurable Technology and Systems 4(3): 23:1–23:14.
• [28] Grout, I. (2008). Digital Systems Design with FPGAs and CPLDs, Elsevier, Oxford.
• [29] Kam, T., Villa, T., Brayton, R. and Sangiovanni-Vincentelli, A. (2010). A Synthesis of Finite State Machines: Functional Optimization, Springer, Boston, MA.
• [30] Khatri, S. and Gulati, K. (Eds) (2011). Advanced Techniques in Logic Synthesis, Optimizations and Applications, Springer, New York, NY.
• [31] Kołopieńczyk, M., Titarenko, L. and Barkalov, A. (2017). Design of EMB-based Moore FSMs, Journal of Circuits, Systems, and Computers 26(7): 1–23.
• [32] Kubatova, H. and Becvar, M. (2002). FEL-Code: FSM internal state encoding method, Proceedings of the 5th International Workshop on Boolean Problems, Freiberg, Germany, pp. 109–114.
• [33] Kubica, M. and Kania, D. (2017). Area-oriented technology mapping for LUT-based logic blocks, International Journal of Applied Mathematics and Computer Science 27(1): 207–222, DOI: 10.1515/amcs-2017-0015.
• [34] Kubica, M., Kania, D. and Kulisz, J. (2019). A technology mapping of FSMs based on a graph of excitations and outputs, IEEE Access 7: 16123–16131.
• [35] LGSynth93 (1993). Benchmark suite, International Workshop on Logic Synthesis, Tahoe City, CA, USA, https://people.engr.ncsu.edu/brglez/CBL/benchmarks/LGSynth93/LGSynth93.tar.
• [36] Li, J., Ren, A., Li, Z., Ding, C., Yuan, B., Qiu, Q. and Wang, Y. (2017). Towards acceleration of deep convolutional neural networks using stochastic computing, 22nd Asia and South Pacific Design Automation Conference, ASPDAC, Chiba/Tokyo, Japan, pp. 115–120.
• [37] Li, P., Lilja, D.J., Qian, W., Riedel, M.D. and Bazargan, K. (2014). Logical computation on stochastic bit streams with linear finite-state machines, IEEE Transactions on Computers 63(6): 1474–1486.
• [38] Liu, B., Cai, Y., Zhou, Q., Bian, J. and Hong, X. (2005). FSM decomposition for power gating design automation in sequential circuits, 6th International Conference on ASIC, Shanghai, China, Vol. 2, pp. 944–947.
• [39] Machado, L. and Cortadella, J. (2020). Support-reducing decomposition for FPGA mapping, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39(1): 213–224.
• [40] Maxfield, C. (2004). The Design Warrior’s Guide to FPGAs, Academic Press, Orlando, FL.
• [41] Michalski, T. and Kokosiński, Z. (2016). Functional decomposition of combinational logic circuits with PKmin, Technical Transactions: Electrical Engineering 113(2-E): 191–202.
• [42] Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill, New York, NY.
• [43] Mishchenko, A. and Brayton, R. (2006). Scalable logic synthesis using a simple circuit structure, https://people.eecs.berkeley.edu/~brayton/publications/2006/iwls06_sls.pdf.
• [44] Mishchenko, A. and Brayton, R. (2007). SAT-based logic optimization and resynthesis, https://people.eecs.berkeley.edu/~alanmi/publications/2007/tech07_imfs.pdf.
• [45] Mishchenko, A., Brayton, R., Jiang, J.-H.R. and Jang, S. (2011). Scalable don’t-care-based logic optimization and resynthesis, ACM Transactions on Reconfigurable Technology and Systems 4(4): 23.
• [46] Nag, A., Das, S. and Pradhan, S. (2018). Low power FSM synthesis based on automated power and clock gating technique, Journal of Circuits, Systems and Computers 28(5), Article ID 1920003.
• [47] Nowicka, M., Łuba, T. and Rawski, M. (1999). FPGA-based decomposition of Boolean functions: Algorithms and implementation, 6th International Conference on Advanced Computer Systems, Szczecin, Poland, pp. 502–509.
• [48] Opara, A. and Kania, D. (2010). Decomposition-based logic synthesis for PAL-based CPLDs, International Journal of Applied Mathematics and Computer Science 20(2): 367–384, DOI: 10.2478/v10006-010-0027-1.
• [49] Opara, A., Kubica, M. and Kania, D. (2019). 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.
• [50] PKmin (2020). http://www.pk.edu.pl/~zk/PKmin/PKmin_pomoc-help.zip.
• [51] Pradhan, S., Kumar, M. and Chattopadhyay, S. (2011). Low power finite state machine synthesis using power-gating, Integration 44(3): 175–184.
• [52] Rafla, N.I. and Gauba, I. (2010). A reconfigurable pattern matching hardware implementation using on-chip RAM-based FSM, 53rd IEEE International Midwest Symposium on Circuits and Systems, Boise, ID, USA, pp. 49–52.
• [53] Rawski, M., Jozwiak, L., Nowicka M. and Luba T. (1997). Non-disjoint decomposition of Boolean functions and its application in FPGA-oriented technology mapping, Proceedings of the 23rd EUROMICRO Conference: New Frontiers of Information Technology, Budapest, Hungary, pp. 24–30.
• [54] Rawski, M., Selvaraj, H. and Łuba, T. (2005). An application of functional decomposition in ROM-based FSM implementation in FPGA devices, Journal of System Architecture 51(6–7): 423–434.
• [55] Rawski, M., Tomaszewicz, P., Borowski, G. and Łuba, T. (2011). Logic synthesis method of digital circuits designed for implementation with embedded memory blocks on FPGAs, in M. Adamski et al. (Eds), Design of Digital Systems and Devices (LNEE 79), Springer, Berlin, pp. 121–144.
• [56] Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer, Boston, MA.
• [57] Sentowich, E., Singh, K., Lavango, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P., Bryton, R. and Sangiovanni-Vincentelli, A. (1992). SIS: A system for sequential circuit synthesis, Technical report, University of California, Berkely, CA.
• [58] Sklyarov, V. (2000). Synthesis and implementation of RAM-based finite state machines in FPGAs, Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing, Villach, Austria, pp. 718–728.
• [59] Sklyarov, V., Skliarova, I., Barkalov, A. and Titarenko, L. (2014). Synthesis and Optimization of FPGA-Based Systems, Springer, Berlin.
• [60] Sutter, G., Todorovich, E., López-Buedo, S. and Boemo, E. (2002). Low-power FSMs in FPGA: Encoding alternatives, Integrated Circuit Design. Power and Timing Modeling, Optimization and Simulation, Seville, Spain, pp. 363–370.
• [61] Testa, E., Amaru, L., Soeken, M., Mishchenko, A., Vuillod, P., Luo, J., Casares, C., Gaillardon, P. and Micheli, G.D. (2019). Scalable Boolean methods in a modern synthesis flow, Design, Automation Test in Europe Conference Exhibition (DATE), Florence, Italy, pp. 1643–1648.
• [62] Tiwari, A. and Tomko, K. (2004). Saving power by mapping finite-state machines into embedded memory blocks in FPGAs, Proceedings of the Conference on Design, Automation and Test in Europe, Vol. 2, pp. 916–921.
• [63] Vivado (2020). https://www.xilinx.com/products/design-tools/vivado.html.
• [64] Wu, X., Pedram, M. and Wang, L. (2000). Multi-code state assignment for low-power design, IEEE Proceedings on Circuits, Devices and Systems 147(5): 271–275.
• [65] Xie, Y., Liao, S., Yuan, B., Wang, Y. and Wang, Z. (2017). Fully-parallel area-efficient deep neural network design using stochastic computing, IEEE Transactions on Circuits and Systems II: Express Briefs 64(12): 1382–1386.
• [66] Xilinx (2010). Virtex-4 Family Overview, http://www.xilinx.com/support/documentation/data_sheets/ds112.pdf.
• [67] Xilinx (2015). Virtex-5 Family Overview, http://www.xilinx.com/support/documentation/data_sheets/ds100.pdf.
• [68] Xilinx (2020a). http://www.xilinx.com.
• [69] Xilinx (2020b). ISE Foundation, https://www.xilinx.com/products/design-tools/ise-design-suite.html.