Miese Leistung mit MPI
Ich lerne MPI und habe eine Frage zu fast keinem Leistungsgewinn in der folgenden einfachen Implementierung.
#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;
}
Die Ausführungszeiten der obigen Implementierung sind:
$ /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
Das ergibt nur einen Leistungszuwachs von ca. 25%. Ich vermute hier, dass der Engpass durch Prozesse verursacht werden kann, die um den Zugriff auf den Speicher konkurrieren. Dann habe ich dasselbe versucht, aber ohne Speicher zu verwenden, um an Daten zu gelangen.
#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;
}
was die folgenden Ergebnisse ergab:
$ /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
Dies zeigt einen Leistungszuwachs von ca. 83% und würde meine Vermutungen bestätigen. Können Sie mir dann sagen, ob meine Vermutungen richtig sind und ob es Möglichkeiten gibt, die erste Implementierung mit Speicherzugriff zu verbessern?
Der Code wurde auf einem Computer mit 20 physischen Kernen ausgeführt.
EDIT1: zusätzliche Ergebnisse der ersten Implementierung für 2, 5 und 10 Prozesse:
$ /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:
Ich habe MPI_Wtime () gesetzt, um den MPI_Scatter-Teil der ersten Implementierung wie folgt zu messen:
...
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);
...
und bekam die folgenden Ergebnisse:
$ /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
Antworten
Das ergibt nur einen Leistungszuwachs von ca. 25%. Ich vermute hier, dass der Engpass durch Prozesse verursacht werden kann, die um den Zugriff auf den Speicher konkurrieren. (..)
Ihr Code ist hauptsächlich kommunikations- und CPU-gebunden. Darüber hinaus gemäß Ihren Ergebnissen für 2, 5 und 10 Prozesse:
$ /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
Der Code stoppt die Skalierung bereits bei ungefähr fünf Prozessen, was (zu diesem Zeitpunkt) unwahrscheinlich ist, dass die Speicherbreitenbreite gesättigt ist.
Dann habe ich dasselbe versucht, aber ohne Speicher zu verwenden, um an Daten zu gelangen. (..) Dies zeigt einen Leistungszuwachs von ca. 83% und würde meine Vermutungen bestätigen.
Sie haben den MPI_ScatterAnruf aber auch entfernt . Infolgedessen wird der Kommunikationsaufwand reduziert, während im Grunde derselbe parallel auszuführende Arbeitsaufwand beibehalten wird.
Ich habe Ihren Code in meinem Computer profiliert (2 physische Kerne; 4 logische). Um die Zeiten zu messen, verwende ich MPI_Wtime();Folgendes:
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);
}
Für eine Eingabe, die Ihrer entspricht ( dh 2000000000), waren die Ergebnisse:
1 process : 25.158740 seconds
2 processes : 19.116490 seconds
4 processes : 15.971734 seconds
Eine Verbesserung von ca. 40% und die Speicherhierarchie meiner Maschine sollten einer Maschine mit 20 physischen Kernen weit unterlegen sein.
Lassen Sie uns jetzt die Eingabegröße und damit den Speicherbedarf von 2000000000 (8 Gigabyte) auf nur 250000000 (1 Gigabyte) erheblich reduzieren und erneut testen:
1 process : 1.312354 seconds
2 processes : 1.229174 seconds
4 processes : 1.232522 seconds
Eine Verbesserung von rund 6%; Wenn der Engpass die Prozesse wären, die um Speicher konkurrieren, würde ich keine solche Verringerung der Beschleunigung erwarten, nachdem der Speicherbedarf verringert wurde. Nichtsdestotrotz kann diese Verringerung leicht durch die Tatsache erklärt werden, dass ich durch Verringern der Eingabegröße das Verhältnis der Kommunikation pro Berechnung erhöhte .
Kehren wir zu den Tests mit 2000000000 Elementen zurück, aber diesmal messen wir die Zeit, die für die MPI_ScatterKommunikationsroutine aufgewendet wurde (die, die Sie entfernt haben):
2 processes : 7.487354 seconds
4 processes : 8.728969 seconds
Wie man bei 2 und 4 Prozessen sehen kann, wurden ungefähr 40% ( dh 7,487354 / 19,116490) bzw. 54% ( dh 8,728969 / 15,971734) der Anwendungsausführungszeit MPI_Scatterallein aufgewendet . Aus diesem Grund haben Sie beim Entfernen dieser Routine eine Verbesserung der Beschleunigung festgestellt.
Nun der gleiche Test für den Eingang 250000000 (1 Gigabyte):
2 processes ::0.679913 seconds (55% of the time)
4 processes : 0.691987 seconds (56% of the time)
Wie Sie sehen können, MPI_scatterblieb der Overhead selbst bei geringerem Speicherbedarf prozentual ungefähr gleich (für 4 Prozesse). Die Schlussfolgerung ist, dass je mehr Prozesse, desto weniger Berechnungen pro Prozess und folglich auch das Verhältnis der Kommunikation pro Berechnung höher sind - mit Ausnahme anderer Overheads, die bei einer höheren Anzahl laufender Prozesse auftreten können. Darüber hinaus wird in Ihrem Code mit mehr Prozessen die Speichernutzung nicht linear, mit Ausnahme des Hauptprozesses (der die gesamten Daten enthält), bei dem die Reibprozesse die Datenstreuung aufweisen.
In der Regel hat eine gute MPI_scatterImplementierung eine zeitliche Komplexität von O (n log p) , nwobei die Größe der Eingabe und pdie Anzahl der Prozesse angegeben werden. Daher MPI_scattersteigt der Overhead von schneller durch Erhöhen der Eingabegröße als durch Erhöhen der Anzahl von Prozessen, die an dieser Kommunikation beteiligt sind. Durch Erhöhen der Eingabegröße wird jedoch mehr Berechnung pro parallel ausgeführtem Prozess ausgeführt. Wenn Sie jedoch die Anzahl der Prozesse erhöhen, wird weniger Berechnung pro ausgeführtem Prozess durchgeführt.
Beachten Sie jedoch, dass die von mir durchgeführten Tests aufgrund der von mir ausgeführten Umgebung nicht die genauesten sind, die ich jemals ausgeführt habe. Meine MPI-Implementierung kann sich von Ihrer unterscheiden und so weiter. Ich bin jedoch zuversichtlich, dass Sie die gleichen Schlussfolgerungen ziehen werden, wenn Sie dieselben Tests an Ihrem Setup durchführen.