我们毕业了IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,VOL.22,NO.4,APRIL2003457 Twin Binary Sequences:A Nonredundant Representation for General Nonslicing Floorplan
Evangeline F.Y.Young,Chris C.N.Chu,and Zion Cien Shen
Abstract—The efficiency and effectiveness of many floorplan-
ning methods depend very much on the representation of the geo-
metrical relationship between the modules.A good representation
can shorten the searching process so that more accurate estima-
tions on area and interconnect costs can be performed.Nonslicing
floorplan is the most general kind of floorplan that is commonly
used.Unfortunately,there is not yet any complete and nonredun-
dant topological representation for nonslicing structure.
In this paper,we propose the first representation of this kind.
Like some previous work(Zhou et al.2001),we have also made use
of mosaic floorplan as an intermediate step.However,instead of
including a more than sufficient number of extra dummy blocks
in the set of modules(that will increase the size of the solution
space significantly),our representation allows us to insert an exact
number of irreducible empty rooms to a mosaic floorplan such that
every nonslicing floorplan can be obtained uniquely from one and
only one mosaic floorplan.The size of the solution space is only
458IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,VOL.22,NO.4,APRIL
2003
(a)(b)
Fig.1.Structures that cannot be represented in a mosaic floorplan. mosaic floorplan,which is later enhanced in[15]by including empty rooms.It is also proved in[15]that the
number of empty
rooms required is
upper bounded
by
where
nodes
TBT Tree
Tree
Tree
2Together with the upper-bound result in[15],the tight bound can be
further
improved to2(n02
p
n).
Fig.2.An example of a
TBT.
Fig.
3.Building a TBT from a mosaic packing.
where Tree nodes,and
obtained as follows.
Starting
with an empty sequence,we perform an inorder traversal of
the
tree
obtained by
interchanging all the0s and
1s in
called TBS
to represent a mosaic floorplan with
is a
sequence of and
and
,we can obtain a pair of TBT
.An example
is shown in Fig.3.To construct
is reached,a node labeled
YOUNG et al.:TBS:A NONREDUNDANT REPRESENTATION FOR GENERAL NONSLICING FLOORPLAN
459Fig.4.Proof of Observation 1(if part).
can be built similarly by starting from the module at the upper
right corner and travel downward (right subtree)and to the left
(left subtree).Similarly,whenever the upper right corner of an-
other
module
until
all of the modules are visited.The paper [13]has shown that
the pair of trees built in this way must be twin binary to each
other,and there is a one-to-one mapping between mosaic floor-
plan and TBT.We observed that the inorder traversal of the two
binary trees constructed by the above method must be the same.
Let us look at the example in Fig.3.We can see that the inorder
traversals of
both
;and 2)their inorder traversals are the same.
Proof:(if part )This part can be proved by induction on
the number of modules in the floorplan.The base case occurs
when there is only one module in the floorplan and conditions
(1)and (2)follow trivially.Assume that these conditions are true
when there are not more
than modules in the floorplan.
Consider a
floorplan modules.Let the pair of bi-
nary trees constructed
from
at the upper left corner
of
as shown in Fig.4.In each case,
let
by moving the thickened slice-
line in the direction shown.Let be the pair of binary
trees constructed
from modules,satisfy conditions (1)and (2)
according to the hypothesis,
i.e.,,and their in-
order traversals are the same.From Fig.4,we can see that in
case (a)(b)Fig.5.Proof of Observation 1(only if part).(a)and
(c),,and the inorder traversal of is the same as that obtained by
appending .Similarly,in case (b)and
(d),
,in front of the inorder traversal of .
Therefore,.Consider a pair of trees
(,and
labelings ,and the bit
sequences
from will correspond to a
460IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,VOL.22,NO.4,APRIL
2003
Fig.6.Example of an extended tree.
pair of trees with inorder
traversal ,and label-
ings
If we extend a tree
.An example of an extended tree is shown in
Fig.6.Notice that the inorder traversal of the extended tree
of
and
is the labeling of
and a
labeling and
and
and
,respectively,such that the bit
in
th module
in
and
is the root of a tree,its directional
bit will be assigned to zero.For a binary
tree
and its directional bit
sequence
to correspond to a
binary tree.
Lemma 1:For any binary tree,its labeling
sequence
must satisfy conditions (1)and (2).
Proof:Given a binary
tree
Lemma 2:For any binary
sequences
bits
and and the
directional bit sequence of
.Proof:The uniqueness can be proved by induction on the number of nodes.The claim is trivially true when there is only
one node,i.e.,
when
.Assume that the claim holds when the number of nodes is at
most
,we can reduce the
problem to the case
with
in front
of at the
end
of
and .This is a place for a leaf node where the leaf is either a left
(when
to denote the set of all such locations,
i.e.,
by
replacing
by
deleting
.Notice that the first bit
of
.According to the induction hypothesis,there
exists a unique binary tree
for the original pair of binary
sequences
by
inserting a leaf to the position of
bit
for
where
and
,according to Lemma 2,there exists a unique binary tree
such that the
YOUNG et al.:TBS:A NONREDUNDANT REPRESENTATION FOR GENERAL NONSLICING FLOORPLAN
461
(a)(b)(c)(d)(e)
Fig.7.
Simple example of constructing a floorplan from its TBS.
labeling sequence of
is and the directional bit se-quence of
is .
Since ,are twin binary.We can then label their nodes according to the in-order
traversal
.Therefore,the mapping between TBS and TBT
is
one-to-one.
C.From TBS to Floorplan
1)Algorithm for Floorplan Realization:In order to realize a
floorplan from its TBS representation efficiently,we devised an algorithm that only needs to scan the sequences once from right to left to construct the packing.We will construct the floorplan by inserting the modules one after another following
the
sequence,i.e.,
module
is
,we will look at the
sequence
into
)to the right as shown
in Fig.7(b)and delete
bit
is
,we will look at the
sequence
,
i.e.,
from above
pushing
)down as shown in Fig.7(c)and delete
bit .
These steps repeat until the whole
sequence Output:
Packing
.
2.
Initially,we have only
module
.3.For
down to
:
4.
If
s.t.
and
of
modules
bit not deleted yet)will be
lying on the left boundary
of
from the left,pushing
those modules
in
.
8.
If :9.
Find the
smallest
and
of
modules
.Add
module from above,pushing those
modules
in .
End
2)Proof of Correctness:The correctness of the above algo-rithm on floorplan realization can be proved by the following lemma and theorem.
Lemma 3:In the for-loop of the above algorithm,when we
scan to a
point
,the corresponding
node
and all the nodes in
rooted
at will have
its
bit deleted.
Proof:W.l.o.g.,we only prove the case
when
.The case
when
can be proved similarly.The proof can be done by induction
on
,must have a right child in
be the right subtree
of in must have been scanned immediately
before
.In
this base case,there is only one
node
and
.Consider the case when
.
If ,
similarly,
must have a right
child be the subtree of
must have been scanned immediately
before .
Let them
be
is the size
of .)If there is any
node
where
,
.According to
462IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,VOL.22,NO.4,APRIL
2003
(a)
(b)
Fig.9.Proof of Theorem 3.
the inductive hypothesis,when we scan
to
)
and
at that
moment.Since the nodes in the right subtree
of
bits up to and
including ,any
node
will
have
its
mod-ules in the floorplan for
some
.The
case
when
can be proved similarly.
