Parallel computing when searching for prime numbers.

    Small laboratory work on parallelization.
    At the input, the frontal algorithm for finding primes, at the output, the change in the calculation speed depending on the number of threads.


    To determine a prime number, the most primitive algorithm for finding prime numbers was used. For everyone who has learned programming, usually follows Hello world!
    The essence of the algorithm: we take the candidate (odd by itself), divide by all known prime numbers, less than half the candidate. If you have never shared without a remainder - a prime number.
    All numbers are taken in the search for the first 10,000 primes in the second million. Those. you need to find primes with serial numbers from 1000001-1010000. The first million prime numbers have already been counted up to.In fact, everything was calculated and a lot after, but the goal (so far) was to compare approaches, and not defeat the GIMPS project.

    First
    run : We take the candidate for a prime number, give it to the thread that counts it. Repeat the operation by the number of threads. We are waiting for all the threads to 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 approach:
    We take the candidate, feed the loafing thread, when the thread counts, take the result and feed the next candidate’s thread. Repeat constantly for all threads.

    What happened:

    Again, in abscissa - threads, in ordinates - seconds.

    As expected, the second approach is much more effective than the first (well, and each of them is several times more effective than one process). Uppercase, in general, truths, but on the graphs everything is somehow more understandable. Again, the boundaries to which parallelization makes sense for a particular machine are clearly visible.

    The results on AMD were very discouraged. I did not think that my laptop could surpass a server piece of iron. Maybe there are experts in iron here - 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 ishere .

    PS Thanks to sannis and barauswald for prompting me to conduct such a mini-study. Thanks to him, I now clearly understand how to program in C # in parallel.

    UPD
    Changed the text of the process to threads (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 machines - this is a by-product, I did not make a conclusion on them, everyone is free to interpret the results as he pleases.
    To all who commented, thanks - enlightened :) In the future, I will try to express myself more clearly and in detail.

    Also popular now: