Algoritm som går snabbare att köra på 3 processer än 4?? (MPI)
Som ett projektarbete i skolan har jag och en klasskompis knåpat ihop ett cluster som för närvarande består av ett par Raspberry Pi's och en ZedBoard. Det var i samband med att jag satte up ZB'n som jag upptäckte ett ganska oväntat resultat. Vi har använt oss av MPI (med hydra) för att fördela arbetet över clustret. MPI är ganska smidigt då det går att ställa in exakt hur många processer varje nod ska ha, så med tanke på att ZB'n har dual core tänkte jag mäta lokalt där och se hur stor skillnad det blev när man delade upp arbetet på båda kärnorna i stället för en. Hur mycket snabbare skulle det gå?
Fenomenet som uppstår är att 1 och 2 processer tar lika lång tid. Kör man 3 processer går det lite snabbare, 4 ~samma som 1 och 2, 5 lite snabbare än 3...? och sådär fortsätter det. När det är jämt antal processer, ökar tiden och när det är udda minskar den?
Jag misstänker att svaret ligger i processhanteraren eller i den algoritm som vi använt men jag är tydligen för dum för att förstå varför det blir som det blir. Man tycker att all logik pekar på att det borde gå fortare att göra en iteration i en process på en kärna? I alla fall inte snabbare med just ett udda antal processer.
Jag har tittat i "top" och när man kör en process använder den 100% av en kärna, 50% totalt och 100% på två kärnor, 100% totalt om man kör på 2 processer osv. Zedboarden har en ARM dual core och kör Linux (Ubuntu), om det spelar någon roll?
Någon som har några tips?
Algortimen räknar antalet primtal mellan 1 och N och visar resultatet mellan varje kvadrat och finns att beskåda här: http://people.sc.fsu.edu/~jburkardt/c_src/prime_mpi/prime_mpi...
Loggen för 1-15 processer finns att beskåda här:
06 May 2013 03:03:46 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 1
N Pi Time
1 0 0.000074
2 1 0.000018
4 2 0.000019
8 4 0.000018
16 6 0.000019
32 11 0.000018
64 18 0.000037
128 31 0.000147
256 54 0.000461
512 97 0.001678
1024 172 0.006156
2048 309 0.020920
4096 564 0.076788
8192 1028 0.283449
16384 1900 1.043555
32768 3512 3.838589
65536 6542 14.345917
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:04:06 PM
06 May 2013 03:04:06 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 2
N Pi Time
1 0 0.000111
2 1 0.000018
4 2 0.000018
8 4 0.000018
16 6 0.000019
32 11 0.000018
64 18 0.000055
128 31 0.000129
256 54 0.000461
512 97 0.001659
1024 172 0.005806
2048 309 0.021068
4096 564 0.081120
8192 1028 0.283118
16384 1900 1.054062
32768 3512 3.898973
65536 6542 14.572392
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:04:26 PM
06 May 2013 03:04:26 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 3
N Pi Time
1 0 0.019409
2 1 0.019925
4 2 0.019962
8 4 0.019981
16 6 0.019962
32 11 0.019981
64 18 0.019980
128 31 0.019962
256 54 0.019980
512 97 0.019980
1024 172 0.019980
2048 309 0.039980
4096 564 0.079996
8192 1028 0.291966
16384 1900 1.035703
32768 3512 3.881942
65536 6542 13.177963
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:04:45 PM
06 May 2013 03:04:45 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 4
N Pi Time
1 0 0.019594
2 1 0.039906
4 2 0.019980
8 4 0.019980
16 6 0.019980
32 11 0.019981
64 18 0.019981
128 31 0.019981
256 54 0.019981
512 97 0.019981
1024 172 0.019980
2048 309 0.059960
4096 564 0.099976
8192 1028 0.299983
16384 1900 1.119975
32768 3512 3.879969
65536 6542 14.559988
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:05:05 PM
06 May 2013 03:05:05 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 5
N Pi Time
1 0 0.032127
2 1 0.057305
4 2 0.029971
8 4 0.029971
16 6 0.019999
32 11 0.039961
64 18 0.039979
128 31 0.039980
256 54 0.059960
512 97 0.039961
1024 172 0.039979
2048 309 0.059978
4096 564 0.082023
8192 1028 0.217905
16384 1900 0.880873
32768 3512 3.027501
65536 6542 11.271543
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:05:21 PM
06 May 2013 03:05:22 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 6
N Pi Time
1 0 0.029491
2 1 0.029915
4 2 0.029971
8 4 0.029971
16 6 0.029971
32 11 0.029971
64 18 0.029989
128 31 0.029933
256 54 0.029971
512 97 0.059979
1024 172 0.029970
2048 309 0.119975
4096 564 0.119957
8192 1028 0.449966
16384 1900 1.619965
32768 3512 5.849962
65536 6542 21.539970
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:05:52 PM
06 May 2013 03:05:52 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 7
N Pi Time
1 0 0.059646
2 1 0.099902
4 2 0.079959
8 4 0.079959
16 6 0.079977
32 11 0.099995
64 18 0.119938
128 31 0.089968
256 54 0.059960
512 97 0.059997
1024 172 0.089930
2048 309 0.059978
4096 564 0.089986
8192 1028 0.299946
16384 1900 0.749968
32768 3512 2.709970
65536 6542 9.089949
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:06:06 PM
06 May 2013 03:06:06 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 8
N Pi Time
1 0 0.079480
2 1 0.119938
4 2 0.079959
8 4 0.079978
16 6 0.119957
32 11 0.119975
64 18 0.119975
128 31 0.119957
256 54 0.119975
512 97 0.119957
1024 172 0.159972
2048 309 0.119957
4096 564 0.159955
8192 1028 0.319982
16384 1900 1.199952
32768 3512 4.279966
65536 6542 14.919949
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:06:29 PM
06 May 2013 03:06:29 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 9
N Pi Time
1 0 0.149448
2 1 0.149927
4 2 0.149964
8 4 0.150001
16 6 0.149945
32 11 0.149964
64 18 0.149964
128 31 0.149982
256 54 0.149946
512 97 0.149964
1024 172 0.149982
2048 309 0.149983
4096 564 0.149927
8192 1028 0.299965
16384 1900 0.949993
32768 3512 3.249940
65536 6542 12.099958
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:06:48 PM
06 May 2013 03:06:48 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 10
N Pi Time
1 0 0.099515
2 1 0.149908
4 2 0.099976
8 4 0.149946
16 6 0.149964
32 11 0.149982
64 18 0.149964
128 31 0.099976
256 54 0.199952
512 97 0.149982
1024 172 0.149964
2048 309 0.149982
4096 564 0.199952
8192 1028 0.449966
16384 1900 1.549960
32768 3512 5.149982
65536 6542 18.299984
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:07:16 PM
06 May 2013 03:07:16 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 11
N Pi Time
1 0 0.179492
2 1 0.179897
4 2 0.179990
8 4 0.179934
16 6 0.239950
32 11 0.179990
64 18 0.179935
128 31 0.179971
256 54 0.119975
512 97 0.179953
1024 172 0.119975
2048 309 0.179953
4096 564 0.179990
8192 1028 0.239950
16384 1900 0.839953
32768 3512 2.459956
65536 6542 8.879988
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:07:31 PM
06 May 2013 03:07:32 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 12
N Pi Time
1 0 0.189501
2 1 0.179934
4 2 0.179935
8 4 0.239968
16 6 0.299965
32 11 0.239950
64 18 0.179972
128 31 0.179972
256 54 0.179935
512 97 0.179972
1024 172 0.239968
2048 309 0.239950
4096 564 0.359962
8192 1028 0.599986
16384 1900 1.679943
32768 3512 5.999982
65536 6542 22.509962
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:08:05 PM
06 May 2013 03:08:06 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 13
N Pi Time
1 0 0.299504
2 1 0.179916
4 2 0.179990
8 4 0.179953
16 6 0.239950
32 11 0.179971
64 18 0.299965
128 31 0.179953
256 54 0.179990
512 97 0.179935
1024 172 0.179971
2048 309 0.179972
4096 564 0.239949
8192 1028 0.299965
16384 1900 0.719960
32768 3512 2.519971
65536 6542 8.879970
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:08:21 PM
06 May 2013 03:08:22 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 14
N Pi Time
1 0 0.279468
2 1 0.279929
4 2 0.349953
8 4 0.280003
16 6 0.279929
32 11 0.209961
64 18 0.209979
128 31 0.209960
256 54 0.279966
512 97 0.209979
1024 172 0.209943
2048 309 0.209961
4096 564 0.279948
8192 1028 0.559969
16384 1900 1.399959
32768 3512 4.829964
65536 6542 16.939967
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:08:49 PM
06 May 2013 03:08:50 PM
PRIME_MPI
C/MPI version
An MPI example program to count the number of primes.
The number of processes is 15
N Pi Time
1 0 0.239507
2 1 0.239931
4 2 0.319964
8 4 0.319945
16 6 0.319945
32 11 0.239968
64 18 0.239968
128 31 0.399960
256 54 0.399959
512 97 0.239968
1024 172 0.239968
2048 309 0.239968
4096 564 0.399941
8192 1028 0.399978
16384 1900 1.279948
32768 3512 3.919968
65536 6542 14.639983
PRIME_MPI - Master process:
Normal end of execution.
06 May 2013 03:09:14 PM
