Технологически независимая оптимизация при реализации в заказных СБИС разреженных систем дизъюнктивных нормальных форм булевых функций

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

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

Результаты. При реализации в заказных СБИС разреженных систем ДНФ булевых функций наряду с традиционными методами совместной минимизации систем функций в классе ДНФ для технологически независимой оптимизации могут применяться методы оптимизации многоуровневых представлений систем булевых функций на основе разложений Шеннона, при этом раздельная минимизация и совместная минимизация всей системы в целом оказываются менее эффективными по сравнению с блочными разбиениями и покрытиями системы ДНФ и последующей минимизацией многоуровневых представлений. Схемы, полученные в результате синтеза по минимизированным представлениям булевых сетей, чаще имеют меньшую площадь, чем схемы, полученные по минимизированным BDD-представлениям.

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

1. Тарасов, И. Е. ПЛИС Xilinx. Языки описания аппаратуры VHDL и Verilog, САПР, приемы проектирования / И. Е. Тарасов. - М. : Горячая линия - Телеком, 2020. - 538 с.

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

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

4. Синтез асинхронных автоматов на ЭВМ / под ред. А. Д. Закревского. - Минск : Наука и техника, 1975. - 184 с.

5. Brayton, R. K. The decomposition and factorization of Boolean expressions / R. K. Brayton, C. T. McMullen // Proc. of IEEE Intern. Symp. on Circuits and Systems (ISCAS 1982), Rome, Italy, 10-12 May 1982. - Rome, 1982. - P. 49-54.

6. MIS: A multiple-level logic optimization systems / R. K. Brayton [et al.] // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. - 1987. - Vol. CAD-6, no. 6. - P. 1062-1081.

7. Scholl, C. Functional Decomposition with Applications to FPGA Synthesis / C. Scholl. - Boston : Kluwer Academic Publishers, 2001. - 288 p.

8. Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. - Минск : Беларус. навука, 2006. - 327 с.

9. Sasao, T. Memory-Based Logic Synthesis / T. Sasao. - N. Y. : Springer, 2011. - 189 p.

10. Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. - Минск : Беларус. навука, 2009. - 211 с.

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

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

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

14. Bryant, R. E. Ordered binary decision diagrams / R. E. Bryant, C. Meinel // Logic Synthesis and Verification / eds.: S. Hassoun, T. Sasao, R. K. Brayton. - Kluwer Academic Publishers, 2002. - P. 285-307.

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

16. Кнут, Д. Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 : пер. с англ. / Д. Э. Кнут. - М. : Вильямс, 2013. - 960 с.

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

18. Бибило, П. Н. Экспериментальное сравнение эффективности алгоритмов оптимизации BDD-представлений систем булевых функций / П. Н. Бибило, Ю. Ю. Ланкевич // Программные продукты и системы. - 2020. - Т. 33, № 3. - С. 449-463.

19. Бибило, П. Н. Логическая минимизация булевых сетей с использованием разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Информатика. - 2019. - Т. 16, № 2. - С. 73-89.

20. A novel basis for logic rewriting / W. Haaswijk [et al.] // Proc. of 22nd Asia and South Pacific Design Automation Conf. (ASP-DAC), Chiba, Japan, 16-19 Jan. 2017. - Chiba, 2017. - P. 151-156. https://doi.org/10.1109/ASPDAC.2017.7858312

21. Optimizing majority-inverter graphs with functional hashing / M. Soeken [et al.] // Proc. of the 2016 Design, Automation & Test in Europe Conf. & Exhibition (DATE), Dresden, Germany, 14-18 March 2016. - Dresden, 2016. - P. 1030-1035.

22. Exact synthesis of majority-inverter graphs and its applications / M. Soeken [et al.] // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 2017. - Vol. 36, no. 11. - P. 1842-1855.

23. Size optimization of MIGs with an application to QCA and STMG technologies / H. Riener [et al.] // Proc. of the 14th IEEE/ACM Intern. Symp. on Nanoscale Architectures, Athens, Greece, 17-19 July 2018. - Athens, 2018. - P. 157-162.

24. Harlecek, I. Are XORs in logic synthesis really necessary? / I. Harlecek, P. Fiser, J. Schmidt // IEEE 20th Intern. Symp. on Design and Diagnostics of Electronic Circuits & Systems (DDECS), Dresden, Germany, 19-21 Apr. 2017. - Dresden, 2017. - Р. 134-139.

25. Кардаш, С. Н. Построение блочных разбиений систем булевых функций на основе задачи покрытия булевых матриц / С. Н. Кардаш // BIG DATA и анализ высокого уровня = BIG DATA and Advanced Analytics : сб. науч. ст. IX Междунар. науч.-практ. конф., Минск, 17-18 мая 2023 г. : в 2 ч. - Минск : БГУИР, 2023. - Ч. 2. - C. 326-330.

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

27. Бибило, П. Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. - М. : СОЛОН-Пресс, 2005. - 384 с.

28. Авдеев, Н. А. Автоматизированное проектирование цифровых операционных устройств с пониженным энергопотреблением / Н. А. Авдеев, П. Н. Бибило // Программная инженерия. - 2021. - Т. 12, № 2. - С. 63-73.

29. Соловьев, В. В. Архитектуры ПЛИС фирмы Xilinx: FPGA и CPLD 7-й серии / В. В. Соловьев. - М. : Горячая линия - Телеком, 2016. - 392 с.

30. Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. - 2017. - № 8. - С. 369-384.

31. Бибило, П. Н. Выделение из многоуровневого представления системы булевых функций подсистем для совместной логической минимизации / П. Н. Бибило, Н. А. Кириенко, В. И. Романов // Программные продукты и системы. - 2023. - Т. 36, № 4. - С. 197-206.

32. Бибило, П. Н. Логическая минимизация многоуровневых представлений систем булевых функций / П. Н. Бибило, Ю. Ю. Ланкевич, В. И. Романов // Информационные технологии. - 2023. - Т. 29, № 2. - С. 59-71.