informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2021-18-4-96-107inform-1168Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNРаспознавание логических вентилей в плоской транзисторной схемеLogical gates recognition in a flat transistor circuitЧеремисиновД. И.CheremisinovD. I.

Черемисинов Дмитрий Иванович - кандидат технических наук, доцент, ведущий научный сотрудник.

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

Dmitry I. Cheremisinov - Cand. Sci. (Eng.), Associate Professor, Leading Researcher, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus.

Surganova st., 6, Minsk, 220012.

cher@newman.bas-net.byЧеремисиноваЛ. Д.CheremisinovaL. D.

Черемисинова Людмила Дмитриевна - доктор технических наук, профессор, главный научный сотрудник.

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

Ljudmila D. Cheremisinova - Dr. Sci. (Eng.), Professor, Chief Researcher, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus.

Surganova st., 6, Minsk, 220012.

cld@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus20213112202118496107Copyright © Черемисинов Д.И., Черемисинова Л.Д., 20212021Черемисинов Д.И., Черемисинова Л.Д.Cheremisinov D.I., Cheremisinova L.D.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1168Ц е л и

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

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

М е то д ы

М е то д ы. Предлагаются графовые методы решения некоторых ключевых задач, возникающих на этапе структурного распознавания КМОП-вентилей в транзисторной схеме: разбиение графа на компоненты связности, соответствующие подсхемам из транзисторов; распознавание подсхем, являющихся логическими элементами, и реализуемых ими функций; формирование библиотеки распознанных вентилей и построение двухуровневого описания транзисторной схемы. Исходная плоская и полученная двухуровневая транзисторные схемы представляются в формате SPICE.

Р е з у л ь т а т ы

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

З а к л ю ч е н и е

З а к л ю ч е н и е. Программа декомпиляции была протестирована на практических схемах транзисторного уровня. Показано, что она имеет достаточное быстродействие, чтобы обрабатывать схемы более чем со 100 тыс. транзисторов за несколько минут на персональной ЭВМ. В настоящее время авторами разрабатываются методы распознавания в транзисторной схеме более сложных элементов, таких как элементы памяти.

O b j e c t i v e s

O b j e c t i v e s. With the increasing complexity of verification and simulation of modern VLSI, containing hundreds of millions of transistors, the means of extracting the hierarchical description at the level of logical elements from

a flat description of circuits at the transistor level are becoming the main tools for computer-aided design and verification. Decompilation tools for transistor circuits can not only significantly reduce the time to perform VLSI topology check, but also provide the basis for generating test cases, logical reengineering of integrated circuits and reverse engineering to detect untrusted attachments.

The objective of the work is to solve the problem of extracting the structure of the functional level from a flat circuit of the transistor level by recognizing in it subcircuits that implement logical elements.

M e t h o d s

M e t h o d s. Graph based methods are proposed for solving some key problems arising at the stage of structural recognition of CMOS gates in a transistor circuit: partitioning a graph into connectivity components corresponding to transistor subcircuits; recognition of subcircuits that are logical elements, and functions implemented by them; forming a library of recognized gates and constructing two-level transistor circuit. The original flat and resulting two-level transistor circuits are presented in SPICE format.

Re s u l t s

Re s u l t s. The proposed methods are implemented in C++ as a part of a transistor circuit decompilation program

for the case without any predetermined cell library. All steps of the proposed methods of structural CMOS gates recognition are performed in a linear time from the number of transistors in the initial circuit.

Co n c l u s i o n

Co n c l u s i o n.  The decompilation program has been tested on practical transistor-level circuits. Experiments indicate that the present tool is fast enough to process circuits with more than a hundred thousand transistors in a few minutes on a personal computer. Currently, the authors are developing methods for recognizing more complex elements in a transistor circuit, such as memory elements.

экстракция транзисторных подсхемКМОП-схемыверификацияперепроектирование СБИСраспознавание логических вентилейформат SPICEtransistor subcircuit extractionCMOS circuitsVLSI layout verificationVLSI reengineeringlogical gates recognitionSPICE formatReferencesCheremisinov, D. I. Extracting a logic gate network from a transistor-level CMOS circuit / D. I. Cheremisinov, L. D. Cheremisinova // Russian Microelectronics. – 2019. – Vol. 48, no. 3. – P. 187–196. https://doi.org/10.1134/S0544126919030037Cheremisinov D. I., Cheremisinova L. D. Extracting a logic gate network from a transistor-level CMOS circuit. Russian Microelectronics, 2019, vol. 48, no. 3, рр. 187–196. https://doi.org/10.1134/S0544126919030037Abadir, M. S. An improved layout verification algorithm (LAVA) / M. S. Abadir, J. Ferguson // Proc. of the European Design Automation Conf., Glasgow, UK, 12–15 March 1990. – Glasgow, 1990. – P. 391–395.Abadir M. S., Ferguson J. An improved layout verification algorithm (LAVA). Proceedings of the European Design Automation Conference (EURO-DAC'90), Glasgow, UK, 12–15 March 1990. Glasgow, 1990, рр. 391–395.Kundu, S. GateMaker: A transistor to gate level model extractor for simulation, automatic test pattern generation and verification / S. Kundu // Proc. of the Intern. Test Conf., Washington, DC, USA, 18–23 Oct. 1998. – Washington, 1998. – P. 372–381.Kundu S. GateMaker: A transistor to gate level model extractor for simulation, automatic test pattern generation and verification. Proceedings of the International Test Conference, Washington, DC, USA, 18–23 October 1998. Washington, 1998, рр. 372–381.Hunt, V. D. Reengineering: Leveraging the Power of Integrated Product Development / V. D. Hunt. – Wiley, 1993. – 283 p.Hunt V. D. Reengineering: Leveraging the Power of Integrated Product Development. Wiley, 1993, 283 p.Framework for simulation of the Verilog/SPICE mixed model: Interoperation of Verilog and SPICE simulators using HLA/RTI for model reusability / M. G. Seok [et al.] // 22nd Intern. Conf. on Very Large Scale Integration (VLSI-SoC), Playa del Garmen, Mexico, 6–8 Oct. 2014. – Playa del Garmen, 2014. – P. 1–6.Seok M. G., Park D. J., Cho G. R., Kim T. G. Framework for simulation of the Verilog/SPICE mixed model: Interoperation of Verilog and SPICE simulators using HLA/RTI for model reusability. 22nd International Conference on Very Large Scale Integration (VLSI-SoC), Playa del Garmen, Mexico, 6–8 October 2014. Playa del Garmen, 2014, рр. 1–6.Белоус, А. И. Основы кибербезопасности. Стандарты, концепции, методы и средства обеспечения / А. И. Белоус, В. А. Солодуха. – М. : Техносфера, 2021. – 482 с.Belous A. I., Solodukha V. A. Osnovy kiberbezopasnosti. Standarty, kontseptsii, metody i sredstva obespecheniya. Fundamentals of Cybersecurity. Standards, Concepts, Methods and Means of Support. Moscow, Tekhnosfera, 2021, 482 p. (In Russ.).Zhang, T. A comprehensive FPGA reverse engineering tool-chain: From bitstream to RTL code / T. Zhang, L. Wang // IEEE Access. – 2019. – Vol. 7. – P. 38379–38389. https://doi.org/10.1109/ACCESS.2019.2901949Zhang T., Wang L. A comprehensive FPGA reverse engineering tool-chain: From bitstream to RTL code. IEEE Access, 2019, vol. 7, рр. 38379–38389. https://doi.org/10.1109/ACCESS.2019.2901949Rabaev, J. M. Digital Integrated Circuits / J. M. Rabaev, A. Chandrakasan, B. Nikolic. – Prentice Hall Press, 2008. – 702 p.Rabaev J. M., Chandrakasan A., Nikolic B. Digital Integrated Circuits. Prentice Hall Press, 2008, 702 p.Bushnell, M. Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI / M. Bushnell, V. Agrawal. – Springer Science & Business Media, 2006. – 690 p.Bushnell M., Agrawal V. Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI. Springer Science & Business Media, 2006, 690 p.Черемисинова, Л. Д. Синтез и оптимизация комбинационных структур СБИС / Л. Д. Черемисинова. – Минск : ОИПИ НАН Беларуси, 2005. – 235 с.Cheremisinova L. D. Sintez i optimizatsiya kombinatsionnykh struktur SBIS. Synthesis and Optimization of Combinational Structures of VLSI. Мinsk, Ob''edinennyj institut problem informatiki Nacional'noj akademii nauk Belarusi, 2005, 235 p. (In Russ.).

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