Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC

Objectives. The problem of choosing the best methods and programs for circuit implementation as part of digital ASIC (Application-Specific Integrated Circuit) sparse systems of disjunctive normal forms (DNF) of completely defined Boolean functions is considered. For matrix forms of sparse DNF systems, the ternary matrix specifying elementary conjunctions contains a large proportion of undefined values corresponding to missing literals of Boolean input variables, and the Boolean matrix specifying the occurrences of conjunctions in DNF functions contains a large proportion of zero values.

Methods. It is proposed to investigate various methods of technologically independent logical optimization performed at the first stage of logical synthesis: joint minimization of systems of functions in the DNF class, separate and joint minimization in classes of multilevel representations in the form of Boolean networks and BDD representations using mutually inverse cofactors, as well as the division of a system of functions into subsystems with a limited number of input variables and the method of block cover of DNF systems, focused on minimizing the total area of the blocks forming the cover.

Results. When implementing sparse DNF systems of Boolean functions in ASIC, along with traditional methods of joint minimization of systems of functions in the DNF class, methods for optimizing multilevel representations of Boolean function systems based on Shannon expansions can be used for technologically independent optimization, while separate minimization and joint minimization of the entire system as a whole turn out to be less effective compared with block partitions and coatings of the DNF system and subsequent minimization of multilevel representations. Schemes obtained as a result of synthesis using minimized representations of Boolean networks often have a smaller area than schemes obtained using minimized BDD representations.

Conclusion. For the design of digital ASIC, the effectiveness of combined approach is shown, when initially the block coverage programs of the DNF system is used, followed by the use of programs to minimize multilevel block representations in the form of Boolean networks minimized based on Shannon expansion.

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

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

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

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

5. Brayton R. K., McMullen C. T. The decomposition and factorization of Boolean expressions. Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS 1982), Rome, Italy, 10–12 May 1982. Rome, 1982, pp. 49–54.

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

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

8. Pottosin Yu. V., Shestakov E. A. Tablichnye metody dekompozicii sistem polnost'yu opredelennyh bulevyh funkcij. Tabular Methods for Decomposition of Systems of Completely Defined Boolean Functions. Minsk, Belaruskaja navuka, 2006, 327 р. (In Russ.).

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

10. Bibilo P. N. Dekompoziciya bulevyh funkcij na osnove resheniya logicheskih uravnenij. Decomposition of Boolean Functions Based on the Solution of Logical Equations. Minsk, Belaruskaja navuka, 2009, 211 p. (In Russ.).

11. Bryant R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 1986, vol. 35, no. 8, рр. 677–691.

12. Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation. Springer, 1998, 210 p.

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

14. Bryant R. E., Meinel C. Ordered binary decision diagrams. In S. Hassoun, T. Sasao, R. K. Brayton (eds.). Logic Synthesis and Verification. Kluwer Academic Publishers, 2002, рр. 285–307.

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

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

17. Bibilo P. N. Primenenie diagram dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Selection Diagrams in the Synthesis of Logic Circuits. Minsk, Belaruskaja navuka, 2014, 231 p. (In Russ.).

18. 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.).

19. Bibilo P. N., Lankevich Yu. Yu. Logical optimization of Boolean nets using Shannon expansion. Informatika [Informatics], 2019, vol. 16, no. 2, рр. 73–89 (In Russ.).

20. Haaswijk W., Soeken M., Amaru L., Gaillardon P.-E., De Micheli G. A novel basis for logic rewriting. Proceedings of 22nd Asia and South Pacific Design Automation Conference (ASP-DAC), Chiba, Japan, 16–19 January 2017. Chiba, 2017, pp. 151–156. https://doi.org/10.1109/ASPDAC.2017.7858312

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

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

23. Riener H., Testa E., Amaru L., Soeken M., De Micheli G. Size optimization of MIGs with an application to QCA and STMG technologies. Proceedings of the 14th IEEE/ACM International Symposium on Nanoscale Architectures, Athens, Greece, 17–19 July 2018. Athens, 2018, pp. 157–162.

24. Harlecek I, Fiser P., Schmidt J. Are XORs in logic synthesis really necessary? IEEE 20th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS), Dresden, Germany, 19–21 April 2017. Dresden, 2017, pp. 134–139.

25. Kardash S. N. Construction of block partitions of Boolean function systems based on the problem of covering Boolean matrices. BIG DATA i analiz vysokogo urovnja : sbornik nauchnyh statej IX Mezhdunarodnoj nauchno-prakticheskoj konferencii, Minsk, 17–18 maja 2023 g. : v 2 chastjah. Chast' 2 [BIG DATA and Advanced Analytics : Collection of Scientific Articles of the IX International Scientific and Practical Conference, Minsk, 17–18 May 2023 : in 2 Parts]. Minsk, Belorusskij gosudarstvennyj universitet informatiki i radiojelektroniki, 2023, part 2, pp. 326–330 (In Russ.).

26. 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 nanoelektronnyh system [Problems of Developing Promising Micro- and Nanoelectronic Systems], 2020, iss. 4, pp. 9–16 (In Russ.).

27. 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.).

28. Avdeev N. A., Bibilo P. N. Design of digital operational units with low power consumption. Programmnaya inzheneriya [Software Engineering], 2021, vol. 12, no. 2, pp. 63–73 (In Russ.).

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

30. Bibilo P. N., Lankevich Yu. Yu. 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 Russ.).

31. Bibilo P. N., Kirienko N. A., Romanov V. I. Extraction from a multilevel representation of a system of Boolean functions of subsystems for joint logical minimization. Programmnye produkty i sistemy [Software & Systems], 2023, vol. 36, no. 4, pp. 197–206 (In Russ.).

32. Bibilo P. N., Lankevich Yu. Yu., Romanov V. I. Logical minimization of multilevel representations of Boolean function systems. Informacionnye tekhnologii [Information Technology], 2023, vol. 29, no. 2, pp. 59–71 (In Russ.).