ГлавнаяАрхивGraph methods for recognition of CMOS gates in transistor-level circuits

Graph methods for recognition of CMOS gates in transistor-level circuits | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/4

Рассматривается задача декомпиляции плоского описания транзисторной схемы в формате SPICE в иерархическое описание схемы на уровне логических элементов. Проблема декомпиляции возникает при верификации СБИС путём сравнения исходного описания для синтеза транзисторной схемы со схемой, восстановленной из топологии, а также при обратном инжиниринге для перепроектирования интегральных схем и обнаружения несанкционированных вложений. Рассматривается случай, когда при извлечении структуры функционального уровня из транзисторной схемы библиотека исходных логических элементов не известна. Предложены графовые методы для решения некоторых ключевых задач, возникающих при декомпиляции описания транзисторной схемы. Представленные методы реализованы на языке C++ как часть программы декомпиляции, которая протестирована на практических схемах транзисторного уровня.
  • Title Graph methods for recognition of CMOS gates in transistor-level circuits
  • Headline Graph methods for recognition of CMOS gates in transistor-level circuits
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 64
  • Date:
  • DOI 10.17223/20710410/64/4
Ключевые слова
КМОП-схема из транзисторов, экстракция подсхем, распознавание логических вентилей, изоморфизм графов, формат SPICE
Авторы
Ссылки
Abadir M. S. and Ferguson J. An Improved Layout Verification Algorithm (LAVA). Proc. ED AC, Glasgow, UK, 1990, pp. 391-395.
Baker R. CMOS Circuit Design, Layout, and Simulation. Third Ed. John Wiley k, Sons, 2010.
Kundu S. A transistor to gate level model extractor for simulation, automatic test pattern generation and verification. Proc.Int. Test Conf. IEEE, Washington, 1998, pp. 372-381.
Blunt V.D. Reengineering: Leveraging the Power of Integrated Product Development. Vermont, Oliver Wight Publ., 1993. 282 p.
Yang L. and Shi C-J.R. FROSTY: A program for fast extraction of high-level structural representation from circuit description for industrial CMOS circuits.Integr. VLSI J., 2006, vol.39, no. 4, pp. 311-339.
Zhang N., Wunsch D. C., and Harary F. The subcircuit extraction problem. IEEE Potentials, 2003, vol.22, no. 3, pp. 22-25.
http://www.silvaco.com/content/appNotes/iccad/2-003_LogicGates.pdf - Logic Gate Recognition in Guardian LVS, Silvaco, 2009.
Lester A., Bazargan-Sabet P., and Greiner A. YAGLE, a second generation functional abstractor for CMOS VLSI circuits. Proc. ICM'98, Monastir, Tunisia, 1998, pp. 265-268.
Ebeiing E. GeminilL A second generation layout validation program. Proc. ICCAD-89, Santa Clara, CA, USA, 1988, pp. 322-325.
Ohlrich M., Ebeiing G., Ginting E., and Sather L. SubGemini: Identifying subcircuits using a fast subgraph isomorphism algorithm. Proc. 30th ACM/IEEE Design Automation Conf., Dallas, TX, USA, 1993, pp. 31-37.
Conte D., Foggia P., Sansone C., and Vento M. Thirty years of graph matching in pattern recognition.Int. J. Pattern Recognit. Artif.Intell., 2004, vol. 18, pp. 265-298.
Cheremisinov D. I. and Cheremisinova L. D. Extracting a logic gate network from a transistor-level CMOS circuit.Russian Microelectronics, 2019, vol. 48, no.3, pp. 187-196.
Cheremisinova L. D. Sintez i optimizatsiva kombinatsionnvkh struktur SBIS [Synthesis and Optimization of Combinational Structures of VLSI]. UIIP NAS Belarus Publ., Minsk, 2005. (in Russian).
Hartke S. G. and Radcliffe A. J. McKay's Canonical Graph Labeling Algorithm, https://api.semanticscholar.org/CorpusID:6454900, 2008.
Carey M. R. and Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness. NY, W.H. Freeman Publ., 1979.
McKay B.D. Practical graph isomorphism. Congressus Numerantium, 1981, vol. 30, pp.45-87.
Junttila T. and Kaski P. Engineering an efficient canonical labeling tool for large and sparse graphs. Proc. ALENEX, New Orleans, LA, 2007, pp. 135-149.
Cheremisinov D. and Cheremisinova L. Subcircuit pattern recognition in transistor level circuits. Pattern Recognit. Image Anal., 2020, vol. 30, pp. 160-169.
Graph methods for recognition of CMOS gates in transistor-level circuits | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/4
Graph methods for recognition of CMOS gates in transistor-level circuits | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/4