Journée "Optimisation pour les Systèmes Intégrés"

Voici le programme de la journée du Groupe de Travail "Optimisation pour les Systèmes Intégrés"

le 11 Juin au CEA LIST à Paris Saclay (voir plan ci joint),

consacrée à l'utilisation de la recherche opérationnelle pour la conception de circuit et l'électronique au sens large.

La participation à la journée est gratuite, mais l'inscription est obligatoire pour des raisons d'organisation (en particulier pour le repas de midi).  Pour vous inscrire, il suffit de répondre à ce mail (seulement à lilia.zaourar@cea.fr). Nous espérons vous accueillir nombreux le 11 juin prochain !

PROGRAMME DE LA MATINEE (10h30 - 12h00)

10h00-10h30 : Lilia Zaourar (CEA LIST LCE) : Accueil des participants et introduction à la journée.

10h30-11h : François Galéa (CEA LIST LCE)

Titre de l'exposé : Placement d'Applications en Flot de Données statiques.

Résumé :  Le modèle de programmation de flot de données statique intervient dans la programmation de puces massivement parallèles pour l'embarqué, connues sous l'appellation de « processeurs manycore ». Ces puces sont constituées de grappes (ou clusters) de cœurs à mémoire locale partagée, l'interconnexion entre ces clusters étant assurée par un réseau sur puce. Cette complexité apparente est cachée au programmeur par le modèle de programmation, qui consiste à décrire l'application sous la forme de tâches élémentaires à exécution cyclique, interconnectées entre elles par des liens de transfert de données FIFO. L'efficacité de l'exécution dépend fortement de la façon dont sont placées les tâches dans les différents clusters, ce qui fait que la tâche de placement effectuée à la compilation est une étape cruciale dans l'efficacité d'exécution de l'application sur l'architecture cible. Cette présentation exposera le problème de placement étudié, ainsi qu'une palette de solutions algorithmiques apportées au CEA dans le cadre et autour de la chaîne de programmation flot de données cyclostatique ΣC.

11h- 11h30 :  Omar Hammami  (ENSTA PARISTECH)

Titre de l'exposé : MPSOCEXPLORER: Automatic Multiobjective Design Space Exploration of Large Scale Manycore with Direct Execution on Large Scale FPGA Platforms.

Résumé : In this talk, we describe the MPSOCEXPLORER platform for the automatic multiobjective design space exploration of large scale manycore with direct execution on large scale FPGA platforms. Simulation based design space exploration (e.g. TLM/ISS) suffers from excessive simulation time - the simulation wall - when adressing large scale manycore architectures and from a lack of physical implementation information (e.g. actual multi-clock post place and route).Actual implementation on large scale FPGA platform allows fast execution and evaluation of architectures configurations with proper physical information. We describe the MPSOCEXPLORER flow and the operations research issues tackled and 2 NOC Based 2400 and  4096 PE executable manycore on Zebu (Synopsys) platforms.

11h30-12h  : Ahcene Bounceur (Lab-STICC)

Titre de l'exposé : Trouver l'enveloppe polygonale d'un réseau de capteurs sans fil.

Résumé : Trouver la frontière d'un réseau de capteurs sans fil (RCSF) fait partie des problématiques les plus importantes aujourd'hui. Cette frontière peut être utilisée, par exemple, pour surveiller une frontière, un endroit sécurisé ou un site sensible d'un pays. Une des méthodes qui peut être utile pour ce type de problèmes est l'algorithme de Jarvis, qui doit être adaptée pour tenir compte des nœuds connectés dans un graphe Euclidien. Pour ce type de réseaux, la complexité est réduite de O(nh) à O(kh2), où n est le nombre de capteurs, k est le nombre maximum de voisins d'un capteur dans le réseau et h est le nombre des capteurs de la frontière. L'application de cet algorithme pour les réseaux de capteurs permet à chaque itération de déterminer le nœud frontière voisin du nœud frontière courant. L'avantage de cette procédure est que chaque nœud connaît son voisin en une seule itération. Ensuite, chaque nœud envoie périodiquement un message à son voisin, qui devrait répondre. Si aucune réponse n'est reçue, une situation de défaillance ou d'intrusion sera déclenchée et la restructuration du réseau sera lancé pour trouver une nouvelle frontière. Dans ce travail, nous avons montré que l'application de cet algorithme en présence de sous-graphes spécifiques peut conduire à une situation de boucle infinie. Nous avons également montré comment surmonter cette situation et comment l'algorithme peut être appliqué au cas des RCSFs.

Déjeuner

PROGRAMME DE L'APRES-MIDI (14h00 - 16h00)

14h-14h30 Pascal Aubry  (CEA LIST L3S)

Titre de l'exposé : Une méthode approchée pour l'évaluation du débit et de la taille mémoire dans les programmes dataflow cyclostatique.

Résumé : Grâce à la multiplication des architectures multicoeurs, les languages de programmation orientés flot de données ont connu un regain d'intérêt ces dernières années. Dans le cadre d'architectures embarquées massivement multicoeurs, le calcul de l'empreinte mémoire en maintenant les performances est primordial.

Cette présentation introduit une méthode approchée pour l'évaluation du débit et l'évaluation des tailles  de tampons dans le cadre des graphes flots de donnée cyclo-statique.

14h30-15h Youen Lesparre (UPMC LIP6)

Titre de l'exposé : Mapping d'une application de flux avec minimisation de la mémoire sous contrainte de débit pour une architecture à mémoire distribuée.

Résumé : Mapper de manière efficace une application sur une architecture parallèle est un des grands problèmes de cette décennie. Cette présentation introduit une nouvelle approche pour une application modélisée à l'aide du modèle Synchronous Dataflow (SDF en abrégé). Notre approche minimise la mémoire nécessaire aux communications entre les unités de calcul de l'architecture parallèle et évalue le débit périodique à l'aide d'algorithmes polynomiaux. L'architecture visée est composée de plusieurs clusters de n processeurs et d'une mémoire distribuée limitée.

Nous avons développé un algorithme polynomial qui permet d'évaluer la quantité de mémoire nécessaire aux communications entre les clusters pour un mapping donné. Cette quantité garantie la vivacité et/ou un débit minimum de l'application. Le problème général de mapping est alors modélisé par un Programme Linéaire en Nombre Entier (PLNE).

Nous avons utilisé le solveur Gurobi pour résoudre exactement le problème de mapping pour des instances de quelques centaines d'acteurs et 4 clusters. Nous avons développé une heuristique inspirée de l'algorithme de Fiduccia-Mattheyses pour des instances plus importantes. Les deux approches sont évaluées et comparées sur un ensemble d'applications générées aléatoirement et trois application réelles. Nous terminerons sur quelques perspectives.

15h-15h30 Jad Khatib (CEA LIST LCE/ UPMC LIP6 )

Titre de l'exposé : Synchronous DataFlow Graphs avec latence.

Résumé : Le but de notre travail est d'utiliser les Synchronous DataFlow Graphs pour modéliser des applications temps-réels.

Deux types de contraintes sont à considérer. D'une part, les contraintes de précédence entre les exécutions successives de deux acteurs adjacents reliés par un buffer. D'autre part, il faut pouvoir garantir un temps de réponse du système.

Nous avons démontré que le problème posé est équivalent à un problème de plus court/long chemin dans un graphe orienté acyclique. Nous avons également proposé plusieurs simplifications locales pour accélérer l'exécution des algorithmes de calcul de chemin.

Cette étude nous a permis de caractériser le nombre d'itérations maximal et minimal pour qu'une donnée se déplace depuis un acteur en entrée jusqu'à un acteur en sortie du SDFG.

15h30-16h Session de problèmes & Clôture de la journée (perspectives, vie du groupe, organisation de la prochaine journée).