Twin binary sequences a non-redundant representation for general non-slicing floorplan

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.

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

本文来源：https://www.bwwdw.com/article/gerq.html