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

RAISE: A Detailed Routing Algorithm for Field-Programmable Gate Arrays V. Baena-Lecuyer, M. A. Aguirre, A. Torralba, L. G. Franquelo and J. Faura* Dpto. de Ingenier´ıaElectr´ onica EscuelaSuperior de Ingenieros, Avda. ReinaMercedes s/n, Sevilla–41012(SPAIN) Tel.: +34(9)5 45568 57 FAX: +34(9)5 45568 49 e–mail: [email protected] *SIDSA C/ IsaacNewton 1, ParqueTecnol´ ogicode Madrid, Tres Cantos, Madrid–28760 Tel.: +34(9)1 80350 52 e–mail: [email protected] Conference Topic: FPGA Design and Applications Abstract— This paper describes a new detailed routing algorithm, specifficallydesignedforthosetypesofarchitecturesthatarefoundon the most recent generationsof Field-ProgrammableGate Arrays (FPGAs). The algorithm, calledRAISE, can be appliedto a broad range of optimizationsproblems and has been used for detailedrouting of symmetricalFPGAs, whose routing architectureconsistsof rows and columnsof logic cellsinterconnectedby routing channels. RAISE (Router using AadaptIve Simulated Evolution) searches not only for a possible solution, but tries to find the one with minimum delay. Excelentroutingresultshavebeenobtainedoverasetofseveral benchmark circuits getting solutions close to the minimum number of tracks. I. INTRODUCTION In the last years, the use of Field-Programmable Gate Arrays (FPGAs) has been widely accepted as an attractive means of implementing digital circuits. There is a wide range of comercial FPGAs, butoneofthemostimportanttypesisthesymmetrical FPGA,which consistsofrowsand columnsof logic blocks with horizontal routing channels between rows and vertical routing channel between columns. This type of FPGAs wasfirst introduced by Xilinx in 1986, but currently it can be found in some of the Altera and Quicklogic families. Symmetrical FPGAs can reach very high logic capacities; for this reason, a key problem in the design of this kind of FPGAs is the structure of their routing channels. The use of short segments improve chip area (less segment length is wastedusing short segments) but to provide long connections, the interconnection of short segments via programmable routing switches is required, reducing speed performance. On the other hand, the usesoflong segmentswasteschip area butimproves speed performance (less segments are required to make long connections passing through only a few switches). This tradeoff forces the design of complex routing channels, with different lenght segments, which requires sofisticated Computer Aided Design (CAD) Tools. Five stages are usually involved in mapping a circuit: design entry, logic optimization technology mapping, placement and routing. The last one is madeintwostep: globalroutinganddetailedrouting. This paper presents RAISE, a new detailed router adapted for generic symmetrical FPGAs. II. RAISE: ROUTER USING ADAPTIVE SIMULATED EVOLUTION RAISE is based on SILK [3], a simulated evolution program for channel routing. Before running RAISE, for each point to point net, a set of possible paths is generated (for example, using the technique called Coarse Graph Expansion (CGE) [1] [2]). RAISE takes this set and searches for a path subset that make possible the routing of all the nets, while minimizing the delays. Theese steps are carried out by RAISE: 1. Initial Routing. 2. Rip-Up and Rerouting. 3. Postoptimization. A. Initial Routing The algorithm, of statistical nature, needs a seed tostartthe iterative process. This seedor solution, does not need to be feasible, that is, it can have conflicts, which have to be solved in the following steps. Our detailed router takes for each point to pointnetthepathwithminimumdelay. The delay can be calculated with the RC-Tree algorithm of [4]. 1 B. Rip-Up and Rerouting The rip-up and rerouter solves the conflicts generated in the initial routing. To this purpose, RAISE uses the Simulated Evolution technique. Basically, acostisgenerated,foreachpointtopoint net using a special function cost, which accounts forthepathsdelayandtheconflictwithothernets; then this cost is scaled in the range [0 : 1 ; 0 : 9]; for eachpointtopointnet, arandomnumberbetween 0 and 1 is generated, if this number is lessthan the scaledcostoftheroutedpath,thepathisremoved. After end of this process, there will be a set of routed point to point nets and another set of nonroutedpointtopointnet. Next,foreachmultipoint net, in a random order, all the non-routed point to point nets are routed, choosing the path with minimum cost. This process is repeated until a solution with no conflicts is obtained or until a maximun number of iterations is reached. Using a random number generator to select the non-routed nets, allows the algorithm to exit from localminimums. Notethatintheselectionprocess, the nets with a high costs have a high probability of being removed. However randomly removing somegoodnetsalsohelpstoavoid gettingstucked at a local minimum. Akey pointin suchalgorithmsisthefunctioncost. This function should contain at least a delay and a conflict term. But other terms can be added to improve the convergence: From the problem definition, we know that point to points nets from the same multipoint net can sharesegments. To improvechip area, thenumber ofsharedsegmentsinapointtopointnetshouldbe maximized, asthisweconsumelessFPGA routing resources. Besides, it would be desirable to get out some advantages of each iteration, i.e., if for each iteration weknowifthenetsarevalidornot,wecould learn not to do the sameserrors we made in previous iterations. This is included in the following function cost: cost =   ( num shar ed wires ) +   ( histor y cost ) +   ( path del ay min path del ay ) +   ( num non shar ed wires min num non shar ed wires ) each term is explained as follow:  num shared: numberofmultipointnetsshared segments.  history cost: demand of each segment in previous iterations.  path delay: self explanatory.  min path delay: minimumpathdelayoftheset of possible paths for this point to point net.  num non shared wires: number of non shared segments between this point to point net and the others of the same multipoint net.  min num non shared wires: minimun number of non shared segmentsbetween this point to point net and the others of the same multipoint net. Thehistory costtermcanbecalculatedeasilyifwe remember wich segmentswere shared in previous iterations. In our case, it is calculated as follow: H istC ost ( Wi; K ) = 0 : 5  H istC ost ( W i ;K , 1 ) + N etsU sing W ( W i ;K ) where NetsUsingW is the number of multipoint net that use wire W i , and K is the number the actualiteration. Theminimumnumberofnotshared segments between one point to point net and the others of the same multipoint net, can be calculated from the netlist of the global router supposing eachcorner ofthenetcan bereached withonly 1 segment. The  ,  ,  and  parametershave tobewell tuned toreducte thenumberofiterationsandtogetafast convergence. LBLOCK LBLOCK LBLOCK LBLOCK LBLOCK LBLOCK LBLOCK LBLOCK LBLOCK SBLOCK SBLOCK SBLOCK SBLOCK Figure 1: FPGAstructure C. Postoptimization This phase is reached when a feasible solutionhas been formed. Then, for each pointto pointnet in a random order, the paths with the least delay from thosethatdonotconflict withpresentsolution,are selected. This phase is repeated until no a change is accepted in an iteration. 2 Circuits Channel Density RAISE SEGA Area SEGA Speed Sega Anneal 9symml 9 9 11 12 11 term1 10 10 11 11 13 C499 10 12 12 15 12 C1355 11 12 12 14 13 vda 14 15 15 15 16 Table 1: Minimum numberof tracks per channel required for asuccessfully routing W RAISE SEGA Area Av. Delay Max. Delay Exec. time (s) Av. Delay Max. Delay Exec. time (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: Average andmaximumdelays generated by RAISE and SEGA Area for 9symml anddifferent channel density III. RESULTS To test the performances of RAISE, different routing solutions have been obtained with a set of benchmark circuits. The FPGA structure we used can be seen in figure 1, the C blocks have a switch for each segment, i.e. in SEGA terminology, fc=W; the routing structure of an S block is shown in figure 2: all segmentsexcepted the first of each channel (segment 0 in the picture) have a connection patternlikesegment1, then fs > 3. Forsimplicity, the vertical and horizontal routing channels have only one track group with W segments, offset 1, and lenght 3. As well we set  parameter to 2.0 ,  parameter to 0.5,  to 1.0 and  to 1.0. 01 Figure 2: S block routing structure We can see the results in table 1 for a set of benchmark circuits. For this FPGA architecture, the number of wiresegments in each routing channel, neededtoroutethecircuitsisveryclosetotheminFigure 3: 9symml RAISE routing solution with nine track per channel imum number told by the global router. Note that RAISE reaches solutions that other routers can’t find. In figure 3 we show a RAISE solution for the 9symml circuit with nine track per channel. From table 2, we see the maximum and average path delay for different number of wiresegments per channel, for the 9symml circuit. We can see that RAISE normally obtains better solutions than SEGAArearouterandcanbeusedtofindsolutions in dificult circuits with hugely saturatedchannels. The price tobe paid for this betterperformances is computetime cost. Like other statistical based optimizationprograms, RAISE take a time searching for new solutions, as can be seen in the execution time column of table 2. 3 IV. CONCLUSIONS This paper has presented RAISE, a simulated evolution router for FPGAs. RAISE uses a statistical technique to explore the solutions space. It has been shown that RAISE normally obtains better solutionsthandifferentversionsofSEGA.Furthermore it find solutionsthat other routers can·t find. V. ACKNOWLEDGMENTS The authors would like to acknowledge financial support by the European Union through the ESPRIT project FIPSOC and by CICYT through the TIC86-0860 project. REFERENCES [1] Stephen Dean Brown, “Routing Algorithms and Architectures for Field-Programmable Gate Arrays”, Thesis, Department of Electrical Engineering , University of Toronto, Canada. January 1992. [2] G. Lemieux and S. Brown, “A Detailed Router forAllocatingWireSegmentsinFPGAs”, ACM Physical Design Workshop , Lake Arrowhead, California, pp. 215-226. April 1993. [3] Youn-Long Lin, Yu-Chin Hsu, and FurShing Tsai, “SILK: A Simulated Evolution Router”, IEEE Transactions on ComputerAided Design , Vol. 8. NO. 10. October 1989. [4] M. Khellah, S. Brown, and Z. Vranesic, “Modelling Routing Delays in SRAM-Based FPGAs”, Proc. 1993 CCVLSI , Banff, Canada, pp. 6B.13-6B.18, Nov.1993. 4