Parallel computing when searching for primes.
A little lab work on parallelization.
At the entrance there is a frontal search algorithm for primes, at the output there is a change in the speed of calculations depending on the number of threads.
To determine the prime number, the most primitive prime number search algorithm was used. For anyone who has taught programming, it usually follows Hello world!
The essence of the algorithm: we take a candidate (odd of itself), divide by all known prime numbers, less than half of the candidate. If you have never shared without a balance - the number is simple.
All numbers are taken on the search for the first 10,000 prime numbers in the second million. Those. you need to find prime numbers with ordinal numbers from 1000001-1010000. The first million prime numbers have already been counted up. In fact, everything counted and much afterwards, but the goal (so far) was to compare the approaches, and not to defeat the GIMPS project.
First run:
We take a candidate for a prime number, give it to the thread that counts him. Repeat the operation for the number of threads. We wait until all the threads count, collect the results, feed the threads with the next batch of candidates.
')
What happened:
The abscissa axis - the number of simultaneous threads. Ordinate - time in seconds.
Second run:
We take a candidate, feed a loafless thread, when the thread counts, pick up the result and feed the next candidate. We repeat constantly for all threads.
What happened:
Again, on the abscissa - the threads, on the ordinate - seconds.
As one would expect, the second approach is much more efficient than the first (well, each of them, many times more efficiently than one process). General, in general, the truth, but on the charts somehow somehow clearer. Again, clearly visible boundaries to which parallelization makes sense for a particular machine.
Very discouraged results on AMD. I did not think that my laptop can surpass the server piece of hardware. Maybe there are experts in iron - share, what could be the matter?
C # code. RE - .Net 3.5.
The following cars took part in the race:
2x XeonDC - hp dl140 g3 Windows 2003 Server
Opteron - FSC RX330 S1 Windows 2003 Server
Core 2 Duo - Lenovo T60 (UD0PSRT). Vista Business.
The definition of a prime number is here .
PS Thank you sannis and barauswald for suggesting this mini research. Thanks to him, I now clearly understand how to program in parallel in C #.
UPD
Changed in the text processes on the thread (thread) to exclude discrepancies.
Processor models: 2x Xeon DC = 2pcs; Intel Xeon 5110; Opteron = Dual-Core AMD Opteron 2216; Core2Duo = Intel Core 2 T5600.
The goal was to check how the number of threads affects the speed of calculations. I do not pretend to compare cars - this is a side effect, I did not make a conclusion on them, everyone is free to interpret the results as he pleases.
All commented, thank you - enlightened :) In the future, I will try to express myself more clearly and deployed.
At the entrance there is a frontal search algorithm for primes, at the output there is a change in the speed of calculations depending on the number of threads.
To determine the prime number, the most primitive prime number search algorithm was used. For anyone who has taught programming, it usually follows Hello world!
The essence of the algorithm: we take a candidate (odd of itself), divide by all known prime numbers, less than half of the candidate. If you have never shared without a balance - the number is simple.
All numbers are taken on the search for the first 10,000 prime numbers in the second million. Those. you need to find prime numbers with ordinal numbers from 1000001-1010000. The first million prime numbers have already been counted up. In fact, everything counted and much afterwards, but the goal (so far) was to compare the approaches, and not to defeat the GIMPS project.
First run:
We take a candidate for a prime number, give it to the thread that counts him. Repeat the operation for the number of threads. We wait until all the threads count, collect the results, feed the threads with the next batch of candidates.
')
What happened:
The abscissa axis - the number of simultaneous threads. Ordinate - time in seconds.
Second run:
We take a candidate, feed a loafless thread, when the thread counts, pick up the result and feed the next candidate. We repeat constantly for all threads.
What happened:
Again, on the abscissa - the threads, on the ordinate - seconds.
As one would expect, the second approach is much more efficient than the first (well, each of them, many times more efficiently than one process). General, in general, the truth, but on the charts somehow somehow clearer. Again, clearly visible boundaries to which parallelization makes sense for a particular machine.
Very discouraged results on AMD. I did not think that my laptop can surpass the server piece of hardware. Maybe there are experts in iron - share, what could be the matter?
C # code. RE - .Net 3.5.
The following cars took part in the race:
2x XeonDC - hp dl140 g3 Windows 2003 Server
Opteron - FSC RX330 S1 Windows 2003 Server
Core 2 Duo - Lenovo T60 (UD0PSRT). Vista Business.
The definition of a prime number is here .
PS Thank you sannis and barauswald for suggesting this mini research. Thanks to him, I now clearly understand how to program in parallel in C #.
UPD
Changed in the text processes on the thread (thread) to exclude discrepancies.
Processor models: 2x Xeon DC = 2pcs; Intel Xeon 5110; Opteron = Dual-Core AMD Opteron 2216; Core2Duo = Intel Core 2 T5600.
The goal was to check how the number of threads affects the speed of calculations. I do not pretend to compare cars - this is a side effect, I did not make a conclusion on them, everyone is free to interpret the results as he pleases.
All commented, thank you - enlightened :) In the future, I will try to express myself more clearly and deployed.
Source: https://habr.com/ru/post/48471/
All Articles