Help with concurrency - traversing a DAG

[tbttfox]

On Friday, 18 October 2013 at 11:40:24 UTC, qznc wrote:
> On Friday, 18 October 2013 at 07:20:07 UTC, tbttfox wrote:
>> So I've got a project in mind, and at the core of that project 
>> is a DAG with lots of nodes. This seems to be a great 
>> candidate for concurrent evaluation. The problem is that a 
>> node can only be evaluated after all of its parents have.
>>
>> I'm really new to D and static typing in general (coming from 
>> Python-it was way too slow for this), and I'm having trouble 
>> navigating the shared/const/immutables and keeping within the 
>> concurrency structure in D.
>>
>>
>> The actual question: Will the following strategy work? I've 
>> tried coding this a couple times, and it just doesn't seem to 
>> be working. Is there something wrong with my logic?
>>
>> I make a shared list of linked nodes and pass that to each 
>> thread on spawn. Then the indexes of any node without a parent 
>> go into a queue.  The main thread then passes list indexes to 
>> the worker threads from that queue. When a worker thread gets 
>> an index, it makes a local copy of that node, evaluates it, 
>> and stores the data it computes with the node.
>>
>> Then every child of that node is checked to see if its parents 
>> have all been processed.  If so, that child is added to the 
>> queue and the thread requests another item from the queue. 
>> When the queue is empty, the job is done.
>
> I assume your goal is to exploit parallelism for a speedup? How 
> expensive is the "evaluates it" step? Is the traversal or the 
> evaluation dominating the run time in the single-threaded 
> version? How scalable do you need to be (e.g. Desktop Multicore 
> or Cluster or Cloud)?
>
> In terms of logic, I can see no error. Though it is not clear, 
> if you use push or pull. The master might push to the workers 
> or the workers might pull from the master.

Correct, I'm trying to exploit the parallelism for a speedup. The 
evaluation will eventually be the expensive part (once I write 
it, of course.).  And this is for a desktop application, so only 
multicore.

My not currently not working implementation has the workers make 
a pull request from the master.  I'll post the code when I have a 
minute later in the day.
And thanks much for the help
~tbttfox