Algorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimization

Objectives. The purpose of experimental research is to determine the effectiveness of new algorithms for extracting the so-called connected subsystems from formula descriptions of the original system of Boolean functions. Subsequently each of the extracted subsystems is minimized independently of the others, but the functions that make up each connected subsystem are minimized jointly.

Methods. Minimization of subsystems is performed in the class of multilevel BDD representations (BDD – Binary Decision Diagram) or Boolean networks. After obtaining minimized descriptions of circuits, specified as a set of interconnected Shannon expansion formulas that correspond to BDD, or as two-operand logical equations corresponding to Boolean networks, synthesis of logic circuits is carried out in the design library of custom digital CMOS ASIC (Application-Specific Integrated Circuits made using complementary metal oxide semiconductor technology). In Boolean networks, node functions can be the logical operations “conjunction” or “disjunction” over literals of Boolean variables. A literal is a Boolean variable or its inversion. Minimization of BDD representations is carried out according to the number of Shannon decomposition formulas, minimization of Boolean networks – according to the number of literals in the formulas defining the networks.

Results. The resulting logic circuits are compared in terms of chip area and speed (time delay). Experiments were carried out on 39 industrial circuit examples. The advantage (in 29 cases) of using the proposed subsystem extraction algorithms is shown compared to joint or separate minimization of the original system of Boolean functions, which is usually performed as the first stage of the synthesis of logic circuits.

Conclusion. The new algorithms for subsystem extraction proposed in the paper have proven their effectiveness in the execution of various programs for optimizing multilevel representations of systems of Boolean functions. The developed software package allows improving the results of technologically independent optimization used in the implementation of digital system projects in custom digital CMOS ASIC.

1. Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascading Circuit. Moscow, Nauka, 1981, 416 р. (In Russ.).

2. 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.

3. Sasao T. Input variable assignment and output phase optimization of PLA's. IEEE Transactions on Computers, 1984, vol. C-33, no. 10, pp. 879–894.

4. Wey C. L., Chang T. Y. An efficient output assignment for PLA minimization. IEEE Transactions on Computer-Aided Design, 1990, vol. 9, pp. 1–7.

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

6. Knuth D. E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 2011, 912 р.

7. Bibilo P. N. Binarnye diagrammy reshenij v logicheskom proektirovanii. Binary Decision Diagrams in Logical Design. Moscow, Lenand, 2024, 560 p. (In Russ.).

8. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Synthesis of multilevel combinational logic circuits. Trudy Instituta inzhenerov po jelektrotehnike i radiojelektronike [Proceedings of the IEEE], 1990, vol. 78, no. 2, рр. 38–83 (In Russ.).

9. Zakrevskij A. D. (ed.). Sintez asinhronnyh avtomatov na JeVM. Synthesis of Asynchronous Automata on a Computer. Minsk, Nauka i tekhnika, 1975, 184 р. (In Russ.).

10. 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. CAD-6, no. 6, рр. 1062–1081.

11. Brayton K. R. Factoring logic functions. IBM Journal of Research and Development, 1987, vol. 31, no. 2, рр. 187–198.

12. Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verification. Springer, 2017, 156 p.

13. Lozhkin S. A., Zizov V. S., Shupletsov M. S., Zhukov V. V., Khzmalian D. E., Belyankov O. O. On complexity of inverter graphs for Boolean functions of small number of variables. Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh system : sbornik trudov [Problems of Developing Promising Micro- and Nanoelectronic Systems : Collection of Works]. In A. L. Stempkovskogo (ed.). 2020, iss. 4, pp. 95–102 (In Russ.). DOI: 10.31114/2078-7707-2020-4-95-102.

14. Soeken M., Amaru L. G., Gaillardon P., De Micheli G. Optimizing majority-inverter graphs with functional hashing. Proceedings of the 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, 14–18 March 2016. Dresden, 2016, pp. 1030–1035.

15. Soeken M., Amaru L., Gaillardon P.-E., De Micheli G. Exact synthesis of majority-inverter graphs and its applications. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, vol. 36, no. 11, pp. 1842–1855.

16. 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 [Software & Systems], 2023, vol. 36, no. 4, pp. 509–522 (In Russ.). DOI: 10.15827/0236-235X.142.509-522.

17. 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 Russ.).

18. Bibilo P. N., Romanov V. I. The system of logical optimization of digital circuits functional structural descriptions based on production-frame knowledge representation model. Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh system [Problems of Advanced Micro- and Nanoelectronic Systems Development], 2020, iss. 4, pp. 9–16 (In Russ.). DOI: 10.31114/2078-7707-2020-4-9-16.

19. Bibilo P. N., Lankevich Yu. Yu. Experimental investigation of effectiveness of algorithms for minimizing BDD representations of Boolean function systems. Programmnye produkty i sistemy [Software & Systems], 2020, vol. 33, no. 3, pp. 449–463 (In Russ.). DOI: 10.15827/0236-235X.131.449-463.

20. Ashenden P. J., Lewis J. VHDL–2008. Just the New Stuff. Burlington, MA, USA, Morgan Kaufman Publishers, 2008, 909 p.