« back to results for ""
Below is a cache of http://cadlab.cs.ucla.edu/~cong/papers/tcad99_assign.pdf. It's a snapshot of the page taken as our search engine crawled the Web.
The web site itself may have changed. You can check the current page or check for previous versions at the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
An Efficient Approach To Multilayer Layer Assignment With An Application To Via Minimization - Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 608
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 18, NO. 5, MAY 1999
An Efcient Approach to Multilayer Layer
Assignment with an Application to Via Minimization
Chin-Chih Chang and Jason (JingSheng) Cong,
Senior Member, IEEE
AbstractIn this paper we present an efcient heuristic algo-
rithm for the post-layout layer assignment and via minimization
problem of multilayer gridless integrated circuit (IC), printed
circuit board (PCB), and multichip module (MCM) layouts. We
formulate the multilayer layer assignment problem by introduc-
ing the notion of the extended conict-continuation (ECC) graph.
When the formulated ECC graph of a layer assignment problem
is a tree, we show that the problem can be solved by an algorithm
which is both linear time and optimal. When the formulated ECC
graph is not a tree, we present an algorithm which constructs
a sequence of maximal induced subtrees from the ECC graph,
then applies our linear time optimal algorithm to each of the
induced subtrees to rene the layer assignment. Our experiments
show that, on average, the number of vertices of an induced
subtree found by our algorithm is between 12% and 34% of
the total number of vertices of an ECC graph. This indicates
that our algorithm is able to rene a large portion of the layout
optimally on each renement, thus, producing highly optimized
layer assignment solutions. We applied this algorithm to the via
minimization problem and obtained very encouraging results. We
achieved 13%15% via reduction on the routing layout generated
by the V4R router [1], which is a router known to have low usage
of vias. Our algorithm has been successfully applied to routing
examples of over 30 000 wire segments and over 40 000 vias.
Finally, we outline how our layer assignment algorithm can also
be used for delay and crosstalk minimization in high-performance
IC, PCB, and MCM designs.
I. I
NTRODUCTION
A
S very large scale integration (VLSI) technology ad-
vances, interconnection and packaging technologies have
become bottlenecks in system performance. For advanced
integrated circuit (IC) designs, four to six routing layers
are commonly used in high-performance and high-density
designs. Multichip module (MCM) technology was developed
to increase packing densities, eliminate the packaging level of
interconnections, and provide more layers for routing. In both
the multilayer IC and MCM designs, the designer or automatic
layout tools may use variable widths and spacings to optimize
performance. This often results in multilayer gridless layouts.
Because multilayer gridless routing is a complex three-
dimensional general area routing problem, it is not easy to
Manuscript received February 11, 1998. This work was supported in part by
DARPA/ETO under Contract DAAL01-96-K-3600 managed by the U.S. Army
Research Laboratory, and a grant from Intel under the 19961997 California
MICRO program. This paper was recommended by Associate Editor C.-K.
Cheng.
C.-C. Chang is with the Computer Science Department, University of
California, Los Angeles, CA 90095 USA (e-mail: cchang@cs.ucla.edu).
J. Cong is with the Computer Science Department, University of California,
Los Angeles, CA 90095 USA (e-mail: cong@cs.ucla.edu).
Publisher Item Identier S 0278-0070(99)02968-1.
design a router which can simultaneously optimize many
different design objectives, such as wire length, area, delay,
crosstalk, number of vias, etc. Therefore, it is important to
perform certain post-layout optimizations to help the router
meet various design constraints and produce better routing
solutions.
One of the important post-layout optimization techniques
is layer assignment, in which wire segments in a routing
solution are reassigned to appropriate layers to achieve cer-
tain optimization objectives. Layer assignment has become
an interesting topic for the following two reasons: rst, it
preserves the wire lengths and topologies during optimizations;
second, it provides considerable exibility for optimizations
of vias, crosstalk, and delays. In this paper, we present an
efcient multilayer layer assignment algorithm for both grided
and gridless layout with focus on its application to the via
minimization problem.
The via minimization problem is that of minimizing the
number of vias in a VLSI layout. A via is a hole lled with
conductive materials to connect wire segments on different
layers in a VLSI layout. Because vias often reduce the manu-
facturing yield, degrade the circuit performance, and increase
layout area (more difcult to compact routing solutions, e.g.,
refer to [2]), it is desirable to minimize the number of vias
without affecting routability.
The via minimization problem was rst studied for two-
layer VLSI layouts. There are two approaches for the two-layer
via minimization problem: unconstrained via minimization (or
topological via minimization) [3], [4] and constrained via
minimization [5][13]. Topological via minimization computes
both the topologies and the layer assignments of all the nets
before detailed routing to minimize the overall via count.
However, topological via minimization may affect routability
considerably and is usually not used in practice. Moreover, the
two-layer topological via minimization problem was shown
to be NP-hard [4]. On the other hand, the constrained via
minimization problem optimizes an existing routing solution
by only changing the layer assignments of the wire segments.
It is also referred to as the layer assignment problem.
For the two-layer constrained via minimization problem for
Manhattan layouts with junction degrees less or equal to three,
polynomial time optimal algorithms have been developed [6],
[8], [9], [12]. These algorithms transform the problem into the
planar maximum cut problem, which is solvable in polynomial
time. However, if the layout is not Manhattan with junction
degrees less or equal to three, the two-layer constrained via
minimization problem was shown to be NP-hard [13][15].
02780070/99$10.00
©
1999 IEEE CHANG AND CONG: MULTILAYER LAYER ASSIGNMENT WITH AN APPLICATION TO VIA MINIMIZATION
609
There is also a considerable amount of research work
done on the multilayer constrained via minimization problem.
Chang and Du rst proved that the three-layer constrained
via minimization problem on Manhattan routing is NP-hard
[16]. They also proposed a heuristic algorithm which checks
vias one by one and conducts a local search up to
levels
on the via-crossing graph to eliminate the via being checked
(in their implementation,
was set to be two). Fang et
al. [17] proposed a two-phase heuristic algorithm. They use
heuristic ordering and backtracking to assign the layers of
wire segments one by one and then do local perturbations to
eliminate vias greedily. However, when one via is eliminated,
other vias might be introduced. Ahn and Sahni [15] proved that
the three-layer constrained via minimization problem remains
to be NP-hard for Manhattan routing even if the routing is
restricted to HVH channel routing. They proposed a track-
by-track heuristic algorithm for layer assignment in the HVH
constrained via minimization problem.
The existing methods for multilayer constrained via mini-
mization suffer from one or more of the following problems:
handles only a xed number of layers;
assumes a grid-base routing solution;
cannot produce good solutions due to very limited range
of local search;
cannot scale to large designs efciently.
All the experimental results on constrained via minimization
reported in the literature are on small test cases with only a
few hundred vias.
In this paper, we introduce the notion of the extended
conict-continuation (ECC) graph that abstracts the connec-
tivity relations of a given layout for the layer assignment
problem. The ECC graph is general enough to handle gridless
layouts with any number of routing layers. When a formulated
ECC graph is a tree, we show that the layer assignment
problem can be solved in linear time optimally by a dynamic
programming technique. For the general case of the layer
assignment problem where the ECC graph is not a tree, our
algorithm constructs a sequence of induced subtrees from the
ECC graph and applies our linear time optimal algorithm to
each induced subtree. Our experiments show that the average
number of vertices of the induced subtrees constructed by
our algorithm is very large, co