La Loi de Rent et ses Applications au Placement/Routage

Description

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ˆ ...

Sujets

• Routage météorologique
• Loisy
• D'une ombre à l'autre
• Banque d'Estonie
• Homo sapiens
• Igny

Informations

• Publié par: Aslae
• Nombre de lectures: 126
• Langue: Français

Extrait

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

Email:{ } 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 ´ etablissonsensuiteunere F IG . 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 `u X est un ensemble(x 1 , x 2 , x 3 , . . .)de sommets etUest un 1. Introduction ensemble d’hyperarcsU⊆P(X), o `u P(X) ´ rseneetrep l’ensemble des partitions deX. Autrement dit un hyper LaloideRentestissuedestravauxdeE.FRentau grapheestungraphedontlesarcspeuvent ˆ etreconnecte ´ s coursdesanne ´ essoixante.Cestravauxontdonn ´ elieu ` a a ` plusdedeuxsommets.Laplupartdespropri ´ ete ´ sdes une relation remarquable entre le nombre de terminaux et graphes restent valables pour les hypergraphes. Dans le lenombredeportesdansuncircuitint ´ egr ´ e.Publie ´ pour cadredecetarticle,chaquenetlistestmode ´ lis ´ eeparun lapremi ` erefoisparLandmanetRusso[1],laloideRent hypergraphedontlessommetssontdesporteslogiques 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 ) r 1 t ( e : l u o ` g o i a` plusieurs portes logiques (notion de sortance, ou de –Tmorbdetereimanxu(portsd’entr ´ eeoeduneltse fanout). sortie), Bipartition minimaleSoit le grapheGdont les som –Best le nombre de cellules (portes logiques) dans metsV sont relie´s par les arcs E, 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 de etWdisjoints, 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 com minimal [5]. plexit ´ edure ´ seaud’interconnexion,obtenuparbi Dn(ioapentitr ´ rgeu’deD i )adreeLpe ´ unegdr’:ti partitionr ´ ecursivedugraphedelanetlist. tionestde ´ finiparlenombred’arcsentrantsetsortants Lesch ´ ematypiquedeRentcontientlestroisr ´ egions decettepartition.Parexemple,pourunepartitionquine de ´ critesdanslaFig.1.Cestroisr ´ egionspr ´ esentent contientqu’unseulsommet,ledegre ´ delapartitionest trois couples(t, p) moemdesuge ´ ralduedeccadrnslet.Daga ´ e aqChs.ntre ´ effdimocesnoige ´ reu ,eratelcit porte comme un ensemble autosemblable par variation nous notonsD i noostbnepsraititsleuesapr ` egrdede ´ ele `eme delahi ´ erarchie(a ` l’instardesensemblesfractals). La i partitionnement re´cursif. loi de Rent a trouve´ des applications concre`tes, comme Coupe minimum (C i ): 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 notonsC i la

F IG . 2. Partitionnement d’un graphe.

e`me valeur de la coupe minimum obtenue apre`s le iparti tionnementr ´ ecursif. Localit ´ ehpargnu’fie ´ dtseearepniLalo:t ´ edcali l’ ´ equationsuivante: . 2C i L i =,(2) D i ou` C i est la valeur de la coupe minimum du graphe et D i aueel ´ soniioitrtenr ´ e.ndegstsoeenapelu,expmaPer localite´ e´gale a` l’infini ( +∞) carD i vaut 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 hypergrapheG 0 (respectivement 0 G i snoitit) ´ greleen ` exparsdeuG 1 (resp.G i+1 ) etG 1 0 (resp.G i+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’esta ` direquechaque noeuddelanetlistestconnect ´ e ` adeuxetseulementdeux terminaux.Onpeutend ´ eduirelarelationsuivanteentre D 0 (resp.D i ),D 1 (resp.D i+1 ) etC 0 (resp.C i ) : D 0 = 2D 1 −2C 0 ,(3) 0 ou` D 1 est la moyenne deD 1 etD 1 . 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 D 0 = 2D 1 −2C 0 2D 1 = 4D 2 −4C 1 4D 2 = 8D 3 −8C 2 . K−1K K 2D K−1 = 2D K −2C K−1 . ` Apartirdes ´ equationspr ´ ece ´ dentes,onpeut ´ ecrire: K K 2D K −D 0 = 2C 1 + 4C 2 + 8C 3 . . .+ 2C K−1 .(4) L i D i Enrempla¸cantlesC i l’e´quation (3), on par dans 2 obtient : D 0 = 2D 1 −L×D 0 ,(5)

2

F IG . ourbedeR ´ esurlaclacolatifEefdtle3..tne

soit : 2D 1 D 0 =.(6) 1 +L Nousfaisonsl’hypoth ` esed’unniveaudepartitionnement ` ` apartirduquellalocalite ´ resteconstante.Apartird’une tellepartition,nouspouvons ´ ecrireles ´ equationssuiv antes : 2D 1 D 0 = 1 +L 2D 2 D 1 = 1 +L 2D 3 D 2 = 1 +L . 2D K D K−1 =. 1 +L ` Apartirdese ´ quationspre ´ c ´ edentes,nousde ´ duisons: K 2D K D 0 =,(7) K (1 +L) soit, en prenant le logarithme binaire de cette expression : K logD 0 = log 2+ logD K −Klog (1 +L),(8) i.e. logD 0 =K(1−log(1 +L)) + logD K .(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 souspartitions est plus grande que1.C’esta ` direquelesterminaux ` al’inte ´ rieur d’unepartitionsontfortementconnect ´ esentreeux et qu’il y a peu de connexions entre les diffe´rentes partitions.