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

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

Методы. Предлагается исследовать различные методы технологически независимой логической оптимизации, выполняемой на первом этапе логического синтеза: совместную минимизацию систем функций в классе ДНФ, раздельную и совместную минимизацию в классах многоуровневых представлений в виде булевых сетей и 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.