Multithreding for loop

Hi Guys!

Can somebody modify this loop for multithreding please? I am very weak with MP.
1
2
3
4
5
for(long l = 1; l <= n; l++ ){
			 if (m % p[l] == 0)
			 {b = false;
			 n -= 1;
			 }}

The main idea is to check the divisibilty between m and p(l) as soon as possible.

Thanks a lot!
Check out "functional programming". This paradigm is specific to multi-threading. The idea is that you replace loops with recursion and pass by value instead of by reference. This eliminates the chance that you are dealing with a value which may change half-way through your calculation.

Another method which I find to be more complicated but can compliment the method above is to use Mutexes or Critical Sections. This will use the OS to place "locks". Before accessing any data shared between the threads, you have to "Aquire" the lock. Doing so locks it and prevents other threads from reading/writing that data until you are done with it. Remember to release locks when you are done or you can run into deadlocks.

Unfortunately, I can't "functionalize" your snippet because:
a) I don't know how everything is defined (particularly b)
b) I don't know what data in here needs to be shared.

If you do not plan on sharing m, p or b, you don't need to worry. If p is pointing to shared data, you have to use a Mutex.
http://www.boost.org/doc/libs/1_39_0/doc/html/boost/signals2/mutex.html
Last edited on
I'll check it. Thanks!

In fact, my code is very simple, too... The model in my mind is something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
for(long l = 1; l <= n; l++ ){
// Thread 0
if (m % p[some of 'l's] == 0)
{b = false;
n -= 1;
// Exit all threads
}
// Thread 1
if (m % p[rest of 'l's] == 0)
{b = false;
n -= 1;
// Exit all threads
}}

Is this possible?
Last edited on
You should know... multiple threads doesn't necessarily mean "faster". Unless this 'p' array is significantly large (thousands of elements or more) adding additional threads is likely to be slower. Synchrozing multiple threads is very slow. Much slower than iterating over a medium sized array. In fact I have found that there are few slower things you can do.

The main idea is to check the divisibilty between m and p(l) as soon as possible.


Rather than try to optimize a slow approach with multithreading, you probably should just choose a faster approach. There are faster ways of determining whether or not a number is prime. Perhaps you should look into those before trying to parallelize your code.

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm



That said....

Setting up an entirely new thread just for this task is not exactly trivial.

But if you can use something like OpenMP, you can do something like this:

1
2
3
4
5
6
7
8
9
#pragma omp parallel for
for(long l = 1; l <= n; ++l)
{
  if(m % p[l] == 0)
  {
    b = false;
    n -= 1;
  }
}


Note: I have no idea whether or not that's valid. I am not at all familiar with OpenMP. You can read more about it here:

http://bisqwit.iki.fi/story/howto/openmp/


Of course, this also depends on whether or not OpenMP is supported by your compiler (it probably is).
Last edited on
Thanks a lot! I had tried the exact code before. It is is not working as it supposed to be.
I have already wrote something different to find the nth prime is which I guess one of the very fastest codes.
It findes the nth prime in the shortest way but as far as I learned, shortest is not he best in programing world.
It consists of two nested for loops so only avaible for one and direct iteration. Nowadays, I am trying to fragment the code to make it suitable for MT.
Using a boolean for each iteration of p(l) parts was one of the ideas to determine if each loop returns with the desired result or not.
I think my project will going to remain for single thread forever...
Last edited on
Topic archived. No new replies allowed.