Hugh Perkins hughperkins at gmail.com
Fri Aug 10 23:32:30 EDT 2007

```On 8/11/07, Thomas Conway <drtomc at gmail.com> wrote:
> area. It is commonly called "Embarrassing Parallelism".

Ah, I wasnt very precise ;-)  I didnt mean I dont understand the
problem; I meant I dont understand why people think it is difficult to
solve ;-)  (And then I tried to explain by examples why it is easy,
but it is true that my communication sucks ;-) )

> you'll only get a benefit if you can break xs into chunks
of e.g. 10^3 elements or more, and more like 10^5 or more for more
usual 'f's.

Actually, the number of elements is irrelevant.  The only measure that
is important is how long the function is taking to execute, and
whether it is parellizable.

Example, the following only has 3 elements but will take a while to run:

strPrtLn \$ sum \$ map getNumberPrimes [10240000, 20480000, 40960000 ]

The following has 10 million elements but runs quickly:

strPrtLn \$ sum \$ map (+1) [1..10000000 ]

In the second, we start the function running, in a single thread, and
after a second, the function has already finished, so great! Were
done!

In the first, we start the function running, in a single thread.
After a second the function is still running, so we look at what is
taking the time and whether it is parallelizable.

Turns out the vm has been chugging away on the map for the last
second, and that that maps are parallelizeable, so we split the map
into Math.Min( <numberelements>, <number cores>) pieces, which on a
1024-core machine, given we have 3 elements, is Math.Min( 1024, 3 ),
which is 3.

So, we assign each of the 3 elements of the map to a thread.  So, now
we're using 3 of our 64 cores.

A second later, each thread is still chugging away at its element, so
we think, ok, maybe we can parallelize more, because we still have 61
threads/cores available, so now we look at the getNumberOfPrimes
function itself, and continue the above type of analysis.

This continues until all 64 cores have been assigned some work to do.

Whenever a thread finishes, we look around for some work for it to do.
If there is some, we assign it.  If there isnt, we look around for an
existing thread that is doing something parallelizeable, and split it
into two pieces, giving one to the old thread, and one to the