Experimental comparison of the effectiveness of programs for minimizing systems of Boolean functions in the class of disjunctive normal forms

Objectives. Methods, algorithms and programs for solving problems of minimizing the DNF representations of Boolean functions are widely used in the design of digital systems to reduce the complexity (crystal area) of functional combinational blocks of digital systems placed into digital VLSI.

The objective of the work is experimental comparison of domestic programs for minimizing Boolean functions in the DNF class included in the FLC-2 with two well-known foreign freely distributed programs for minimizing DNF known as Espresso IIC and ABC.

Methods. Four sets sample of input data were used to compare the programs – there are widely known examples on which the effectiveness of the Espresso IIC program was tested and two sets of industrial examples from the practice of designing the logic circuits. Algorithms and programs for parallelization of calculations when separate functions of minimizing have been developed. Software tools for the application of joint minimization programs with separate minimization of functions are proposed.

Results. The areas of preferred use and the execution time of programs for the source systems of functions (for minimization) characterized by large parameter values of dozens of arguments and functions, tens of thousands of elementary conjunctions are revealed. The efficiency of application of minimization programs for various forms of input data assignment is investigated – DNF, orthogonalized DNF, BDD (Binary Decision Diagrams) representations for systems of functions, truth tables and perfect DNF systems.

Conclusion. The experimental results show the effectiveness of parallel programs – reducing the calculation time and increasing the dimensions of solved problems of separate minimization of Boolean function systems.

1. Quine W. V. The problem of simplifying of truth functions. The American Mathematical Monthly, 1952, vol. 59, no. 8, pp. 521–531.

2. McCluskey E. J. Minimization of Boolean functions. The Bell System Technical Journal, 1956, vol. 35, no. 6, pp. 1417–1444.

3. Zakrevskij A. D., Toropov N. R., Romanov V. I. DNF-implementation of partial Boolean functions of many variables. Informatika [Informatics], 2010, no. 1(25), pp. 102–111 (In Russ.).

4. Sapozhenko A. A., CHuhrov I. P. Minimization of Boolean functions in the class of disjunctive normal forms. Itogi nauki i tekhniki. Teoriya veroyatnostej. Matematicheskaya statistika. Teoreticheskaya kibernetika, [Results of Science and Technology. Probability Theory. Mathematical Statistics. Theoretical Cybernetics], 1987, vol. 25, pp. 68–116 (In Russ.).

5. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Synthesis of multi-level combinational logic circuits. Trudy Institute inzhenerov po jelektronike i radiotehnike [Proceedings of the Institute of Electronics and Radio Engineering], 1990, vol. 78, no. 2, рр. 38–83 (In Russ.).

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

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

8. Avdeev N. A., Bibilo P. N. Logical optimization efficiency in the synthesis of combinational circuits. Mikroelektronika [Microelectronics], 2015, vol. 44, no. 5, рр. 383–399 (In Russ.).

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

10. Leonchik P. V. Minimization of Boolean function systems in the class of disjunctive normal forms. Informatika [Informatics], 2006, no. 1(9), pp. 88–96 (In Russ.).

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

12. Rudell R., Sangiovanni-Vincentelli A. L. Multiple-valued minimization for PLA optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. CAD-6, no. 5, pp. 727–751.

13. McGeer P., Sangiovanni-Vincentelli A. L. Espresso-signature: A new exact minimizer for logic functions. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1993, vol. 1, no. 4, pp. 618–624.

14. Gol'dberg E. I. Metod sbrasyvaniya resheniya s lokal'nogo minimuma pri minimizacii interval'nogo pokrytiya. The Method of Resetting the Solution from the Local Minimum While Minimizing the Interval Coverage. Minsk, Institut tehnicheskoj kibernetiki Akademii nauk Belarusi, 1991, 18 p. (Preprint no. 13) (In Russ.).

15. Mishchenko A. An Introduction to Zero-Suppressed Binary Decision Diagrams. Berkeley, University of California, 2014, 15 p.

16. Karpov Y. G. Model checking. Verifikaciya parallel'nyh i raspredelennyh programmnyh system. Model Checking. Verification of Parallel and Distributed Software Systems. Saint Petersburg, BHV-Peterburg, 2010, 560 p. (In Russ.).

17. Leonchik P. V. Algorithm of sparse Boolean matrix covering. Informatika [Informatics], 2007, no. 2(14), pp. 53–61 (In Russ.).

18. Toropov N. R. Minimization of systems of Boolean functions in the class DNF. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1999, iss. 4, рр. 4–19 (In Russ.).

19. Toropov N. R. An approximate algorithm for minimizing systems of weakly defined Boolean functions. Izvestija Akademii nauk SSSR. Tekhnicheskaya kibernetika [Proceedings of the Academy of Sciences of the USSR. Technical cybernetics], 1969, no. 1, pp. 72–78 (In Russ.).

20. Romanov V. I., Vasil'kova I. V. Boolean vectors and matrices in C++. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1997, iss. 2, pp. 150–158 (In Russ.).

21. Cheremisinov D. I., Cheremisinova L. D. Ternary vectors and matrices in C++. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1998, iss. 3, pp. 146–156 (In Russ.).

22. Bibilo P. N., Romanov V. I. Logicheskoe proektirovanie diskretnyh ustrojstv s ispol'zovaniem produkcionno-frejmovoj modeli predstavlenija znanij. Logical Design of Discrete Devices with Use of Productional and Frame Model of Representation of Knowledge. Minsk, Belaruskaja navuka, 2011, 279 p. (In Russ.).

23. Zakrevskij A. D., Toropov N. R. Generators of pseudorandom logical-combinatorial objects in C++. Logicheskoe proektirovanie [Logical Design], Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1999, iss. 4, pp. 49–63 (In Russ.).

24. Kardash S. N. Orthogonalization of the DNF system of Boolean functions. VII Mezhdunarodnaya nauchno-prakticheskaya konferenciya "BIG DATA and Advanced Analytics" (BIG DATA 2021) : materialy mezhdunarodnoj nauchnoj konferencii, Minsk, Belarus, 19–20 maya 2021 g. [VII International Scientific and Practical Conference "BIG DATA and Advanced Analytics" (BIG DATA 2021) : Materials of the International Scientific Conference, Minsk, Belarus, 19–20 May 2021]. Minsk, Belorusskij gosudarstvennyj universitet informatiki i radiojelektroniki, 2021, pp. 26–30 (In Russ.).

25. Toropov N. R. Transformation of a multi-level combinational network into a two-level one. Logicheskoe proektirovanie [Logical Design], Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 2000, iss. 5, pp. 4–14 (In Russ.).

26. Williams A. C++ Concurrency in Action: Practical Multithreading. Manning Publications, 2012, 528 p.

27. Darryl G. Multicore Application Programming: for Windows, Linux, and Oracle Solaris. Addison-Wesley, 2010, 480 p.

28. Ayguade E., Copty N., Duran A., Hoeflinger J., Lin Y., …, Zhang G. The design of OpenMP tasks. IEEE Transactions on Parallel and Distributed Systems, 2009, vol. 20, no. 3, pp. 404–418.

29. SHlee M. Qt 5.10. Professional'noe programmirovanie na S++. Qt 5.10. Professional programming in C++. Saint Petersburg, BHV-Peterburg, 2018, 1072 p.

30. Fišer P., Toman D. A fast SOP minimizer for logic functions described by many product terms. Proceedings of 12th Euromicro Conference on Digital Systems Design, Patras, 27–29 August 2009. Patras, 2009, pp. 757–764.

31. Fišer P., Kubatova H. Two-Level Boolean minimizer BOOM-II. Proceedings of the 6th International Workshop on Boolean Problems (IWSBP'04), Freiberg, Germany, 23–24 September 2004. Freiberg, 2004, pp. 221–228.

32. Hlavicka J., Fišer P. BOOM – a heuristic Boolean minimizer. Computers and Information, 2003, vol. 22, no. 1, pp. 19–51.

33. Fišer P., Kubatova H. Flexible two-level Boolean minimizer BOOM-II and its applications. Proceedings of 9th Euromicro Conference on Digital System Design (DSD’06), Washington, US, 30 August – 1 September 2006. Washington, 2006, pp. 369–376.

34. Fišer P., Hlavička J., Kubatova H. FC-Min: A fast multi-output Boolean minimizer. Proceedings Euromicro Symposium on Digital Systems Design (DSD'03), Belek-Antalya, Turkey, 3–5 September 2003. Belek-Antalya, 2003, pp. 451-454.

35. Coudert O. Doing two-level logic minimization 100 times faster. Discrete Algorithms: Proceedings of the Sixth Annual ACM-SIAM Symposium, San Francisco, California, USA, 21 January 1995. San Francisco, 1995, pp. 112–121.

36. Mishchenko A., Sasao T. Large-scale SOP minimization using decomposition and functional properties. Proceedings of the 40th Design Automation Conference (DAC 2003), Anaheim, California, 2–6 June 2003. Anaheim, 2003, pp. 149–154.

37. Sapra S., Theobald M., Clarke E. SAT-based algorithms for logic minimization. Proceedings 21st International Conference on Computer Design, San Jose, California, 13–15 October 2003. San Jose, 2003, pp. 510–517.

38. Ashmouni E. F., Ramadan R. A., Rashed A. A. Espresso for rule mining. The 5th International Conference on Ambient Systems, Networks and Technologies (ANT-2014), Hasselt, Belgium, 2–5 June 2014. Hasselt, 2014, pp. 596–603.

39. Smagin A. A., SHigotarov A. V. Application of Boolean function minimization methods to optimize digital devices. Izvestiya Samarskogo nauchnogo centra Rossijskoj akademii nauk [Proceedings of the Samara Scientific Center of the Russian Academy of Sciences], 2009, vol. 11, no. 3(2), pp. 343–349.

40. Zakrevskij A. D. Vychisleniya v mnogomernom bulevom prostranstve. Computations in a Multidimensional Boolean Space. Minsk, Ob"edinjonnyj institut problem informatiki Nacional'noj akademii nauk Belarusi, 2011, 106 p. (In Russ.).

41. Pottosin Y. V., Toropov N. R., Shestakov E. A. A method for minimizing a system of completely specified Boolean functions. Informatika [Informatics], 2008, no. 2(18), pp. 102–110 (In Russ.).

42. Pottosin Y. V., Toropov N. R., Shestakov E. A. A method for minimizing the system of incompletely specified Boolean functions. Informatika [Informatics], 2009, no. 3(23), pp. 16–26 (In Russ.).

43. Cheremisinov D. I. Comparison of two Boolean function minimization programs. Avtomatizaciya proektirovaniya diskretnyh sistem (CAD DD’10): materialy Sed'moj Mezhdunarodnoj konferencii, Minsk, 16–17 noyabrya 2010 g. [Discrete Systems Design Automation (CAD DD'10): Proceedings of the Seventh International Conference, Minsk, 16–17 November 2010], Minsk, Ob"edinjonnyj institut problem informatiki Nacional'noj akademii nauk Belarusi, 2010, pp. 194–200.

44. Mihtonyuk S. V., Davydov M. D., Kuznecov E. S., Parfentij A. N. Modification of the Boolean function minimization method for multi-core INTEL architecture. Radioelektronika i informatika [Radio Electronics and Computer Science], 2007, no. 3, pp. 50–55 (In Russ.).

45. Alharbi E. Truth graph: A novel method for minimizing Boolean algebra expressions by using graphs. Proceedings 11th International Conference on the Theory and Application of Diagrams (DIAGRAMS 2020), Tallinn, Estonia, 24–28 August 2020. Tallinn, 2020, pp. 461–469.

46. Miheeva E. A., Enikeeva A. F. Minimization of Boolean functions by the geometric method. Uchenye zapiski Ul'janovskogo gosudarstvennogo universiteta. Serija Matematika i informacionnye tehnologii [Scientific notes of Ulyanovsk State University. Series Mathematics and Information Technology], 2018, no. 1, pp. 72–82.

47. Riznyk V., Solomko M. Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves. Information and Control Systems, 2017, vol. 4, no. 2(36), pp. 49–64.