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

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

Целью работы является сравнение программ, входящих в отечественную систему 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.