Running on 8 Cores?

I made a program which finds the prime numbers from 0 to 100 million, and ran it on my laptop (core 2 duo, 1.83ghz, 2gb ram).

It takes around 35 seconds for it to sieve all the non-prime numbers on my laptop.

I then ran the same program on a windows server, 2x 64 bit Intel Xeon Quad Core Processors @ 1.6 ghz, 6gb ram, and it takes the same amount of time, even when I set the priority to high and the affinity to all 8 cores, it seems to only use one core for the processing, is there any way to make it use all 8 cores at close to 100%?

I really want to see how fast I can get this program up to!

Cheers,
-Sam

http://en.wikipedia.org/wiki/Concurr...mputer_science)
http://msdn.microsoft.com/en-us/library/dd504870.aspx

>> I made a program ...
Did you create any threads in your program?

gg

Quote:

---

Originally Posted by Codeplug

>> I made a program ...
Did you create any threads in your program?

gg

---

I looked into multithreading but it looked far too complicated for my to tackle right now, I've only been learning C++ for about 1 week.

Unless there is an easier way of creating threads?

Creating threads is not difficult at all, it takes only a few lines of code - find some samples. Parallelizing your code to run on those threads would be challenging - google for it, I bet you'll find some answers on how to parallelize finding primes algorithm.

Quote:

---

Originally Posted by SamstaUK

I really want to see how fast I can get this program up to!

---

Theoretically the 8-core version can run 8 times faster than the 1-core version. In practice it will be somewhat slower due to overhead but you should be able to get at least within 90% of maximum performance. But first you need to accomplish two things; You need to come up with a parallellized version of the prime number algorithm, and you need to ensure all 8 cores are kept buzy at all times.

For the second part I recommend the task based approach represented by say the TBB package,

http://threadingbuildingblocks.org/

Rewarping oneself from sequential to parallell thinking requires some effort but it's a worthwile investement for the future.

If you find running multiple threads is too complicated, you can always look into running two independent program instances first...

For example one could find all the primes between 1-5000, while the other finds all the primes between 5001-10000.

I agree with nuzzle, as using Intel TBB has certainly more advantages than managing threads yourself.

For prime numbers, you can take a look at the example provided for parallel_reduce.

You have to create threads to use multiple core. A good rule of thumb is however many cores you have, you should have double the number of threads. That rule starts degrading as the number of cores climbs, but for 8 core, 16 threads should still be close to optimal.

Quote:

---

Originally Posted by ninja9578

You have to create threads to use multiple core. A good rule of thumb is however many cores you have, you should have double the number of threads. That rule starts degrading as the number of cores climbs, but for 8 core, 16 threads should still be close to optimal.

---

Who's rule of thumb is that? AFAIK, the ideal is to have as many threads as there are processor cores available to the program and then try to minimize synchronization. If you have more active (i.e. not waiting) threads than processor cores, you will likely get more context switches, which does not help performance.

Quote:

---

Originally Posted by SamstaUK

I made a program which finds the prime numbers from 0 to 100 million, and ran it on my laptop (core 2 duo, 1.83ghz, 2gb ram).

It takes around 35 seconds for it to sieve all the non-prime numbers on my laptop.

---

What exactly are you timing?
I am not sure I did it right, but I found 5,725,359 prime numbers in under 2.5 seconds.
Not sure how to verify it, but the last number is 99,999,989.
Can you please match it with your results?
If I got it right – I don’t know what are you doing for 35 seconds.
However, I was not able to output those numbers (just don’t have patience to wait for it); it does take a LOT of time, way more than 35 seconds.
My point is – before getting into multithreading, make sure that you use a good algorithm and that you implement it correctly.
<Added>
Ran this thing to completion, with printf() for each prime number found.
It took 548 seconds (over 9 minutes)!

Quote:

---

Originally Posted by VladimirF

My point is – before getting into multithreading, make sure that you use a good algorithm and that you implement it correctly

---

The problem is that the good serial algorithm you've meticulously implemented then seldom is easy to parallelize. The much better and recommended approach is to design for parallelism from the ground up.

If you start with a serial design and then try to parallelize it you almost always end up with mutexes all over the place and threads that spend lots of time waiting. If you think parallel from the start and use a task based approach (ala TBB) you can often achieve a lock-free design with much better core utilization that also scales much better when more cores become available.