La Loi de Rent et ses Applications au Placement/Routage Florent Flament, Sumanta Chaudhuri, Sylvain Guilley GET / Tel´ ecom´ Paris, CNRS – LTCI (UMR 5141) ´Ecole Nationale Superieure´ des Tel´ ecommunications´ 46 rue Barrault, 75634 PARIS Cedex 13, FRANCE E mail:{fflament,chaudhur,guilley}@enst.fr Resum´ e´ R´egion 1 R´egion 2 R´egion 3 Cet article presente´ la loi de Rent en tant qu’outil theorique´ d’analyse et de prediction´ pour le place ment/routage des portes logiques dans un ASIC ou un FPGA. Nous presentons´ une demonstr´ ation analytique de cette loi dans un cas particulier, afin de mieux compren logt dre la signification des differ´ entes zones qui apparais 0 log(B)sent dans la courbe de Rent. Les limites fondamentales du placement/routage d’un circuit dans un plan bidimen sionnel sont examinees.´ Nous etablissons´ ensuite une re FIG. 1. Schema´ de Rent pour une netlist typique. lation entre cette approche analytique et l’approche du recuit simule´ (couramment utilise´ dans la pratique), suivi 2. Definitions´par une application dans le cadre du placement/routage d’une netlist dans un FPGA. Hypergraphe : Un hypergraphe G est defini´ par un . couple G = (X,U) de deux ensembles X et U, ou` X est un ensemble(x ,x ,x ,...) de sommets etU est un1 2 3 1. Introduction ensemble d’hyperarcs U P(X), ou` P(X) represente´ l’ensemble des partitions deX. Autrement dit un hyper La loi de Rent est issue des travaux de E.F Rent au graphe est un graphe dont les arcs peuvent etreˆ ...
La Loi de Rent et ses Applications au Placement/Routage
Florent Flament, Sumanta Chaudhuri, Sylvain Guilley GET/Te´l´ecomParis,CNRS–LTCI(UMR5141) ´ EcoleNationaleSup´erieuredesTe´le´communications 46 rue Barrault, 75634 PARIS Cedex 13, FRANCE
Email:{ } fflament,chaudhur,guilley @enst.fr
Re´sum´e Cet article pre´sente la loi de Rent en tant qu’outil the´orique d’analyse et de pre´diction pour le place ment/routage des portes logiques dans un ASIC ou un FPGA.Nouspr´esentonsuned´emonstrationanalytiquede cette loi dans un cas particulier, afin de mieux compren drelasignificationdesdiff´erenteszonesquiapparais sent dans la courbe de Rent. Les limites fondamentales du placement/routage d’un circuit dans un plan bidimen sionnelsontexamin´ees.Nous´etablissonsensuiteunereFIG.1. Sche´ma de Rent pour une netlist typique. lation entre cette approche analytique et l’approche du recuit simule´ (couramment utilise´ dans la pratique), suivi 2.D´efinitions par une application dans le cadre du placement/routage d’une netlist dans un FPGA. Hypergraphe: Un hypergrapheGaripfin´edtseun . coupleG= (X, U)de deux ensemblesXetU, o`uX est un ensemble(x1, x2, x3, . . .)de sommets etUest un 1. Introduction ensemble d’hyperarcsU⊆P(X), o`uP(X)´rseneetrep l’ensemble des partitions deX. Autrement dit un hyper LaloideRentestissuedestravauxdeE.FRentaugrapheestungraphedontlesarcspeuventˆetreconnecte´s coursdesanne´essoixante.Cestravauxontdonn´elieu`aa`plusdedeuxsommets.Laplupartdespropri´ete´sdes une relation remarquable entre le nombre de terminaux etgraphes restent valables pour les hypergraphes. Dans le lenombredeportesdansuncircuitint´egr´e.Publie´pourcadredecetarticle,chaquenetlistestmode´lis´eeparun lapremi`erefoisparLandmanetRusso[1],laloideRenthypergraphedontlessommetssontdesporteslogiques s’exprime comme :et les connexions des hyperarcs. Cette mode´lisation est la mieux approprie´e pour les circuits e´lectriques, car dans p T=tB ,0≤p≤1,ee´tcennocerteunc,ahuqpeneteiltsquepeutˆo)r1t(e:luo`goi a` plusieurs portes logiques (notion desortance, ou de –Tmorbdetereimanxu(portsd’entr´eeoeduneltsefanout). sortie),Bipartition minimaleSoit le grapheGdont les som –Best le nombre de cellules (portes logiques) dansmetsVsont relie´s par les arcsE, on noteG= (V, E). une netlist (re´seau de cellules),La bipartition minimale deGest la partition deVenU –test le coefficient de Rent,i.e.le nombre moyen deetWdisjoints, tels que|U|=|W|, et quee(U, W), le terminaux par porte,nombre d’arcs de{(u, w)∈E|u∈wU et∈W}soit –pest l’exposant de Rent,i.e.une mesure de la comminimal [5]. plexit´edure´seaud’interconnexion,obtenuparbiDn(ioapentitr´rgeu’deDi)adreeLpe´unegdr’:ti partitionr´ecursivedugraphedelanetlist.tionestde´finiparlenombred’arcsentrantsetsortants Lesch´ematypiquedeRentcontientlestroisr´egionsdecettepartition.Parexemple,pourunepartitionquine de´critesdanslaFig.1.Cestroisr´egionspr´esententcontientqu’unseulsommet,ledegre´delapartitionest trois couples(t, p)moemdesuge´ralduedeccadrnslet.Daga´eaqChs.ntre´effdimocesnoige´reu,eratelcit porte comme un ensemble autosemblable par variationnous notonsDinoostbnepsraititsleuesapr`egrdede´ele `eme delahi´erarchie(a`l’instardesensemblesfractals). Laipartitionnement re´cursif. loi de Rent a trouve´ des applications concre`tes, commeCoupe minimum (Ci): La coupe minimum d’un hy l’estimationdelalongueurmoyennedesinterconnexionspergrapheestd´efinieparlenombred’arcsentrelespar d’unenetlist[2,3]etl’e´valuationdesarchitecturesdestitionsobtenuesapr`esbipartitionminimaledel’hyper FPGAs [4].graphe. Dans le cadre de cet article, nous notonsCila
FIG.2. Partitionnement d’un graphe.
e`me valeur de la coupe minimum obtenue apre`s leiparti tionnementr´ecursif. Localit´ehpargnu’fie´dtseearepniLalo:t´edcali l’´equationsuivante: .2Ci Li=,(2) Di ou`Ciest la valeur de la coupe minimum du graphe et Diaueel´soniioitrtenr´e.ndegstsoeenapelu,expmaPer localite´ e´gale a` l’infini (+∞) carDivaut 0. Dans le cas d’unhypergraphe,lalocalit´esede´finitcommelerapport apr`esbipartition,dunombredeterminauxconnect´es`a desterminauxdelapartitionduale,parledegr´edel’hy pergraphe.
3. Parame`tres de Rent et Localite´
La bipartition d’un hypergrapheG0(respectivement 0 Gisnoitit)´greleen`exparsdeuG1(resp.Gi+1) etG1 0 (resp.Gi+1), comme de´crit dans la figure 2. Afin de fa ciliter les calculs, nous conside´rons que notre netlist peut eˆtremod´elise´eparungraphe,c’esta`direquechaque noeuddelanetlistestconnect´e`adeuxetseulementdeux terminaux.Onpeutend´eduirelarelationsuivanteentre D0(resp.Di),D1(resp.Di+1) etC0(resp.Ci) : D0= 2D1−2C0,(3) 0 ou`D1est la moyenne deD1etD1. En poursuivant nospartitionnementsdemani`erere´cursive,jusqu’a`l’ob tention de partitions indivisibles (i.e. les partitions sont form´eesd’uneuniquecellule),rangquenousnommons Kosuonetbn,atqunsioslon´ees:snaetusvi D0= 2D1−2C0 2D1= 4D2−4C1 4D2= 8D3−8C2 . K−1K K 2DK−1= 2DK−2CK−1. ` Apartirdes´equationspr´ece´dentes,onpeut´ecrire: K K 2DK−D0= 2C1+ 4C2+ 8C3. . .+ 2CK−1.(4) LiDi Enrempla¸cantlesCil’e´quation (3), onpar dans 2 obtient : D0= 2D1−L×D0,(5)
2
FIG.ourbedeR´esurlaclacolatifEefdtle3..tne
soit : 2D1 D0=.(6) 1 +L Nousfaisonsl’hypoth`esed’unniveaudepartitionnement ` `apartirduquellalocalite´resteconstante.Apartird’une tellepartition,nouspouvons´ecrireles´equationssuiv antes : 2D1 D0= 1 +L 2D2 D1= 1 +L 2D3 D2= 1 +L . 2DK DK−1=. 1 +L ` Apartirdese´quationspre´c´edentes,nousde´duisons: K 2DK D0=,(7) K (1 +L) soit, en prenant le logarithme binaire de cette expression : K logD0= log 2+ logDK−Klog (1 +L),(8) i.e. logD0=K(1−log(1 +L)) + logDK.(9) Commeaudernierrang,apr`esKbipartitionnements, toutes les partitions sont indivisibles, nous avons autant de partitions que de sommets dans l’hypergraphe. Nous avons doncK= logB`u, oBest le nombre total de sommets. Et nous posonstte.sosmm,gr´eledendesmoye Nouspouvonsdonc´ecrirel’e´quation(9)souslaformede la loi de Rent : logD=plogB+ logt ,(10) avec l’exposant de Rentp= 1−log(1 +L). On peut alors constater que : –p≥0pourL≤1et –p≤0pourL≥1. Ceci revient a` dire que : – Dansla zone 2 de la courbe de Rent (cf. figure 1), la localite´ moyenne des souspartitions est plus grande que1.C’esta`direquelesterminaux`al’inte´rieur d’unepartitionsontfortementconnect´esentreeux et qu’il y a peu de connexions entre les diffe´rentes partitions.