Offre de th
Forum 'Emplois' - Sujet créé le 2008-05-28
Proposition d'un sujet de thèse/ Thesis proposal in English at the end of this post
Titre : La coloration de graphes
Sous-titre : Application aux problèmes de placement mémoire en électronique
Encadrement : Pr. Marc SEVAUX
Co-encadrement : Dr. André ROSSI
Laboratoire d'accueil : Lab-STICC (CNRS, UMR 3192)
Localisation : Lorient (56), France
Environnement de travail :
Le laboratoire des Sciences et Techniques de l'Information, de la
Communication et de la Connaissance (Lab-STICC) est un laboratoire CNRS, UMR 3192, crée en 2008 par la fusion de 4 laboratoires de Brest, Lorient et Vannes. L'équipe Lorientaise est intégré en totalité dans le pôle
Communications, Architectures, Circuits et Systèmes (pôle CACS) et
travaille principalement au développement de méthodes et d'outils pour la conception d'architectures. Depuis 2005, une équipe « recherche
opérationnelle » a trouvé sa place dans le laboratoire en proposant des
méthodes d'optimisation à tous les niveaux de la conception. Cette thèse
entre parfaitement dans ce cadre et s'attaque à une problématique de très haute importance pour nos collègues électroniciens.
Description du sujet :
Le problème général de la coloration de graphe consiste à affecter une
couleur aux sommets d'un graphe donné de façon à ce que deux sommets adjacents (reliés par une arête) aient une couleur différente. Un des problèmes rencontré consiste à placer des structures de données dans des bancs mémoires en minimisant les conflits lors d'accès simultanés, afin d'augmenter l'efficacité des circuits. Une première approche nous a conduit à modéliser ce problème comme une coloration particulière de graphes. Plusieurs variantes de ce problème seront étudiées au cours de cette thèse, ainsi que des méthodes de résolution exactes et approchées compatibles avec la taille des instances à traiter. Le candidat aura à confronter ses modèles aux besoins réels du laboratoire dans ce domaine, il participera également à l'implémentation des algorithmes dans les outils logiciels développés au Lab-STICC.
Mots-Clés : Optimisation, coloration de graphes, branch and bound,
métaheuristiques.
Financement :
Ces travaux de thèse sont co-financés par la région Bretagne dans le cadre d'une ARED, à partir du 1er octobre 2008. Rémunération, environ 1300€ net par mois.
Profil du candidat :
Le candidat recherché devra avoir un profil « Mathématique » et/ou
« Recherche Opérationnelle ». Il devra être titulaire d'un Master-
Recherche, DEA ou diplôme équivalent (ingénieur). Il maîtrisera les langages de programmation C et/ou C++
Dossier de candidature :
Il doit comporter :
• Un curriculum vitae
• Une lettre de motivation
• Une copie du diplôme universitaire
Il est recommandé mais non obligatoire de fournir :
• Le relevé de notes et le classement de la dernière année universitaire
• Une ou plusieurs lettres de recommandation
Contact :
Pr. Marc SEVAUX
Email : marc.sevaux@univ-ubs.fr
Tél. +33 (0)2 97 87 45 64
Fax : +33 (0)2 97 87 45 27
Université de Bretagne-Sud
LESTER, CNRS, UMR 3192
Centre de recherche
56321 Lorient, France
Dossier de candidature à adresser à : andre.rossi@univ-ubs.fr
*** ENGLISH VERSION ***
PhD Thesis Proposal
Title: Graph Coloring
Subtitle: Application to Memory Allocation in Electronic Chip Design
PhD supervisor: Prof. Marc SEVAUX
Co-supervisor: Dr. André ROSSI
Lab: Lab-STICC (CNRS, UMR 3192)
Location: Lorient (56), France
Context:
The Lab-STICC (Laboratory of Sciences and Techniques for Information,
Communication and Knowledge) is a CNRS-affiliated lab created in 2008 after the merging of four existing labs of Brest, Lorient and Vannes. The
research team in Lorient is part of the CACS dept. (Communications,
Architectures, Chips and Systems) and has been working in the field of high level synthesis for electronic design for more than ten years. An
operations research team supports the lab activities since 2005 by
providing advanced optimization methods for improving electronic design
tools. This PhD proposal aims at reinforcing the OR team by addressing high stakes issues for electronic designers and optimization researchers as well.
Thesis statement:
The general graph coloring problem aims at allocating a color to the nodesof a given graph so that two adjacent nodes have different colors while minimizing the number of colors used. In electronic design, researchers face the challenge of improving chips efficiency by allocating data structures to memory banks while minimizing access conflicts (that occur during simultaneous access to the data structures). Preliminary works have shown that this problem can be modeled as a particular graph coloring problem. During the PhD program, several versions of this problem will be studied along with exact methods and heuristics that will have to be very efficient for real life instances. The PhD student will compare and test his/her models to the actual requirements of electronic designers and researchers, and will be involved in the implementation of algorithms as well as in their integration to the software tools developed by the Lab-STICC
Keywords: Optimization, Graph Coloring, Branch and Bound, Methaheuristics.
Funding:This work is co-funded by the Brittany Region (ARED) from October 1st 2008.
The net monthly wage is around 1300 euros.
Candidate profile:
The candidate should have sound knowledge in mathematics and/or operations research. A Master of Science, an Engineering Diploma or any equivalent academic qualification is required to apply.
The candidate must also master C and or C++ programming languages.
Application form:
It must include:
• A curriculum vitae
• A motivation letter
• A copy of the highest diploma
It is recommended but not mandatory to provide:
• The ranking and the statement of courses and marks for the last
academic year
• One or more letters of recommendation
Contacts:
Pr. Marc SEVAUX
Email : marc.sevaux@univ-ubs.fr
Tél. +33 (0)2 97 87 45 64
Fax : +33 (0)2 97 87 45 27
Université de Bretagne-Sud
LESTER, CNRS, UMR 3192
Centre de recherche
56321 Lorient, France
Applications should be submitted to: andre.rossi@univ-ubs.fr
Titre : La coloration de graphes
Sous-titre : Application aux problèmes de placement mémoire en électronique
Encadrement : Pr. Marc SEVAUX
Co-encadrement : Dr. André ROSSI
Laboratoire d'accueil : Lab-STICC (CNRS, UMR 3192)
Localisation : Lorient (56), France
Environnement de travail :
Le laboratoire des Sciences et Techniques de l'Information, de la
Communication et de la Connaissance (Lab-STICC) est un laboratoire CNRS, UMR 3192, crée en 2008 par la fusion de 4 laboratoires de Brest, Lorient et Vannes. L'équipe Lorientaise est intégré en totalité dans le pôle
Communications, Architectures, Circuits et Systèmes (pôle CACS) et
travaille principalement au développement de méthodes et d'outils pour la conception d'architectures. Depuis 2005, une équipe « recherche
opérationnelle » a trouvé sa place dans le laboratoire en proposant des
méthodes d'optimisation à tous les niveaux de la conception. Cette thèse
entre parfaitement dans ce cadre et s'attaque à une problématique de très haute importance pour nos collègues électroniciens.
Description du sujet :
Le problème général de la coloration de graphe consiste à affecter une
couleur aux sommets d'un graphe donné de façon à ce que deux sommets adjacents (reliés par une arête) aient une couleur différente. Un des problèmes rencontré consiste à placer des structures de données dans des bancs mémoires en minimisant les conflits lors d'accès simultanés, afin d'augmenter l'efficacité des circuits. Une première approche nous a conduit à modéliser ce problème comme une coloration particulière de graphes. Plusieurs variantes de ce problème seront étudiées au cours de cette thèse, ainsi que des méthodes de résolution exactes et approchées compatibles avec la taille des instances à traiter. Le candidat aura à confronter ses modèles aux besoins réels du laboratoire dans ce domaine, il participera également à l'implémentation des algorithmes dans les outils logiciels développés au Lab-STICC.
Mots-Clés : Optimisation, coloration de graphes, branch and bound,
métaheuristiques.
Financement :
Ces travaux de thèse sont co-financés par la région Bretagne dans le cadre d'une ARED, à partir du 1er octobre 2008. Rémunération, environ 1300€ net par mois.
Profil du candidat :
Le candidat recherché devra avoir un profil « Mathématique » et/ou
« Recherche Opérationnelle ». Il devra être titulaire d'un Master-
Recherche, DEA ou diplôme équivalent (ingénieur). Il maîtrisera les langages de programmation C et/ou C++
Dossier de candidature :
Il doit comporter :
• Un curriculum vitae
• Une lettre de motivation
• Une copie du diplôme universitaire
Il est recommandé mais non obligatoire de fournir :
• Le relevé de notes et le classement de la dernière année universitaire
• Une ou plusieurs lettres de recommandation
Contact :
Pr. Marc SEVAUX
Email : marc.sevaux@univ-ubs.fr
Tél. +33 (0)2 97 87 45 64
Fax : +33 (0)2 97 87 45 27
Université de Bretagne-Sud
LESTER, CNRS, UMR 3192
Centre de recherche
56321 Lorient, France
Dossier de candidature à adresser à : andre.rossi@univ-ubs.fr
*** ENGLISH VERSION ***
PhD Thesis Proposal
Title: Graph Coloring
Subtitle: Application to Memory Allocation in Electronic Chip Design
PhD supervisor: Prof. Marc SEVAUX
Co-supervisor: Dr. André ROSSI
Lab: Lab-STICC (CNRS, UMR 3192)
Location: Lorient (56), France
Context:
The Lab-STICC (Laboratory of Sciences and Techniques for Information,
Communication and Knowledge) is a CNRS-affiliated lab created in 2008 after the merging of four existing labs of Brest, Lorient and Vannes. The
research team in Lorient is part of the CACS dept. (Communications,
Architectures, Chips and Systems) and has been working in the field of high level synthesis for electronic design for more than ten years. An
operations research team supports the lab activities since 2005 by
providing advanced optimization methods for improving electronic design
tools. This PhD proposal aims at reinforcing the OR team by addressing high stakes issues for electronic designers and optimization researchers as well.
Thesis statement:
The general graph coloring problem aims at allocating a color to the nodesof a given graph so that two adjacent nodes have different colors while minimizing the number of colors used. In electronic design, researchers face the challenge of improving chips efficiency by allocating data structures to memory banks while minimizing access conflicts (that occur during simultaneous access to the data structures). Preliminary works have shown that this problem can be modeled as a particular graph coloring problem. During the PhD program, several versions of this problem will be studied along with exact methods and heuristics that will have to be very efficient for real life instances. The PhD student will compare and test his/her models to the actual requirements of electronic designers and researchers, and will be involved in the implementation of algorithms as well as in their integration to the software tools developed by the Lab-STICC
Keywords: Optimization, Graph Coloring, Branch and Bound, Methaheuristics.
Funding:This work is co-funded by the Brittany Region (ARED) from October 1st 2008.
The net monthly wage is around 1300 euros.
Candidate profile:
The candidate should have sound knowledge in mathematics and/or operations research. A Master of Science, an Engineering Diploma or any equivalent academic qualification is required to apply.
The candidate must also master C and or C++ programming languages.
Application form:
It must include:
• A curriculum vitae
• A motivation letter
• A copy of the highest diploma
It is recommended but not mandatory to provide:
• The ranking and the statement of courses and marks for the last
academic year
• One or more letters of recommendation
Contacts:
Pr. Marc SEVAUX
Email : marc.sevaux@univ-ubs.fr
Tél. +33 (0)2 97 87 45 64
Fax : +33 (0)2 97 87 45 27
Université de Bretagne-Sud
LESTER, CNRS, UMR 3192
Centre de recherche
56321 Lorient, France
Applications should be submitted to: andre.rossi@univ-ubs.fr