我们毕业了Since ,the upper left
module
in should be packed in one of the two ways shown in
Fig.8in the
floorplan
where
out of the
floorplan
modules.Note that the
TBS
by
changing
from ,
and modules,the algorithm can
construct the
floorplan
.
The
first
and
in
,if there is
an
,we will only delete
those
,the intermediate floorplan
obtained is the same
as ,according to the above
lemma,
in
.Therefore,we will delete
all
the
to
down to and including
module
and
is
,the number of
different TBS configurations is bounded
by
.III.E XTENSION TO G ENERAL F LOORPLAN
A.Empty Rooms in Mosaic Floorplan
A
TBS
.Now,we want to insert an exact number of empty rooms at the right places in
YOUNG et al.:TBS:A NONREDUNDANT REPRESENTATION FOR GENERAL NONSLICING FLOORPLAN
463
(a)(b)
Fig.10.Examples of reducible and irreducible empty
rooms.
Fig.11.Wheel
structure.
does not form a wheel struc-
ture,there is at least one slicing cut (Fig.12)on one of its four
sides.By removing this slicing cut,we can
merge
Lemma 5:The adjacent rooms at the four T-junctions of an
irreducible empty room must not be irreducible empty rooms
themselves.
Proof:W.l.o.g.,we consider an irreducible empty
room
the T-junction at its upper left corner is also an
irreducible empty room (Fig.13).
Then width
can be merged
with
can be merged
with B.Mapping Between Mosaic Floorplan and General Nonslicing Floorplan In this section,we will show how a nonslicing
floorplan .For simplicity,we will make use of TBT for explanation.That means,given a mosaic
floorplan )to the trees appropriately so that they will correspond to a valid nonslicing
floorplan ,each of its irre-ducible empty rooms must form a wheel structure,sharing its
four corners with four different modules.Each of them can only
464IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,VOL.22,NO.4,APRIL
2003
(a)(b)
Fig.14.Tree structure of an irreducible empty
room.
Fig.15.Mapping between mosaic floorplan and nonslicing floorplan.
be created from one slicing structure as described in the map-
ping
From Lemma 5,we know that the adjacent rooms of an ir-
reducible empty room must be occupied.Therefore,if we want
to
insert
s must be inserted between some module nodes as shown in
Fig.16.Given this observation,we will first insert as
many and and
s that are inserted
cor-Fig.16.Only two ways to insert X into a
tree.(a)
(b)(c)Fig.17.Simple example of constructing a nonslicing floorplan from a mosaic floorplan.rectly.According to Observation 2,a pair of TBT are valid (cor-respond to a packing)if and only if the inorder traversal of their extended trees are equivalent except that all the bits are reversed.Therefore,in order to find out those
valid s.The matching is not difficult since there must be an equal number
of
between
YOUNG et al.:TBS:A NONREDUNDANT REPRESENTATION FOR GENERAL NONSLICING FLOORPLAN465
Fig.18.Example of searching the last module in the right subtree of
466IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,VOL.22,NO.4,APRIL
2003Fig.23.Four cases of Left-Rotate (T; .
Now we consider the case
that
in the left subtree of from the TBS,and insert one .Note
that the left subtree of is exactly a general binary tree.In
addition,.We thus obtain the modified conditions for the left subtree
of ,the number of 0s is two more than the number of 1s.b)For any proper prefix of the bit
sequence ,the number of 0s is
less than or equal to the number of 1s plus 1.
Based on the above conditions,we can count the number of 0and 1from
until we reach the
module at
module
)of the left subtree
of .The labeling bit for the inserted
,module
at s,we obtain the inorder
traversals of the trees are obtained.Matching can then
be done as described in Section III-C.
D.Tight Bound on the Number of Irreducible Empty Rooms
In order to describe nonslicing structure by a mosaic floorplan representation,some previous works [14],[15]include dummy blocks of zero area in the set of modules.The method described in Section II-C is very efficient but it is applicable to the TBS representation only.In general,we only need to have and a lower bound
of dummy blocks are
needed and we cannot use much less.
Theorem 4:In a nonslicing floorplan
must be occupied.Therefore,each irreducible empty room will take up four corners of some oc-cupied rooms.Since there are
only irreducible empty
rooms.
YOUNG et al.:TBS:A NONREDUNDANT REPRESENTATION FOR GENERAL NONSLICING FLOORPLAN
467Fig.24.Proof of Lemma 7.
Theorem 5:There exists a nonslicing
floorplan
be the number of modules along each edge (for the example
in Fig.
20,
IV .F LOORPLAN O PTIMIZATION BY S IMULATED A NNEALING
Simulated annealing is used to search for a good TBS.The
temperature is set to
1.5
10
.
M2:Change the width and height of a module.
M3:Rotation based on
sequence by applying one or
more moves from the
set
sequence by move M1and M2changes
the dimensions of a module,all TBSs are reachable by applying
moves from the
set
time.For
move M3and M4,we borrow and modify the idea of rotations
in red–black tree [2].A red–black tree is a binary search tree.
The rotation in a red-black tree is an operation that changes the
tree structure locally while preserving the inorder traversal of
the tree.Two kinds of rotations,Right-Rrotate and Left-Rotate,
are defined originally in [2](Fig.
21).
and in Fig.21should not be 1or 0.In the case that sub-
tree or Left-Rotate
from .
If
,.They are similar to each other and one of them will be randomly picked and applied.W.l.o.g.,we present the details of Left-Rotate on
and has a left child.Case
3)has no left child.For Case 1,after left rotation of
module
and
and
.Thus,we
keep
468IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,VOL.22,NO.4,APRIL 2003
TABLE III
C OMPARISONS W ITH ECBL AN
D
E NHANCED Q -S
EQUENCES
TABLE IV
C OMPARISONS W ITH O THER R EPRESENTATIONS FOR N ONSLICING F
LOORPLAN
the directional bit of
module
by flipping one directional bit
of in is 0,we will
flip
from 0to 1.Case 4is similar to Case 3.Actually,
updating
on .One
of them will be randomly picked and applied.The algorithm of
right rotation is similar to that of left rotation.
In move M3and M4,
if
time.
If
time in practice.
Lemma 7:Starting from any TBS,we can generate any other
TBS with the
same
left rotations suffice
to transform any
arbitrary
left rotations by move M3.The binary tree -node TBT where right rotations by move M3.Therefore,at
most moves are sufficient to convert a TBS to any other arbitrary TBS with the
same
V .E XPERIMENTAL R ESULTS
All experiments are carried out on a PC with 1400MHz Intel Xeon Processor and 256Mb Memory.Simulated annealing as stated in Section IV is used to search for a good TBS.We test our algorithm using TBS with empty room insertion on six MCNC benchmarks.Besides,we also run the algorithm with empty room insertion disabled.In other words,only mo-saic floorplan can be generated.For each case,two objective functions are considered.The first is to minimize area only.The second is to minimize a weighted sum of area and wirelength.The weights are set such that the costs of area and wirelength are approximately equal.Because of the stochastic nature of simu-lated annealing,for each experiment,ten runs are performed and the result of the best run is reported.The results for area mini-mization is listed in Table I.The results for area and wirelength
minimization is listed in Table II.
As the results show,our floorplanner can produce
high-quality floorplans in a very short runtime.We also
notice that empty room insertion is very effective in reducing
the floorplan area.If empty room insertion is disabled,the
deadspace is worse for all but two cases.The deadspace is
YOUNG et al.:TBS:A NONREDUNDANT REPRESENTATION FOR GENERAL NONSLICING FLOORPLAN469 32.84%more on average.However,with empty room insertion,
the floorplanner is about40.8%slower.
In Table III,we compare our results with ECBL[14]and
the enhanced
-tree[9],
-tree and TCG are run
on Sun Sparc20(248MHz),and the scaling factors for their
speeds are0.613:1.Again,the runtimes reported in brackets in
Table IV are the scaled runtimes.We can see that TBS has again
out-performed the other representations in terms of runtimes,
while the packing quality in terms of area is similar.TBS is
thus a more desirable representation since its fast computation
allows us to handle very large circuits and to embed more
interconnect optimization issues in the floorplanning process.
R EFERENCES
[1]Y.C.Chang,Y.W.Chang,G.M.Wu,and S.W.Wu,“B
