Parallélisation d'insertions dans un graphe
Bonjour tout le monde !
Voici mon problème: j'ai actuellement un programme qui, à partir de données en entrée, construit un graphe. Un deuxième jeu de données est ensuite utilisé pour procéder à des insertions dans ce graphe. Une insertion commence par un noeud, insère des données dans ce noeud et procède à quelques calculs. En fonction du résultat retourné, l'insertion suit une arrête pour aller sur noeud voisin. Ce processus se répète indéfiniment jusqu’à ce que le résultat retourné par un noeud indique que l'insertion doit s’arrêter. L'insertion se fait donc sur un chemin dans le graphe et ne modifie pas la topologie du graphe.
J'aimerais paralléliser les insertions suivant la propriété suivante: je sais de façon certaine que plusieurs insertions, SI elles commencent sur deux noeuds différents, vont emprunter deux chemins différents et vont donc modifier des noeuds différents. En clair, plusieurs insertions peuvent être faites en parallèle à la condition qu'elles commencent sur des noeuds différents.
Mon programme est en C, j'ai une connaissance basique de la programmation parallèle et d'OpenMP. J'avais pensé à modifier mon programme de façon à ce que chaque noeud intègre un sémaphore. De cette façon, je peux lancer en parallèle plusieurs insertions, qui devront attendre éventuellement si elles commencent sur les mêmes noeuds.
Mes questions sont:
- Pensez vous que mon approche de parallélisation soit la bonne ?
- Quelle technologie me conseillerez-vous pour cette implémentation ? OpenMP ? MPI ? Pthread ?
Merci d'avance pour vos réponses et commentaires.
Bonne journée
Répondre avec citation
Je vais me remettre dans OpenMP alors
Partager