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.
