ROADEF - Le bulletin - n024 - Printemps - Été 2010 11

Article invité

Conception électronique et recherche opérationnelle :une association gagnant-gagnant

Marc Sevaux, Professeurresponsable de l'équipe Recheche Opérationnelleet directeur-adjoint du Laboratoire des Sciences etTechniques de l'Information, de la Communicationet de la Connaissance (Lab-STICC � UMR 3192)

marc.sevaux@univ-ubs.fr

Pourquoi une équipe de Recherche Opéra-tionnalle dans un laboratoire d'électronique ? Laconception électronique regorge de problèmes d'op-timisation en tous genres. Nos collègues de la com-munauté électronique (en majorité de la 61◦ sec-tion CNU) sont déjà familiers des méthodes et desoutils de l'optimisation, mais ils sont loin des per-formances que nous savons atteindre aujourd'hui.Alors, c'est à nous de les aider, notre tâche esténorme et nous allons devoir faire preuve de beau-coup de pédagogie. . .

Un cadre de travail idéal

Le Laboratoire des Sciences et Techniquesde l'Information, de la Communication et de laConnaissance (Lab-STICC) est une UMR du CNRSet a vu sa création au 1er janvier 2008. Il dépendde l'Université de Bretagne-Sud, de l'Université deBretagne Occidentale et de Télécom Bretagne, il aété créé par fusion de quatre laboratoires existants(LESTER, LEST, TAMCIC et SABRES). Le labo-ratoire est rattaché au département ST2I du CNRS(section 08 et 07). Il développe des méthodologiespour la conception sous contraintes de systèmes etcircuits électroniques. Les champs d'applications ci-blés sont ceux du traitement de l'information (trai-tement du signal, traitement de l'image, communi-

cations numériques, etc) sous contraintes d'implé-mentation (temps, surface, puissance consommée,�abilité, etc). Le Lab-STICC compte aujourd'huiplus de 360 personnes dont environ la moitié dedoctorants. Il est dirigé par Alain Hillion (TélécomBretagne) et par trois directeurs adjoints (un parétablissement). L'Université de Bretagne-Sud repré-sente 75 personnes dont 35 doctorants au sein dulaboratoire.

L'équipe Recherche Opérationnelle ne compteque deux permanents : Marc Sevaux (Prof.) et An-dré Rossi (MCF), une ATER, Kods Trabelsi et troisdoctorants : Rachid Dafali, Maria Soto et BoureimaZerbo. Même si cette équipe est de taille modeste,elle collabore au quotidien avec les autres perma-nents du laboratoire. Le soutien de ces derniersest d'ailleurs primordial pour éviter de nous perdredans les méandres de la conception électronique.Cette équipe RO va s'agrandir sous peu, faîtes pas-ser le message. . .

Les deux premières années après la création del'équipe au sein du Lab-STICC (anciennement LES-TER) ont été le cadre de discussion et d'échangesintenses pour expliquer les méthodes connues, dé-cortiquer les procédures classiques et redémontrerquelques preuves pour convaincre que l'optimisa-tion peut donner des résultats. A titre d'exemple,il a fallu convaincre que l'ILP ne se résume pasà un modèle pour résoudre un problème, que

Bulletin de la Société Française de Recherche Opérationnelle et d'Aide à la Décision � http://www.roadef.org

12 ROADEF - Le bulletin - n024 - Printemps - Été 2010

l'on peut utiliser un algorithme génétique sous di�é-rentes formes, qu'il existe des métaheuristiques plusavancées que le recuit simulé dans sa version origi-nale et qu'étudier la complexité des problèmes n'estpas du temps perdu.

Des problèmes en pagaille

Le premier problème sur lequel nous avons euà travailler concerne la synthèse de haut niveau.En quelques mots (et de manière extrêment sim-pli�ée � pardonnez-moi chers collègues électroni-ciens), cela consiste à transformer une applicationlogicielle en un composant électronique. Au sein decette transformation, on retrouve une foule de pe-tits problèmes d'optimisation : de l'assignation, del'ordonnancement sous contraintes, de l'a�ectationde ressources, des traitements de graphes, etc. Cesproblèmes ont souvent été traités séparément et au-jourd'hui, une thèse (Kods Trablesi) qui o�re des so-lutions concrètes pour résoudre de manière globalece problème a été soutenue.

Dans les NoC (Network on Chip), on chercheà faire communiquer des processeurs entre eux etavec des registres en mémoire. Il faut donc transpor-ter des données de plusieurs sources vers plusieursdestinations avec des contraintes très particulières(contraintes de type �ot avec bu�ers dans les n÷udsintermédiaires du graphe). Comme le délai est unfacteur de coût, on cherche donc à proposer des so-lutions qui se basent sur des algorithmes de pluscourts chemins sous contraintes. Pour ce sujet, deuxdoctorants travaillent de manière complémentaireavec d'un côté une vision �électronique� (Rachid Da-fali) et de l'autre une vision �RO� (Bouréima Zerbo)du problème. Ces deux approches s'enrichissent mu-tuellement et les deux thèses commencent à porterleurs fruits. Les résultats sont directement utilisésdans l'ANR AFANA.

L'année dernière une étudiante équatoriènne(María Soto) est venu renforcer l'équipe et s'estattaquée au problème de l'allocation des donnéesen mémoire. C'est un problème de coloration degraphes avec des contraintes particulières sur lataille des données stockées dans les mémoires. Aprèsavoir étudié le problème de manière théorique, nousavons commencé à être en mesure de proposer denouvelles bornes supérieures pour la coloration degraphes, puis d'adapter des heuristiques connuespour notre problème spéci�que. Pour satisfaire lesdemandes de nos collègues électroniciens, nous éten-dons progressivement le problème en intégrant deplus en plus de contraintes réalistes.

En�n, nous avons depuis peu abordé le problèmedes réseaux de capteurs sans �ls. Il s'agit de dé�nirdes sous-ensembles de capteurs qui seront alluméspuis éteints successivement et qui permettront decouvrir un ensemble de cibles à surveiller. On peutalors, soit maximiser la durée de vie du réseau (pourune qualité de couverture donnée), soit maximiserla couverture des cibles pour une durée de vie duréseau �xée. Il existe bien sûr de nombreuses exten-sions à ce problème que nous envisageons. Pour ré-soudre ce problème, nous avons développé une mé-thode par génération de colonnes qui intègre uneheuristique pour la résolution du sous-problème.

Le dernier challenge que nous nous sommes �xésconcerne la résolution des problèmes de RO en uti-lisant des composants électroniques. Cette fois-ci,ce serait l'électronique qui viendrait au secours dela recherche opérationnelle avec pour ambition derésoudre des problèmes plus gros et de les résoudreplus rapidement. Pour l'instant, ce travail en est àses débuts, mais nous devrions être en mesure dedi�user des premiers résultats très prochainement.Ce nouveau thème fera sans doute l'objet d'un dé-pôt de projet dans les mois à venir.

Des collaborations nationales etinternationales

Contrairement à l'habitude, les collaborationssont d'abord venues du monde entier avant de com-mencer à se répandre en France. Nous travaillonsdepuis longtemps avec la Belgique et l'universitéd'Anvers (Kenneth Sörensen). Par le recrutementde Doctorants (Boureima Zerbo, université de Oua-gadougou au Burkina-Faso et María Soto, Equa-teur), nous avons comencé à tisser des contacts deplus en plus importants. C'est ensuite avec l'Inde(Alok Singh, université d'Hyderabad) puis le Por-tugal (Ana Viana, INESC), et plus récemment avec

Bulletin de la Société Française de Recherche Opérationnelle et d'Aide à la Décision � http://www.roadef.org

ROADEF - Le bulletin - n024 - Printemps - Été 2010 13

le Royaume-Uni (Dario Landa-Silva, université deNottingham) que nous poursuivons nos travaux.En�n, pour ce qui concerne la France, nous di�usonsnos travaux et nous sommes en relation avec Bor-deaux, Gardanne et Grenoble. Nous espérons quecette dynamique ne va pas s'arrêter là. Si vous êtesintéressés par nos problèmes ou s'il existe un moyende collaborer, nous serions enchantés d'agrandirnotre réseau.

Des projets pour l'avenir

Cette activité de recherche opérationnelle estamenée à se développer de plus en plus. Comme

on a pu le voir précédemment, les problèmes nemanquent pas et il reste beaucoup à faire avecla communauté électronique. Comment envisagerl'avenir ? Par des recrutements, c'est sans doute undes pas à franchir dans un horizon de temps assezcourt. Il y a ensuite des possiblités de recruter desdoctorants et des post-doctorants sur des sujets in-novants et importants pour tout le laboratoire. En-�n, l'équipe RO devrait prochainement débuter lemontage d'un projet (ANR ou Européen) avec desperspectives d'embauche pour des ingénieurs et desdoctorants.

Bulletin de la Société Française de Recherche Opérationnelle et d'Aide à la Décision � http://www.roadef.org