Hardware Reduction for Lut–Based Mealy FSMs

Barkalov, Alexander; Titarenko, Larysa; Mielcarek, Kamil

doi:10.2478/amcs-2018-0046

Abstract

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.

References

ABC System (2018). https://people.eecs.berkeley.edu/~alanmi/abc/.
Search in Google Scholar Back to article
Altera (2018). Cyclone IV Device Handbook, http://www.altera.com/literature/hb/cyclone-iv/cyclone4-handbook.pdf.
Search in Google Scholar Back to article
Baranov, S. (1994). Logic Synthesis of Control Automata, Kluwer, Boston, MA.10.1007/978-1-4615-2692-6
Search in Google Scholar Back to article
Baranov, S. (2008). Logic and System Design of Digital Systems, TUT Press, Tallinn.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Barkalov, A. and Titarenko, L. (2009). Logic Synthesis for FSMbased Control Units, Springer, Berlin.10.1007/978-3-642-04309-3
Search in Google Scholar Back to article
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.10.1007/s10559-012-9410-2
Search in Google Scholar Back to article
Barkalov, A., Titarenko, L., Kołopie´nczyk, M., Mielcarek, K. and Bazydło, G. (2015). Logic Synthesis for FPGA-Based Finite State Machines, Springer, Cham.10.1007/978-3-319-24202-6
Search in Google Scholar Back to article
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.1145/329166.329183
Search in Google Scholar Back to article
Czerwiński, R. and Kania, D. (2013). Finite State Machine Logic Synthesis for Complex Programmable Logic Devices, Springer, Berlin.10.1007/978-3-642-36166-1
Search in Google Scholar Back to article
DEMAIN (2018). http://zpt2.tele.pw.edu.pl/Files/demain/demain.htm.
Search in Google Scholar Back to article
Gajski, D.D., Abdi, S., Gerstlauer, A. and Schirner, G. (2009). Embedded System Design: Modeling, Synthesis and Verification, Springer, Berlin/Heidelberg.10.1007/978-1-4419-0504-8
Search in Google Scholar Back to article
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.10.1109/TCAD.2015.2406859
Search in Google Scholar Back to article
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.10.1109/ISIE.2007.4374972
Search in Google Scholar Back to article
Grout, I. (2008). Digital Systems Design with FPGAs and CPLDs, Elsevier, Oxford.
Search in Google Scholar Back to article
Kam, T., Villa, T., Brayton, R. and Sangiovanni-Vincentelli, A. (1997). A Synthesis of Finite State Machines: Functional Optimization, Springer, Boston, MA.10.1007/978-1-4757-2622-0
Search in Google Scholar Back to article
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.10.1142/S0218126617501250
Search in Google Scholar Back to article
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.10.1515/amcs-2017-0015
Open DOI Search in Google Scholar Back to article
LGSynth93 (1993). Benchmarks test, http://people.engr.ncsu.edu/brglez/CBL/benchmarks/LGSynth93/LGSynth93.ta.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Maxfield, C. (2004). The Design Warrior’s Guide to FPGAs, Academic Press, Orlando, FL.
Search in Google Scholar Back to article
Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill, New York, NY.
Search in Google Scholar Back to article
Minns, P. and Elliot, I. (2008). FSM-Based Digital Design Using Verilog HDL, Wiley, Hoboken, NJ.10.1002/9780470987629
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
PKmin (2018). http://pkmin.za.pl/.
Search in Google Scholar Back to article
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.10.1016/j.sysarc.2004.07.004
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.1007/978-3-642-17545-9_5
Search in Google Scholar Back to article
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.10.1515/amcs-2017-0003
Open DOI Search in Google Scholar Back to article
Sasao, T. (2011). Memory-Based Logic Synthesis, Springer, New York, NY.10.1007/978-1-4419-8104-2
Search in Google Scholar Back to article
Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer, Boston, MA.10.1007/978-1-4757-3393-8
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.1007/3-540-44614-1_76
Search in Google Scholar Back to article
Sklyarov, V., Skliarova, I., Barkalov, A. and Titarenko, L. (2014). Synthesis and Optimization of FPGA-Based Systems, Springer, Berlin.10.1007/978-3-319-04708-9
Search in Google Scholar Back to article
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.10.1007/3-540-45716-X_36
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Xilinx (2018). Virtex-5 Family Overview, http://www.xilinx.com/support/documentation/data_sheets/ds100.pdf.
Search in Google Scholar Back to article

Hardware Reduction for Lut–Based Mealy FSMs

Abstract

Paradigm

My account