Logical minimization for combinatorial structure in FPGA

The paper describes the research results of application efficiency of minimization programs of functional descriptions of combinatorial logic blocks, which are included in digital devices projects that are implemented in FPGA. Programs are designed for shared and separated function minimization in a disjunctive normal form (DNF) class and minimization of multilevel representations of fully defined Boolean functions based on Shannon expansion with finding equal and inverse cofactors. The graphical form of such representations is widely known as binary decision diagrams (BDD). For technological mapping the program of "enlargement" of obtained Shannon expansion formulas was applied in a way that each of them depends on a limited number of k input variables and can be implemented on one LUT-k – a programmable unit of FPGA with k input variables. It is shown that a preliminary logic minimization, which is performed on the domestic programs, allows improving design results of foreign CAD systems such as Leonardo Spectrum (Mentor Graphics), ISE (Integrated System Environment) Design Suite and Vivado (Xilinx). The experiments were performed for FPGA families’ Virtex-II PRO, Virtex-5 and Artix-7 (Xilinx) on standard threads of industrial examples, which define both DNF systems of Boolean functions and systems represented as interconnected logical equations.

1. Zotov Yu. V. Proektirovanie cifrovyh ustrojstv na osnove PLIS firmy XILINX v SAPR WebPack ISE. The Design of Digital Devices Based on FPGA in XILINX ISE WebPack CAD. Moscow, Goryachaya liniya – Telekom, 2003, 624 р. (in Russian).

2. Designing with Xilinx FPGAs. Using Vivado. In Churiwala S. (ed.). Springer, 2017, 260 p.

3. Kalyaev I. A., Levin I. I., Semernikov E. A., Shmojlov V. I. Rekonfiguriruemye mul'tikonvejernye vychislitel'nye struktury. Multiconference Reconfigurable Computing Structures. In Kalyaev I. A. (ed.). Rostovon-Don, Izdatel'stvo Juzhnogo nauchnogo centra Rossijskoj akademii nauk, 2008, 320 р. (in Russian).

4. Nakahara H., Sasao T. A deep convolutional neural network based on nested residue number system. 25th International Conference on Field Programmable Logic and Applications (FPL), Lausanne, 2–4 September 2015. Lausanne, 2015, рр. 1–6.

5. Petrovskij Al. A., Stankevich A. V., Petrovskij A. A. Bystroe proektirovanie sistem mul'timedia ot prototipa. Rapid Design of Multimedia Systems from a Prototype. Minsk, Bestprint, 2011, 410 р. (in Russian).

6. Solov'ev V. V. Arhitektury PLIS firmy Xilinx: FPGA i CPLD 7-j serii. XILINX FPGA Architectures: FPGA and CPLD 7-Series. Moscow, Goryachaya liniya – Telekom, 2016, 392 р. (in Russian).

7. Bibilo P. N., Enin S. V. Sintez kombinacionnyh skhem metodami funkcional'noj dekompozicii. Synthesis of Combinational Circuits by Methods of Functional Decomposition. Minsk, Nauka i tekhnika, 1987, 189 р. (in Russian).

8. Sasao T. FPGA design by generalized functional decomposition. Representations of Discrete Functions. In Sasao T., Fujita M. (eds.). Kluwer Academic Publishers, 1996, рр. 233–258.

9. Sasao T. Memory-Based Logic Synthesis. New York, Springer, 2011, 189 p.

10. Bibilo P. N. Cistemy proektirovaniya integral'nyh skhem na osnove yazyka VHDL. StateCAD, ModelSim, LeonardoSpectrum. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum. Moscow, SOLON-Press, 2005, 384 p. (in Russian).

11. Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: A multiple-level logic optimization systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1987, vol. 6, iss. 6, рр. 1062–1081.

12. Chang S.-C., Marek-Sadowska M., Hwang T. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 1996, vol. 15, nо. 10, рр. 1226–1235.

13. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. Berlin, Heidelberg, Springer-Verlag, 1998, 267 p.

14. Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization. Springer, 2005, 222 p.

15. Scholl C. Functional Decomposition with Application to FPGA Synthesis. Boston, Kluwer Academic Publisher, 2001, 288 p.

16. Chen D., Cong J., Pan P. FPGA design automation: a survey. Foundations and Trends in Electronic Design Automation, 2006, vol. 1, no. 3, рр. 195–330.

17. Kubica M., Kania D. SMTBDD: New form of BDD for logic synthesis. International Journal of Electronics and Telecommunications, 2016, vol. 62. no. 1, рр. 33–41.

18. Kubica M., Kania D. Decomposition of multi-output functions oriented to configurability of logic blocks. Bulletin of the Polish Academy of Sciences. Technical Sciences, 2017, vol. 65, no. 3, рр. 317–331.

19. Vemuri N., Kalla P., Tessier R. BDD-based logic synthesis for LUT-6-based FPGAs. ACM Transactions on Design Automation of Electronic Systems, 2002, vol. 7, no. 4, рр. 501–525.

20. Yang S., Ciesielski M. BDS: a BDD-based logic optimization system. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 7, рр. 866–876.

21. Lin H.-P., Jiang J.-H. R., Lee R.-R. Ashenhurst decomposition using SAT and interpolation. Advanced Techniques in Logic Synthesis, Optimizations and Applications. In Khatri S. P., Gulati K. (eds.). Springer, 2010, рр. 67–85.

22. Ashenhurst R. L. The decomposition of switching functions. Annals of Computation Laboratory of Harvard University. Cambrige, Mass., 1959, vol. 29, рр. 74–116.

23. Handbook of Satisfiability. In Biere A., Heule M., Van Maaren H., Walsh T. (eds.). IOS Press, 2009, 980 p.

24. Bibilo P. N., Romanov V. I. Logicheskoe proektirovanie diskretnyh ustrojstv s ispol'zovaniem produkcionno-frejmovoj modeli predstavlenija znanij. Logical Design of Discrete Devices Using a Production-Frame Knowledge Representation Model. Minsk, Belaruskaja navuka, 2011, 279 p. (in Russian).

25. Avdeev N. A., Bibilo P. N. Effektivnost' logicheskoj optimizacii pri sinteze kombinacionnyh skhem iz bibliotechnyh elementov [Logical optimization efficiency in the synthesis of combinational circuits]. Mikroelektronika [Microelectronics], 2015, vol. 44, no. 5, рр. 383–399 (in Russian).

26. Toropov N. R. Minimizaciya sistem bulevyh funkcij v klasse DNF [Minimization of Boolean function systems in the DNF class]. Logicheskoe proektirovanie [Logical Design], Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1999, iss. 4, рр. 4–19 (in Russian).

27. Bibilo P. N., Lankevich Yu. Yu. Ispol'zovanie polinomov Zhegalkina pri minimizacii mnogourovnevyh predstavlenij sistem bulevyh funkcij na osnove razlozheniya Shennona [The use of Zhegalkin polynomials for minimization of multilevel represintations of Boolean functions based on Shannon expansion]. Programmnaya inzheneriya [Software engineering], 2017, no. 8, рр. 369–384 (in Russian).

28. Bibilo P. N., Romanov V. I. Optimizaciya mnogourovnevyh predstavlenij sistem bulevyh funkcij pri pereproektirovanii logicheskih skhem [Optimization of multi-level representations of systems of Boolean functions in the redesign of logic circuits]. Upravlyayushchie sistemy i mashiny [Control Systems and Machines], 2006, no. 5, рр. 20–29 (in Russian).

29. Cheremisinov D. I. Analiz i preobrazovanie strukturnyh opisanij SBIS. Analysis and Transformation of VLSI Structural Descriptions. Minsk, Belorusskaya nauka, 2006, 275 р. (in Russian).

30. Kuzelin O. M., Knyshev D. A., Zotov Yu. V. Sovremennye semejstva PLIS firmy Xilinx. Modern

31. XILINX FPGA Families. Moscos, Goryachaya liniya – Telekom, 2004, 440 р. (in Russian).

32. Jeong C. Computer-aided design of digital systems. Department of Computer Science. Available at: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex (accessed 20.03.2018).

33. Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli A. Logic Minimization Algorithm for VLSI Synthesis. Boston, Kluwer Academic Publishers, 1984, 193 p.

34. Tarasov I. E. PLIS Xilinx. Yazyki opisaniya apparatury VHDL i Verilog, SAPR, priemy proektirovaniya. XILINX FPGA. Hardware Description Languages VHDL and Verilog, CAD, Design Techniques. Moscow, Goryachaya liniya – Telekom, 2020, 538 р. (in Russian).

35. Avdeev N. A., Bibilo P. N. Effektivnost' proektirovaniya zakaznyh skhem v sintezatore LeonardoSpectrum [Efficiency of custom circuit design in the Leonardo Spectrum synthesizer]. Sovremennaya elektronika [Modern Electronics], 2015, no. 1, рр. 58–61 (in Russian).