partitionnement graphique rapide pour mpi parallèle

Question

Je ne connais pas encore le partitionnement de graphiques, mais je pense que la question que je pose devrait déjà avoir une bonne réponse. Je veux juste partitionner un énorme réseau (des milliards de nœuds) en quelques sous-graphes. Ainsi, lorsque vous utilisez MPI, chaque sous-graphe est traité par différents processeurs. J'utilise actuellement la représentation de la liste d'adjacence du graphique. quels algorithmes peuvent faire cela? Je vous remercie!

Answer 1

Oui, vous pouvez le faire et il existe plusieurs outils open source disponibles. L'outil que j'utilise le plus souvent est parMETIS.

Il s'agit d'une bibliothèque parallèle basée sur MPI qui fournit une variété de fonctions, y compris le partitionnement de graphiques. La façon dont vous utilisez cette bibliothèque dépend entièrement de votre application. En général, je préfère alimenter parMETIS le graphe d'entrée, obtenir la partition, puis alimenter les partitions en entrée de mes programmes MPI, mais vous pouvez également appeler les fonctions de votre application pour les graphiques qui changent en temps réel.