Abstract

Technical and economic factors have caused the field of physical design automation to receive increasing attention and commercialization. The steady down-scaling of complementary metal oxide semiconductor (CMOS) device dimensions has been the main stimulus to the growth of microelectronics and computer-aided very large scale integration (VLSI) design. The more an Integrated Circuit (IC) is scaled, the higher its packing density becomes. For example, in 2006 Intel's 65-nm process technology for high performance microprocessor has a reduced gate length of 35 nanometers. In their 70-Mbit SRAM chip, there are up to 0.5 billion transistors in a 110 mm2 chip size with 3.4 GHz clock speed. New technology generations come out every two years and provide an approximate 0.7 times transistor size reduction as predicted by Moore's Law. For the ultimate scaled MOSFET beyond 2015 or so, the transistor gate length is projected to be 10 nm and below. The continually increasing size of chips, measured in either area or number of transistors, and the wasted investment involving fabricating and testing faulty circuits, make layout analysis an important part of physical design automation. Layout-versus-schematic (LVS) is one of three kinds of layout analysis tools. Subcircuit extraction is the key problem to be solved in LVS. In LVS, two factors are important. One is run time, the other is identification correctness. This has created a need for computational intelligence. Fuzzy attributed graph is not only widely used in the fields of image understanding and pattern recognition, it is also useful to the fuzzy graph matching problem. Since the subcircuit extraction problem is a special case of a general-interest problem known as subgraph isomorphism, fuzzy attributed graphs are first effectively applied to the subgraph isomorphism problem. Then we provide an efficient fuzzy attributed graph algorithm based on the solution to subgraph isomorphism for the subcircuit extractio- n problem. Similarity measurement makes a significant contribution to evaluate the equivalence of two circuit graphs. To evaluate its performance, we compare fuzzy attributed graph approach with the commercial software called SubGemini, and two of the fastest approaches called DECIDE and SubHDP. We are able to achieve up to 12 times faster performance than alternatives, without loss of accuracy

Department(s)

Electrical and Computer Engineering

Second Department

Computer Science

Keywords and Phrases

CMOS Device; CMOS Integrated Circuits; Fuzzy Attributed Graph; VLSI; Circuit CAD; Circuit Layout CAD; Complementary Metal Oxide Semiconductor Device; Computer-Aided Very Large Scale Integration; Fuzzy Attributed Graphs; Fuzzy Logic; Layout Analysis Tools; Microelectronics; Physical Design Automation; Subcircuit Extraction; Very Large Scale Integration (VLSI)

International Standard Serial Number (ISSN)

1063-6706

Document Type

Article - Journal

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 2006 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jan 2006

Download

Full Text Link

Share

 
COinS