Maverick:
Hierarchical Netlist Extractor for PC Platforms

Introduction

Maverick is a modern hierarchical netlist extractor, providing extraordinary efficiency as well as comprehensive features and ease of use. It runs on PC under Microsoft Windows NT providing unique productivity in processing of virtually any size VLSI/ULSI designs. The extractor is fully integrated with state-of-the-art Expert Layout Editor, and represents important part of its verification shell along with Savage Design Rule Checker, and Guardian LVS System.

Maverick is used to restore circuit netlist from hierarchically designed mask layout. It accomplishes that by:

• accurately identifying standard semiconductor devices (transistors, diodes, resistors, capacitances) as well as generic (user-defined) constructions
  
• accurately estimating most common parameters for each device
  
• extracting hierarchical connectivity with fast runtime and low memory requirements
  

Main Features

• full-chip hierarchical extraction for designs containing arbitrary number of elements
  
• user- definable and technology- tunable extraction process
  
• fully hierarchical processing and reporting
  
• maximum preserving of original hierarchy for layout pathologies
  
• handling of arbitrary-shaped geometry
  
• essential advantage in processing speed in comparison with existing tools
  

Maverick is a core part of the Celebrity framework providing input to Layout Versus Schematic (LVS), a comparison tool for logical and physical networks.

Advantages

At the present time there are no PC-based tools in the market capable of performing netlist extraction for comparably large (several millions devices) layouts. At the same time the demand for such CAD tools is dramatically increasing.

However, even UNIX-based tools which are capable to do full-chip verification of large designs need to improve both productivity and level of comprehension in use.

Analysis of current extractors shows that they suffer from one or more of these typical problems

- Too slow

- Can not handle large design

- Either act only over flatten design or assume essential restrictions on hierarchy structure.

Most those tools which claim hierarchical extraction have weaknesses in handling of hierarchically distributed devices (i.e. devices whose elements are not concentrated inside primary primitives of a single cell). The typical behavior is one of the following:

- Do not detect such a devices at all,

- Detect overlapping of hierarchically disjoined primitives from device-making layers but do not report distributed devices, advising to user to "improve" hierarchy structure.

- Detect the hierarchical overlapping, but flatten all instances of those cells whose any instance participates in hierarchical overlapping.

- Redistribution of device-making layout elements between hierarchy levels (to collect them on common level), followed by rebuilding the hierarchy structure of design. Extraction results in this case are output in terms of new hierarchy which is difficult to interpret.

To be competitive, Maverick delivers unique features:

• incomparable efficiency by using
  the most advanced mathematical methods for hierarchical geometry operations and pattern recognition supplied by
  
  efficient access to proprietary layout data base common for Expert layout editor and Savage design rule checker
  
• most comprehensive and easy use through:
  - true hierarchy reporting. Presenting of the all extracted devices in the most convenient for user form, where their components enumerated in the terms of source design hierarchy
  
  - integration of Maverick into state-of-the-art environment of Expert (see Figures 1 and 2).
• Multi-technology (Mixed-technology) design handling
  
• Automatic recognition and assignment of contacts
  
• Reflection of device distribution on hierarchy structure
  
• Flexible tools for connectivity setup and device definition
  
• On-the-fly (on guard) control of layout's netlist consistency during editing
  
• Incremental and selective modes (preserving already extracted components, re-extraction on edited areas only)
  

In addition an interface with the DISCOVERY family of physics-based Interconnect Parasitic Extraction Tools is planned.

Figure 1. Integrated GUI of Maverick.

Figure 2. Maverick can be run directly from Expert.

True Hierarchical Nature of Processing

Maverick efficiently handles traditionally difficult kinds of designs where hierarchical units are strongly overlapped. A typical example is presented in Figures 3 through 5.

In contrast to other hierarchical extraction tools, Maverick provides:

• efficient hierarchical recognition and reporting of distributed devices whose elements are not concentrated inside a single cell
  
• fast and reliable hierarchical deriving of connectivity regardless of existence and nature of hierarchically overlapped components

Figure 3. Sample hierarchical layout with overlapped cells.

Figure 4. Sample from Figure 3 with one level of hierarchy expanded.

Figure 5. Sample from Figure 3 with all hierarchy expanded.

Basic Methodology

Core Problem of Hierarchical Extraction.

Hierarchy must be utilized in design of VLSI circuits to handle the large amount of layout data efficiently. Entry of the circuit schematic as well as layout description is simplified and the amount of data to be stored for the circuit description is substantially reduced. Circuit modifications are easily performed as a changes in a basic cell are automatically repeated on all multiple uses of the cell. This hierarchy in circuit description should also be exploited to gain speed and efficiency in VLSI circuit verification and element extraction. The handling of hierarchy on layout verification would have been no problem if the layout were truly hierarchical and the cell instances did not interact through layout overlap. However, cell instance interaction can hardly be avoided since the designer can easily find a number if reasons why cells should be allowed to overlap. From the designers point of view complete release of any constraint is preferable. However, this freedom for the designer complicates design verification.

The usual solution to this problem is either:

a) to flatten the design in overlapping areas thereby letting these problems surface at the next hierarchical level,

b) to form a new disjunct hierarchy.

However both of this schemes are unacceptable since they produce a different hierarchy than the original hierarchy specified by designer. Instead the hierarchy of the design must be preserved as much as possible. Implicitly, the designer violates the hierarchy and creates a new one if he allows circuit elements to be formed when cell instances overlap.

The core problem is:

Does the element belong to the hierarchical level where the cells overlap or does it belong to one of the cell instances?

The same is true for a DRC. If design rule violations appear when cell instances overlap the question is:

Which hierarchical level should be chosen to display these errors to make them as simple as possible for the designer to correct?

To solve these problems we need to define a set of rules specifying the most correct hierarchical level in the original circuit description to which elements in overlapping layout should be referred. In short, this level is the lowest hierarchical level where an element always appears.

The model of dual layout forest is implemented as a mean of performing fully hierarchical design verification without any restrictions on cell instance overlaps. This provides us with fast and general method of marking design rule errors or extracted devices at the correct hierarchical level. The dual layout forest for each element is built up as a layout data is processed from the bottom up. When layout processing is completed we can determine the most appropriate cell for each element. New elements are formed as a layout from different cell overlaps can now be placed at the lowest level of hierarchy where they always appear instead of being indiscriminately incorporated in the parent cell. Thereby, the method using dual layout forests preserves the original hierarchy to the largest possible extent.

Layout Pattern Recognition

The capability of the dual layout forest by looking at the way it handles hierarchical mask operations used in extraction process. These Boolean mask operations between layers in a layout must be carried out before circuit extraction in order to create device specific rectangles. If the design is described in actual mask layers we must form abstract layers describing electrical elements such as transistor gates and N+ an P+ diffusions. In a polysilicon gate CMOS process, transistors are formed by the overlap of active (thinoxide) and polysilicon rectangles. Gate rectangles are formed by Boolean AND operations between these layers. After formation of the transistor the active rectangle belongs to two different electrical nodes, the source and the drain. Since the circuit extractor cannot handle rectangles that are shared between two nodes these have to be divided into two different rectangles. This is done with the Boolean DIFF operation.

Dual Forest of Hierarchy

The dual layout forest is a major mean of accomplishing fully hierarchical design verification according to the predefined rules. The rule set or dual layout forest allow the original hierarchy to be preserved without any restrictions on cell instance overlaps. When designer himself endangers the hierarchy by letting new devices form as cell instances overlaps, this is handled by the rule system embedded in the dual layout forest.

During hierarchical design verification or device extraction process, the layout data is processed twice:

1) We need to carry out some mask operations before the actual design rule checking and circuit extraction takes place.

2) The circuit extraction is performed such a way that layout data is processed cell by cell. For each cell its cell instances has already been checked.

In the first run we form new elements when layers overlap. In the second run we look for design rule errors or couplings between nodes.

Each of these new elements is assigned to a certain rectangle in the layout and dual layout forest. New elements can be formed when cells overlap. Elements can also disappear when cells overlap if, a design rule error is corrected by the way the cell is used. In all these cases we make notes if these changes by adding or removing branches in an dual layout forests of these elements. After each run is completed we can go through the layout data again and use the dual layout forests to place rectangles or design rule errors and couplings, respectively, in the most appropriate or correct cell.

A hierarchical layout can then be modeled as a rooted directed forest whose leaf cells represent flat layouts. As an example, a simple layout is shown on Figure 6.

Figure 6. Sample layout with devices distributed across hierarchy.

A leaf cell, C, that contains two active rectangles and one polysilicon rectangle. One of the active rectangles overlaps the polysilicon rectangle forming a transistor. This transistor belongs to cell C. Cell C is instantiated three times in cell B at the next hierarchical level and once in the main cell, A, at the topmost hierarchical level. Cell B is used one time in cell A. Cell B contains polysilicon overlapping the right active rectangle in cell C at two of three instances. This rectangle was not overlapped by the polysilicon in cell C itself so new transistors are formed. At the top most level, in cell A, there is also a polysilicon, forming new transistors both in instance of cell B and the directly instantiated cell C. There is also N+ implant rectangle in cell A, changing the transistor in cell C from P-channel to N-channel at one of the instances. This layout will be used to show the generality of the dual layout forest in hierarchical AND and DIFF operations. The rooted directed tree of this layout is shown in Figure 7a. The main cell, A, is a root of the forest. Cell C is the only leaf cell in this example. When the Boolean mask operations are performed we traverse the layout tree from the bottom up. To keep track of the different paths from cell C to the main cell we can draw a dual layout forest with cell C as a root as shown in Figure 7b.

Figure 7. Cell hierarchy tree and its dual forest.

When we start the Boolean mask operations, gate rectangles belonging to cell C are formed where the active and the polysilicon rectangles overlap. However, as we go on with the mask operations with cell B, a transistor is formed through the polysilicon overlap at two of the instances of cell C. A gate rectangle is now formed too through the AND operation. Since we do not know at how many instances in the cell C this overlap will occur until the mask operations are completed we must mark those instances in the dual layout forest where it does appear and save them until the mask operations of the chip are completed. This is shown in Figure 8a. To simplify the dual layout forest we only need to record those hierarchical levels where the status of rectangle is changed. Such a reduced dual layout forest is shown in Fig. 8b. We now see that even if the gate does not exist in cell B at the rightmost instance it exists at all instances of this B cell in A. We can then reduce the dual layout forest further by deleting the three A vertices and mark the rectangle true in cell B shown in Fig. 8c. Hence, the rectangle exists at all the instances and using the same rule again the dual layout forest is reduced to the root cell as shown in figure 8d.

Figure 8. Dual forest reduction for N+- regions.

The active rectangle overlapped by polysilicon will be considered to form a gate rectangle at the cell C level. This means that even if the element did not exist in the cell but exists in all the instances of the cell it will be transferred to the cell. For the left gate rectangle, formed when active and polysilicon overlap in cell C, the dual layout forest only consists of the root since the rectangle status is not changed at higher hierarchical levels. This is true for all the rectangles in a strictly non-overlapping hierarchical layout, where each rectangle belongs to the cell where it appears as a flat layout. This example shows the use of the of the dual layout forest for rectangles formed by the AND operation between mask layers. Such elements might be correctly moved down to the lowest possible hierarchical layer instead of simply remaining at the level where they are formed. However, in the case of DIFF-operations the use of an dual layout forest is an absolute necessity for hierarchical operations because we may need to go back to the cell instances and selectively divide already processed rectangles. This is possible with the dual layout forest since it keeps track of the instances where the rectangle's status is changed. If we return to the layout of cell C in Fig. 6 the right active rectangle is not overlapped by polysilicon is used to form a P+-diffusion rectangle in cell C. However, as we go on with the mask operations to cell B the transistor is formed through the polysilicon overlap at two of the instances of cell C. The P+-rectangle is already stored in cell C should now be divided into two smaller P+-rectangles through the DIFF operation. Since information is to be removed from cell C we must go through all its instances before we can do this. The dual layout forest for each of these source/drain P+- rectangles is shown in Figure 9.

Figure 9. Dual forest reduction for P+- regions.

Note that the source/drain rectangles that were changed to N+ no longer exist as a P+ rectangles at the top right instance (marked false in a dual layout forest).

The following procedure is used in the build-up of the dual layout forests:

When element changes status the program determines which rectangle the element is associated with and a list with the path of instances from this rectangle to the current cell. Three parameters are sent when procedure is called: 1) new status of the element; 2) path; 3) dual layout forest associated with the element.

The procedure then recursively modifies dual forest. It presumes that cell instances of the cell are checked before the cell itself. The dual layout forests are formed as mask operations proceed from leaf cells to the main cell. When changes in a rectangle's status are encountered new branches are added to or removed from the dual layout forest. This is easily done since the path between the involved cells is returned by the search procedure.

Since no operation is performed until changes are encountered no extra CPU time or memory storage space is wasted in dual layout forests for strict hierarchical designs. When mask operations are completed the layout data is processed again and rectangles placed in appropriate cells according to their dual layout forests. Finally the dual layout forests are disposed of as they are not needed anymore.

So, the dual layout forest provides us with possibility of going back to cell instances and dividing already processed rectangles in to smaller rectangles with DIFF operation. It also makes it possible to move rectangles formed by AND operations to a lower and more correct hierarchical level. Embedded in the dual layout forest are rules for determining the correct hierarchical level for the elements formed by cell overlaps. We have defined the correct level as the lowest level of hierarchy along the path from the leaf cell to the main cell where the element always appears in all of its instances. This means that an element that appears at all instances of the cell belongs to this cell and is located only here. It also means that if an element exists at all of the instances of the cell, but not the cell itself, it will be transferred to the cell anyway. An element that disappears at higher levels is removed from abstract layout. An element that is only removed at some of its instances is maintained at the other instances. An element that appears at some of its instances is only marked at these instances.

NOTE: Using the dual layout forest to display errors in DRC makes it possible to display only true errors. Errors occurring in leaf cells but which are removed later no longer have to be displayed in the leaf cell. The designer no longer has to be follow how errors are created and removed through the error printout.

Assembling of Connectivity

When all designed devices are extracted, the most efficient way to obtain interconnections between their pins is to apply appropriate dialect of classical scan-line algorithm ([3]). Being enriched by specifically tuned set merging algorithm ([2]) and reduced model of circuit hierarchy handling ([4]), it provides the optimal efficiency for deriving of interconnections. Even in worst case (flatten layout) the algorithm requires the time proportional NlogN, where N is the overall quantity of vertices of polygons from layers using for interconnections.

Interface Overview

Both batch and built-in Expert GUI modes are available for Maverick. Note, built-in version is supplied by advanced viewer for convenient displaying of circuits and comprehensive representation of hierarchy of distributed devices.

Maverick works with layout presented in EIF (Expert Internal Format), utilizing very efficient access functions using by Expert and specially designed hierarchy handlers.

It also is able to accept data prepared in GDSII and CIF formats.

Maverick does not need any kind of labels to be used for layout components, but labels can be used when appropriate regime is given .

To restore correct electrical circuits, extractor utilizes specifications of devices, basic circuit elements (e.g., transistors, diodes, resistors, capacitors), customized configurations and functional knots (subcircuits).

Every device is described by device attribute block (DAB).

Device attribute blocks are collected either in technology file or in the special Device Attribute File. It is also possible to provide correction of device attributes as well as creating of new device descriptions via GUI.

Connectivity info is specified as sets of layers connected by a connecting layer (via layer):

CONNECT=("layer1", "lay2", "lay3",...,"vialayer")

Layers, mentioned in DABs or connectivity statements can be as basic (technology) layers as generated ones (i.e. obtained with help of layer construction statements).

There are 3 sources of layer descriptions:

1) Technology file; 2) Rule script file; 3) GUI forms

Connectivity also can be stated using all enumerated ways

Construction and connectivity statements used both in technology and rule script files have the same syntax basically inherited from Expert/Savage DRC script language.

Run options are located in special configuration file. They also can be assigned/corrected using Maverick's Extraction Setup. Several major options (concerned, basically, hierarchy processing/reporting) are presented below:

TRUE_HIERARCHICAL

FULL_REGARDLESS_HIERARCHY

PARENT_LEVEL_ONLY

HIERARCHICAL_IGNORING_OVERLAP

FLAT_OVERLAP

STOP_IF_OVERLAP

RECONSTRUCT_HIERARCHY

REPORT_IN_SPICE

Maverick generates two types of netlist: one in internal format used for internal LVS comparison, and the other in standard SPICE format used for running external LVS programs and circuit simulation.

Note also, that devices, whose elements are distributed through hierarchy, are reported in special file, containing hierarchy history of components. In addition to this report file, GUI solution is designed for convenient visual highlighting of distributed device genesis.

References

[1] L.K. Scheffer, R. Soetarman "Hierarchical Analysis of IC Artwork", Proc. 22nd
Design Automation Conference, p. 293-298.

[2] J.D. Ullman. "Computational Aspects of VLSI", Morgan-Kaufmann, 1992.

[3] V. Feinberg. Geometrical Problems of VLSI Computer Graphics. Radio i Sviaz, Moscow, 1987.

[4] A.Azarenok. V.Sarvanov. Extremal realizations of hypergraphs in VLSI design. Reports of the
National Academy of Science. Minsk, Vol.30, No. 10, 1989.