Tytuł artykułu

Improving LUT count of FPGA-based sequential blocks

Tytuł czasopisma

Bulletin of the Polish Academy of Sciences Technical Sciences








Barkalov, Alexander : University of Zielona Góra, ul. Licealna 9, 65-417 Zielona Góra, Poland ; Barkalov, Alexander : Vasyl’ Stus Dohetsk National University, 21, 600-richya str., Vinytsia, 21021, Ukraine ; Titarenko, Larysa : University of Zielona Góra, ul. Licealna 9, 65-417 Zielona Góra, Poland ; Titarenko, Larysa : Kharkiv National University of Radio Electronics, Nauky avenye, 14, 6166, Kharkiv, Ukraine ; Mazurkiewicz, Małgorzata : University of Zielona Góra, ul. Licealna 9, 65-417 Zielona Góra, Poland ; Krzywicki, Kazimierz : The Jacob of Paradies University, ul. Teatralna 25, 66-400 Gorzów Wielkopolski, Poland


Słowa kluczowe

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

Wydział PAN

Nauki Techniczne




  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]. (accesed: May, 2020).
  21.  Atmel, [Online]. (accesed: May, 2020).
  22.  Xilinx, [Online]. (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]. documentation/lro1402536290550.html (accesed: May, 2020).
  27.  Xilinix, “Zynq UltraScale+MPSoC”. [Online]. 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]. (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]. (accesed: May, 2020).
  50.  Vivado. [Online]. (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]. 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.






DOI: 10.24425/bpasts.2021.136728 ; ISSN 2300-1917


Bulletin of the Polish Academy of Sciences: Technical Sciences; 2021; 69; 2; e136728