Quelle taille de chunk donnera les meilleures performances en utilisant master-worker avec MPI ?

Question

J'utilise MPI pour parrler un programme qui essaie de résoudre le problème Metric TSP. J'ai P processeurs, et N villes à passer.

Chaque fil demande du travail au maître, reçoit un chunk - qui est une gamme de permutation qu'il doit vérifier et calcule le minimum parmi eux. J'optimise cela en élaguant les mauvaises routes à l'avance.

Il y a un total de (N-1) ! routes à calculer. Chaque travailleur reçoit un morceau avec un numéro qui représente la première route qu'il doit vérifier et aussi la dernière. En outre, le maître lui envoie le meilleur résultat connu le plus récent, ce qui lui permet de repousser facilement les mauvaises routes à l'avance avec une certaine limite inférieure sur leurs restes.

Chaque fois qu'un travailleur trouve un résultat meilleur que le global, il l'envoie de manière asynchrone à tous les autres travailleurs et au maître.

Je ne cherche pas une meilleure solution, j'essaie juste de déterminer quelle est la meilleure taille de morceau.

La meilleure taille de morceau que j'ai trouvée jusqu'à présent est (n !)/(n/2) ! mais elle ne donne pas de si bons résultats.

Veuillez m'aider à comprendre quelle est la meilleure taille de morceau ici. J'essaie de trouver un équilibre entre la quantité de calculs et de communications. Merci

Answer 1

Cela dépend fortement de facteurs indépendants de votre volonté : l'implémentation de MPI, la charge totale de la machine, etc. Cependant, je pense que cela dépend aussi fortement du nombre de processus de travail qu'il y a. Sur cette note, comprenez que MPI génère des processus, pas des threads.

En fin de compte, comme c'est souvent le cas pour la plupart des questions d'optimisation, la réponse est simplement "testez de nombreux paramètres différents et voyez lequel est le meilleur". Vous pouvez le faire manuellement ou écrire une application de test qui met en œuvre une sorte d'heuristique (par exemple, un algorithme génétique).