Экспериментальное сравнение эффективности программ минимизации систем булевых функций в классе дизъюнктивных нормальных форм

Цели. Методы, алгоритмы и программы решения задач минимизации дизъюнктивных нормальных форм (ДНФ) представлений булевых функций широко используются при проектировании цифровых систем для уменьшения сложности (площади кристаллов) функциональных комбинационных блоков, размещаемых в составе цифровых СБИС.

Целью работы является сравнение программ, входящих в отечественную систему FLC-2 логической оптимизации, с двумя широко известными и свободно распространяемыми зарубежными программами минимизации Espresso IIC и ABC.

Методы. Для сравнения программ использованы четыре набора примеров входных данных: широко известные примеры, на которых проверялась эффективность программы Espresso IIC, псевдослучайные системы ДНФ и два набора промышленных примеров из практики проектирования логических схем. Предложены программные средства для применения программ совместной минимизации при раздельной минимизации функций. Разработаны алгоритмы и программы распараллеливания вычислений при раздельной минимизации функций в классе ДНФ.

Результаты. Выявлены области предпочтительного использования и время работы программ для исходных (минимизируемых) систем функций, характеризуемых большими значениями параметров (десятками аргументов и функций, десятками тысяч элементарных конъюнкций) и различными формами задания входных данных. Изучена эффективность применения программ минимизации для различных форм задания входных данных: ДНФ, ортогонализованных ДНФ, BDD-представлений систем функций, таблиц истинности и систем совершенных ДНФ.

Заключение. Результаты экспериментов показывают эффективность параллельных программ. Они позволяют сокращать время вычислений и увеличивать размерности решаемых задач раздельной минимизации систем булевых функций.

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

2. McCluskey, E. J. Minimization of Boolean functions / E. J. McCluskey // The Bell System Technical J. – 1956. – Vol. 35, no. 6. – P. 1417–1444.

3. Закревский, А. Д. ДНФ-реализация частичных булевых функций многих переменных / А. Д. Закревский, Н. Р. Торопов, В. И. Романов // Информатика. – 2010. – № 1(25). – С. 102–111.

4. Сапоженко, А. А. Минимизация булевых функций в классе дизъюнктивных нормальных форм / А. А. Сапоженко, И. П. Чухров // Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. – 1987. – Т. 25. – C. 68–116.

5. Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // ТИИЭР. – 1990. – Т. 78, № 2. – С. 38–83.

6. Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 1981. – 416 c.

7. Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.

8. Авдеев, Н. А. Эффективность логической оптимизации при синтезе комбинационных схем из библиотечных элементов / Н. А. Авдеев, П. Н. Бибило // Микроэлектроника. – 2015. – Т. 44, № 5. – С. 383–399.

9. Бибило, П. Н. Система логической оптимизации функционально-структурных описаний цифровых устройств на основе продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов // Проблемы разработки перспективных микро- и наноэлектронных систем. – 2020. – Вып. 4. – С. 9–16.

10. Леончик, П. В. Минимизация систем булевых функций в классе дизъюнктивных нормальных форм / П. В. Леончик // Информатика. – 2006. – № 1(9). – С. 88–96.

11. Logic Minimization Algorithm for VLSI Synthesis / K. R. Brayton [et al.]. – Boston : Kluwer Academic Publishers, 1984. – 193 p.

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

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

14. Гольдберг, Е. И. Метод сбрасывания решения с локального минимума при минимизации интервального покрытия / Е. И. Гольдберг. – Минск : Ин-т техн. кибернетики АН Беларуси, 1991. – 18 с. (Препринт № 13).

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

16. Карпов, Ю. Г. Model checking. Верификация параллельных и распределенных программных систем / Ю. Г. Карпов. – СПб. : БХВ-Петербург, 2010. – 560 с.

17. Леончик, П. В. Алгоритм покрытия разреженных булевых матриц / П. В. Леончик // Информатика. – 2007. – № 2(14). – С. 53–61.

18. Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование : сб. науч. тр. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.

19. Торопов, Н. Р. Приближенный алгоритм минимизации систем слабоопределенных булевых функций / Н. Р. Торопов // Известия АН СССР. Техническая кибернетика. – 1969. – № 1. – C. 72–78.

20. Романов, В. И. Булевы векторы и матрицы в С++ / В. И. Романов, И. В. Василькова // Логическое проектирование : сб. науч. тр. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1997. – Вып. 2. – С. 150–158.

21. Черемисинов, Д. И. Троичные векторы и матрицы в С++ / Д. И. Черемисинов, Л. Д. Черемисинова // Логическое проектирование : сб. науч. тр. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1998. – Вып. 3. – С. 146–156.

22. Бибило, П. Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. – Минск : Беларус. навука, 2011. – 279 с.

23. Закревский, А. Д. Генераторы псевдослучайных логико-комбинаторных объектов в С++ / А. Д. Закревский, Н. Р. Торопов // Логическое проектирование : сб. науч. тр. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 49–63.

24. Кардаш, С. Н. Ортогонализация системы ДНФ булевых функций / С. Н. Кардаш // VII Междунар. науч.-практ. конф. «BIG DATA and Advanced Analytics» (BIG DATA 2021) : материалы междунар. науч. конф., Минск, Беларусь, 19–20 мая 2021 г. – Минск : БГУИР, 2021. – C. 26–30.

25. Торопов Н. Р. Преобразование многоярусной комбинационной сети в двухъярусную / Н. Р. Торопов // Логическое проектирование : сб. науч. тр. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5. – С. 4–14.

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

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

28. The design of OpenMP tasks / E. Ayguade [et al.] // IEEE Transactions on Parallel and Distributed Systems. – 2009. – Vol. 20, no. 3. – P. 404 –418.

29. Шлее, М. Qt 5.10. Профессиональное программирование на С++ / М. Шлее. – СПб. : БХВ-Петербург, 2018. – 1072 с.

30. Fišer, P. A fast SOP minimizer for logic functions described by many product terms / P. Fišer, D. Toman // Proc. of 12th Euromicro Conf. on Digital Systems Design (DSD'09), Patras, 27–29 Aug. 2009. – Patras, 2009. – P. 757–764.

31. Fišer, P. Two-level Boolean minimizer BOOM-II / P. Fišer, H. Kubatova // Proc. of the 6th Intern. Workshop on Boolean Problems (IWSBP'04), Freiberg, Germany, 23–24 Sept. 2004. – Freiberg, 2004. – P. 221–228.

32. Hlavicka, J. BOOM – a heuristic Boolean minimizer / J. Hlavicka, P. Fiser // Computers and Information. – 2003. – Vol. 22, no. 1. – P. 19–51.

33. Fišer, P. Flexible two-level Boolean minimizer BOOM-II and its applications / P. Fišer, H. Kubatova // Proc. of 9th Euromicro Conf. on Digital System Design (DSD’06), Washington, USА, 30 Aug. – 1 Sept. 2006. – Washington, 2006. – P. 369–376.

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

35. Coudert, O. Doing two-level logic minimization 100 times faster / O. Coudert // Discrete Algorithms : Proc. of the Sixth Annual ACM-SIAM Symp., San Francisco, California, USA, 21 Jan. 1995. – San Francisco, 1995. – P. 112–121.

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

37. Sapra, S. SAT-based algorithms for logic minimization / S. Sapra, M. Theobald, E. Clarke // Proc. 21st Intern. Conf. on Computer Design, San Jose, California, 13–15 Oct. 2003. – San Jose, 2003. – P. 510–517.

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

39. Смагин, А. А. Применение методов минимизации булевых функций для оптимизации цифровых устройств / А. А. Смагин, А. В. Шиготаров // Изв. Самарск. науч. центра РАН. – 2009. – Т. 11, № 3(2). – С. 343–349.

40. Закревский, А. Д. Вычисления в многомерном булевом пространстве / А. Д. Закревский. – Минск : ОИПИ НАН Беларуси, 2011. – 106 с.

41. Поттосин, Ю. В. Метод минимизации системы полностью определенных булевых функций / Ю. В. Поттосин, Н. Р. Торопов, Е. А. Шестаков // Информатика. – 2008. – № 2(18). – C. 102–110.

42. Поттосин, Ю. В. Метод минимизации системы не полностью определенных булевых функций / Ю. В. Поттосин, Н. Р. Торопов, Е. А. Шестаков // Информатика. – 2009. – № 3(23). – C. 16–26.

43. Черемисинов, Д. И. Сравнение двух программ минимизации булевых функций / Д. И. Черемисинов // Автоматизация проектирования дискретных систем (CAD DD’10) : материалы Седьмой Междунар. конф., Минск, 16–17 нояб. 2010 г. – Минск : ОИПИ НАН Беларуси, 2010. – С. 194–200.

44. Модификация метода минимизации булевых функций для мультиядерной INTEL-архитектуры / С. В. Михтонюк [и др.] // Радиоэлектроника и информатика. – 2007. – № 3. – С. 50–55.

45. Alharbi, E. Truth graph: A novel method for minimizing Boolean algebra expressions by using graphs / E. Alharbi // Proc. 11th Intern. Conf. on the Theory and Application of Diagrams (Diagrams 2020), Tallinn, Estonia, 24–28 Aug. 2020. – Tallinn, 2020. – P. 461–469.

46. Михеева, Е. А. Минимизация булевых функций геометрическим методом / Е. А. Михеева, А. Ф. Еникеева // Ученые записки УлГУ. Сер. Математика и информационные технологии. – 2018. – № 1. – С. 72–82.

47. Riznyk, V. Minimization of Boolean functions by combinatorial method / V. Riznyk, M. Solomko // Technology audit and production reserves. Information and Control Systems. – 2017. – Vol. 4, no. (36). – P. 49–64.