Nous nous plaçons dans le contexte du mapping de réseaux de processus du
modèle flot de données (Dataflow Process Network ou DPN) sur une
architecture multiprocesseurs parallèles (SMP) interconnectés par un
réseau paquets asynchrone.
Un DPN se modélise par un graphe dont les sommets sont les tâches à placer,
et les arêtes représentent des canaux de communication entre les tâches.
Les sommets sont pondérés par une ou plusieurs quantités représentant des
consommations de ressources processeur (temps CPU, taille mémoire, ...) et
les arêtes sont pondérées par un débit de communication inter-tâches.
L'objectif de notre problème consiste alors à placer les sommets du graphe
de tâches sur les différents SMP de l'architecture, de sorte à maximiser la
communication entre tâches à l'intérieur des SMP, en minimisant la
communication sur le réseau, représentée par le produit du débit inter-tâches par
la distance sur les réseaux inter-SMP.
Cette opération se fait sous des contraintes de capacité en termes
d'occupation de ressources par les tâches sur les SMP.
Dans le cas d'une seule ressource processeur, notre problème se réduit à un
problème d'affectation quadratique généralisé (GQAP) qui est NP-difficile au
sens fort.

Les méthodes généralement rencontrées pour le placement de tâches répondent
le plus souvent au problème d'équilibrage de charges inter-processeurs. Les
méthodes de résolution du GQAP se placent dans le contexte de la résolution
exacte d'instances de taille relativement faible. Notre objectif est la
résolution approchée d'instances de grande taille (placement de plusieurs
dizaines de milliers de tâches sur quelques centaines de SMP). Les solutions
pourront paraître déséquilibrées au sens de l'équilibrage de charge puisque
nos seules contraintes sont des contraintes de capacité sur les processeurs.

Dans cet exposé, nous détaillons une heuristique parallèle qui se base sur des
échanges locaux de tâches entre paires de SMP, de manière asynchrone à la
méthode de Kernighan-Lin. Elle fait usage de plusieurs partitionnements par
paires de SMP de la topologie cible. L'utilisation successive de ces
partitionnements assure la possibilité pour chaque tâche de se déplacer dans
les différents SMP du réseau, et permet la convergence vers une solution
globale acceptable. De plus, les échanges par paires de processeurs offrent
un fort potentiel de parallélisation.