Idiomatic way to share mutable data?

Chris Cain clcain at uncg.edu
Sun Dec 22 14:24:41 PST 2013


On Sunday, 22 December 2013 at 21:07:11 UTC, Charles McAnany 
wrote:
> How do I parallelize this efficiently?

 From what you describe, std.parallelism would probably be 
appropriate for this. However, from your problem description, 
you're going to have a _lot_ of trouble with false sharing. I 
suggest a trick like this:

The atoms list probably needs to be pretty big. I'd assume this 
is the case since you're modeling atoms and you're concerned 
about using parallelism to speed it up. Split the atoms list into 
several lists of approximately equal size. I'd suggest splitting 
into about 8 * totalCPUs lists to start with and go from there. 
That should be very efficient with slices.

So, something like this (pseudocode):
```
atom[] allAtoms = ...;
atom[][] atomsList;
assert(allAtoms.length > (64 * totalCPUs),
     "Probably not worth parallelizing...");
atomsList.length = 8*totalCPUs;
size_t partitionSize = allAtoms / atomsList.length;
foreach(i, ref list; atomsList) {
     list = allAtoms[i*partitionSize .. (i+1)*partitionSize];
}

long leftOvers = allAtoms % atomsList.length;
if(leftOvers) {
     atomsList.length++;
     atomsList[$-1] =
         allAtoms[(atomsList.length - 2)*partitionSize .. $];
}

// Since the leftovers are the only partition that has an odd
// size, it might be appropriate to just save it for last after
// you parallelize everything else.

foreach(a, b; parallelPickPairs(atomsList)) {
     foreach(ref atom; a) {
         foreach(partner; b) {
             atom.vx += atom.interaction(partner)/mass;
         }
     }
}
```

Obviously the bulk of the work left is implementing 
"parallelPickPairs" which is just pseudocode for "use 
std.parallelism while picking all possible pairs of items in some 
list". In this case, it's just picking pairs of atom arrays in 
atomsList. The pair picking process should queue the work up in 
such a way to prevent tasks from accessing the same list at the 
same time (with 8*totalCPUs lists, there are tons of ways to do 
that).

There's some room for improvement, but this kind of idea should 
get you started down the right path, I think.

One kind of landmine with foreach loops, though, is forgetting to 
use "ref" and trying to modify the thing. For instance, in your 
OP, you're modifying a _copy_ of atom, so it wouldn't work 
(although, in your original code that might not be how you did 
it). Just a heads up for you.


More information about the Digitalmars-d-learn mailing list