informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2024-21-1-28-47inform-1276Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNТехнологически независимая оптимизация при реализации в заказных СБИС разреженных систем дизъюнктивных нормальных форм булевых функцийTechnology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASICБибилоП. Н.BibiloP. N.

Бибило Петр Николаевич, доктор технических наук, профессор

ул. Сурганова, 6, Минск, 220012

Petr N. Bibilo, D. Sc. (Eng.), Prof.

st. Surganova, 6, Minsk, 220012 

bibilo@newman.bas-net.byКардашС. Н.KardashS. N.

Кардаш Сергей Николаевич, кандидат технических наук

ул. Сурганова, 6, Минск, 220012

Sergey N. Kardash, Ph. D. (Eng.)

st. Surganova, 6, Minsk, 220012 

kardash77@gmail.comОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus2024290320242112847Copyright © Бибило П.Н., Кардаш С.Н., 20242024Бибило П.Н., Кардаш С.Н.Bibilo P.N., Kardash S.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1276Цели

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

Методы

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

Результаты

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

Заключение

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

Objectives

Objectives. The problem of choosing the best methods and programs for circuit implementation as part of digital ASIC (Application-Specific Integrated Circuit) sparse systems of disjunctive normal forms (DNF) of completely defined Boolean functions is considered. For matrix forms of sparse DNF systems, the ternary matrix specifying elementary conjunctions contains a large proportion of undefined values corresponding to missing literals of Boolean input variables, and the Boolean matrix specifying the occurrences of conjunctions in DNF functions contains a large proportion of zero values.

Methods

Methods. It is proposed to investigate various methods of technologically independent logical optimization performed at the first stage of logical synthesis: joint minimization of systems of functions in the DNF class, separate and joint minimization in classes of multilevel representations in the form of Boolean networks and BDD representations using mutually inverse cofactors, as well as the division of a system of functions into subsystems with a limited number of input variables and the method of block cover of DNF systems, focused on minimizing the total area of the blocks forming the cover.

Results

Results. When implementing sparse DNF systems of Boolean functions in ASIC, along with traditional methods of joint minimization of systems of functions in the DNF class, methods for optimizing multilevel representations of Boolean function systems based on Shannon expansions can be used for technologically independent optimization, while separate minimization and joint minimization of the entire system as a whole turn out to be less effective compared with block partitions and coatings of the DNF system and subsequent minimization of multilevel representations. Schemes obtained as a result of synthesis using minimized representations of Boolean networks often have a smaller area than schemes obtained using minimized BDD representations.

Conclusion

Conclusion. For the design of digital ASIC, the effectiveness of combined approach is shown, when initially the block coverage programs of the DNF system is used, followed by the use of programs to minimize multilevel block representations in the form of Boolean networks minimized based on Shannon expansion.

система булевых функцийДНФминимизация ДНФбинарная диаграмма решенийбулева сетьразложение Шеннонаблочное покрытие системы ДНФсинтез логической схемызаказная СБИСVHDLBoolean function systemDNFDNF minimizationBinary Decision DiagramBoolean networkShannon expansionblock cover of the DNF systemlogic synthesisASICVHDLReferencesТарасов, И. Е. ПЛИС Xilinx. Языки описания аппаратуры VHDL и Verilog, САПР, приемы проектирования / И. Е. Тарасов. – М. : Горячая линия – Телеком, 2020. – 538 с.Tarasov I. E. PLIS Xilinx. Yazyki opisaniya apparatury VHDL i Verilog, SAPR, priemy proektirovaniya. XILINX FPGA. Hardware Description Languages VHDL and Verilog, CAD, Design Techniques. Moscow, Goryachaya liniya – Telekom, 2020, 538 р. (In Russ.).Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 1981. – 416 c.Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascading Circuit. Moscow, Nauka, 1981, 416 р. (In Russ.).Logic Minimization Algorithm for VLSI Synthesis / K. R. Brayton [et al.]. – Boston : Kluwer Academic Publishers, 1984. – 193 p.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.Синтез асинхронных автоматов на ЭВМ / под ред. А. Д. Закревского. – Минск : Наука и техника, 1975. – 184 с.Zakrevskij A. D. (ed.). Sintez asinhronnyh avtomatov na EHVM. Synthesis of Asynchronous Automata on a Computer. Minsk, Nauka i tekhnika, 1975, 184 р. (In Russ.).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.Brayton R. K., McMullen C. T. The decomposition and factorization of Boolean expressions. Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS 1982), Rome, Italy, 10–12 May 1982. Rome, 1982, pp. 49–54.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.Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: A multiple-level logic optimization systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. CAD-6, no. 6, рр. 1062–1081.Scholl, C. Functional Decomposition with Applications to FPGA Synthesis / C. Scholl. – Boston : Kluwer Academic Publishers, 2001. – 288 p.Scholl C. Functional Decomposition with Application to FPGA Synthesis. Boston, Kluwer Academic Publishers, 2001, 288 p.Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. – Минск : Беларус. навука, 2006. – 327 с.Pottosin Yu. V., Shestakov E. A. Tablichnye metody dekompozicii sistem polnost'yu opredelennyh bulevyh funkcij. Tabular Methods for Decomposition of Systems of Completely Defined Boolean Functions. Minsk, Belaruskaja navuka, 2006, 327 р. (In Russ.).Sasao, T. Memory-Based Logic Synthesis / T. Sasao. – N. Y. : Springer, 2011. – 189 p.Sasao T. Memory-Based Logic Synthesis. New York, Springer, 2011, 189 p.Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.Bibilo P. N. Dekompoziciya bulevyh funkcij na osnove resheniya logicheskih uravnenij. Decomposition of Boolean Functions Based on the Solution of Logical Equations. Minsk, Belaruskaja navuka, 2009, 211 p. (In Russ.).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.Bryant R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 1986, vol. 35, no. 8, рр. 677–691.Drechsler, R. Binary Decision Diagrams: Theory and Implementation / R. Drechsler, B. Becker. – Springer, 1998. – 210 p.Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation. Springer, 1998, 210 p.Ebendt, R. Advanced BDD Optimization / R. Ebendt, G. Fey, R. Drechsler. – Springer, 2005. – 222 p.Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization. Springer, 2005, 222 p.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.Bryant R. E., Meinel C. Ordered binary decision diagrams. In S. Hassoun, T. Sasao, R. K. Brayton (eds.). Logic Synthesis and Verification. Kluwer Academic Publishers, 2002, рр. 285–307.Meinel, C. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications / C. Meinel, T. Theobald. – Berlin, Heidelberg : Springer-Verlag, 1998. – 267 p.Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. Berlin, Heidelberg, Springer-Verlag, 1998, 267 p.Кнут, Д. Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 : пер. с англ. / Д. Э. Кнут. – М. : Вильямс, 2013. – 960 с.Knuth D. E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 2011, 912 р.Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.Bibilo P. N. Primenenie diagram dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Selection Diagrams in the Synthesis of Logic Circuits. Minsk, Belaruskaja navuka, 2014, 231 p. (In Russ.).Бибило, П. Н. Экспериментальное сравнение эффективности алгоритмов оптимизации BDD-представлений систем булевых функций / П. Н. Бибило, Ю. Ю. Ланкевич // Программные продукты и системы. – 2020. – Т. 33, № 3. – С. 449–463.Bibilo P. N., Lankevich Yu. Yu. Experimental investigation of effectiveness of algorithms for minimizing BDD representations of Boolean function systems, Programmnye produkty i sistemy [Software & Systems], 2020, vol. 33, no. 3, pp. 449–463 (In Russ.).Бибило, П. Н. Логическая минимизация булевых сетей с использованием разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Информатика. – 2019. – Т. 16, № 2. – С. 73–89.Bibilo P. N., Lankevich Yu. Yu. Logical optimization of Boolean nets using Shannon expansion. Informatika [Informatics], 2019, vol. 16, no. 2, рр. 73–89 (In Russ.).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.7858312Haaswijk W., Soeken M., Amaru L., Gaillardon P.-E., De Micheli G. A novel basis for logic rewriting. Proceedings of 22nd Asia and South Pacific Design Automation Conference (ASP-DAC), Chiba, Japan, 16–19 January 2017. Chiba, 2017, pp. 151–156. https://doi.org/10.1109/ASPDAC.2017.7858312Optimizing 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.Soeken M., Amaru L. G., Gaillardon P., De Micheli G. Optimizing majority-inverter graphs with functional hashing. Proceedings of the 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, 14–18 March 2016. Dresden, 2016, pp. 1030–1035.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.Soeken M., Amaru L., Gaillardon P.-E., De Micheli G. Exact synthesis of majority-inverter graphs and its applications. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, vol. 36, no. 11, pp. 1842–1855.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.Riener H., Testa E., Amaru L., Soeken M., De Micheli G. Size optimization of MIGs with an application to QCA and STMG technologies. Proceedings of the 14th IEEE/ACM International Symposium on Nanoscale Architectures, Athens, Greece, 17–19 July 2018. Athens, 2018, pp. 157–162.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.Harlecek I, Fiser P., Schmidt J. Are XORs in logic synthesis really necessary? IEEE 20th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS), Dresden, Germany, 19–21 April 2017. Dresden, 2017, pp. 134–139.Кардаш, С. Н. Построение блочных разбиений систем булевых функций на основе задачи покрытия булевых матриц / С. Н. Кардаш // BIG DATA и анализ высокого уровня = BIG DATA and Advanced Analytics : сб. науч. ст. IX Междунар. науч.-практ. конф., Минск, 17–18 мая 2023 г. : в 2 ч. – Минск : БГУИР, 2023. – Ч. 2. – C. 326–330.Kardash S. N. Construction of block partitions of Boolean function systems based on the problem of covering Boolean matrices. BIG DATA i analiz vysokogo urovnja : sbornik nauchnyh statej IX Mezhdunarodnoj nauchno-prakticheskoj konferencii, Minsk, 17–18 maja 2023 g. : v 2 chastjah. Chast' 2 [BIG DATA and Advanced Analytics : Collection of Scientific Articles of the IX International Scientific and Practical Conference, Minsk, 17–18 May 2023 : in 2 Parts]. Minsk, Belorusskij gosudarstvennyj universitet informatiki i radiojelektroniki, 2023, part 2, pp. 326–330 (In Russ.).Бибило, П. Н. Система логической оптимизации функционально-структурных описаний цифровых устройств на основе продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов // Проблемы разработки перспективных микро- и наноэлектронных систем. – 2020. – Вып. 4. – С. 9–16.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.).Бибило, П. Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. – М. : СОЛОН-Пресс, 2005. – 384 с.Bibilo P. N. Cistemy proektirovaniya integral'nyh skhem na osnove yazyka VHDL. StateCAD, ModelSim, LeonardoSpectrum. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum. Moscow, SOLON-Press, 2005, 384 p. (In Russ.).Авдеев, Н. А. Автоматизированное проектирование цифровых операционных устройств с пониженным энергопотреблением / Н. А. Авдеев, П. Н. Бибило // Программная инженерия. – 2021. – Т. 12, № 2. – С. 63–73.Avdeev N. A., Bibilo P. N. Design of digital operational units with low power consumption. Programmnaya inzheneriya [Software Engineering], 2021, vol. 12, no. 2, pp. 63–73 (In Russ.).Соловьев, В. В. Архитектуры ПЛИС фирмы Xilinx: FPGA и CPLD 7-й серии / В. В. Соловьев. – М. : Горячая линия – Телеком, 2016. – 392 с.Solov'ev V. V. Arhitektury PLIS firmy Xilinx: FPGA i CPLD 7-j serii. XILINX FPGA Architectures: FPGA and CPLD 7-Series. Moscow, Goryachaya liniya – Telekom, 2016, 392 р. (In Russ.).Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. – 2017. – № 8. – С. 369–384.Bibilo P. N., Lankevich Yu. Yu. The use of Zhegalkin polynomials for minimization of multilevel represintations of Boolean functions based on Shannon expansion. Programmnaya inzheneriya [Software Engineering], 2017, no. 8, рр. 369–384 (In Russ.).Бибило, П. Н. Выделение из многоуровневого представления системы булевых функций подсистем для совместной логической минимизации / П. Н. Бибило, Н. А. Кириенко, В. И. Романов // Программные продукты и системы. – 2023. – Т. 36, № 4. – С. 197–206.Bibilo P. N., Kirienko N. A., Romanov V. I. Extraction from a multilevel representation of a system of Boolean functions of subsystems for joint logical minimization. Programmnye produkty i sistemy [Software & Systems], 2023, vol. 36, no. 4, pp. 197–206 (In Russ.).Бибило, П. Н. Логическая минимизация многоуровневых представлений систем булевых функций / П. Н. Бибило, Ю. Ю. Ланкевич, В. И. Романов // Информационные технологии. – 2023. – Т. 29, № 2. – С. 59–71.Bibilo P. N., Lankevich Yu. Yu., Romanov V. I. Logical minimization of multilevel representations of Boolean function systems. Informacionnye tekhnologii [Information Technology], 2023, vol. 29, no. 2, pp. 59–71 (In Russ.).

The authors declare that there are no conflicts of interest present.