Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using nested Parallel.For

Consider this example:

var x = 0;

for (var i = 0; i < 100; i++ )
{
    for (var a = i+1; a < 100; a++)
        x += 1;
}

When printing x we always get 4950. What about if I want to parallelise this?

This is what I come up with

Parallel.For(0, 100, i => Parallel.For(i + 1, 100, a => { x += 1; }));

However this does Not print 4950 each time I run it. Why?

like image 353
Filip Ekberg Avatar asked Jul 19 '10 11:07

Filip Ekberg


People also ask

Is nested parallelism possible in OpenMP?

OpenMP parallel regions can be nested inside each other. If nested parallelism is disabled, then the new team created by a thread encountering a parallel construct inside a parallel region consists only of the encountering thread. If nested parallelism is enabled, then the new team may consist of more than one thread.

How do you parallelize a nested loop?

Parallelizing nested loops. If we have nested for loops, it is often enough to simply parallelize the outermost loop: a(); #pragma omp parallel for for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { c(i, j); } } z(); This is all that we need most of the time.

Which has nested parallelism that works and guarantees speed up?

The OpenMP scheduler uses this added parallelism to improve performance when possible.

Can FOR loops be parallel?

Can any for loop be made parallel? No, not any loop can be made parallel. Iterations of the loop must be independent from each other. That is, one cpu core should be able to run one iteration without any side effects to another cpu core running a different iteration.


2 Answers

Parallel Extensions helps you with task creation, allocation, running and rendezvous, in a near-imperative syntax. What it doesn't do is take care of every kind of thread safety (one of the pitfalls). You are trying to make parallel threads simultaneously update a single shared variable. To do anything like this correctly, you have to introduce e.g. locking.

I'm not sure what you're trying to do. I assume your code is just a placeholder or experiment. Parallelization is only suitable when you can isolate your different pieces of work; not when you constantly have to rendezvous with shared data.

like image 168
Pontus Gagge Avatar answered Dec 07 '22 06:12

Pontus Gagge


Here would be the "correct" way of doing it, this would not require you to lock on your final total object and would only require you to do the interlocked operations at the end of each local thread's looping.

int x = 0;
Parallel.For(0, 100,
    () => 0, //LocalInit
    (i, loopstate, outerlocal) =>
    {
        Parallel.For(i + 1, 100,
            () => 0, //LocalInit
            (a, loopState, innerLocal) => { return innerLocal + 1; },
            (innerLocal) => Interlocked.Add(ref outerlocal, innerLocal)); //Local Final
        return outerlocal;
    },
    (outerLocal) => Interlocked.Add(ref x, outerLocal)); //Local Final

However, having two nested Parallel statements doing this little of work is likely a bad idea. There is a overhead cost that needs to be considered, if you are doing such small amount of work it would be much better to do only one Parallel statement or have none at all.

I highly recommend you go download and read Patterns for Parallel Programming, it goes in to good detail about why small nested parallel loops like this are not a good idea.

like image 27
Scott Chamberlain Avatar answered Dec 07 '22 06:12

Scott Chamberlain