Université de Rennes

De
Publié par

Niveau: Supérieur

  • rapport de stage


Université de Rennes 1 IFSIC MRI parcours P1 Rapport de stage Application de la fusion de chemin de données à la synthèse d'architectures parallèles par Clément Guy Encadrant : Steven Derrien (Équipe CAIRN - INRIA) Rennes, 2010 du m as -0 05 30 70 0, v er sio n 1 - 2 9 O ct 2 01 0

  • traitements successifs

  • nids de boucles

  • boucles imbriquées

  • application de la fusion de chemin

  • liaison pdpg-datapath

  • implémentation des pdpg

  • circuits spécifiques

  • clique de poids maximal


Publié le : mardi 29 mai 2012
Lecture(s) : 44
Source : dumas.ccsd.cnrs.fr
Nombre de pages : 45
Voir plus Voir moins

GuyUniversit?synth?sede-Rennesrall?les1DerrienIFSIC2010MRIrchitecturesparrcours:P1eRappRennes,olartd'adepastagepaApplicationCl?mentdeEncadrantlaStevenfusion(?quipdeCAIRNcheminINRIA)dedonn?es?
dumas-00530700, version 1 - 29 Oct 2010dumas-00530700, version 1 - 29 Oct 2010.T.able.des.mati?re.s.Intro.duction.1T1.?tat.dequ?sl'a.rt313.1.13.2.1Algorithmes.sources.et.arc.hitectures.cibles........3.1.............compatibilit?.p...3.3.1.........3.3.5.41...des.......27..3.1.1.1.Nids.de.b.oucles.?.con31tr?le.statique..........................ill?gaux...3.3.2.....37.........tes...et....3.1.1.2.R?seaux.r?guliers.de.proill?gauxcesseursdeux.....ectiv...........Mise.utilis?s...........oly.........e.........tation....4.1.2.Or.donnanc.emen.t.et.allo.cationConstructionde.nids.de.bdeouclesconstruction...futurs...........temen.....................Mo.......3.3.45.1.2.1.Mo.d?.leetp.oly.?drique38.oids.fusionn?...........2.3.3.ill?gaux...............2.3.4.v.plus...........P....................5.1.2.228Ordonnancemen?uvrettiet.allo.cation.a.v.ec.le.mo.d?le.p.oly.?driqueLibrairies...................M?ta-mo.EMF......7.1.2.3.En.vironnemen.t.MMAlpha3.2.......................d?les...................32.graphe.............3.2.3.clique.maximal9graphe1.3.P35artagevde.ressources....................r.des.................est.......................Liaison..............9.1.3.1MMAlpha-PDPGP.artitionnemen.t.et.temps.m.ulti-dimensionnel....tations.v...........39.i.maximal.PDPG..................10.1.3.2.F25usionD?tectiondecyclesc.hemins.de.donn?e.s......................26.Cycles.pro.o.par.de.fusions...................2.4.ersp.es..12.1.3.3.P.artage.de.ressour.c.es.au.sein.de.r?seaux.r?guli.ers................3.en.31.Ou.ls..............15.2.Contribution.17.2.1.F.l.ot.de.syn.th?se..........3.1.1.p.?driques...................................3.1.2.d?les.t............................17.2.2.P.olyhedral31Data-PImpl?menath.Graph........................................31.M?ta-mo..........................17.2.2.1.D?nitions..........3.2.2.du.de.........................33.Calcul.la.de.oids.et.du.fusionn?.......3.3.ra.aux..............19.2.2.2.Exemple.de.PDPG.d?taill?..................36.T.ai.t.cycles...............................36.T.s19.2.3.P.artage.de.ressources.au.sein.de.r?seaux.r?guliers........................3.3.3.PDPG-Datapath.del..................21.2.3.1.Graphe.de.compatibilit?..37.Liaison.................................38.Impl?men.d'optimisations.de.arian....................21Conclusion2.3.2BibliographieCliquedep
dumas-00530700, version 1 - 29 Oct 2010dumas-00530700, version 1 - 29 Oct 2010laInoutiltroconductionlaLexmarcLeh?dedudesyst?mecircuitemrapidemebarqu?teestsonlemat?rielth??treouclesd'uneprvet?ritablelacoursemat??latousl'autreleshaut-nivniv(C,eauxc(pdeerformance,bminiaturisation,taille.consommationdans?lectrique).hapitreEndeeetdequepcen?rique.soituepd'unourmaislelimitanmultiplicationultim?diaos?espdeortablela(consolesautomatiquep),ortables,uappareilsex?cutanphotosseinetutilis?ecam?rastsndonum?riques...)ourouettanpourourortlesqt?l?comsth?se(?mduetteursectu?-r?aphscepteurs(enettationt?l?-pphones?3aussietqu'unbseicircuitsendet?teet,4G),delaunetr?sminimforteduconcurrencedeoblige?vitanlests.syst?mescon?celle?treossibledemaximplusmiterenCeplusconduisenpoueourrfbutod'unrprogrammationmmansptss'i(meilleure?r?solution,ameilleureettransmission...)r?utilisationetle?seabutvdeotenanirpunelesplusdegrandeleautonomie,hapitretoutunensconser-tes,vneapndanst,Levtraoirstage,endrdiminetu?alennt,delespurltaille.fonctionsLafoispluparttdepceconsom-scesseursyst?meslaemosebarqu?sdeon?ct?unorithmepcritique.oinletalgorithmecommoirund?j?:hoseilsfautdoivleeniteex?cuterladesparfonctionsmplelourdeslaetcompr?pqui?titivsousestesduesd'unauletraitementtetd'imagesl'ex?cutionouetdudesignal.co?tIlobtens'agittg?n?ralementestladecircuitstraith?set(HLSeevelmenttsd'os?ucd?critcessifslangagesurhaut-nivdesunematrices,d'uneutilidescetadent?ressetladesr?bdeouclesdeimunbriqu?es,dquiparsicompellesC'estsondrtHLSex?cut?escesurlled'obtenirproconceptioncesseurd?di?sg?n?algorithmesrdeiimqruedeemcbarqu?,aul'alourdissencircuitstdiminetetlepremierralencetissend?di?t.deUntexemplehdesceslafoncetlaihaut-nivonslesditesbriqu?escritiquesdomestdel'algorithmemeduteltreaildecoursKalmanpalemen[6].desCeData-PathdernierSectionestd'unutilis?deenestraitemen2.3).tcdessignall'impl?mepPDPGour1estimermani?reles?ciqueparam?tresourd'un'unesyst?mecesdestynamilaqplusueerforman?maispartirplusdeetitmesuresmoinsbruit?esmateuretproutiliseg?uneMaissuccessiondicult?depcalculsdanssurconceptiondescesmatrices.spPiqasrpartirexemplel'algunder?cepteurfonctionauxEnnormesextraireLparall?lismeTEtel(anLconcevongunTn'estepasrcmais?e,Evolutionil,ensuitenormesiserquico?tdoivreneltcircuitassurernletpassagesurfacedesilicium,lae3Ge?enlat4G)mactuellesdedoitosanr?aliserCeenconduittreconception83deuxettrain2000oppltres:dec?t?Kalmand'ex?cuterenplusparall?lnepenl'algorithme,0.13doncms,parall?liseranaud'estimerum,lesdeparam?trescelledulicanallededepropagationpuceradioue.ensontrecesl'antraintenne-relaisquiettleconceptiontde?d?di?s,l?phone.synIldeesteaun?pcessaireHigh-LqueSynthesiscedonttleeestestimationbaniritpartirlieualgorithmeapr?sdanslanpropagation,dedoncdeaueaunivMatlab...)eaudescriptionduat?rieller?cepteur,puce?tl'mani?rein?ciquet?rieuralgorithme.dupartaget?l?phone.ressourcesIlnestaudoncden?ceHLSslasaidurtioneld'asurfacevsiliciumoirparunecircuit,pucedoncr?alisanetco?t,ceslacalculsdedeosanmani?remat?riels.massivdansemencateparall?lelaaquevsitueecstage,unetconsommatieon?taitetununedesurfaceautomatiqueminimale.circuitsLespcircdesuconittssspoucles?cialis?sbriqu?es,appeortenmttunepartagersolutionressour?esceslesbseinesoinscesenpconstanenteueraugmenco?ttation.laQu'iUnlscsoiendetrapprecongurablesest(Field-Pr?o?tatgrl'artammabledi?renGateeAtecrrniay)ueouexistannon?(ApplicfoisationlSpdomaiedecicsynIntedegreauateourdbCirimcuit)et,lecesainecircuitspartagesonressources.tdeuxi?ccharg?spr?send'ex?cuterlelesvfonctionselesauplusduco?teusesprincidutsyst?med?nitiondePolyhemani?alreGrsp(en?cialis?e.2.2)Cel'adaptationsemalgorithmeblepartage?treressourcesunecr?pgraphesonseSectionoptimaleEnnauxdernierprobl?meshapitrede?l'eemtebarqu?,npuisquedesunetcl'algorithme.ircuitcon?u
dumas-00530700, version 1 - 29 Oct 2010dumas-00530700, version 1 - 29 Oct 2010Z
!
x = fx ;x :::x g n1 2 n
x i xi i
!
x x ni
!x =i;j;k
f0; 0; 0g
nidouhaqcircuitsrd?di?s,m?nspartirLesd'algorithmesouetoss?dededeprogrammes,eauqu'ellesassosoienAnetdesconsacderdu?hniquesesenglobanauxtiernidsvdeenbouclouclesdeou?lnon.nidsCeencendenhapitrePinptrojduitChaquelespronidsl'denombo?oucles.?conconetr?lesous-ensemstatiquet(1.1.1),l'instruction.psourlesles-dimensions.quelsChapitrenousouclesaAvop)onslescpherc)heranes?constand?voucleseloppprogrammeerenunesnouvleselled?pm?thotaidededed'it?rationHaLSestminimisanitsloucleatructiosondurfaceledesestr?seauxvr?guliersdes(1.1.2).desIlindicespr?sen(HLS)tespaussiCecertainessdetcesleteconhniques,duengurerappquiortunalevl'artectr?lenotredetraconvstatiqueail,pnotam-trolmenttbletmobd?leunp(dansolyorn??driquetrain(1.2.1),nelaquem?thodedededesexternessomexemple,metsm(1.2.2)pr?senet1.plusieurstm?thoouclesdesdondeipartagekdetressources,N?desund'unnivoucleseauvd'abstractiondes?levt?i(1.3.1)o?ouprofondeurauruccdansonbtrairec'est-?-diredirectedemenimtl'iau,nivnomeaul'indicdesbunit?sprofondeurfonctionnelles?(1.3.2).un1.1tAlgorithmesursourcesteetlin?aires.arcmhitecttrainusurrd?esd'indicesciblestIld'unestceg?ouncon?bleralemenointcorrespadmisit?rationsqu'unarprogrammeecteurpasset80%dedetsondetempsdedanse20%traindesonsond?nissencoendeceetoinqordonn?esue?tatcescon20%statiquesonnidstbles?btrouclesedu(ouprogramme.CLObtenirouruneConarcLohitecturesond?di?edes?del'acc?l?ratioucondond'uncensemuebleoucledeoss?debindiceouclestieril?rateursmbbriqu?es,parouconnidstesdequibd?poucles,testdedonctes,particuli?remenparam?trestd'indicesinbt?ressanplust[12].puisquearceledernierdeconcenultiplicationtrematricesunet?grandegurepartie1,duoss?detempsroidebcalculid'unebriqu?es,application.tOr,indiceslorsque,l'onetcnehercendenheque?param?treex?cuter(laecacemenlletmatrices).cesinstructionnidsniddebbpouclesunanecteurd'acc?-acc?l?rerduireun?programme,nunesdesvsolutions,ptecossibleslaestdedeinstctherconherle?deobteniroucleun,cleircuitbrespb?ciques?briqu?esl'etxns?ncutionetdebreusescescorrespt?c?heseclaroucidetiqudeeIci,s.eloppCettedoncsectionens'attacdonhela?alepr?senesttertrainlesparnids?quationsdeL'ebeouclesble?conconttr?lesslestatique,vquidusonecteurtauned?nissenfunobleremae?dedimensionsnidsdomaine.dedomainebtienouclesl'ensemparticulide?respdanstsunetierspremi?reondanpartieauxetdelesPr?seauxexempler?guliers,vquid'it?sonatideshaut-nivarcehitecturesh?d?vsyneloppnid?esbspes?ciquemenlamat?riels,1.1correspt?conpremi?retesduluiett?ci?esdest:domaine[0][0]3aDans]*domaine,[0][0];ptmp2t=co[0Latmp1de.13?tondplaourit?rationl'acc?l?rationprogrammedesdoncnidsl'ex?cutiondeinstructionsbtmp1oucles=dans[0][0unebdeuxi?meet.[0][0]1.1.1tmp2Nids][0]+de[0][0];boucles
dumas-00530700, version 1 - 29 Oct 2010b[2,0]
b[1,1] b[1,0]
b[0,2] b[0,1] b[0,0]
a[0,0]
a[1,0] a[0,1]
a[2,0] a[1,1] a[0,2]
a b
a
b
t = 0 (0; 0)
a[0; 0] b[0; 0]
0 a[0; 0] b[0; 0]
droite.kcesseurs=0;[kadditionne<ParametreNun;prokoisins++){ts10definetmp1ultiplication[mile][vjk]de=estales[vii][Fig.kultiplication-]d'un*labi[ordske][deju];?l11Ainsitmp2la[proiseul][etjle]le=Ntmp2N[];i;]r?alisan[projgure]+arctmp1cesseurs[etire][deuxjprogressiv];au,12de}les13enancns[mic][ejpuis]matrices=detmp2v[danside][[][])jordonn?es]e14oir}a152}additionne16dereturntocan;r17oisin}iFig.i1.1:forMultiplication][deintmatrices,enR?seauCune1.1.2matricesR?seauxder?guliersulationdepr?senprod'unecesseursIlLesdearcthitecturesdeform?esexempleparucdesprr?seauxr?seau.r?guliers,,outrenarcthitecstlesurebasshe.systoliques,r?cupsontstmatricesdesdearcshitecturesbasmassivhe,emen,tvparall?les,cono?sonlastostrleuclttsuresesdehauttousolesmatriceproycenessr?seaueeursheest?similaireseuletdeo?][],lesilconnexionseetsonatdesuniquemenmatricest(lointcalesI[11].ultiplie,Ellesvprennententregistrelaetplupartkduatempsd'elayforme100d'unesongrillehautou1d'une;ligne<de=0;pro(cesseurs6o?NlesNcommcunic5ationskajv1.2:ecr?gulierl'ext?rieurtsonmtdeassur?esetparcesseurlesmproaccumcesseursLasitu?s1.2surtelesexemplec?t?stelledehitecture.las'agitgrille.r?seauEllesprosonr?alisantuneparticuli?remenultiplicationtmatrices,ecacesd'unpdeourstrex?cutertudedesmani?reoparaldul?leLeslesmatricesnidsetdeenbtoucles,emenpuisqu'?danscr?haqueeit?rationpardubniddudeetbgaucouclesChaquelacesseurm?me?resuite?l?mendd'sopv?rationstestsesex?cut?e,oisouviendutetsurgaucdeslesdonn?esultipliecalcul?esles?al'it?rationepr?c?ledentente.deC'estregistreexactementtcleescr?sultat,h?matransmetdesesr?seaux?menr?guliers,deso??lesvdonn?esdud'eetn-drtr?eite.(oulaparam?tres)intenotrenagetbasd'unhautc?t?ledeetlamatricgrille,4subissengauct?uAinsi,n{traitemenbtledanscesseurlacopremi?reintligne[deactif,proestcesseurs,nleler?sultat??tanv(re?u??l?menvdesde(?int4matmultligne[][]de3pro).cesseursletmainsilesdeasuite.ecforcon9u0son=(])js][cie[r?sultat,tmp2v8t++){njo;eN//<=j?=0;vjdu(etfor#7++){tsonensuiteoisinpass?droite.?laseconde
dumas-00530700, version 1 - 29 Oct 2010t = 1 (0; 1) (1; 0)
(0; 0)
nfz2Q jQzqg Q
q n
nfz2Z jQzqg
concesseursurdeolycoIlordonn?ese,actifs.?om?-texiste?galemenlimit?ettuntr?l?men(guretduparonlespb?ordsouduonr?seau.mani?Lestprotcesseursolyactifshacunemduultipliencelles-cit?rationslesi?l?meneuxtspdd'alloueretsmatricesere?us,desadditionnenrationnelttlepr?sultatdeauosconutenensemusderepr?senlemuunrpr?senregistreetetinstrusto11cleurkossibleens.t?rationslear?sultatleurdestage.cettecaddition,formepuissommetsils[12].enblev?oitrainenolyt?driquelesen?l?menunts?l?mendeolymatricessre?usUn?t?leurs:vlaoisins,petnainsidimensions.ded'in?galit?ssuite.1.2UnOrdonnancemenlin?airetyetlaquelleallooincation.depr?sennidsrde?driquebtructions.ouclesrepr?senPecoureobtenircorrespuneformenarcoucleshitecture1.d?di?e??lel'ex?cution?dresd'uncertainprogrammeolycondetenanleurtclassiquesdese,nidsesdesb?ciques.oucservisles,oond'unvlin?airesasacdeherclahequirn?sordonnancerunetp?unallouerdimensionscdeshaquelin?aiopUn?rationendespnl'ensemioindsideusbolyouclematrice?re?uunduinstanrationneltcoetl'espaceunenopoly?rateur?tremat?rieldi?renpr?ciseanG?om?triquemendeapinouvouroir?dresspd?ciersusammeuneucircuit.PLeensemmooud?lenparolyde?driqueeetcoml'utilisationsommededestecduhniquesformecommeplalesm?d'untdrhoprogrammedededesplussommetsppetermettenptourd'obteniricetgureordonnancedemen(taet=cettebleallotraincation.olyUnetfoistionscesle?tapdee10slafrancEnhies,tilm?mefautestensuiteOpg?n?rerpleestcircr?aliseruitbrecorresplesondandrt.sonCeensemcircuiteutselespr?senblteig?n?ralementersection,tosouseclahabituels.formetd'unsr?seautded'enprooncesseurs,coursparticuli?remendetaadapt?de?blel'ex?cutiontrainparall?letde?drenidstationdesommetsbyoucles.utilis?Cettedesectionoirs'ermetinopt?resserepr?sendC'eatnsdireuneensempremi?redepartieoinaudansmoespaced?leparpd?olypar?drique,conquitesprermets.d'exprimerpdes?drealgorithmestiercondomainetenanolytestdesblenidspdetsbtoucleserssoustenformedansdepsyst?me?drele:prodetC'est-?-direunbletsoind'?quations.r?currenl'ensemtesdeanes.pLatsdeuxi?meppartie?dreindontrolesduitordonn?eladansm?thosondedesdestiers.sommets,pqui?drepeutermetrepr?send'obtenirdeuntesordonnancemenrtsetunet,allolcationmani?repplusourtuitivcespslesyst?mesolyd'?quationspets?ennaunettroisin?meppartiedepr?senteraarl'ennvironnemenbletlin?aires,MMAlphaconquiaiimpl?mentes.tePlaunm?thobledeconstructeurs.desconstructeursommets.s1.2.1uneMobinaisond?ledesptoletyra?driqueonsLepmo?dre,d?lesousponolyeut?driqueterestpunetsrepr?senptation?math?matiqueequiLepdeeultiplicationrmet,matricesent?trehautautres,1.1)d'exprimerelesmnidsd'obtenirdedomainebolyouclepscendesfonctionnsdesLacon1.3trainteteuxstationssgurtriquelesvindicesNdes2bensemoucles.dCetteconpartietes)pr?senpte?dreceondanmoauxd?lecetquis'intt?ressecorpsplusnidparticulbi?remen(lignestetaudecasguredes3).peetolyson?dresex?cut?esenlatiers.it?ration,Edomainendonceetm?me.ceux-ci?rationsplesermettenolytIld'utiliserpladeprogrammationunlin?airenomend'opti?resurppour?obteniredesCeordonnancementtssetbles,allopcationsdoncanappliquerdeopconcevensemoiristesune(unarcon,hitecturenparall?ledi?rencex?cutanprtjection)levnidlder?sultatsbIloucles?galemenexprim?de[1].algorithmePquiolyson?dresspenDeuxtierstreUnnousptolyau?dredurationnelL'algorithmeestChernikuvn[7]ensemermetblepasserdeensemladeformeonttessond?nissanetunordonn?esolyo?crepr?sendesouscesseursdeproetlesrao?ons.,estt?esdansunm?thoolydes5(vti?re1.2.2)etpIlsd'ordonnanceretundesv?ratioecteursentierparestpune?dre.matriceen
dumas-00530700, version 1 - 29 Oct 20108
0iN<
D =D = 0jNtmp1 tmp2
:
0kN
D Dtmp1 tmp2
z2D;p2P)V (z;p) =f(:::;V (I(z;p));:::)i j
V V V V 2 Vi j i
V :D ! X D V Zi V V ii i
R
D DDVi
z dV dVj iI(z;p) =D +d Z Z
p
p2P
nf V V
P
D
nDZ DVi
V Zi
f D
tmp1(i;j;k;N) = a(i;j;k;N)b(i;j;k;N)
k 0; 0
tmp2(i;j;k;N) =
k> 0; tmp2(i;j;k 1;N) +tmp1(i;j;k;N)
c(i;j) = tmp2(i;j;N;N)
cast?dre,?tl'ensemdeblecondem.blesChaquebvestariauable1.1bre?drenomdeleSAREtLespieut-?tretr?levuesoncommecteuruneo?fonctionmexprimant?olyn?mefonctionspleunnestd'?quationstierccurrenend'?quations?dreouro?tationolytr?leplesunbestdomainele?dredom)ainesurdeque?aci?deset).Xpr?senunSAREensemo?bplicationlestetierquelconquenid(sesassodansou(v[7]la,sonparofenxLesealgorithmesmple).sonlatnidsest?leadomaineueparam?Danstrnid??dell'?quation,desapvtierecoind'Ehrharparolyn?metespvLedetesdomaines.desidi?ren(lesformesouclesdeuxsursousprogrammematricesdedeenultiplicationpmsyst?melaguredeet)t(tl'additionetdepestvunetanfonctiond'it?rationanebdefonctionets'il)Nous(m?thoultiplicationdev2.3.1).erstesmd'?quationsladesdeEquations)?driqueRappourel?eanesfonctioncurrdeyst?med?psendance.led?liserolyutilis?espr?currenDomaine?estrepr?sen-undesvdeecteurouclesdesconparam?tresstdettailleqduparsyst?me.SARE.le1.3:d'unndeanesouclesprcongrstatique,mmeeultt6?quationsdeunariablesolyFig.env(erspvet.d?niLesles?quationstrainsonlin?airestlediteser?currend'indices,tesm?meparcelesqu'etsllesevxrprimeablesnseintindicesdesbd?psonendancesexprim?sendutreLeleursdediultiplicationvmatricesersest?vgureaarourileables,pr?senetenp1.4,euvl'additionenlatuldonciservirson?lesd?crirepuneolybleoucle,olysconappartenanexeen1.4:repr?send'?quationsturdomaineparam?tr?duparcedequ'iloucles.prenedendparam?tresenecomptea.del'utilisons,notreundeensempartagebleressourcesdeoirparam?Syst?mestr?currenreformesdequinisinueensemsurtsonparam?tr?sdomaine.tLeseSAREAnesonSystemtpun(ouformalismetestr?sepuissanr?tsquispparall?liser.ermetled'exprimerbutundansgranddesnommobrepd'algorithmes.tNoustesnous?quationsinanest?resseronsetFig.leSyst?mesyst?mer?cestredittesestduuneofoncatmatmionquelconque
dumas-00530700, version 1 - 29 Oct 2010

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.