Hardware reduction for LUT-based mealy FSMs

• Autorzy: Barkalov A. , Titarenko L. , Mielcarek K.

Identyfikatory

DOI

10.2478/amcs-2018-0046

• Języki publikacji: EN

Abstrakty

EN

A method is proposed targeting a decrease in the number of LUTs in circuits of FPGA-based Mealy FSMs. The method improves hardware consumption for Mealy FSMs with the encoding of collections of output variables. The approach is based on constructing a partition for the set of internal states. Each state has two codes. It diminishes the number of arguments in input memory functions. An example of synthesis is given, along with results of investigations. The method targets rather complex FSMs, having more than 15 states.

Słowa kluczowe

EN

Mealy FSM; FPGA; LUT; partition; encoding collection; output variables

PL

automat Mealy'ego; FPGA; LUT; zbiór kodowany; zmienne wyjściowe

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2018
• Tom: Vol. 28, no. 3
• Strony: 595--607
• Opis fizyczny: Bibliogr. 37 poz., rys., tab., wykr.

Twórcy

autor

Barkalov A.

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

autor

Titarenko L.

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

autor

Mielcarek K.

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

Bibliografia

• [1] ABC System (2018). https://people.eecs.berkeley.edu/~alanmi/abc/.
• [2] Altera (2018). Cyclone IV Device Handbook, http://www.altera.com/literature/hb/cyclone-iv/cyclone4-handbook.pdf.
• [3] Baranov, S. (1994). Logic Synthesis of Control Automata, Kluwer, Boston, MA.
• [4] Baranov, S. (2008). Logic and System Design of Digital Systems, TUT Press, Tallinn.
• [5] 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.
• [6] Barkalov, A. and Titarenko, L. (2009). Logic Synthesis for FSM-based Control Units, Springer, Berlin.
• [7] Barkalov, A., Titarenko, L. and Barkalov Jr., A. (2012). Structural decomposition as a tool for the optimization of an FPGA-based implementation of a Mealy FSM, Cybernetics and Systems Analysis 48(2): 313–322.
• [8] 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.
• [9] Cong, J. and Yan, K. (2000). Synthesis for FPGAs with embedded memory blocks, Proceedings of the 2000 ACM/SIGDA 8th International Symposium on FPGAs, New York, NY, USA, pp. 75–82.
• [10] Czerwiński, R. and Kania, D. (2013). Finite State Machine Logic Synthesis for Complex Programmable Logic Devices, Springer, Berlin.
• [11] DEMAIN (2018). http://zpt2.tele.pw.edu.pl/Files/demain/demain.htm.
• [12] Gajski, D.D., Abdi, S., Gerstlauer, A. and Schirner, G. (2009). Embedded System Design: Modeling, Synthesis and Verification, Springer, Berlin/Heidelberg.
• [13] Garcia-Vargas, I. and Senhadji-Navarro, R. (2015). Finite state machines with input multiplexing: A performance study, IEEE Transactions a Computer-Aided Design of Integrated Circuits and Systems 34(5): 867–871.
• [14] 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, Proceedings of the IEEE International Symposium on Industrial Electronics, ISIE 2007, Toronto, Canada, pp. 2342–2347.
• [15] Grout, I. (2008). Digital Systems Design with FPGAs and CPLDs, Elsevier, Oxford.
• [16] Kam, T., Villa, T., Brayton, R. and Sangiovanni-Vincentelli, A. (1997). A Synthesis of Finite State Machines: Functional Optimization, Springer, Boston, MA.
• [17] 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.
• [18] 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.
• [19] LGSynth93 (1993). Benchmarks test, http://people.engr.ncsu.edu/brglez/CBL/benchmarks/LGSynth93/LGSynth93.tar.
• [20] Lin, B. and Newton, A. (1989). Synthesis of multiple level logic from symbolic high-level description languages, Proceedings of the International Conference on VLSI, Taipei, Taiwan, pp. 187–196.
• [21] Maxfield, C. (2004). The Design Warrior’s Guide to FPGAs, Academic Press, Orlando, FL.
• [22] Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill, New York, NY.
• [23] Minns, P. and Elliot, I. (2008). FSM-Based Digital Design Using Verilog HDL, Wiley, Hoboken, NJ.
• [24] Nowicka, M., Łuba, T. and Rawski, M. (1999). FPGA-based decomposition of Boolean functions: Algorithms and implementation, Proceedings of the 6th International Conference on Advanced Computer Systems, Szczecin, Poland, pp. 502–509.
• [25] PKmin (2018). http://pkmin.za.pl/.
• [26] Rawski, M., Selvaraj, H. and Łuba, T. (2005a). An application of functional decomposition in ROM-based FSM implementation in FPGA devices, Journal of System Architecture 51(6–7): 423–434.
• [27] Rawski, M., Selvaraj, H., Luba, T. and Szotkowski, P. (2005b). Application of symbolic functional decomposition concept in FSM implementation targeting FPGA devices, Proceedings of the 6th International Conference on Computational Intelligence and Multimedia Applications (ICCIMA’05), Las Vegas, NV, USA, pp. 153–158.
• [28] 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, Springer, Berlin, pp. 121–144.
• [29] Sajewski, Ł. (2017). Minimum energy control of descriptor fractional discrete-time linear systems with two different fractional orders, International Journal of Applied and Computer Science 27(1): 33–41, DOI: 10.1515/amcs-2017-0003.
• [30] Sasao, T. (2011). Memory-Based Logic Synthesis, Springer, New York, NY.
• [31] Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer, Boston, MA.
• [32] Sentowich, E., Singh, K., Lavango L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., P, P.S., Bryton, R. and Sangiovanni-Vincentelli, A. (1992). SIS: A system for sequential circuit synthesis, Technical report, University of California, Berkeley, CA.
• [33] Sklyarov, V. (2000). Synthesis and implementation of RAM-based finite state machines in FPGAs, Proceedings of the 10th International Conference on Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing, Villach, Austria, pp. 718–728.
• [34] Sklyarov, V., Skliarova, I., Barkalov, A. and Titarenko, L. (2014). Synthesis and Optimization of FPGA-Based Systems, Springer, Berlin.
• [35] Sutter, G., Todorovich, E., López-Buedo, S. and Boemo, E. (2002). Low-power FSMs in FPGA: Encoding alternatives, Proceedings of the 12th International Workshop on Power and Timing Modelling Optimization and Simulation, Sevilla, Spain, pp. 363–370.
• [36] 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, Paris, France, pp. 916–921.
• [37] Xilinx (2018). Virtex-5 Family Overview, http://www.xilinx.com/support/documentation/data_sheets/ds100.pdf.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).