Advice on threading/fibers/?

[Jonathan M Davis]

On 2011-06-15 16:57, Justin Whear wrote:
> Consider the following:
> 
> You have 10 million data points and you need to apply a multipass algorithm
> to them. Each pass is like a cellular automata: it can read from the
> previous pass but it doesn't know the "current" values. This makes the
> actual processing of each value trivially parallelizable. The actual
> operation for each value is fairly simple and cheap (essentially a
> multidimensional ancestor-child averaging operation).
> 
> After each value has been operated on once, the pass is complete and the
> "current" and "old" buffers are switched (conceptually, the "current"
> buffer can only be written to, the "old" buffer can only be read--using
> __gshared here).
> 
> The number of passes is not fixed; in the course of each value operation,
> an error is computed. When the worst individual error falls below a
> certain threshold, the algorithm is finished. Generally this will take
> between one thousand and ten thousand passes.
> 
> How would you go about parallelizing this? My thought is to take the
> map/reduce approach within each pass: each thread/fiber takes a slice of
> the dataset, makes its modifications, then returns an error summary. These
> summaries are quickly combined and the algorithm loop decides whether to
> run again. Each pass shouldn't take more than a second or two, so I'm not
> sure whether introducing the overhead of spawning, say, 10 threads each
> pass is worthwhile (times 5000 passes). On the other hand, I have plenty
> of CPUs to throw at it (at least 16 cores, each with hyperthreading) and
> am in a situation where "as fast as possible" is important (while
> individual datasets may not grow, the number of them is).
> 
> Any thoughts appreciated.

You should take a look at std.parallelism.

- Jonathan M Davis