Help with concurrency - traversing a DAG

[qznc]

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.