DOI: 10.17587/prin.15.176-189

An Experimental Research of the Algorithm for Extracting of a Boolean Function Subsystems for Joint Multilevel Optimization

P. N. Bibilo, Head of Laboratory, bibilo@newman.bas-net.by, N. A. Kirienko, Senior Researcher, kir@newman.bas-net.by V. I. Romanov, Leading Researcher, rom@newman.bas-net.by, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 220012, Belarus

Corresponding author: Petr N. Bibilo, Head of Laboratory, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 220012, Belarus, E-mail: bibilo@newman.bas-net.by

The results of an experimental comparison of programs for technologically independent minimization of complexity of multilevel representations of systems of fully defined functions based on the Shannon expansion are described. The main attention is paid to the effectiveness of using, when synthesizing logical circuits, a program that implements an algorithm for solving the problem of extracting from a system of functions such subsystems for which it is advisable to carry out joint minimization of multi-level representations of subsystems in the form of Binary Decision Diagrams, called BDD-representations, and in the form of Boolean net. The complexity of the representation is estimated by the total number of literals of Boolean variables in a set of interrelated logical equations that define a system of Boolean functions. After extracting the subsystems and their joint minimization, the synthesis of logic circuits is carried out in the design library of custom digital CMOS VLSIs, the results are compared in terms of chip area and speed (time delay) on a stream of 39 industrial examples of circuits. It was found that for 20 examples, the subsystem selection algorithm allows one to obtain better solutions than joint or separate minimization of multi-level representations based on Shannon expansion (13 examples). The three best solutions are obtained by applying the well-known Espresso program for minimizing functions in the DNF class, and the three solutions are obtained by the synthesizer using the original (non-optimized) matrix representations of DNF systems of Boolean functions.

Keywords: the system of Boolean functions, disjunctive normal form (DNF), Binary Decision Diagram (BDD), Boolean net, digital logic synthesis, VHDL, VLSI, CMOS

pp. 176–189

For citation:
Bibilo P. N., Kirienko N. A., Romanov V. I. An Experimental Research of the Algorithm for Extracting of a Boolean Function Subsystems for Joint Multilevel Optimization, Programmnaya Ingeneria, 2024, vol. 15, no. 4, pp. 176-189. DOI: 10.17587/prin.15.176-189 (in Russian).

References:

• Synthesis of Asynchronous Automata on a Computer / Ed. A. D. Zakrevskiy, Minsk, Nauka i tekhnika, 1975, 184 p. (in Russian).
• Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: A multiple-level logic optimization systems, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. CAD-6, no. 6, pp. 1062-1081.
• Knut D. E. The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Moscow, Vil'yams, 2013, 960 p. (in Russian).
• Amaru L. G New Data Structures and Algorithms for Logic Synthesis and Verification, Springer, 2017. 156 p.
• Scholl C. Functional Decomposition with Applications to FPGA Synthesis. Boston, Kluwer Academic Publishers, 2001, 288 p.
• Sasao T. Memory-Based Logic Synthesis. N. Y., Springer, 2011, 189 p.
• Bibilo P. N. Decomposition of Boolean functions on solving logical equations, Minsk, Belorusskaya nauka, 2009, 211 p. (in Russian).
• Bibilo P. N. Splitting a system of Boolean functions into subsystems of "related" functions, Teoriya i sistemyu pravleniya, 2019, no. 2, pp. 14-29. DOI: 10.1134/S0002338819020057 (in Russian).
• Bibilo P. N., Pazniak A. M. The search for subsystems of related functions from multilevel representation of systems of Boolean functions, Informatika, 2020, vol. 17, no. 1, pp. 63-77. DOI: 10.37661/1816-0301-2020-17-1-63-77 (in Russian).
• Bibilo P. N., Kirienko N. A., Romanov V. I. Extracting subsystems from a multilevel representation of a Boolean function system for joint logical minimization, Programmnye produkty i sistemy, 2023, vol. 36, no. 4, pp. 197-206. DOI: 10.15827/0236-235X.142.197-206 (in Russian).
• Bibilo P. N., Lankevich Yu. Yu., Romanov V. I. Logical minimization for combinatorial structure in FPGA, Informatika, 2021, vol. 18, no. 1, pp. 7-24. DOI: 10.37661/1816-0301-2021-181-7-24 (in Russian).
• Zakrevskij A. D. Logical Synthesis of Cascading Circuit, Moscow, Nauka, 1981, 416 р. (in Russian).
• Bibilo P. N., Romanov V. I. The system of logical optimization of functional structural descriptions of digital circuits based on production-frame knowledge representation model, Problemy razrabotki perspektivnyh mikro- i nanoelektronnyhsistem, 2020, Sb. trudov / Ed. A. L. Stempkovskiy, Moscow, IPPMRAN, 2020, no. 4, pp. 9-16. DOI: 10.31114/2078-7707-2020-4-9-16 (in Russian).
• Bibilo P. N., Lankevich Yu. Yu. Experimental investigation of effectiveness of algorithms for minimizing BDD representations of Boolean function systems, Programmnye produkty i sistemy, 2020, vol. 33, no. 3, pp. 449-463. DOI:10.15827/0236-235X.131.449-463 (in Russian).
• Bibilo P. N. Binary decision diagrams in logical design. M.: LENAND, 2024. 560 p. (in Russian).
• Bibilo P. N. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum, Moscow, SOLON-Press Publ., 2005, 384 p. (in Russian).
• Lozhkin S. A., Zizov V. S., Shuplecov M. S. et al. On the complexity of inverse graphs implementing Boolean functions from a small number of variables, Problemy razrabotki per-spektivnyh mikro- i nanoelektronnyhsistem, 2020, Sb. trudov / Ed. A. L. Stempkovskiy. Moscow, IPPM RAN, 2020, no. 4, pp. 95-102. DOI: 10.31114/2078-7707-2020-4-95-102 (in Russian).
• Amaru L., Gaillardon P.-E., De Micheli G. The EPFL Combinational Benchmark Suite, available at: https://infoscience.epfl.ch/record/207551/files/IWLS15.pdf.
• Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli A. L. Logic Minimization Algorithm for VLSI Synthesis, Boston, Kluwer Academic Publishers, 1984, 193 p.
• Tarasov I. E. XILINX FPGA. Hardware Description Languages VHDL and Verilog, CAD, Design Techniques, Moscow, Goryachaya liniya-Telekom, 2020, 538 р. (in Russian).
• Bibilo P. N. Joint and Separate Minimization of Multilevel Representations of Boolean Function Systems, Informacionnye tekhnologii, 2023, vol. 29, no. 11, pp. 574-582. DOI: 10.17587/it.29.574-582 (in Russian).