Coloration avec préférences dans les graphes triangulés ...

pages

Catalan

Documents

Écrit par
Sandrine Blazy , Benoît Robillard Et Éric Soutif

Publié par
Zoun

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

pages

Catalan

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Zoun

Nombre de lectures

Langue

Catalan

Pr´esentation du probl`eme et de son cadre d’´etude
R´esolution du probl`eme
Conclusion et perspectives
Coloration avec pr´ef´erences dans les graphes
triangul´es
V´eriﬁcation formelle de la r´esolution d’un probl`eme de graphes
´Sandrine Blazy, Benoˆıt Robillard et Eric Soutif
CEDRIC, ´equipes CPR et OC
9 Novembre 2007
´S. Blazy B. Robillard E. Soutif Journ´ees Graphes et Algorithmes 2007Pr´esentation du probl`eme et de son cadre d’´etude
R´esolution du probl`eme
Conclusion et perspectives
Plan
1 Pr´esentation du probl`eme et de son cadre d’´etude
Cadre d’´etude
Allocation de registres
´Etat de l’art
2 R´esolution du probl`eme
D´emarche g´en´erale
Coloration avec pr´ef´erences et multicoupe minimale
´S. Blazy B. Robillard E. Soutif Journ´ees Graphes et Algorithmes 2007Pr´esentation du probl`eme et de son cadre d’´etude Cadre d’´etude
R´esolution du probl`eme Allocation de registres
´Conclusion et perspectives Etat de l’art
Contexte d’´etude
Besoin de logiciels sursˆ (domaines s´ecuritaires)
⇒ D´eveloppement de m´ethodes formelles
Probl`eme La compilation n’est pas sureˆ
⇒ Besoin de compilateurs certiﬁ´es
Besoin de code eﬃcace
⇒ Recours `a la recherche op´erationnelle
´S. Blazy B. Robillard E. Soutif Journ´ees Graphes et Algorithmes 2007Pr´esentation du probl`eme et de son cadre d’´etude Cadre d’´etude
R´esolution du probl`eme Allocation de registres
´Conclusion et perspectives Etat de l’art
Allocation de registres
Ex´ecution de programme
⇒ Acc`es m´emoire par le ...

Voir

Publié par

Zoun

Nombre de lectures

Langue

Catalan

Soutien-gorge Conclusions en procédure civile française Perspectives de la Chine comme superpuissance potentielle APX Algorithme de colonies de fourmis Allocation de registres

CEDRIC,e´quipesCPRetOCSandrineBlazy,BenoıˆtRobillardetE´ricSoutifVe´riﬁcationformelledelare´solutiond’unproble`medegraphestriangule´sColorationavecpre´fe´rencesdanslesgraphes9Novembre20077002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.SsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP

7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.S2Re´solutionduproble`meDe´marchege´ne´raleColorationavecpre´fe´rencesetmulticoupeminimale1Pre´sentationduproble`meetdesoncadred’e´tudeCadred’e´tudeAllocationderegistresE´tatdel’artnalPsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP

CsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP⇒Besoindecodeeﬃcace⇒Proble`meLacompilationn’estpassˆuree´msellemrofsedoht⇒De´veloppementdeBesoindelogicielssuˆrs(domainesse´curitaires)Contexted’e´tude7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.Sellennoitare´poehcrehcerala`sruoceRse´ﬁitrecsruetalipmocednioseBtra’ledtatE´sertsigerednoitacollAedute´’derda

ituoS.E´dralliboR.ByzalB.S)ediparse`ccaPassagea`unnombrelimite´deregistresK⇒Quellesvariablessontdansquelsregistresa`toutmomentdel’exe´cutionduprogramme?aAllocationderegistres`⇒eloadetstore)g⇒Acce`sme´moirepaaExe´cutiondeprogrammekAllocationderegistrescotsedsenoz(sertsigeredecnetsixEsnoitcurtsni(ruessecorpelrtra’ledtatE´sertsigerednoitacollAedute´’derdaCsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP7002semhtiroglAtesehparGsee´nruoJf

7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.Ssetnere´ﬀidsrueluocedse´time´rtxe’decnere´fe´rpedseteˆrasedsdiopsedemmosaSommets=VariablesduprogrammeDeuxtypesd’areˆtes1Areˆtesd’interf´erence(v1,v2)siv1etv2nepeuventeˆtredanslemeˆmeregistre2Areˆtesdepre´fe´rence(v1,v2)s’ilseraitpre´fe´rablequev1etv2soientdanslemeˆmeregistrelMode´lisationparungraphed’interfe´rence(construitgraˆcea`uneanalysedugraphedeﬂotdecontrˆole)tMod´elisationparunproble`medecolorationnasiminimnoitaroloc-KenurevuorT⇒elbairaveuqahcruopertsigeredxiohC=ehpargudnoitaroloc-Ktra’ledtatE´sertsigerednoitacollAedute´’derdaCsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP

7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.Ssedstra’ledtatE´sertsigerednoitacollAedute´’derdaCsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP⇒TrouveruneK-colorationminimisantlasommedespoidareˆtesdepre´fe´renced’extre´mite´sdecouleursdiﬀe´rentesK-colorationdugraphe=Choixderegistrepourchaquevariable1Areˆtesd’interfe´rence(v1,v2)siv1etv2nepeuventeˆtredanslemeˆmeregistre2Areˆtesdepre´fe´rence(v1,v2)s’ilseraitpre´fe´rablequev1etv2soientdanslemeˆmeregistreDeuxtypesd’areˆtesSommets=VariablesduprogrammeMode´lisationparungraphed’interf´erence(construitgraˆcea`uneanalysedugraphedeﬂotdecontroˆle)Mode´lisationparunproble`medecoloration

tacollAedute´’derdaCsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rPExempleedgraphed’interfe´rence7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.Stra’ledtatE´sertsigerednoi

GrundetHack(2007):algorithmedecoupes(pourgraphecolorable)⇒Proble`meNPMajorite´desgraphesd’interfe´rencetriangule´s(95%)7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.Secnere´fretni’dehpargelrusseuqitsirueH)7002(se´lugnairtsehpargselsnadelicﬃid-tra’ledtatE´tra’ledtatE´sertsigerednoitacollAedute´’derdaCsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP

elaminimepuocitlumtesecnere´fe´rpcevanoitaroloCelare´ne´gehFusion=TrouveruneK-colorationcVidage=Rendrelegraphed’interfe´renceK-colorablerDe´compositionduproble`meaDe´marchege´ne´raleme´DsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.S...noisufteegadiV⇒noN2lamitpotatluse´R⇒noisuF⇒iuO1e´tilibaroloc-KedtseT)dnamruogogla(sehpargsecsnadelaimonylopnoitaroloC⇒tnevuossulpele´lugnairtecnere´fretni’dehparG

7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.Slamitpotatluse´RDe´compositionduproble`me)Vidage=Rendrelegraphed’interfe´renceK-colorabledFusion=TrouveruneK-colorationnGraphed’interfe´rencetriangule´leplussouventa⇒mTestdeK-colorabilite´r2Non⇒Vidageetfusion...u1Oui⇒Fusion⇒oDe´marchege´ne´ralegogla(sehpargsecsnadelaimonylopnoitaroloCelaminimepuocitlumtesecnere´fe´rpcevanoitaroloCelare´ne´gehcrame´DsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´rP

rPApprocheneuedxspmet7002semhtiroglAtesehparGsee´nruoJfituoS.E´dralliboR.ByzalB.Selaminimepuocitlumtesecnere´fe´rpcevanoitaroloCelare´ne´gehcrame´DsevitcepsreptenoisulcnoCeme`lborpudnoitulose´Redute´’derdacnosedteeme`lborpudnoitatnese´

Voir