Performances minables avec MPI
J'apprends MPI et j'ai une question sur presque aucun gain de performance dans la mise en œuvre simple ci-dessous.
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
int main(int argc, char **argv)
{
int mpirank, mpisize;
int tabsize = atoi(*(argv + 1));
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &mpirank);
MPI_Comm_size(MPI_COMM_WORLD, &mpisize);
unsigned long int sum = 0;
int rcvsize = tabsize / mpisize;
int *rcvbuf = malloc(rcvsize * sizeof(int));
int *tab = malloc(tabsize * sizeof(int));
int totalsum = 0;
if(mpirank == 0){
for(int i=0; i < tabsize; i++){
*(tab + i) = 1;
}
}
MPI_Scatter(tab, tabsize/mpisize, MPI_INT, rcvbuf, tabsize/mpisize, MPI_INT, 0, MPI_COMM_WORLD);
for(int i=0; i < tabsize/mpisize; i++){
sum += *(rcvbuf + i);
}
MPI_Reduce(&sum, &totalsum, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
if(mpirank == 0){
printf("The totalsum = %li\n", totalsum);
}
MPI_Finalize();
return 0;
}
Les délais d'exécution de la mise en œuvre ci-dessus sont:
$ /usr/bin/time mpirun -np 1 test1 2000000000 The totalsum = 2000000000 13.76user 3.31system 0:17.30elapsed 98%CPU (0avgtext+0avgdata 15629824maxresident)k 0inputs+8outputs (0major+21720minor)pagefaults 0swaps $ /usr/bin/time mpirun -np 1 test1 2000000000
The totalsum = 2000000000
13.78user 3.29system 0:17.31elapsed 98%CPU (0avgtext+0avgdata 15629824maxresident)k 0inputs+8outputs (0major+21717minor)pagefaults 0swaps
$ /usr/bin/time mpirun -np 1 test1 2000000000 The totalsum = 2000000000 13.78user 3.32system 0:17.33elapsed 98%CPU (0avgtext+0avgdata 15629828maxresident)k 0inputs+8outputs (0major+20697minor)pagefaults 0swaps $ /usr/bin/time mpirun -np 20 test1 2000000000
The totalsum = 2000000000
218.42user 6.10system 0:12.99elapsed 1727%CPU (0avgtext+0avgdata 8209484maxresident)k 0inputs+17400outputs (118major+82587minor)pagefaults 0swaps
$ /usr/bin/time mpirun -np 20 test1 2000000000 The totalsum = 2000000000 216.17user 6.37system 0:12.89elapsed 1726%CPU (0avgtext+0avgdata 8209488maxresident)k 0inputs+17168outputs (126major+81092minor)pagefaults 0swaps $ /usr/bin/time mpirun -np 20 test1 2000000000
The totalsum = 2000000000
216.16user 6.09system 0:12.88elapsed 1724%CPU (0avgtext+0avgdata 8209492maxresident)k 0inputs+17192outputs (111major+81665minor)pagefaults 0swaps
Ce qui ne donne qu'un gain de performances d'environ 25%. Je suppose ici que le goulot d'étranglement peut être causé par des processus qui se font concurrence pour accéder à la mémoire. Ensuite, j'ai essayé la même chose mais sans utiliser la mémoire pour accéder aux données.
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
int main(int argc, char **argv)
{
int mpirank, mpisize;
int tabsize = atoi(*(argv + 1));
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &mpirank);
MPI_Comm_size(MPI_COMM_WORLD, &mpisize);
unsigned long int sum = 0;
for(int i=0; i < tabsize/mpisize; i++){
sum += 1;
}
MPI_Reduce(&sum, &totalsum, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
if(mpirank == 0){
printf("The totalsum = %li\n", totalsum);
}
MPI_Finalize();
return 0;
}
qui a donné les résultats suivants:
$ /usr/bin/time mpirun -np 1 test2 2000000000 The totalsum = 2000000000 6.17user 0.11system 0:06.49elapsed 96%CPU (0avgtext+0avgdata 5660maxresident)k 0inputs+8outputs (0major+4005minor)pagefaults 0swaps $ /usr/bin/time mpirun -np 1 test2 2000000000
The totalsum = 2000000000
6.16user 0.12system 0:06.49elapsed 96%CPU (0avgtext+0avgdata 5660maxresident)k 0inputs+8outputs (0major+4007minor)pagefaults 0swaps
$ /usr/bin/time mpirun -np 1 test2 2000000000 The totalsum = 2000000000 6.15user 0.11system 0:06.47elapsed 96%CPU (0avgtext+0avgdata 5664maxresident)k 0inputs+8outputs (0major+4005minor)pagefaults 0swaps $ /usr/bin/time mpirun -np 20 test2 2000000000
The totalsum = 2000000000
8.67user 2.41system 0:01.06elapsed 1040%CPU (0avgtext+0avgdata 6020maxresident)k 0inputs+16824outputs (128major+49952minor)pagefaults 0swaps
$ /usr/bin/time mpirun -np 20 test2 2000000000 The totalsum = 2000000000 8.59user 2.74system 0:01.05elapsed 1076%CPU (0avgtext+0avgdata 6028maxresident)k 0inputs+16792outputs (131major+49960minor)pagefaults 0swaps $ /usr/bin/time mpirun -np 20 test2 2000000000
The totalsum = 2000000000
8.65user 2.61system 0:01.06elapsed 1058%CPU (0avgtext+0avgdata 6024maxresident)k 0inputs+16792outputs (116major+50002minor)pagefaults 0swaps
Cela montre un gain de performance d'environ 83% et confirmerait mes suppositions. Alors pourriez-vous me dire si mes suppositions sont correctes et si oui, y a-t-il des moyens d'améliorer la première implémentation avec un accès mémoire?
Le code a été exécuté sur une machine avec 20 cœurs physiques.
EDIT1: résultats supplémentaires de la première implémentation pour les processus 2, 5 et 10:
$ /usr/bin/time mpirun -np 2 test1 2000000000 The totalsum = 2000000000 24.05user 3.40system 0:14.03elapsed 195%CPU (0avgtext+0avgdata 11724552maxresident)k 0inputs+960outputs (6major+23195minor)pagefaults 0swaps $ /usr/bin/time mpirun -np 5 test1 2000000000
The totalsum = 2000000000
55.27user 3.54system 0:12.88elapsed 456%CPU (0avgtext+0avgdata 9381132maxresident)k 0inputs+4512outputs (26major+31614minor)pagefaults 0swaps
$ /usr/bin/time mpirun -np 10 test1 2000000000
The totalsum = 2000000000
106.43user 4.07system 0:12.44elapsed 887%CPU (0avgtext+0avgdata 8599952maxresident)k 0inputs+8720outputs (51major+50059minor)pagefaults 0swaps
EDIT2:
J'ai mis MPI_Wtime () pour mesurer la partie MPI_Scatter de la première implémentation comme suit:
...
for(int i=0; i < tabsize; i++){
*(tab + i) = 1;
}
}
MPI_Barrier(MPI_COMM_WORLD);
double start = MPI_Wtime();
MPI_Scatter(tab, tabsize/mpisize, MPI_INT, rcvbuf, tabsize/mpisize, MPI_INT, 0, MPI_COMM_WORLD);
MPI_Barrier(MPI_COMM_WORLD);
double end = MPI_Wtime();
for(int i=0; i < tabsize/mpisize; i++){
sum += *(rcvbuf + i);
...
et a obtenu les résultats suivants:
$ /usr/bin/time mpirun -np 1 test1 400000000
The MPI_Scatter time = 0.576 (14% of total)
3.13user 0.74system 0:04.08elapsed 95%CPU
$ /usr/bin/time mpirun -np 2 test1 400000000 The MPI_Scatter time = 0.580 (18% of total) 5.19user 0.79system 0:03.25elapsed 183%CPU $ /usr/bin/time mpirun -np 4 test1 400000000
The MPI_Scatter time = 0.693 (22.5% of total)
9.99user 1.05system 0:03.07elapsed 360%CPU
$ /usr/bin/time mpirun -np 5 test1 400000000 The MPI_Scatter time = 0.669 (22.3% of total) 12.41user 1.01system 0:03.00elapsed 446%CPU $ /usr/bin/time mpirun -np 8 test1 400000000
The MPI_Scatter time = 0.696 (23.7% of total)
19.67user 1.25system 0:02.95elapsed 709%CPU
$ /usr/bin/time mpirun -np 10 test1 400000000 The MPI_Scatter time = 0.701 (24% of total) 24.21user 1.45system 0:02.92elapsed 876%CPU $ /usr/bin/time mpirun -np 1 test1 1000000000
The MPI_Scatter time = 1.434 (15% of total)
7.64user 1.71system 0:09.57elapsed 97%CPU
$ /usr/bin/time mpirun -np 2 test1 1000000000 The MPI_Scatter time = 1.441 (19% of total) 12.72user 1.75system 0:07.52elapsed 192%CPU $ /usr/bin/time mpirun -np 4 test1 1000000000
The MPI_Scatter time = 1.710 (25% of total)
24.16user 1.93system 0:06.84elapsed 381%CPU
$ /usr/bin/time mpirun -np 5 test1 1000000000 The MPI_Scatter time = 1.675 (25% of total) 30.29user 2.10system 0:06.81elapsed 475%CPU $ /usr/bin/time mpirun -np 10 test1 1000000000
The MPI_Scatter time = 1.753 (26.6% of total)
59.89user 2.47system 0:06.60elapsed 943%CPU
$ /usr/bin/time mpirun -np 10 test1 100000000 The MPI_Scatter time = 0.182 (15.8% of total) 6.75user 1.07system 0:01.15elapsed 679%CPU $ /usr/bin/time mpirun -np 10 test1 200000000
The MPI_Scatter time = 0.354 (20% of total)
12.50user 1.12system 0:01.71elapsed 796%CPU
$ /usr/bin/time mpirun -np 10 test1 300000000 The MPI_Scatter time = 0.533 (22.8% of total) 18.54user 1.30system 0:02.33elapsed 849%CPU $ /usr/bin/time mpirun -np 10 test1 400000000
The MPI_Scatter time = 0.702 (23.95% of total)
24.38user 1.37system 0:02.93elapsed 879%CPU
$ /usr/bin/time mpirun -np 10 test1 1000000000
The MPI_Scatter time = 1.762 (26% of total)
60.17user 2.42system 0:06.62elapsed 944%CPU
Réponses
Ce qui ne donne qu'un gain de performances d'environ 25%. Je suppose ici que le goulot d'étranglement peut être causé par des processus qui se font concurrence pour accéder à la mémoire. (..)
Votre code est principalement lié à la communication et au processeur. De plus, selon vos résultats pour 2, 5 et 10 processus:
$ /usr/bin/time mpirun -np 2 test1 2000000000 The totalsum = 2000000000 24.05user 3.40system 0:14.03elapsed 195%CPU (0avgtext+0avgdata 11724552maxresident)k 0inputs+960outputs (6major+23195minor)pagefaults 0swaps $ /usr/bin/time mpirun -np 5 test1 2000000000
The totalsum = 2000000000
55.27user 3.54system 0:12.88elapsed 456%CPU (0avgtext+0avgdata 9381132maxresident)k 0inputs+4512outputs (26major+31614minor)pagefaults 0swaps
$ /usr/bin/time mpirun -np 10 test1 2000000000
The totalsum = 2000000000
106.43user 4.07system 0:12.44elapsed 887%CPU (0avgtext+0avgdata 8599952maxresident)k 0inputs+8720outputs (51major+50059minor)pagefaults 0swaps
Le code arrête déjà la mise à l'échelle à environ cinq processus, peu probable (à ce stade) pour que la largeur de la limite de la mémoire soit saturée.
Ensuite, j'ai essayé la même chose mais sans utiliser la mémoire pour accéder aux données. (..) Cela montre un gain de performance d'environ 83% et confirmerait mes suppositions.
Mais vous avez également supprimé l' MPI_Scatterappel. Par conséquent, réduire la surcharge de communication, tout en conservant fondamentalement la même quantité de travail à effectuer en parallèle.
J'ai profilé votre code dans ma machine (2 cœurs physiques; 4 logiques). Pour mesurer les temps, j'utilise MPI_Wtime();comme suit:
int main(int argc, char **argv)
{
int mpirank, mpisize;
int tabsize = atoi(*(argv + 1));
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &mpirank);
MPI_Comm_size(MPI_COMM_WORLD, &mpisize);
MPI_Barrier(MPI_COMM_WORLD);
double start = MPI_Wtime();
...
if(mpirank == 0){
printf("The totalsum = %li\n", totalsum);
}
MPI_Barrier(MPI_COMM_WORLD);
double end = MPI_Wtime();
if(mpirank == 0)
printf("Time:%f\n",end-start);
}
pour une entrée égale à la vôtre ( c'est-à-dire 2000000000), les résultats étaient:
1 process : 25.158740 seconds
2 processes : 19.116490 seconds
4 processes : 15.971734 seconds
Une amélioration d'environ 40% et la hiérarchie mémoire de ma machine devraient être bien inférieures à une machine avec 20 cœurs physiques.
Réduisons maintenant considérablement la taille d'entrée, réduisant ainsi l'empreinte mémoire, de 2000000000 (8 gigaoctets) à seulement 250000000 (1 gigaoctets), et retestons à nouveau:
1 process : 1.312354 seconds
2 processes : 1.229174 seconds
4 processes : 1.232522 seconds
Une amélioration d'environ 6%; Si le goulot d'étranglement était les processus en compétition pour la mémoire, je ne m'attendrais pas à une telle réduction des accélérations après réduction de l'empreinte mémoire. Néanmoins, cette réduction peut être facilement expliquée par le fait qu'en réduisant la taille d'entrée j'ai augmenté le rapport de communication par calcul.
Revenons aux tests avec 2000000000 éléments mais cette fois en mesurant le temps passé sur la MPI_Scatterroutine de communication (celle que vous avez supprimée):
2 processes : 7.487354 seconds
4 processes : 8.728969 seconds
Comme on peut le voir avec 2 et 4 processus, environ 40% ( soit 7,487354 / 19,116490) et 54% ( soit 8,728969 / 15,971734) du temps d'exécution de l'application ont été respectivement consacrés au MPI_Scatterseul. C'est pourquoi, lorsque vous avez supprimé cette routine, vous avez remarqué une amélioration de l'accélération.
Maintenant, le même test pour l'entrée 250000000 (1 gigaoctets):
2 processes ::0.679913 seconds (55% of the time)
4 processes : 0.691987 seconds (56% of the time)
Comme vous pouvez le voir, même avec une empreinte mémoire plus petite, la surcharge du MPI_scatterpourcentage est restée à peu près la même (pour 4 processus). La conclusion est que plus il y a de processus, moins il y a de calculs par processus et, par conséquent, plus le ratio de communication par calcul est élevé - à l'exclusion des autres frais généraux qui pourraient apparaître avec un plus grand nombre de processus en cours d'exécution. De plus, dans votre code, avec plus de processus, l'utilisation de la mémoire ne devient pas linéaire, sauf pour le processus principal (qui contient toutes les données), les processus d'alésage auront les données dispersées entre eux.
En règle générale, une bonne MPI_scatterimplémentation aura une complexité temporelle de O (n log p) , nétant la taille de l'entrée et ple nombre de processus. Par conséquent, la surcharge du MPI_scatteraugmentera plus rapidement en augmentant la taille d'entrée puis en augmentant le nombre de processus impliqués sur cette communication. Cependant, en augmentant la taille d'entrée, vous avez plus de calculs par processus exécuté en parallèle, tandis que si vous augmentez le nombre de processus, vous aurez moins de calculs par processus en cours d'exécution.
Gardez à l'esprit, cependant, que les tests que j'ai effectués ne sont pas les plus précis qui soient, à cause de l'environnement que j'exécute, mon implémentation MPI peut différer de la vôtre, et ainsi de suite. Néanmoins, je suis convaincu que si vous effectuez les mêmes tests sur votre configuration, vous en tirerez les mêmes conclusions.