RAISE: A De ailed Rou ing Algo i hm o
Field-P og ammable Ga e A ays
V. Baena-Lecuye , M. A. Agui e, A. To alba, L. G. F anquelo and J. Fau a*
Dp o. de Ingenie ´ıaElec ´
onica
EscuelaSupe io de Ingenie os,
A da. ReinaMe cedes s/n, Se illa–41012(SPAIN)
Tel.: +34(9)5 45568 57
FAX: +34(9)5 45568 49
e–mail: [email p o ec ed]
*SIDSA
C/ IsaacNew on 1, Pa queTecnol´
ogicode Mad id, T es Can os, Mad id–28760
Tel.: +34(9)1 80350 52
e–mail: [email p o ec ed]
Con e ence Topic: FPGA Design and Applica ions
Abs ac — This pape desc ibes a new de ailed ou ing algo i hm,
speci icallydesigned o hose ypeso a chi ec u es ha a e oundon
he mos ecen gene a ionso Field-P og ammableGa e A ays (FP-
GAs). The algo i hm, calledRAISE, can be applied o a b oad ange
o op imiza ionsp oblems and has been used o de ailed ou ing o
symme icalFPGAs, whose ou ing a chi ec u econsis so ows and
columnso logic cellsin e connec edby ou ing channels.
RAISE (Rou e using Aadap I e Simula ed E olu ion) sea ches no
only o a possible solu ion, bu ies o ind he one wi h minimum
delay. Excelen ou ing esul sha ebeenob ainedo e ase o se e al
benchma k ci cui s ge ing solu ions close o he minimum numbe
o acks.
I. INTRODUCTION
In he las yea s, he use o Field-P og ammable
Ga e A ays (FPGAs) has been widely accep ed as
an a ac i e means o implemen ing digi al ci -
cui s. The e is a wide ange o come cial FPGAs,
bu oneo hemos impo an ypesis hesymme -
ical FPGA,which consis so owsand columnso
logic blocks wi h ho izon al ou ing channels be-
ween ows and e ical ou ing channel be ween
columns. This ype o FPGAs was i s in oduced
by Xilinx in 1986, bu cu en ly i can be ound in
some o he Al e a and Quicklogic amilies.
Symme ical FPGAs can each e y high logic ca-
paci ies; o his eason, a key p oblem in he de-
sign o his kind o FPGAs is he s uc u e o hei
ou ing channels. The use o sho segmen s im-
p o e chip a ea (less segmen leng h is was edus-
ing sho segmen s) bu o p o ide long connec-
ions, he in e connec ion o sho segmen s ia
p og ammable ou ing swi ches is equi ed, e-
ducing speed pe o mance. On he o he hand,
he useso long segmen swas eschip a ea bu im-
p o es speed pe o mance (less segmen s a e e-
qui ed o make long connec ions passing h ough
only a ew swi ches).
This adeo o ces he design o complex ou -
ing channels, wi h di e en lengh segmen s,
which equi es so is ica ed Compu e Aided De-
sign (CAD) Tools.
Fi e s ages a e usually in ol ed in mapping a ci -
cui : design en y, logic op imiza ion echnology
mapping, placemen and ou ing. The las one is
madein wos ep: global ou ingandde ailed ou -
ing. This pape p esen s RAISE, a new de ailed
ou e adap ed o gene ic symme ical FPGAs.
II. RAISE: ROUTER USING ADAPTIVE SIMULATED EVOLU-
TION
RAISE is based on SILK [3], a simula ed e olu-
ion p og am o channel ou ing. Be o e unning
RAISE, o each poin o poin ne , a se o pos-
sible pa hs is gene a ed ( o example, using he
echnique called Coa se G aph Expansion (CGE)
[1] [2]). RAISE akes his se and sea ches o a
pa h subse ha make possible he ou ing o all
he ne s, while minimizing he delays.
Theese s eps a e ca ied ou by RAISE:
1. Ini ial Rou ing.
2. Rip-Up and Re ou ing.
3. Pos op imiza ion.
A. Ini ial Rou ing
The algo i hm, o s a is ical na u e, needs a seed
os a he i e a i e p ocess. This seedo solu ion,
does no need o be easible, ha is, i can ha e
con lic s, which ha e o be sol ed in he ollowing
s eps. Ou de ailed ou e akes o each poin o
poin ne hepa hwi hminimumdelay. The delay
can be calcula ed wi h he RC-T ee algo i hm o
[4].
1
B. Rip-Up and Re ou ing
The ip-up and e ou e sol es he con lic s gene -
a ed in he ini ial ou ing. To his pu pose, RAISE
uses he Simula ed E olu ion echnique.
Basically, acos isgene a ed, o eachpoin opoin
ne using a special unc ion cos , which accoun s
o hepa hsdelayand hecon lic wi ho he ne s;
hen his cos is scaled in he ange [0
:
1
;
0
:
9]; o
eachpoin opoin ne , a andomnumbe be ween
0 and 1 is gene a ed, i his numbe is less han he
scaledcos o he ou edpa h, hepa his emo ed.
A e end o his p ocess, he e will be a se o
ou ed poin o poin ne s and ano he se o non-
ou edpoin opoin ne . Nex , o eachmul ipoin
ne , in a andom o de , all he non- ou ed poin
o poin ne s a e ou ed, choosing he pa h wi h
minimum cos . This p ocess is epea ed un il a
solu ion wi h no con lic s is ob ained o un il a
maximun numbe o i e a ions is eached.
Using a andom numbe gene a o o selec he
non- ou ed ne s, allows he algo i hm o exi om
localminimums. No e ha in heselec ionp ocess,
he ne s wi h a high cos s ha e a high p obabili y
o being emo ed. Howe e andomly emo ing
somegoodne salsohelps oa oid ge ings ucked
a a local minimum.
Akey poin in suchalgo i hmsis he unc ioncos .
This unc ion should con ain a leas a delay and
a con lic e m. Bu o he e ms can be added o
imp o e he con e gence:
F om he p oblem de ini ion, we know ha poin
o poin s ne s om he same mul ipoin ne can
sha esegmen s. To imp o echip a ea, henumbe
o sha edsegmen sinapoin opoin ne shouldbe
maximized, as hisweconsumelessFPGA ou ing
esou ces.
Besides, i would be desi able o ge ou some ad-
an ages o each i e a ion, i.e., i o each i e a ion
weknowi hene sa e alido no ,wecould lea n
no o do he samese o s we made in p e ious i -
e a ions.
This is included in he ollowing unc ion cos :
cos
=


(
num sha ed wi es
)
+


(
his o y cos
)
+


(
pa h del ay
min pa h del ay
)
+


(
num non sha ed wi es
min num non sha ed wi es
)
each e m is explained as ollow:

num sha ed: numbe o mul ipoin ne ssha ed
segmen s.

his o y cos : demand o each segmen in p e-
ious i e a ions.

pa h delay: sel explana o y.

min pa h delay: minimumpa hdelayo hese
o possible pa hs o his poin o poin ne .

num non sha ed wi es: numbe o non sha ed
segmen s be ween his poin o poin ne and
he o he s o he same mul ipoin ne .

min num non sha ed wi es: minimun numbe
o non sha ed segmen sbe ween his poin o
poin ne and he o he s o he same mul i-
poin ne .
Thehis o y cos e mcanbecalcula edeasilyi we
emembe wich segmen swe e sha ed in p e ious
i e a ions. In ou case, i is calcula ed as ollow:
H is C os
(
Wi; K
) =
0
:
5

H is C os
(
W
i
;K
,
1
)
+
N e sU sing W
(
W
i
;K
)
whe e Ne sUsingW is he numbe o mul ipoin
ne ha use wi e
W
i
, and K is he numbe he ac-
uali e a ion. Theminimumnumbe o no sha ed
segmen s be ween one poin o poin ne and he
o he s o he same mul ipoin ne , can be calcu-
la ed om he ne lis o he global ou e suppos-
ing eachco ne o hene can be eached wi honly
1 segmen .
The

,

,

and

pa ame e sha e obewell uned
o educ e henumbe o i e a ionsand oge a as
con e gence.
LBLOCK LBLOCK
LBLOCK LBLOCK LBLOCK
LBLOCK LBLOCK LBLOCK
LBLOCK
SBLOCK SBLOCK
SBLOCK SBLOCK
Figu e 1: FPGAs uc u e
C. Pos op imiza ion
This phase is eached when a easible solu ionhas
been o med. Then, o each poin o poin ne in a
andom o de , he pa hs wi h he leas delay om
hose ha dono con lic wi hp esen solu ion,a e
selec ed. This phase is epea ed un il no a change
is accep ed in an i e a ion.
2
Ci cui s Channel Densi y RAISE SEGA A ea SEGA Speed Sega Anneal
9symml 9 9 11 12 11
e m1 10 10 11 11 13
C499 10 12 12 15 12
C1355 11 12 12 14 13
da 14 15 15 15 16
Table 1: Minimum numbe o acks pe channel equi ed o asuccess ully ou ing
W RAISE SEGA A ea
A . Delay Max. Delay Exec. ime (s) A . Delay Max. Delay Exec. ime (s)
9 3.599 32.414 159.80 - - -
10 3.837 35.316 4.80 - - -
11 3.863 37.063 3.07 3.949 32.571 0.53
12 3.895 35.167 2.09 4.350 36.549 0.64
13 4.120 39.930 1.73 4.384 45.569 0.71
14 4.310 40.658 1.86 4.563 45.771 1.03
15 4.349 41.386 1.90 4.363 37.691 1.14
Table 2: A e age andmaximumdelays gene a ed by RAISE and SEGA A ea o 9symml anddi e en channel densi y
III. RESULTS
To es he pe o mances o RAISE, di e en ou -
ing solu ions ha e been ob ained wi h a se o
benchma k ci cui s. The FPGA s uc u e we used
can be seen in igu e 1, he C blocks ha e a swi ch
o each segmen , i.e. in SEGA e minology, c=W;
he ou ing s uc u e o an S block is shown in ig-
u e 2: all segmen sexcep ed he i s o each chan-
nel (segmen 0 in he pic u e) ha e a connec ion
pa e nlikesegmen 1, hen
s >
3. Fo simplici y,
he e ical and ho izon al ou ing channels ha e
only one ack g oup wi h W segmen s, o se 1,
and lengh 3.
As well we se

pa ame e o 2.0 ,

pa ame e o
0.5,

o 1.0 and

o 1.0.
01
Figu e 2: S block ou ing s uc u e
We can see he esul s in able 1 o a se o bench-
ma k ci cui s. Fo his FPGA a chi ec u e, he
numbe o wi esegmen s in each ou ing channel,
needed o ou e heci cui sis e yclose o hemin-
Figu e 3: 9symml RAISE ou ing solu ion wi h nine ack pe channel
imum numbe old by he global ou e . No e ha
RAISE eaches solu ions ha o he ou e s can’
ind. In igu e 3 we show a RAISE solu ion o
he 9symml ci cui wi h nine ack pe channel.
F om able 2, we see he maximum and a e age
pa h delay o di e en numbe o wi esegmen s
pe channel, o he 9symml ci cui . We can see
ha RAISE no mally ob ains be e solu ions han
SEGAA ea ou e andcanbeused o indsolu ions
in di icul ci cui s wi h hugely sa u a edchannels.
The p ice obe paid o his be e pe o mances is
compu e ime cos . Like o he s a is ical based op-
imiza ionp og ams, RAISE ake a ime sea ching
o new solu ions, as can be seen in he execu ion
ime column o able 2.
3
IV. CONCLUSIONS
This pape has p esen ed RAISE, a simula ed e o-
lu ion ou e o FPGAs. RAISE uses a s a is ical
echnique o explo e he solu ions space. I has
been shown ha RAISE no mally ob ains be e
solu ions handi e en e sionso SEGA.Fu he -
mo e i ind solu ions ha o he ou e s can· ind.
V. ACKNOWLEDGMENTS
The au ho s would like o acknowledge inancial
suppo by he Eu opean Union h ough he ES-
PRIT p ojec FIPSOC and by CICYT h ough he
TIC86-0860 p ojec .
REFERENCES
[1] S ephen Dean B own, “Rou ing Algo i hms
and A chi ec u es o Field-P og ammable
Ga e A ays”,
Thesis, Depa men o Elec ical
Enginee ing
, Uni e si y o To on o, Canada.
Janua y 1992.
[2] G. Lemieux and S. B own, “A De ailed Rou e
o Alloca ingWi eSegmen sinFPGAs”,
ACM
Physical Design Wo kshop
, Lake A owhead,
Cali o nia, pp. 215-226. Ap il 1993.
[3] Youn-Long Lin, Yu-Chin Hsu, and Fu -
Shing Tsai, “SILK: A Simula ed E olu-
ion Rou e ”,
IEEE T ansac ions on Compu e -
Aided Design
, Vol. 8. NO. 10. Oc obe 1989.
[4] M. Khellah, S. B own, and Z. V anesic, “Mod-
elling Rou ing Delays in SRAM-Based FP-
GAs”,
P oc. 1993 CCVLSI
, Ban , Canada, pp.
6B.13-6B.18, No .1993.
4