informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2021-18-1-7-24inform-1100Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNЛогическая минимизация при синтезе комбинационных структур в FPGALogical minimization for combinatorial structure in FPGAБибилоП. Н.BibiloP. N.

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

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

Petr N. Bibilo, Dr. Sci. (Eng.), Professor

st. Surganova, 6, Minsk, 220012

bibilo@newman.bas-net.byЛанкевичЮ. Ю.LankevichYu. Yu.

Ланкевич Юрий Юрьевич, младший научный со-трудник

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

Yury Yu. Lankevich, Junior Researcher

st. Surganova, 6, Minsk, 220012

yurafreedom18@gmail.comРомановВ. И.RomanovV. I.

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

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

Vladimir I. Romanov, Cand. Sci. (Eng.)

st. Surganova, 6, Minsk, 220012

rom@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus202129032021181724Copyright © Бибило П.Н., Ланкевич Ю.Ю., Романов В.И., 20212021Бибило П.Н., Ланкевич Ю.Ю., Романов В.И.Bibilo P.N., Lankevich Y.Y., 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/1100

Описываются результаты исследования эффективности применения программ минимизации функциональных описаний блоков комбинационной логики, входящих в проекты цифровых устройств, реализуемых в FPGA (Field-Programmable Gate Array). Программы предназначены для раздельной и совместной минимизации функций в классе ДНФ (дизъюнктивных нормальных форм) и минимизации многоуровневых представлений систем полностью определенных булевых функций на основе разложения Шеннона с нахождением как равных, так инверсных коэффициентов (кофакторов) разложения. Графические формы таких представлений широко известны в литературе как BDD (Binary Decision Diagrams). Для технологического отображения применялась программа «укрупнения» полученных формул разложения Шеннона (логических уравнений), так, чтобы  каждое из них зависело от ограниченного числа k входных переменных и могло быть реализовано на одном LUT-k ‑ программируемом элементе  FPGA, имеющем k входных переменных (LUT ‑ Look-Up Table) . Показано, что предварительная логическая минимизация , выполняемая с помощью отечественных программ, позволяет улучшать результаты проектирования в зарубежных САПР (системах автоматизированного проектирования), таких как LeonardoSpectrum (ф. Mentor Graphics)  и ISE (ф. Xilinx). Эксперименты проводились для семейств FPGA Virtex-II PRO и Virtex-5 (ф. Xilinx) на потоках стандартных промышленных примеров, задающих как системы дизъюнктивных нормальных форм булевых функций, так системы булевых функций в виде взаимосвязанных логических уравнений.

The paper describes the research results of application efficiency of minimization programs of functional descriptions of combinatorial logic blocks, which are included in digital devices projects that are implemented in FPGA. Programs are designed for shared and separated function minimization in a disjunctive normal form (DNF) class and minimization of multilevel representations of fully defined Boolean functions based on Shannon expansion with finding equal and inverse cofactors. The graphical form of such representations is widely known as binary decision diagrams (BDD). For technological mapping the program of "enlargement" of obtained Shannon expansion formulas was applied in a way that each of them depends on a limited number of k input variables and can be implemented on one LUT-k – a programmable unit of FPGA with k input variables. It is shown that a preliminary logic minimization, which is performed on the domestic programs, allows improving design results of foreign CAD systems such as Leonardo Spectrum (Mentor Graphics), ISE (Integrated System Environment) Design Suite and Vivado (Xilinx). The experiments were performed for FPGA families’ Virtex-II PRO, Virtex-5 and Artix-7 (Xilinx) on standard threads of industrial examples, which define both DNF systems of Boolean functions and systems represented as interconnected logical equations.

булева функциялогическая минимизацияразложение ШеннонаBDD-представлениедизъюнктивная нормальная формасинтез логических схемVHDLFPGABoolean functionlogical minimizationShannon expansionBDD representationdisjunctive normal formlogic synthesisVHDLFPGAИсследование выполнено при финансовой поддержке БРФФИ в рамках проекта № Ф19-023.The study was carried out with the financial support of the BRFFR within the framework of the project no. F19-023.ReferencesЗотов, Ю. В. Проектирование цифровых устройств на основе ПЛИС фирмы XILINX в САПР WebPack ISE / Ю. В. Зотов. – М. : Горячая линия – Телеком, 2003. – 624 с.Zotov Yu. V. Proektirovanie cifrovyh ustrojstv na osnove PLIS firmy XILINX v SAPR WebPack ISE. The Design of Digital Devices Based on FPGA in XILINX ISE WebPack CAD. Moscow, Goryachaya liniya – Telekom, 2003, 624 р. (in Russian).Designing with Xilinx® FPGAs: Using Vivado / ed. S. Churiwala. – Springer, 2017. – 260 p.Designing with Xilinx FPGAs. Using Vivado. In Churiwala S. (ed.). Springer, 2017, 260 p.Реконфигурируемые мультиконвейерные вычислительные структуры / И. А. Каляев [и др.] ; под общ. ред. И. А. Каляева. – Ростов н/Д : Изд-во ЮНЦ РАН, 2008. – 320 с.Kalyaev I. A., Levin I. I., Semernikov E. A., Shmojlov V. I. Rekonfiguriruemye mul'tikonvejernye vychislitel'nye struktury. Multiconference Reconfigurable Computing Structures. In Kalyaev I. A. (ed.). Rostovon-Don, Izdatel'stvo Juzhnogo nauchnogo centra Rossijskoj akademii nauk, 2008, 320 р. (in Russian).Nakahara, H. A deep convolutional neural network based on nested residue number system / H. Nakahara, T. Sasao // 25th Intern. Conf. on Field Programmable Logic and Applications (FPL), Lausanne, 2–4 September 2015. – Lausanne, 2015. – P. 1–6.Nakahara H., Sasao T. A deep convolutional neural network based on nested residue number system. 25th International Conference on Field Programmable Logic and Applications (FPL), Lausanne, 2–4 September 2015. Lausanne, 2015, рр. 1–6.Петровский, Ал. А. Быстрое проектирование систем мультимедиа от прототипа / Ал. А. Петровский, А. В. Станкевич, А. А. Петровский. – Минск : Бестпринт, 2011. – 410 с.Petrovskij Al. A., Stankevich A. V., Petrovskij A. A. Bystroe proektirovanie sistem mul'timedia ot prototipa. Rapid Design of Multimedia Systems from a Prototype. Minsk, Bestprint, 2011, 410 р. (in Russian).Соловьев, В. В. Архитектуры ПЛИС фирмы 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 Russian).Бибило, П. Н. Синтез комбинационных схем методами функциональной декомпозиции / П. Н. Бибило, С. В. Енин. – Минск : Наука и техника, 1987. – 189 с.Bibilo P. N., Enin S. V. Sintez kombinacionnyh skhem metodami funkcional'noj dekompozicii. Synthesis of Combinational Circuits by Methods of Functional Decomposition. Minsk, Nauka i tekhnika, 1987, 189 р. (in Russian).Sasao, T. FPGA design by generalized functional decomposition / T. Sasao // Representations of Discrete Functions / eds.: T. Sasao, M. Fujita. – Kluwer Academic Publishers, 1996. – P. 233–258.Sasao T. FPGA design by generalized functional decomposition. Representations of Discrete Functions. In Sasao T., Fujita M. (eds.). Kluwer Academic Publishers, 1996, рр. 233–258.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.Бибило, П. Н. 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 Russian).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. 6, iss. 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. 6, iss. 6, рр. 1062–1081.Chang, S.-C. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams / S.-C. Chang, M. Marek-Sadowska, T. Hwang // IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems. – 1996. – Vol. 15, no. 10. – P. 1226–1235.Chang S.-C., Marek-Sadowska M., Hwang T. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 1996, vol. 15, nо. 10, рр. 1226–1235.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.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.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 Publisher, 2001, 288 p.Chen, D. FPGA design automation: a survey / D. Chen, J. Cong, P. Pan // Foundations and Trends in Electronic Design Automation. – 2006. – Vol. 1, no. 3. – P. 195–330.Chen D., Cong J., Pan P. FPGA design automation: a survey. Foundations and Trends in Electronic Design Automation, 2006, vol. 1, no. 3, рр. 195–330.Kubica, M. SMTBDD: New form of BDD for logic synthesis / M. Kubica, D. Kania // Intern. J. of Electronics and Telecommunications. – 2016. – Vol. 62, no. 1. – P. 33–41.Kubica M., Kania D. SMTBDD: New form of BDD for logic synthesis. International Journal of Electronics and Telecommunications, 2016, vol. 62. no. 1, рр. 33–41.Kubica, M. Decomposition of multi-output functions oriented to configurability of logic blocks / M. Kubica, D. Kania // Bulletin of the Polish Academy of Sciences. Technical Sciences. – 2017. – Vol. 65, no. 3. – P. 317–331.Kubica M., Kania D. Decomposition of multi-output functions oriented to configurability of logic blocks. Bulletin of the Polish Academy of Sciences. Technical Sciences, 2017, vol. 65, no. 3, рр. 317–331.Vemuri, N. BDD-based logic synthesis for LUT-6-based FPGAs / N. Vemuri, P. Kalla, R. Tessier // ACM Transactions on Design Automation of Electronic Systems. – 2002. – Vol. 7, no. 4. – P. 501–525.Vemuri N., Kalla P., Tessier R. BDD-based logic synthesis for LUT-6-based FPGAs. ACM Transactions on Design Automation of Electronic Systems, 2002, vol. 7, no. 4, рр. 501–525.Yang, S. BDS: a BDD-based logic optimization system / S. Yang, M. Ciesielski // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 2002. – Vol. 21, no. 7. – P. 866–876.Yang S., Ciesielski M. BDS: a BDD-based logic optimization system. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 7, рр. 866–876.Lin, H.-P. Ashenhurst decomposition using SAT and interpolation / H.-P. Lin, J.-H. R. Jiang, R.-R. Lee ; eds.: S. P. Khatri, K. Gulati // Advanced Techniques in Logic Synthesis, Optimizations and Applications. – Springer, 2010. – P. 67–85.Lin H.-P., Jiang J.-H. R., Lee R.-R. Ashenhurst decomposition using SAT and interpolation. Advanced Techniques in Logic Synthesis, Optimizations and Applications. In Khatri S. P., Gulati K. (eds.). Springer, 2010, рр. 67–85.Ashenhurst, R. L. The decomposition of switching functions / R. L. Ashenhurst // Annals of Computation Laboratory of Harvard University. – Cambrige, Mass., 1959. – Vol. 29. – P. 74–116.Ashenhurst R. L. The decomposition of switching functions. Annals of Computation Laboratory of Harvard University. Cambrige, Mass., 1959, vol. 29, рр. 74–116.Handbook of Satisfiability / ed. A. Biere [et al.]. – IOS Press, 2009. – 980 p.Handbook of Satisfiability. In Biere A., Heule M., Van Maaren H., Walsh T. (eds.). IOS Press, 2009, 980 p.Бибило, П. Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. – Минск : Беларус. навука, 2011. – 279 с.Bibilo P. N., Romanov V. I. Logicheskoe proektirovanie diskretnyh ustrojstv s ispol'zovaniem produkcionno-frejmovoj modeli predstavlenija znanij. Logical Design of Discrete Devices Using a Production-Frame Knowledge Representation Model. Minsk, Belaruskaja navuka, 2011, 279 p. (in Russian).Авдеев, Н. А. Эффективность логической оптимизации при синтезе комбинационных схем из библиотечных элементов / Н. А. Авдеев, П. Н. Бибило // Микроэлектроника. – 2015. – Т. 44, № 5. – С. 383–399.Avdeev N. A., Bibilo P. N. Effektivnost' logicheskoj optimizacii pri sinteze kombinacionnyh skhem iz bibliotechnyh elementov [Logical optimization efficiency in the synthesis of combinational circuits]. Mikroelektronika [Microelectronics], 2015, vol. 44, no. 5, рр. 383–399 (in Russian).Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.Toropov N. R. Minimizaciya sistem bulevyh funkcij v klasse DNF [Minimization of Boolean function systems in the DNF class]. Logicheskoe proektirovanie [Logical Design], Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1999, iss. 4, рр. 4–19 (in Russian).Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. – 2017. – № 8. – С. 369–384.Bibilo P. N., Lankevich Yu. Yu. Ispol'zovanie polinomov Zhegalkina pri minimizacii mnogourovnevyh predstavlenij sistem bulevyh funkcij na osnove razlozheniya Shennona [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 Russian).Бибило, П. Н. Оптимизация многоуровневых представлений систем булевых функций при перепроектировании логических схем / П. Н. Бибило, В. И. Романов // Управляющие системы и машины. – 2006. – № 5. – С. 20–29.Bibilo P. N., Romanov V. I. Optimizaciya mnogourovnevyh predstavlenij sistem bulevyh funkcij pri pereproektirovanii logicheskih skhem [Optimization of multi-level representations of systems of Boolean functions in the redesign of logic circuits]. Upravlyayushchie sistemy i mashiny [Control Systems and Machines], 2006, no. 5, рр. 20–29 (in Russian).Черемисинов, Д. И. Анализ и преобразование структурных описаний СБИС / Д. И. Черемисинов. – Минск : Белорус. наука, 2006. – 275 с.Cheremisinov D. I. Analiz i preobrazovanie strukturnyh opisanij SBIS. Analysis and Transformation of VLSI Structural Descriptions. Minsk, Belorusskaya nauka, 2006, 275 р. (in Russian).Кузелин, О. М. Современные семейства ПЛИС фирмы Xilinx : справ. пособие / О. М. Кузелин, Д. А. Кнышев, Ю. В. Зотов. – М. : Горячая линия – Телеком, 2004. – 440 с.Kuzelin O. M., Knyshev D. A., Zotov Yu. V. Sovremennye semejstva PLIS firmy Xilinx. ModernJeong, C. Computer-aided design of digital systems / C. Jeong // Department of Computer Science [Electronic resource]. – Mode of access: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex. – Date of access: 20.03.2018.XILINX FPGA Families. Moscos, Goryachaya liniya – Telekom, 2004, 440 р. (in Russian).Logic Minimization Algorithm for VLSI Synthesis / K. R. Brayton [et al.]. – Boston : Kluwer Academic Publishers, 1984. – 193 p.Jeong C. Computer-aided design of digital systems. Department of Computer Science. Available at: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex (accessed 20.03.2018).Тарасов, И. Е. ПЛИС Xilinx. Языки описания аппаратуры VHDL и Verilog, САПР, приемы проектирования / И. Е. Тарасов. – М. : Горячая линия – Телеком, 2020. – 538 с.Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli A. Logic Minimization Algorithm for VLSI Synthesis. Boston, Kluwer Academic Publishers, 1984, 193 p.Авдеев, Н. А. Эффективность проектирования заказных схем в синтезаторе LeonardoSpectrum / Н. А. Авдеев, П. Н. Бибило // Современная электроника. – 2015. – № 1. – С. 58–61.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 Russian).Avdeev N. A., Bibilo P. N. Effektivnost' proektirovaniya zakaznyh skhem v sintezatore LeonardoSpectrum [Efficiency of custom circuit design in the Leonardo Spectrum synthesizer]. Sovremennaya elektronika [Modern Electronics], 2015, no. 1, рр. 58–61 (in Russian).Avdeev N. A., Bibilo P. N. Effektivnost' proektirovaniya zakaznyh skhem v sintezatore LeonardoSpectrum [Efficiency of custom circuit design in the Leonardo Spectrum synthesizer]. Sovremennaya elektronika [Modern Electronics], 2015, no. 1, рр. 58–61 (in Russian).

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