informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2024-21-4-7-23inform-1310Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNАлгоритмы выделения из многоуровневого представления системы булевых функций подсистем для совместной минимизацииAlgorithms for extracting subsystems from a multilevel representation of a system of Boolean functions for joint minimizationБибилоП. Н.BibiloP. N.

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

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

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

st. Surganova, 6, Minsk, 220012

bibilo@newman.bas-net.byКириенкоН. А.KirienkoN. A.

Кириенко Наталья Алексеевна, кандидат технических наук, доцент

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

Natalia A. Kirienko, Ph. D. (Eng.), Assoc. Prof.

st. Surganova, 6, Minsk, 220012

kir@newman.bas-net.byРомановВ. И.RomanovV. I.

Романов Владимир Ильич, кандидат технических наук, доцент

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

Vladimir I. Romanov, Ph. D. (Eng.), Assoc. Prof.

st. Surganova, 6, Minsk, 220012

rom@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus202430122024214723Copyright © Бибило П.Н., Кириенко Н.А., Романов В.И., 20242024Бибило П.Н., Кириенко Н.А., Романов В.И.Bibilo P.N., Kirienko N.A., Romanov V.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1310Цели

Цели. Целью экспериментальных исследований является выяснение эффективности новых алгоритмов выделения из формульных описаний исходной системы булевых функций так называемых связанных подсистем. При этом каждая из выделенных подсистем впоследствии минимизируется независимо от других, однако функции, составляющие каждую связанную подсистему, минимизируются совместно.

Методы

Методы. Минимизация подсистем выполняется в классе многоуровневых BDD-представлений (BDD – Binary Decision Diagram – бинарная диаграмма решений) либо булевых сетей. После получения минимизированных описаний схем, заданных в виде совокупности взаимосвязанных формул разложения Шеннона, которые соответствуют BDD, либо в виде двухоперандных логических уравнений, соответствующих булевым сетям, выполняется синтез логических схем в библиотеке проектирования заказных цифровых КМОП СБИС (сверхбольших интегральных схем, выполненных по комплементарной технологии металл-оксид-полупроводник). В булевых сетях функциями вершин могут быть логические операции «конъюнкция» либо «дизъюнкция» над литералами булевых переменных. Литерал – это булева переменная либо ее инверсия. Минимизация BDD-представлений осуществляется по числу формул разложения Шеннона, минимизация булевых сетей – по числу литералов в формулах, задающих сети.

Результаты

Результаты. Полученные логические схемы сравнены по площади кристалла и быстродействию (временной задержке). Эксперименты проведены на 39 промышленных примерах схем. Показано преимущество (в 29 случаях) применения предлагаемых алгоритмов выделения подсистем по сравнению с совместной либо раздельной минимизацией исходной системы булевых функций, которая обычно выполняется в качестве первого этапа синтеза логических схем.

Заключение

Заключение. Предложенные в работе новые алгоритмы выделения подсистем доказали свою эффективность при выполнении различных программ оптимизации многоуровневых представлений систем булевых функций. Разработанный комплекс программ позволяет улучшать результаты технологически независимой оптимизации, применяемой при реализации проектов цифровых систем в заказных цифровых КМОП СБИС.

Objectives

Objectives. The purpose of experimental research is to determine the effectiveness of new algorithms for extracting the so-called connected subsystems from formula descriptions of the original system of Boolean functions. Subsequently each of the extracted subsystems is minimized independently of the others, but the functions that make up each connected subsystem are minimized jointly.

Methods

Methods. Minimization of subsystems is performed in the class of multilevel BDD representations (BDD – Binary Decision Diagram) or Boolean networks. After obtaining minimized descriptions of circuits, specified as a set of interconnected Shannon expansion formulas that correspond to BDD, or as two-operand logical equations corresponding to Boolean networks, synthesis of logic circuits is carried out in the design library of custom digital CMOS ASIC (Application-Specific Integrated Circuits made using complementary metal oxide semiconductor technology). In Boolean networks, node functions can be the logical operations “conjunction” or “disjunction” over literals of Boolean variables. A literal is a Boolean variable or its inversion. Minimization of BDD representations is carried out according to the number of Shannon decomposition formulas, minimization of Boolean networks – according to the number of literals in the formulas defining the networks.

Results

Results. The resulting logic circuits are compared in terms of chip area and speed (time delay). Experiments were carried out on 39 industrial circuit examples. The advantage (in 29 cases) of using the proposed subsystem extraction algorithms is shown compared to joint or separate minimization of the original system of Boolean functions, which is usually performed as the first stage of the synthesis of logic circuits.

Conclusion

Conclusion. The new algorithms for subsystem extraction proposed in the paper have proven their effectiveness in the execution of various programs for optimizing multilevel representations of systems of Boolean functions. The developed software package allows improving the results of technologically independent optimization used in the implementation of digital system projects in custom digital CMOS ASIC.

система булевых функцийдизъюнктивная нормальная формабинарная диаграмма решенийбулева сетьсинтез логической схемыVHDLзаказная СБИСsystem of Boolean functionsdisjunctive normal formbinary decision diagramBoolean networklogic synthesisVHDLASICReferencesЗакревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 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, G. D. Hachtel, C. McMullen, A. L. Sangiovanni-Vincentelli. – 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.Sasao, T. Input variable assignment and output phase optimization of PLA's / T. Sasao // IEEE Transactions on Computers. – 1984. – Vol. C-33, no. 10. – P. 879–894.Sasao T. Input variable assignment and output phase optimization of PLA's. IEEE Transactions on Computers, 1984, vol. C-33, no. 10, pp. 879–894.Wey, C. L. An efficient output assignment for PLA minimization / C. L. Wey, T. Y. Chang // IEEE Transactions on Computer-Aided Design. – 1990. – Vol. 9. – P. 1–7.Wey C. L., Chang T. Y. An efficient output assignment for PLA minimization. IEEE Transactions on Computer-Aided Design, 1990, vol. 9, pp. 1–7.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.Кнут, Д. Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 : пер. с англ. / Д. Э. Кнут. – М. : Вильямс, 2013. – 960 с.Knuth D. E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 2011, 912 р.Бибило, П. Н. Бинарные диаграммы решений в логическом проектировании / П. Н. Бибило. – М. : Ленанд, 2024. – 560 с.Bibilo P. N. Binarnye diagrammy reshenij v logicheskom proektirovanii. Binary Decision Diagrams in Logical Design. Moscow, Lenand, 2024, 560 p. (In Russ.).Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // Труды Института инженеров по электротехнике и радиоэлектронике. – 1990. – Т. 78, № 2. – С. 38–83.Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Synthesis of multilevel combinational logic circuits. Trudy Instituta inzhenerov po jelektrotehnike i radiojelektronike [Proceedings of the IEEE], 1990, vol. 78, no. 2, рр. 38–83 (In Russ.).Синтез асинхронных автоматов на ЭВМ / под ред. А. Д. Закревского. – Минск : Наука и техника, 1975. – 184 с.Zakrevskij A. D. (ed.). Sintez asinhronnyh avtomatov na JeVM. Synthesis of Asynchronous Automata on a Computer. Minsk, Nauka i tekhnika, 1975, 184 р. (In Russ.).MIS: A multiple-level logic optimization systems / R. K. Brayton, R. Rudell, A. L. Sangiovanni-Vincentelli, A. R. Wang // IEEE Transactions 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.Brayton, K. R. Factoring logic functions / K. R. Brayton // IBM Journal of Research and Development. – 1987. – Vol. 31, no 2. – P. 187–198.Brayton K. R. Factoring logic functions. IBM Journal of Research and Development, 1987, vol. 31, no. 2, рр. 187–198.Amaru, L. G. New Data Structures and Algorithms for Logic Synthesis and Verification / L. G. Amaru. – Springer, 2017. – 156 p.Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verification. Springer, 2017, 156 p.О сложности инверсных графов, реализующих булевы функции от малого числа переменных / С. А. Ложкин, В. С. Зизов, М. С. Шуплецов [и др.] // Проблемы разработки перспективных микро и наноэлектронных систем : сб. тр. / под общ. ред. А. Л. Стемпковского. – 2020. – Вып. 4. – С. 95–102. – DOI: 10.31114/2078-7707-2020-4-95-102.Lozhkin S. A., Zizov V. S., Shupletsov M. S., Zhukov V. V., Khzmalian D. E., Belyankov O. O. On complexity of inverter graphs for Boolean functions of small number of variables. Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh system : sbornik trudov [Problems of Developing Promising Micro- and Nanoelectronic Systems : Collection of Works]. In A. L. Stempkovskogo (ed.). 2020, iss. 4, pp. 95–102 (In Russ.). DOI: 10.31114/2078-7707-2020-4-95-102.Optimizing majority-inverter graphs with functional hashing / M. Soeken, L. G. Amaru, P. Gaillardon, G. De Micheli // 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, L. Amaru, P.-E. Gaillardon, G. De Micheli // 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.Бибило, П. Н. Выделение из многоуровневого представления системы булевых функций подсистем для совместной логической минимизации / П. Н. Бибило, Н. А. Кириенко, В. И. Романов // Программные продукты и системы. – 2023. – Т. 36, № 4. – С. 509–522. – DOI: 10.15827/0236-235X.142.509-522.Bibilo P. N., Kirienko N. A., Romanov V. I. Extracting subsystems from a multilevel representation of a Boolean function system for joint logical minimization. Programmnye produkty i sistemy [Software & Systems], 2023, vol. 36, no. 4, pp. 509–522 (In Russ.). DOI: 10.15827/0236-235X.142.509-522.Бибило, П. Н. 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.).Бибило, П. Н. Система логической оптимизации функционально-структурных описаний цифровых устройств на основе продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов // Проблемы разработки перспективных микро- и наноэлектронных систем. – 2020. – Вып. 4. – С. 9–16. – DOI: 10.31114/2078-7707-2020-4-9-16.Bibilo P. N., Romanov V. I. The system of logical optimization of digital circuits functional structural descriptions based on production-frame knowledge representation model. Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh system [Problems of Advanced Micro- and Nanoelectronic Systems Development], 2020, iss. 4, pp. 9–16 (In Russ.). DOI: 10.31114/2078-7707-2020-4-9-16.Бибило, П. Н. Экспериментальное сравнение эффективности алгоритмов оптимизации BDD-пред ставлений систем булевых функций / П. Н. Бибило, Ю. Ю. Ланкевич // Программные продукты и системы. – 2020. – Т. 33, № 3. – С. 449–463. – DOI: 10.15827/0236-235X.131.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.). DOI: 10.15827/0236-235X.131.449-463.Ashenden, P. J. VHDL–2008. Just the New Stuff / P. J. Ashenden, J. Lewis. – Burlington, MA, USA : Morgan Kaufman Publishers, 2008. – 909 p.Ashenden P. J., Lewis J. VHDL–2008. Just the New Stuff. Burlington, MA, USA, Morgan Kaufman Publishers, 2008, 909 p.

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