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

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

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新实用文档Twin binary sequences a non-redundant representation for general non-slicing floorplan(2)全文阅读和word下载服务。