Heuristic algorithms for determining feasible routing order in non sliceable floorplans

I

_"~

1

i

2

:.::-

J

,;

,~

I I

I

~ 'J j

I

5

~--

7 (~i

+- ^{~(a )}

'10

'12

I~

. i

~

(b)

"

.

Cliquf~~i : {'1,4},{Z~,4},{2,5},{3,5},.{4,6},{lI,n, ~~j,n,{5,Ln,

{b,9},{7,9}, .:7,10},{S,'10},{9,'1'1},{9,12},<10,12},{10,'13}

Mi!! Clique c,)ver- ^: {{'1,4},{2,5},{3,~5},{/I,t.J},{5,7},{8,'10},

{9,'11},{9,'1?>,{10,'13}}

Fig 2.9 A ion,,;) cycle remains after t-el""vin'J t-IF\)S obtained

ill Heut-istic '1.

18 I---t

I I

-1, L.----+

b

(

^,

-+-- -

9

'1 '1

"1";'---t

:to

. ¹³

~

.

iO

,

^/-

9

"

-1r3

("'---'

f.~ig 2.10

c,j

1()

1

^'7,J

b

10

---

11

-' ...~

17

~~

".

13

rI

11

11

CHAPTER

4

CONCLUSIONS

There are three known

methods to

determine

a

feasible channel routing order as given in CPV79J,CDAK85J and CGW88J.

The

MFVS solution can be used in all the three methods to reduce

the

number of iterations.

Reserved Channels:

In this method CPV79J, the straight ^channels corresponding to the vertices in the MFVS solution

are

reserved

(i.e their

width is estimated in advance with

some

allowance).

Since the

effort is to minimiz~ the number of such channels, the number

of

required iterations

will be reduced without

_affecting

the

completion of successful channel routing.

L-channels :

Feasible routing order with L-~hannels CDAKBSJ can al S.o be extracted from the M':VS. For each vertex in

the MFVS

_solution, the channels are "red2fined by splitting a T-junction opposite: to it. For the channel graph in Fig 4.1(b)

by

usin'J

the

_L-sha:ped channel we ';Jetthe nl')dified channel graph as shown in Fig 4.1(c).

I The advantage of USi'lg L-channels is that it can be e:<panded

or

contracted for the purpose of completion of routing in it without r~routing other rout2d channels. Since routing of L-channels

is

more complex than straight channels, one tries to minimize their

39