RAISE: A detailed routing algorithm for field-programmable gate arrays

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