# *Maverick*- Hierarchcal Full-Chip Extractor Recent Significant Advances

*Maverick*

Introduction

** Maverick** is a sophisticated full
chip hierarchical netlist extractor [1]. It augments the existing

**framework which includes state-of-the-art software for VLSI layout editing, hierarchical design rule checking and layout versus schematic comparison. The latest release of**

*CELEBRITY***is equipped with many new interface features, including the ability to search for a net by name, and new engine upgrades, such as extraction of parameters of active devices. A new numerical procedure has been developed for resistance extraction of complex geometrical shapes.**

*Maverick*

Parameter Extraction

An important feature of any netlist extractor is the ability to accurately report geometrical active device parameters to the netlist.

For MOS technology, ** Maverick** provides
channel length (

*L*), channel width (W), drain diffusion area (

*AD*), source diffusion area (

*AS*), perimeter of the drain junction including the channel edge (

*PD*), perimeter of the source junction including the channel edge (

*PS*).

For diodes, extraction is performed for the area
of the diode (*AREA*) and perimeter of junction (*PJ*).

For capacitors, ** Maverick** reports
the capacitance combining inputs from the technology file with extracted
geometries. To obtain the capacitance the technology file must include
two technology constants: area capacitance (

*AreaAttr*in aF/?m

^{2}) and perimeter capacitance per unit length (

*PerimAttr*in aF/?m). These are supplied together with both layer names for the capacitor. A typical technology file input might be:

Capacitance

{

Layer1 = "Pin1"

Layer2 = "Pin2"

AreaAttr = 60

PerimAttr = 90

}

Here *Pin1* and *Pin2* are layers of
the capacitor.

Formula for calculating capacitance is standard

*C = AreaAttr * A + PerimAttr * P,*

where *A* and *P* are area and perimeter of capacitor.

Resistance Extraction

Resistance extraction for arbitrary shaped elements is a more sophisticated problem that the purely geometrical extraction active device geometries.

The resistance extraction routine always needs
a sheet resistance value in Ohms/square to be specified for resistor
*recognition* layer in technology file. The following fragment
of an **Expert** technology file shows how
this is done. Here the relevant row has been highlighted with bold
type.

Layer

{

Name = "N-Act"

Wire

{

MiterAngle = 20.00

Width = 1.00

Joint = LAYOUT

End = EXTEND

}

Material

{

MaterialName = ""

Resistivity = 555Permittivity = -1.00

Thickness = 1.00

}

CIFName = "XXXX"

Stipple = "0sparse11"

Color = (200,190,0)

ColorName = ""

GDS2Num = 21

GDS2DataType = 0

Derive = ""

Scope = CELLWISE

Processing

{

DesignLayer = TRUE

ProcessingStep = -1

Operation = NONE

StepCoverage = 0.00

Undercut = 0.00

Angle = 0.00

}

}

Here the layer N-Act is the resistor recognition
layer with sheet resistance equal to 555 Ohm/square. The efficient
numerical procedure implemented in ** Maverick** provides
high accuracy of extracted resistance value for a resistor of arbitrary
configuration.

There are several geometrical shapes such rectangular resistors, bends, T-shaped and X-shaped resistive fragments of whose the resistance can be calculated using analytical formulas.

**uses these analytical expressions while dealing with resistors of these shapes. However all-angle geometry often results in even more complex shapes with multiple ports.**

*Maverick***is able to extract the resistance of these using more advanced numerical techniques.**

*Maverick***can extract a full equivalent resistance network from the shape of which the ports are connected to**

*Maverick**N*different electrical nodes.

*N*can be arbitrarily large however its typical value is two. This requires solving the following partial differential equation

*N-1*times over the resistive region[2]. Here =

*1/p, p*is a piecewise constant sheet resistance and is electric potential. The whole boundary of the region can be subdivided into two major parts, namely and , where Dirichlet and Neumann conditions respectively are imposed.

and

where

_{0}and

*q*

_{0}mean prescribed values of potential and its normal derivative respectively. In most cases sheet resistance is constant over the whole region under consideration. Then (1) reduces to Laplace's equation

It has to be solved assuming one of the ports under unit potential and the rest of ports under zero potential. This should be done

*N-1*times moving unit voltage to different port every time.

Among the techniques for solving equations (2)-(4), two main categories of methods should be mentioned. For the first category of methods, one needs to discretize the whole region under consideration using spatial mesh and to solve resulting linear system of which the coefficient matrix is very large although sparse. Finite element method (FEM) [2], [3], [4] and finite difference method (FDM) [5] are well-known examples of such an approach. The large size of coefficient matrix is clearly a disadvantage of mesh-based methods. The second category of methods for extracting resistance implies reducing the governing partial differential equation to an equivalent integral equation formulation. In this case the system of linear equations to be solved is of significantly lower order although dense. Boundary element method (BEM) [6] is an integral equation approach, which does not need expensive computation of complicated Green's functions. Instead, it usually employs simple Green's functions, for instance, the free-plane one, as a fundamental solution.

Despite its simplicity, FDM faces difficulties in handling all-angle geometry. The former two approaches are more general. Advanced implementation of FEM needs sophisticated triangulation routine [7], which itself requires substantial computational resources. The geometrical engine in

**subdivides whole polygons into smaller pieces. This means that the problem of resistance extraction over an arbitrarily shaped polygon is usually stated for a relatively small region. Taking into account all the above mentioned considerations after intensive testing it has been found that BEM is more efficient for computing resistance of irregular regions.**

*Maverick*There are two main formulations of BEM [8]: direct and indirect. Indirect or charge formulation is based on using a generalized charge as a variable. This can be found at the matching points by solving related discrete system of linear equations. Then boundary values of electric potential and its normal derivative can be evaluated. The conceptual disadvantage of indirect formulation is that the solution of the problem is obtained through computation of some intermediate variable namely the generalized charge. This sometimes bears no physical relation to the problem. In direct BEM potential and its normal derivative are used as variables. In addition direct BEM is less sensitive to smoothness of the boundary than indirect [8]. The direct formulation is implemented in

**.**

*Maverick*A new direct boundary element numerical procedure has been developed. This offers improved performance compared with [6] and can handle singularities in a quite natural manner avoiding generating excessive mesh points. An example of this approach is supplied below.

It can be shown that the error introduced by replacing * and

*q*by an approximate solution can be minimized by writing the following weighted residual expression

where * is interpreted as a weighting function and

Integrating (5) by parts twice and assuming * to be a fundamental solution to Laplace's equation we finally arrive at

Here index

*i*indicates the field point. The discussion of the coefficient

*c*is left for the next section. Equation (6) expresses direct formulation of (4). For the points on potential is known and its normal derivative has to be found from (6). The opposite is true for the points on .

_{i}If the problem is solved in a piecewise homogeneous region, the discrete analog of (6) contains two unknown values at the interface. In that case different regions are treated separately. This provides two different equations for each pair of interface unknowns and

*q*. These equations should be related to each other by imposing compatibility and equilibrium conditions as follows

where subscripts appear to distinguish the values from two adjacent subregions. It is clear that direct BEM is a diakoptic-based algorithm when applied to nonhomogeneous region. This intrinsic diakoptic property results in linear system of which the coefficient matrix is banded rather than fully dense which can be employed in developing efficient solver. On the other hand, this matrix has block structure, which can be utilized for multiprocessor handling.

To solve (6), the boundary is discretized into a series of boundary elements.

*n*

_{k}matching points (nodes) are assigned to

*k*th boundary element. (For instance,

*n*

_{k}=1 for zero-order constant element,

*n*

_{k}=2 for first-order linear element,

*n*k =3 for second-order quadratic element and so on.) Particular placement of nodes within each element depends on type of that element. Then the fundamental solution has to be chosen. The free-plane Green's function

will be used throughout this paper, where

*r*is the position vector of the source. Equation (6) is discretized as follows

Here

*N*is the total number of boundary elements. For each kth boundary element one introduces local interpolation functions

_{m},

*m=1, 2,...,*

*n*

_{k}, which have the unity value at mth node of the current element and zero values at all the other nodes of that element. The integrals along an element

*j*on the left-hand side and the right-hand side of (8) can be written as

respectively. Integrals on the right-hand sides of (9) can be evaluated numerically using Gaussian quadrature formulas. Hence, (8) represents the assembled equation for node

*i*and can be written as

where *H _{ii}* includes the term

*c*

_{i}*. The complete set of equations (10) may be rearranged to take the form of standard system of linear equations*

_{i}*Ax=b*, where the vector x contains all of the unknown values and

*q*. The resulting linear system can be solved by

*LU*-factorization.

The accuracy of boundary element solution depends on the set of interpolation functions assigned to each element. Using higher order elements it is possible to obtain more accurate resistance values. However higher order elements require more nodes and the order of linear system matrix is increased. The latter is rather disappointing because assembling and solving system of linear equations takes the major part of overall computational time. By defining computational efficiency as the primary objective, zero-order constant elements are employed in resistance extraction routine as default. This yields minimum possible number of nodes. Linear continuous element does not work here without special adjustments because of multiply defined normal derivative at the corner nodes. Linear and higher order elements can be used to enhance the accuracy of numerical solution if necessary. In contrast to [6], a concept of partially discontinuous element has been developed which decreases the total number of nodes by a half for linear element, by one third for quadratic element, etc. In the most cases constant element provides quick solutions which are accurate enough compared to third order solutions. In the worst case has been faced during testing, the maximum difference of zero-order solution from first-order one is less than 15%, while typical difference is below 5%.

Device Setup in *Maverick*

The user is given two options to define devices
to extract from a layout. First one is to use special statements
and keywords in the ** Expert** technology file. The example
of such description would read like this:

Device

{

Type = "n-MOSFET"

SpName = "_n_"

DevLay

{

NameL = "N-Gate"

TypeL = REC

}

DevLay

{

NameL = "N-SD"

TypeL = PIN

}

DevLay

{

NameL = "Poly"

TypeL = PIN

}

DevLay

{

NameL = "N-SD"

TypeL = PIN

}

DevLay

{

NameL = "Bulk"

TypeL = PIN

}

}

Here *Device* is a keyword followed by a number
of attributes in parenthesis. The first of these attributes has
*Type* as a keyword. Its value is a string. Allowed values
of that string include "n-MOSFET", "p-MOSFET", "npn-BJT", "pnp-BJT",
"diode", "resistor", "capacitor", and some others. They specify
the type of a particular active or passive SPICE netlist circuit
element. The other attributes define the SPICE model name of the
corresponding model in string format. Its keyword is *SpName*.
The next attribute occurs several times in a typical *Device*
statement. Its keyword is *DevLay*. This construction implies
two inner attributesof whose keywords are *NameL* and *TypeL*.
NameL must be a string containing previously defined possibly derived
layer. TypeL can take just one of two allowed values REC or PIN,
specifying device recognition layer and pin layer respectively.
It is recommended that the user list pin layers in the same order
as they appear in SPICE statement. For instance, in the above example
pin layers of n-channel MOSFET are listed in the sequence drain,
gate, source, substrate exactly as SPICE netlist format requires.
The presence of device recognition layer is obligatory. The number
of pin layers depends on the type of device.

The other way to set up devices is to use an intuitive
GUI in ** Maverick**. To call the extractor, the user has
to choose

*Verification>>Netlist Extraction>>Extract*menu command, as it is shown in Figure 1. This action opens the dialog window presented in Figure 2.

Figure 1. Calling ** Maverick**
from within the

**layout editor.**

*Expert*

Figure 2. Netlist Extractor dialog box

Now to enter device settings users should click
*Edit Devices* button. Then the user arrives in dialog window
shown in Figure 3.

Figure 3. Graphical Interface for defining active devices.

This window can be conditionally displayed as three columns. The left column contains the list of all devices defined for the project. The user is able to add and delete devices by clicking on corresponding button at the very bottom of this column. All the devices listed in this box have distinctive SPICE model names. This means that one can define several kinds of the same device type by referring it to different SPICE models.

Once a particular device has been selected in the left column, its attributes appear in four windows in the middle column of the dialog box. The top window in the middle column is dropdown list box. The user can select device type from the set of predefined ones. The second window from the top is an edit box. The user can type directly in this window to specify SPICE name of selected device. The third window from the top contains recognition layers for selected device. The user can delete this by clicking on the corresponding button. The bottom window in the middle column is ordered list of pin layers of the device selected in the left column. Users can delete either of them by selecting particular layer and then clicking on the button at the very bottom of this column.

The right column includes the list of all the layers defined in the project. The user can select any of them and then set it as device recognition layer or as pin layer for the device selected in the list in the left column of the dialog box by clicking corresponding button under layers list box.

An example of the operations required to add a device to the extraction follows. After clicking the Add Device button, a new device is added to the list box and becomes selected. Its type is initially set up as p-MOSFET and SPICE name appears as noname_1, noname_2, etc. The windows for device recognition layer and for pin layers are empty. The user is responsible for filling-in all the four windows in the middle column with the necessary information.

Working with dialog shown in Figure 3 the user
creates the same information pattern as the technology file specifies.
It is recommended to use dialog capabilities rather than manual
updating the technology file because several consistency checks
are performed when the OK button is clicked. For instance, ** Maverick**
verifies the presence of device recognition layer and the correctness
of the number of pin layers specified.

Using Layout Texts as Net Names

It is common practice to use texts such as VDD
and VSS for naming electrical nodes. ** Maverick** provides
the flexibility to add user defined names. First of all one should
place the text to be accepted as net name into the connected layer
from that net. It is recommended to click the

*More Options*button in extractor dialog box (Figure 2) which results in the dialog box presented in Figure 4, and make sure the control option

*Use Layout Texts as Net Names*is checked. While accepting layout texts during extraction,

**can encounter several problems. A typical problem is when two or more different texts belong to the same net. The current version of**

*Maverick***assigns new name to such a node. That new name would appear as,**

*Maverick*-
MULTILABEL-35,

where MULTILABEL- is a key word and 35 is an example of internally generated node identifier. In addition a warning is generated and added to

*message file*.

Figure 4. Netlist Extraction Options Dialog Box.

The other typical problem is when the *same text is used for different
nets*. ** Maverick** generates different name for one
of two equally labeled nets and puts an appropriate warning into
the message file. However the user often needs to do so while designing
subcells where power supply or ground may be represented by multiple
shapes that are intended to be connected somewhere else in parent
cell. In this case the user can specify a string of special symbols
in

*Unfinished Net Symbols*edit control of

*Extraction Options*dialog box. Any of these symbols can then be used to indicate intentionally unfinished nets by simply adding them to the text from either side. For example, if user specified the string "!:%", then the following texts mean different shapes of the same net

*VDD*

VDD

VDD:

:VDD

!VDD%

%VDD:

VDD!

The name *VDD* without one of the above specified
symbols may only be used once. Those special symbols will never
appear in output netlist so that in the previous example the only
output node is *VDD*.

Viewing Netlist Tags

During execution ** Maverick** adds certain
records to the property lists attached to several geometrical primitives
apart from creating netlist file. Once the extraction has been completed,
this information becomes available to the user. The user can view
these records by selecting a single shape of a noninstance layer,
and further choosing special Menu item

**Verification >> View Netlist Tags**, as shown in Figure 5.

Figure 5. Calling the Netlist Tag Browser.

Device Tags**
**If the shape from the device recognition layer has been selected
as in Figure 5, the user is presented with the dialog box in Figure
6. This box includes netlist record of the selected device. This
dialog box provides the name of related device recognition layer.

Figure 6. Device Recognition Shape Dialog Box.

Connectivity Records

Once the extraction is completed, connectivity information is also been added to the property. The user can select a single shape of any connected layers. After this the Menu

**Verification >> View Netlist Tags**calls the dialog box presented in Figure 7.

Figure 7. Node Name Dialog Box.

This box includes the name of the node and the name of the layer
from which the shape has been selected.

Search for Node by Name

After extraction has been completed, the user can
obtain all the shapes connected to a in specific net using *Search
Node* property page of *Netlist Tag Browser* presented in
Figure 8. This page may be easily activated when one is viewing
netlist tags as has been shown in Figures 6 and 7.

Figure 8. Search Node Property Page.

This page can also be activated directly from the

**main menu asseen in Figure 9.**

*Maverick*Figure 9. Calling the Search Node Feature from

**.**

*Maverick*To perform a search the user has to specify the name of the node to be found within corresponding edit control. Then it is necessary simply to click the

*Search*button. After that the number of objects representing the specified node and zero-based index of the current object appear in corresponding gray windows. This is shown in Figure 10.

Figure 10.

Furthermore, the current selection is highlighted in the layout
as a bright white hatched object. Using *Previous Object* and
*Next Object* buttons, the user can browse through all the
objects and view them in the layout.

If the user has selected the shape in a connected layer, the name
of the node given to that shape by ** Maverick** is automatically
substituted into

*Search for the Node*field of

*Netlist Tag Browser*.

The

*Select Node*button allows selecting/deselecting of all the shapes of the specified node at once. After the

*Netlist Tag Browser*is closed, the status of selection of the node is preserved.

Search for Device

The ** Expert** Menu option shown in Figure
11 opens the dialog window presented in Figure 12. The user can
also bring up this window by selecting the

*Device Search*property page while viewing device tag as shown in Figure 6. The user can now type the name of any device present in the netlist within edit control and then click on the

*Search*button. For example if the string "M10" has been typed for the multiplexer layout shown in Figure 11, then the result of search might be as shown in Figure 13. After the search is done, the edit control now contains the full SPICE record of the device, the shape of device recognition layer associated with that device is highlighted in the layout.

Figure 11. Calling Search Device Feature
Directly from ** Expert**.

Figure 12. Search Device Property Page.

Figure 13. Results of the Device Search highlighted in the layout.

**References**

- A.Azarenok and V.Feinberg, "
: hierarchical netlist extractor for PC platforms", Simulation Standard, vol. 9, pp. 1-6, Jun 1998.*Maverick* - C.M.Sakkas, "Potential distribution and multi-terminal DC resistance computations for LSI technology", IBM J. Res. Develop, vol. 23, pp. 640-651, Nov 1979.
- E.Barke, "Resistance calculation from mask artwork data by finite element method", in Proc. 22nd DAC, Jun 1985, pp. 305-311.
- T.Mitsuhashi and K.Yoshida, "A resistance calculation algorithm and its application to circuit extraction", IEEE Trans. Comput.-Aid.Design, vol. CAD-6, pp. 337-345, May 1987.
- M.Glez Harbour and J.M.Drake, "Calculation of multiterminal resistances in integrated circuits", IEEE Trans. Circ. Syst., vol. CAS-33, pp. 462-465, Apr 1986.
- Z.Wang and Q.Wu, "A two-dimensional resistance simulator using the boundary element method", IEEE Trans. Comput.-Aid.Design, vol. CAD-11, pp. 497-504, Apr 1992.
- A.J.Kemp, J.A.Pretorius, and W.Smit, "The generation of a mesh for resistance calculation in integrated circuits", IEEE Trans.Comput.-Aid.Design, vol. CAD-7, pp. 1029-1037, Oct 1988.
- C.A.Brebbia, J.C.F.Telles, and L.C.Wrobel, Boundary Element Techniques. Berlin: Springer-Verlag, 1984.