Wire Congestion And Thermal Aware Global Placement For 3D VLSI Circuits
d bgcolor=black height=1 colspan=2>
Wire Congestion And Thermal Aware Global Placement For 3D VLSI Circuits
Wire Congestion And Thermal Aware
Global Placement For 3D VLSI Circuits
Karthik Balakrishnan, Vidit Nanda, Siddharth Easwar, and Sung Kyu Lim
School of Electrical and Computer Engineering
Georgia Institute of Technology
gte245v, gte272u, gte581t, limsk
@ece.gatech.edu
Abstract The recent popularity of 3D IC technology stems
from its enhanced performance capabilities and reduced wiring
length. However, wire congestion and thermal issues are exacer-
bated due to the compact nature of these layered technologies.
In this paper, we develop techniques to reduce global the
temperature gradient and local and global congestions of 3D
circuit designs without compromising total intra-layer wirelength
or inter-layer via count. Our approach consists of two phases.
First, we use a multilevel min-cut based approach with a modied
gain function in order to minimize the local wire congestion
and power dissipation. Then, we perform simulated annealing
with a full-length thermal analysis to reduce the circuits global
congestion and thermal gradient. Experimental results show that
when compared to the standard mincut approach, our thermal
gradient and local congestion are reduced by 25% each, global
congestion is reduced by over 7%. Moreover, we only see a 10%
increase in the wiring length and the number of vias required.
I. I
NTRODUCTION
With the recent advent of three-dimensional Integrated
Circuit technologies, there has been a positive impact on the
performance and wiring length of these ICs. Typically, the
layered placement of transistors in multiple planes (i.e. 2.5D
placement) allows for a more compact chip with inherently
better performance than one fabricated with traditional 2D
placement techniques. However, the stacked nature of these
circuits induces and aggravates problems of non-uniform ther-
mal dissipation as well as local and global wire congestion.
Simultaneously, it is necessary to minimize the wiring in single
layers as well as the interconnect among different layers so as
to maintain routability.
Previous work in the area of 2.5D placement [1], [2], [3],
[4], [5] has focused on minimizing the intra-layer wirelength
and the number of interlayer connections, or vias. The results
of [6] indicate an improvement in overall wirelength when im-
plementing the 2.5D layered placement framework instead of
equivalent traditional 2D placement. Other work has employed
stochastic methods to determine the wirelength distributions,
trends in power consumption, and performance capabilities of
2.5D ICs [7]. The conclusions derived from stochastic analysis
conrm that 2.5D chips will provide better performance with
larger compaction, but do not predict the amount of routing
congestion that could be present.
In this paper, we provide a technique to reduce both local
and global congestion in a 2.5D chip in order to increase
the routability of the chip. We also improve the tempera-
ture prole of the circuit using state-of-the-art thermal ADI
Fig. 1. 3D physical design automation
methodologies. Our approach involves a two-stage renement
procedure: Initially, we use a multilevel min-cut based method
to minimize the congestion and power dissipation within
conned areas of the chip. This is followed by a simulated
annealing-based technique that serves to minimize the amount
of congestion created from global wires as well as improve
the temperature distribution of the circuit. We show that our
congestion and thermal gradient minimization does not have
any signicant negative impact on the inter-layer wirelength
or the number of intra-layer vias.
We provide data to establish that these objectives are
pairwise independent in the sense that minimizing the thermal
gradient, for example, does not necessarily have a positive
impact on total wirelength or wire congestion. Our contribu-
tions include a exible multi-objective optimization technique
for 3D VLSI circuits, the incorporation of accurate full-length
thermal analysis at the global placement phase in the design
process, and a thorough analysis of the correlations among
local congestion, global congestion, and thermal quality.
The rest of this paper is organized as follows. Section 2
provides preliminaries of our approach. Section 3 discusses
our min-cut based approach to reduce local wire congestion.
Section 4 explains our simulated annealing approach aimed
for global wire congestion. Section 5 provides experimental
results. Section 6 concludes our paper and describes the
ongoing research in this eld.
II. P
ROBLEM
F
ORMULATION
Given a sequential gate-level netlist
ⅳ＆エ
, let
de-
note cells consisting of gates and ip-ops, and
denote nets
that connect the cells. The purpose of the 3D Global Placement
Problem (3D-GP) is to assign cells in
ⅳ
to a given
slots in a 3D while satisfying the prescribed area constraints.
Given a 3D-GP solution
, our primary objective is to
minimize local/global wire congestion and maximum thermal
gradient. As secondary objectives, we minimize wirelength
and via induced by
. The formal denition of the problem
is as follows.
Denition 1:
3D Global Placement (3D-GP) Problem
Given a netlist
＆!"
, a set of
#$%'&)(0
slots
1
&
2
143
65
3
7
3
"8
3
9
1A@
5
@
〤7
@
8
@
D〧EFEGEH
1HI
5
I
〤7
I
"8
I
9P
with
1HQSR
, and area constraints
T
= (
Q
,
U
Q
) for
VXW$Y`Wa(
has a solution
cbde
1
, where each cell in
is assigned
to a unique slot.
is optimal if it satises the following
conditions; (1)
Q
Whg
1AQ
giWpU
Q
for
VqWrYfWr(
, (2)
1
3ts
1
@us
EGEFE
s
1
I
&v
, (3)
1HQxwi1y
&v
for all
Y儌
&厔
,
(4) wire congestion and thermal gradient are minimized.
A. Thermal and Congestion Objectives
Let
噲
denote the temperature of a block
. Then, the
maximum temperature gradient of the entire 3D-GP solution
is dened as follows:
啨墣&拺敁枙2梿
Q
S槂!
y
橮d〆VfW$Y櫓▌擶g(
Given a block
from the 3D-GP problem, we dene the local
wiring congestion cost
!噅
as:
噲`&
k
lnmporq
lpsnteu
vHw
g
`gx榞V
This value corresponds to the minimum number of wires
required to construct the tree representation of a net of size
g
`g
. Then, the local congestion of the entire solution is given
by:
&拺i摉晎2棧h!
Q
S榺
y
橮d〆VfW$Y櫓▌擶g(
For any two adjacent blocks
Q
,
y
from the 3D-GP solution,
}
Q~y
denotes a set of all hyperedges having cells in both
Q
and
y
. Then, the global congestion at the boundary
Q
"
yD
, denoted
%
Q
y
, is simply
g
}
Q~y
g
. Then, the
global congestion of the entire solution is given by:
%&亼i摉晙2x%
Q
"
y
倶儔%!僴"嚘劏橮
where
Q
and
y
are adjacent and
and
in the given
3D grid.
Fig. 2. 3D thermal modeling
B. Wirelength and Via Objective
We model the netlist
ⅳ
using a hypergraph
}
&エ厗"噓圶
,
where the vertex set
represents cells, and the hyperedge set
噒
represents nets in
ⅳ
. Each hyperedge is a non-empty
subset of
. The x-span of hyperedge
, denoted
墈
, is the
maximum distance between any x-coordinates of cells in
.
The y-span of hyperedge
, denoted
墈
, is the based on the
y-coordinates. Then the wirelength of a hyperedge
, denoted
宼
is simply
墍
. The wirelength of the entire 3D-GP
solution is:
&慿
mpor
宼
The via cost of a hyperedge
is the z-span of
, denoted
,
is the maximum distance between any z-coordinates of cells
in
. Then, the via cost of the entire 3D-GP solution is:
敃T&梜
mpor
III. 3D T
HERMAL
A
NALYSIS
A high-speed thermal simulator was implemented based
on the three dimensional Alternate Direction Implicit Method
(3D-ADI) [8]. The simulator has a linear runtime, and memory
requirement. The motivation for a thermal driven partitioning
was to maximize the efciency of heat transfer to the environ-
ment, and thereby reduce the maximum temperature gradient.
A brief explanation of the 3D-ADI method is provided in this
section.
The temperature prole of a design is governed by the
following partial differential equation for heat conduction:
櫅
濩
&仧燛
〤唘焜
〤濩
巌
濩
(1)
where
is the density of the material,
is the specic heat
of the material,
is the thermal conductivity of the material,
is the time dependent temperature, and
is the heat generation
rate. The solution for this equation is set the by the following
boundary condition equation:
唘
濩
Q
Q
〤濩h&仯
Q
漻う
〤濩
where
Q
is the heat transfer coefcient, and
Q
is an arbitrary
function on the boundary surface.
In order to solve Equation 1 using the nite difference
method, it has to be discretized in the time as well as
space domain. Assuming that the material is homogenous,
and the thermal conductivity
independent of temperature,
the divergence of the product of thermal conductivity and
temperature gradient can be rewritten as:
5洨C7{"8d濩
&枾j9
@
654〤7{8〤濩
5
@
@
654〤7{8〤濩
7
@
@
654〤7{8〤濩
8
@
V
榥
654〤7{8〤濩
where
0&
‖
. The second order partial differential terms
in the above equation can be approximated according to central
nite difference method. For example, the second order partial
derivative with respect to x can be approximated as
@
5
@
g
l
Q
q
y
q
僗
l
Q
3
q
y
q
榠氨
l
Q
q
y
q
l
QB
3
q
y
q
エ5{
@
&荡
@
l
エ砵5
@
Following this step, the average of an explicit and implicit
update, also known as the Crank-Nicholson method, is applied.
After applying these updates to the previous equation, we have
l
3
0
l
砵
&枾j
@
l
3
@
l
癲!砵5