Transcript An Efficient 3D Reluctance Extractor for On

Efficient Reluctance
Extraction for Large-Scale
Power Grid with HighFrequency Consideration
Shan Zeng, Wenjian Yu, Jin Shi, Xianlong Hong
Dept. Computer Science & Technology, Tsinghua
University, Beijing 100084, China
Importance of Inductance
Extraction for P/G Grid





More than thousand million transistors
Working frequency: multiple giga-hertz (GHz)
Power consumption increases exponentially
Capture the potential problems of power integrity
Accurate modeling and dynamic simulation of the
power/ground (P/G) grid critical for VLSI circuit
design and verification.
Importance of Inductance
Extraction for P/G Grid




Modeling the inductive effect of on-chip and
off-chip interconnects is another research
focus for current nano-scale VLSI chip.
Conventional RC model is not enough
Resistance copper, capacitance Low-k
material
Denser geometries, growing complexity of
interconnect structures bring challenges to
on-chip inductance modeling and extraction
Main Difficulty





One major difficulty: unknown return path.
The partial element equivalent circuit (PEEC)
model
The resulted inductance matrix is dense.
Simply truncating would make the system
unstable
Prevents inductive modeling of large-scale
interconnect structures, such as the P/G grid.
Introduction of K




The reluctance matrix K is the inverse of
inductance matrix L, introduced in [Devgan ICCAD’00]
1
K L
(1)
K has the locality similar to capacitance.
Later works show circuit simulation has great
advantage in both speed and accuracy.
[Du ASP-DAC’05] proved:
 the sparsified partial reluctance matrix is
positive definite
 the circuit simulation is stable
Previous Works Considering
High Frequency Effect
• [Luk ASP-DAC’04]: necessity of considering
high-frequency effect
• extension of double-inversion on DATE’01.
• [Wei ICCCAS’05]: extend to admittance at ultra
high frequency
• obtain inductance and resistance.
• [Zhang ASP-DAC’06]: direct extraction,
combined with window technique
• avoid double-inversion computation
• We improved and reinforced through calculating
frequency-dependent resistance in 2007
Structure Based Idea





P/G grid extraction problem: large scale
[Shi TCAD’07]: a pattern idea to accelerate the DC
simulation
 the geometry characteristics
 topology similarity to sub-matrix regularity.
 divided the whole P/G grid into blocks
 reuse of resistance elements among blocks
Not sufficient, dynamitic simulation with
capacitance and inductance required.
Inductance extraction is very time consuming.
Brought the idea in extraction
Main Contribution




Structure regularity exploited, locality property
of reluctance.
Block division, reuse scheme.
Combined with frequency-dependent
reluctance and resistance extraction
Inductive modeling with high-frequency effect.
5
 up to 10 of wire segments
 several to tens of times faster than existing
methods
 preserving high accuracy.
Overview of Window-Based
Extraction
window-based method, main steps:
 1. For conductor i, select window Wi;
 2. Calculate the mutual reluctances within Wi,
conductor i and conductors outside is set to 0;
 3. Execute the above steps for every conductor,
fill reluctances, column by column,
 4. Generate a symmetric reluctance matrix
High-frequency Effects
•
•
•
•
Not considering the high-frequency effects:
• inverting the inductance matrix, based on (1).
Considering the high-frequency effects:
• conductors meshed into filaments.
The frequency-dependent reluctance can be
extracted, collaborated with the window
technique.
The flow will not change, the intra-window
extraction (i.e. the 2nd step) becomes
complicated.
P/G Grid Structure




Several metal layers, mesh structure
Along either X-axis or Y-axis, alternatively.
Power wires interlaced with ground wires.
Connected
through
vias, which cut the
wires into small metal
segments.
Via
Power wire
Ground wire
Figure 1. A two-layer structure of P/G grid.
P/G Structure




In a certain metal layer, the same width, and
the same pitch
The evenly distributed metal wires, evenly
distribution of vias.
If irregular in later design stages,
regularization process can be performed to
make the distribution of P/G wires similar [Shi
TCAD’07].
In this paper, the regularity is taken
advantage, for high-frequency reluctance and
resistance extraction.
Basic Idea of Block Reuse




Fig. 2 The X-Y plane partition of
P/G grid with overlapped blocks

[Shi TCAD’07] a
pattern idea for DC
simulation
Explores the geometry
characteristics
Translates topology
similarity to sub-matrix
regularity.
Divided into blocks on
the X-Y plane (see Fig.
2)
Reuse of resistance
elements among blocks.
Basic Idea of Block Reuse
Fig 3. The reluctance
is different
1
2
1
Wires on different
layers are denoted by
diamond and ellipse
marks.
2
z
(a)
x
1
2
(b)
1
2


z
x

(c)
(d)
Extended for reluctance
extraction
The idea can not be directly
applied
The reluctance affected by
environment
Basic Idea of Block Reuse





Mutual impedance of perpendicular conductors
negligible, the reluctance interaction among
metal wires along same direction considered.
Reluctance for wires along Y-axis and describe
the block partition along X-axis.
Fig. 3 and 4 shows the side view of two-layer Ydirection P/G wires for extraction.
Assume power wire and ground wire appear in
pair and their distance is the same.
Only plot the P wires.
Basic Idea of Block Reuse

pitch


z
3 overlapped
blocks.
Geometric is
identical.
The results
reused for
other blocks.
block1
block
x

2
block3
Figure 4. The division of blocks
Proper block position and
size, the error induced
may be very limited.
Basic Idea of Block Reuse


Wires along X-axis handled with similar
procedure
Whole reluctance matrix generated.
Algorithm Flow



For X-direction, determine the block division from
the Y-Z plane view; Y-direction similarly, obtain the
blocks on the X-Y plane;
Extract the reluctances for the X-direction wires
and Y-direction wires within the middle block,
respectively; If considering high-frequency effect,
both reluctance and resistance are obtained;
Assemble the extraction results to obtain two
global matrices, one for X-direction wires and the
other for Y-direction wires; combine the two
matrices to obtain the whole reluctance matrix.
Algorithm Analysis



Reduces the number of conductors to that
within one block.
Speedup ratio: approximate to the ratio of
the number of segments in the whole P/G
grid over that in a block.
The number of wires within block obtained
may approximate to the number of P/G wires.
degrade to window-based algorithm. suitable
for number of wire within block is small.
Numerical Results


The proposed algorithm implemented as
PG_extractor, for frequency-dependent reluctance
and resistance extraction considering the regular
P/G grid structure.
Compared with the DRRE (direct reluctance and
resistance extraction) [Zhang’06, Zeng’07] and
the impedance extractor FastHenry [Kamon TMTT’
94 ] developed by MIT.
[Zhang’06]M. Zhang, W. Yu, et al., “An efficient algorithm for 3-D reluctance
extraction considering high frequency effect,” ASP-DAC, 2006.
[Zeng’07]S. Zeng, W. Yu, et al., “Efficient extraction of the frequency-dependent K
element and resistance of VLSI interconnects,” Acta Electronica Sinica, 2007 (in
Chinese).
Numerical Results: the First
Example
Table 1: Error distribution of loop
inductance for the fist case

Error distribution
of loop
inductance (%)

<3% 3%6%
>6
%

PG_extractor
vs FastHenry[14]
93.9
0.4

DRRE vs
FastHenry
98.7
PG_extractor
vs DRRE
97.6
5.7

1.3
0

2.1
0.3
Four layers,1830 segments.
Upper two layers: 10 P wires
and 10 G wires, pitch: 6.36m
Lower two layers: 16 P wires
and 16 G wires, pitch: 4.23m.
3×3 blocks, each block:
Upper two layers: 6 P wires, 6
G wires
The lower two: 10 P wires. 10
G wires
Other Three Examples




Similar structure, different wire pitches and
number of wires.
Segment numbers: 4810, 11156 and 102674,
10GHz, segment in upper two layers partitioned
into 33 filaments
The second case:
 lower two layers: 25 P wires, 25 G wires,
upper two layers: 17 P wires, 17 G wires,
6×6 blocks
 99% of loop inductances have discrepancy
within 3%.
Numerical Result
Table 2 Time comparison
Case
Segment #
FastHenry*
DRRE
PG_extractor
Speedup*
1
1830
8856
55.6
18.5
3.0
2
4810
--
109.9
19.2
5.7
3
11156
--
428.7
41.9
10
4
102674
--
5034.6
109.2
46
* The speedup is with respect to DRRE
* FastHenry is not able to extract the impedance for
the three larger cases, due to the limitation of CPU
time and memory usage
Conclusion





Exploit the regularity of P/G grid,
Technique of block division, blocks with
similar inner structure, reuse scheme
Efficient window-based method.
Handle large-scale P/G grid structure with
high accuracy and efficiency.
In the future
 extending for specific P/G grid structures,
 investigating the regularity of reluctance
matrix for accelerating dynamic simulations.
Thank you!