Advice on threading/fibers/?

[Jeremy Wright]

On 06/16/2011 06:22 AM, Lars T. Kyllingstad wrote:
> On Wed, 15 Jun 2011 23:57:25 +0000, 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.
>
> I would recommend you take a look at the new std.parallelism module,
> which was introduced in the most recent DMD release (2.053):
>
> http://www.d-programming-language.org/phobos-prerelease/
> std_parallelism.html
>
> -Lars
I wrote an article on using std.parallelism for a bucket-sort algorithm. 
  http://www.codestrokes.com/archives/116

I hope it helps.