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.
