Liste des thèmes présentés :

Problèmes d'ordonnancement : Dans cet exposé nous allons présenter quelques résultats classiques d'ordonnanceement avec prise en compte des délais de communications. L'utilisation du parallélisme pour le traitement des applications de grande taille qui réclament une puissance de calcul de plus en plus importante est aujourd'hui une réalité. Néanmoins, les puissances de calcul théoriques des machines parallèles ne sont, en pratique, jamais atteintes. Ceci est dû principalement aux difficultés liées à la gestion des ressources et des contraintes de fonctionnement des architectures multiprocesseurs. Parmi les difficultés que l'on rencontre, on peut citer l'étape d'extraction du parallélisme intrinsèque d'une application ou les problèmes de routage et d'ordonnancement des communications entre les différents processeurs de l'architecture.

Pour tenter de pallier la première difficulté, une phase de partitionnement est nécessaire. Elle correspond à la première étape fondamentale de la parallélisation et consiste en l'extraction du parallélisme potentiel d'une application.

L'extraction du parallélisme détermine les dépendances fonctionnelles entre les parties de l'application. Ainsi, une application parallèle peut être représentée sous forme d'un graphe orienté sans cycle (graphe de précédence) où chaque sommet du graphe représente une partie (instruction ou ensemble d'instructions) du programme et les arcs les contraintes chronologiques entre ces parties (dites aussi contraintes de précédence). Dans le modèle avec communications homogènes [2], nous pouvons distinguer deux types de communications :

• les communications intra-processeurs : ce sont les communications entre deux tâches adjacentes dans le graphe de précédence, qui s'exécutent sur le même processeur (en respectant les contraintes de précédence). Nous supposerons ces délais négligeables.

• les communications inter-processeurs : ce sont les communications entre deux tâches adjacentes dans le graphe de précédence qui s'exécutent sur des processeurs différents.

Formellement, nous considérons un graphe orienté sans cycle avec l'ensemble des sommets et l'ensemble des arcs. Chaque tâche a une durée d'exécution de et à chaque arc est associé un délais de communications . Soit (resp. ) la date de début d'exécution de la tâche (resp. ), alors si et sont exécutées sur le même processeur alors nous avons , sinon si elles sont exécutées sur des processeurs différents, nous avons . Nous allons présenter quelques résultats de compléxité (NP-complétude, et borne de non-approximabilité) et nous des algorithmes approchés avec garantie de performances non triviale. Nous verrons les extensions de ces résultats dans d'autres modèles d'ordonnancement.

Problèmes algorithmiques dans les réseaux du futur.

Nous étudions des problèmes algorithmiques inspirés du fonctionnement des nouveaux réseaux de communication. Nous présenterons deux de ces problèmes qui s'avèrent être NP difficiles et non approximables à un facteur constant près par des algorithmes polynomiaux (sauf si P=NP). Mais dans certaines circonstances (restriction à des topologies de réseaux ou des routages spécifiques), la complexité de ces problèmes bascule parfois...

Dans les réseaux tout-optique, une collection de routes de communication étant donnée, on cherche à affecter une fréquence à chaque route de communication de sorte que deux routes qui partagent un même lien du réseau n'aient pas la même fréquence et que le nombre de fréquences utilisées soit le plus petit possible. Nous montrerons par exemple un algorithme glouton (polynomial et exact) pour le cas des réseaux linéaires... qui a inspiré un algorithme approchant pour le cas des routages ligne-colonnes dans des grilles.

Nous présenterons également le problème DAWN (Date Assignment in Wireless Network) inspiré du fonctionnement des réseaux sans fil et dont l'ensemble des instances est le même que celui du problème de coloration de routes...