Activités de recherche

Parallélisme

Etude d'algorithmes de tri pour une grille de calcul et problématique du  stockage à grande échelle.

Au cours des dernières années, notre travail a consisté à réviser les algorithmes de tri parallèles basés sur le principe de l'échantillonnage, en les adaptant à des environnements hétérogènes afin de les raffiner et en tenant compte de nouveaux facteurs.

Les algorithmes concernés consistent essentiellement à échanger les données entre les processeurs, à partir d'une distribution initiale, puis à effectuer  une phase de tri local sur les différents processeurs. Le but est d'arriver à minimiser le temps d'exécution global. Nous avons traité en  particulier le cas d'une exécution sur une plate-forme constituée de processeurs hétérogènes ayant des vitesses différentes. L'idée, ici, est de faire faire trier les processeurs des quantités de données ajustées à leurs vitesses respectives. Ace propos, nous avons élaboré un schéma de partitionnement de données qui permet de partitionner des données aléatoires suivant des facteurs respectant la proportionnalité des vitesses des processeurs.

Afin de raffiner l'équilibrage des charges dans cette première solution, nous avons proposé de tenir compte de la complexité du tri séquentiel. Ainsi, le schéma de partitionnement devient plus réaliste. La prise en compte de la complexité permet aussi de généraliser le schéma de partitionnement pour d'autres applications parallèles. De cette manière, il sera possible  de  paramétrer le schéma de partitionnement suivant la complexité de la tâche à exécuter en parallèle.

Sur un autre plan, nous projetons  de tenir compte des temps de communication entre les processeurs. Cela permettra de mieux estimer le temps d'exécution réel. Pour cela, il faudra déterminer le degré de mobilité des données afin de trouver un compromis entre l'équilibrage des charges, d'une part, et la minimisation des communications d'autre part.

Les résultats obtenus au cours de la période écoulée ont fait l'objet de plusieurs publications dont deux dans des journaux.

Conception et élaboration d'algorithmes parallèles embarqués pour le traitement d'images 

Le traitement numérique du son, de l'image et de la vidéo et l'un des domaines les plus consommateurs de temps de calcul et d'espace de stockage. En effet, ce domaine utilise d'énorme quantité d'information sous la forme de matrices pluridimensionnelles nécessitent de multiples traitements. Avec tout ceci, vient s'ajouter le problème de consommation d'énergie puisque les processeurs dédiés, comme les DSP (Digital Signal Processors), sont généralement très gourmands en énergie et par conséquent chauffent rapidement ce qui leur donne un taux de fiabilité assez bas.

A ce propos, la compression par Ondelettes est l'une des méthodes les plus avancées pour l'analyse des signaux, qu'il s'agisse d'images ou de son, on trouve le concept de schéma itératif (c'est-à-dire la répétition sans fin d'une même opération) à des échelles de plus en plus petites. La technique des Ondelettes consiste en la décomposition d'un signal par une Ondelette mère qui sera déplacée (le long de l'axe des temps) et dilatée.

Cependant, bien que les algorithmes de transformation par Ondelettes aient une complexité proportionnelle à la taille du problème, le temps d'exécution peut être très élevé.  L'utilisation des machines parallèles constitue une alternative intéressante qui permet d'accélérer le temps de traitement et d'ouvrir de nouvelles perspectives.

Dans ce contexte, l'objectif de notre travail est de concevoir une solution parallèle (pour l'accélération des algorithmes de traitement d'images), pouvant disposer facilement d'assez grandes mémoires (pour les applications en temps réels), peu gourmande en énergie (pour une utilisation intensive) et se déployant sur une architecture de petite taille pour être exploitable par le grand public.

Activités de recherche